Всем привет, добро пожаловать в тему codeforces.
Выбранный сегодня вопрос - это вопрос D конкурса 1438, а количество людей, прошедших тест, составило 1325 человек. Как правило, сложность вопросов, переданных тысячами людей в codeforces, невелика, но этот вопрос является небольшим исключением, хоть он и не требует немного продвинутого алгоритма, но все же немного сложно сделать это самостоятельно.
Ссылка на тему: https://codeforces.com/contest/1438/problem/D
Без лишних слов, давайте сразу к вопросу.
смысл названия
Учитывая свойство с n () массив положительных целых чисел, а затем мы выполняем волшебную операцию XOR над элементами массива.
Операция заключается в следующем, мы выбираем три разных индекса i, j, k. правильноa[i],a[j],a[k]Эти три элемента выполняютоперация исключающее ИЛИ,Сейчас. Затем эти три числа соответственно присваиваются результату после этого XOR.
Теперь мы хотим быть внутри волшебной операции XOR, такой как n шаговСделать все элементы в массиве равными, Это возможно? Сначала выведите YES или NO, указывая, есть ли решение. Если есть решение, выведите количество шагов, необходимых для работы, и соответствующий индекс выбранного элемента.
Образец
В первом примере результат XOR 4, 1 и 7 равен 2, поэтому после этой одношаговой операции все элементы могут быть удовлетворены.
отвечать
В начале я думал об инерции, так как это операция XOR, тоОбязательно начните с двоичного. Все элементы в массиве равны, фактически это эквивалентно тому, что они также равны в каждом двоичном бите, как 0, так и 1. Итак, я долго думал о том, как судить и выбирать каждый двоичный бит, и по незнанию зашел в тупик, потому что эти двоичные биты влияют друг на друга, нам трудно разобраться один за другим.
Я зашел в тупик, потому что меня обмануло условие в заголовке, котороеОграничение до n шагов операции. Мы все интуитивно чувствуем, что это очень требовательное требование, поэтому мы ожидаем, что придумаем идеальное решение, которое может решить проблему с наименьшим количеством шагов.
Но на самом деле это n достаточно велико, чтобы некоторые очень глупые методы также могли использовать AC. Я должен сказать, что это также распространенная ловушка мышления во многих темах, которая проверяет смелость и опыт игроков.
Природа XOR
Во-первых, давайте проанализируем операцию XOR В этом вопросе нет специальной трактовки XOR. Единственная разница в том, что мы выполняем XOR над тремя числами. Мы анализируем из самого основного двоичного бита 01, есть только четыре случая, когда 3 числа должны быть объединены XOR. 000, 010, 011 и 111, мы находим, что результат 000 и 011 равен 0, а результат 010 и 111 равен 1. так какXOR то же, что 0, отличается от 1Вычислительные свойства , заставляют исключать одни и те же числа.
Например, мы вычисляем три числа:[a,b,b]Тогда конечным результатом будет a, и мы можем использовать это, чтобы поднять шумиху. Об этом может быть немного сложно думать, но, говоря прямо, это действительно бесполезно.
Предположим, что n=7, эти 7 чисел равны[a,b,c,d,e,f,g]. Сначала мы XOR первые три числа, так что мы получаем:[h,h,h,d,e,f,g], а затем выбираем операцию элемента 3-го, 4-го и 5-го бит, и получаем:[h,h,j,j,j,f,g]. Продолжаем выбирать элементы 5-го, 6-го и 7-го разрядов для работы, и получаем[h,h,j,j,k,k,k].
На самом деле здесь немного хмурится, потому что[a,b,b]Результатом операции является a, и все, что нам осталось сделать, это продолжить выбор и исключить все элементы, кроме k.
Продолжаем выбирать элемент операции 3-го, 4-го и 5-го битов, и получаем[h,h,k,k,k,k,k], таким же образом окончательно выбираем операцию элемента 1-го, 2-го и 3-го битов, чтобы элементов во всем массиве стало k. мы здесьВсего 5 раз, то есть n-2 операции, вообще не превышали лимит титров.
Но здесь есть небольшая проблема: причина, по которой эта схема реализуема, носит предпосылочный характер. ЭтоСамая большая предпосылка состоит в том, что n — нечетное число.. Если n — четное число, в конце останется один элемент, как это решить?
даже случай
В случае четных чисел нам сложно найти решение, потому что мы не можем решить проблему лишнего элемента в конце.
Здесь необходимо использовать ключевой вывод, который очень скрыт, и его действительно нелегко придумать. мы предполагаем, что, когда n четно, тоНезависимо от того, что мы делаем с этими n элементами, k, полученное из этого XOR, остается прежним..
Откуда такой вывод? На самом деле, это также вытекает из природы XOR. Мы выполняем операцию XOR над тремя числами и анализируем их по определенному двоичному разряду. мы найдемНаша операция не изменит общую четность n битов.. Для операции XOR эти две операции компенсируют друг друга, и окончательный результат связан только с четностью. Окончательный результат связан только с этим паритетом.
Отсюда далее можно получить, если, то решения быть не должно.
Этот вывод на самом деле очень прост, потому что мы уже знаем, что что бы мы ни делали, значение k не изменится.Поскольку n четно, если n чисел точно равны, их значение XOR должно быть равно 0., поэтому, когда k не равно 0, решения быть не может.
Что происходит, когда k равно 0? На самом деле это очень просто, нам нужно только отбросить последний элемент и сделать предыдущие n-1 элементов равными операциям, когда n — нечетное число выше. После этого массив будет выглядеть так[a,a,a,a...a,b].Значение XOR первого n-1 a равно a, а значение XOR всех n чисел равно 0, поэтому вы можете получить a=b. Тогда мы закончили со всем этим.
После того, как вся идея реализована, реализация кода становится слишком простой.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <functional>
#define rep(i,a,b) for (int i=a;i<b;i++)
#define Rep(i,a,b) for (int i=a;i>=b;i--)
#define foreach(e,x) for (__typeof(x.begin()) e=x.begin();e!=x.end();e++)
#define mid ((l+r)>>1)
#define lson (k<<1)
#define rson (k<<1|1)
#define MEM(a,x) memset(a,x,sizeof a)
#define L ch[r][0]
#define R ch[r][1]
const int N=100050;
const long long Mod=1000000007;
using namespace std;
int a[N];
int main() {
int n, x;
scanf("%d", &n);
rep(i, 0, n) {
scanf("%d", a + i);
}
// 如果n为奇数，一定有解
if (n % 2) {
puts("YES");
printf("%d\n", n-2);
for (int i = 0; i + 2 < n; i+=2) {
printf("%d %d %d\n", i+1, i+2, i+3);
}
for (int i = n-3; i - 2 >= 0; i-=2) {
printf("%d %d %d\n", i+1, i, i-1);
}
}else {
// 如果n为偶数，判断整个数组的异或值是否为0
x = 0;
rep(i, 0, n) x ^= a[i];
if (x > 0) {
puts("NO");
}else {
n --;
puts("YES");
printf("%d\n", n-2);
for (int i = 0; i + 2 < n; i+=2) {
printf("%d %d %d\n", i+1, i+2, i+3);
}
for (int i = n-3; i - 2 >= 0; i-=2) {
printf("%d %d %d\n", i+1, i, i-1);
}
}
}
return 0;
}
На этом сегодняшний вопрос закончен, как насчет этого, сегодняшний вопрос весьма интересен. Разумно говоря, алгоритм очень прост, и сложности почти нет, но если мы позволим себе думать самостоятельно, то это станет очень сложно, и нам будет трудно разобраться в своих мыслях. Идея умная и интересная, в этом и есть самая большая прелесть темы codeforces, надеюсь каждый сможет испытать удовольствие от алгоритма.
Вот и все, что касается сегодняшней статьи, и я искренне желаю вам удачи каждый день. Если вам все еще нравится сегодняшний контент, пожалуйста, зайдите на одинТройная поддержкабар~(Нравится, подписывайтесь, делайте репост)