做网站卖水果哪里进货,临沧网站建设公司,户外运动网站程序,乌市网络营销公司CF1572B. Xor of 3
题意#xff1a;
给你个01序列#xff0c;你有一种操作#xff1a;每次选位置x#xff0c;然后位置x#xff0c;x1#xff0c;x2的值变为三者的异或值。 现在要让所有的数都等于0#xff0c;请输出存在的合法操作序列
题解#xff1a;
首先如果有…CF1572B. Xor of 3
题意
给你个01序列你有一种操作每次选位置x然后位置xx1x2的值变为三者的异或值。 现在要让所有的数都等于0请输出存在的合法操作序列
题解
首先如果有奇数个1显然是无解的 此时我们从第一个1开始考虑成对考虑消除1(因为这样异或为0)每次消除掉第一对1 如果两个1之间有奇数个0 比如10001,100000001,这种是可以直接消掉的 就拿100000001来说假设第一个1的位置为x那我们可以依次操作xx2,x4,…(x长度)此时序列为111111101然后操作x6就得到111111000然后再倒着执行x4x2…这样就都变成0
如果两个1之间有偶数个0 这样是不能和上面一样直接消除的可以先全部变成1然后需要借助外面的0也就是如果左边或右边有一个0就可以消除否则无解 比如1001 - 1111 假设 原序列是10010, 右边有一个0, 那么现在11110可以消掉
实现起来挺麻烦的
代码
#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
bool Handsome;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
void read(){};
template typename _Tp, typename... _Tps void read(_Tp x, _Tps... Ar)
{x 0;char c getchar();bool flag 0;while (c 0 || c 9)flag| (c -), c getchar();while (c 0 c 9)x (x 3) (x 1) (c ^ 48), c getchar();if (flag)x -x;read(Ar...);
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test(bool Most)
{
#ifdef ONLINE_JUDGE
#elseprintf(%.2lfMB\n,(Most-Handsome)/1024.0/1024.0);startTime clock ();freopen(data.in, r, stdin);
#endif
}
void Time_test()
{
#ifdef ONLINE_JUDGE
#elseendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn2e59;
int a[maxn],nex[maxn];
vectorintans;
int n;
bool Most;
int solve(int x){if(xn)return 0;if(nex[x]0)return 1;if(a[x]0||(nex[x]-x-1)%2){//如果当前位置是0或者中间有奇数个1 if(a[x]0)xnex[x];//找到后面最近1的位置 while(x){if((nex[x]-x-1)%2){//中间奇数个1内部直接消 int i;for(ix;i2nex[x];i2)ans.push_back(i);for(;ix;i-2)ans.push_back(i);}else {//借助左边的0消除 for(int ix;i2nex[x];i2)ans.push_back(i);for(int ix-1;i2nex[x];i2)ans.push_back(i);}xnex[nex[x]];//下下一个1的位置(因为1都是成对处理) }return 1; }else{//因为中间有偶数个1且当前不是0所以需要判断后面能否出现0 if(solve(nex[x]1)){for(int ix;inex[x]-2;i2)ans.push_back(i);for(int inex[x]1;i-2x;i-2)ans.push_back(i-2);return 1;}elsereturn 0; }
}
int main()
{rd_test(Most);int t;read(t);while(t--){read(n);for(int i1;in;i)read(a[i]);int las0;int cnt0;for(int in;i1;i--){nex[i]las;if(a[i])//如果非0记录位置{lasi;cnt;} }if(cnt%2)//如果奇数个1{printf(NO\n);continue; }ans.clear();if(solve(1)){printf(YES\n%d\n, ans.size());for(int i0; ians.size(); i) {printf(%d , ans[i]);}printf(\n);} else printf(NO\n);}//Time_test();
}
