D. Ehab and the Expected XOR Problem(构造 + 异或和)
Problem - D - Codeforces
对于数组中的任何元素aiai，1≤ai<2n1≤ai<2n；
没有非空的子段，其位数XOR值等于00或xx、
它的长度ll应该是最大的。
一个序列bb是一个序列aa的子段，如果bb可以通过从aa中删除几个（可能是零或全部）元素开始和几个（可能是零或全部）元素结束得到。
输入
唯一一行包含两个整数nn和xx（1≤n≤181≤n≤18，1≤x<2181≤x<218）。
输出
第一行应该包含数组ll的长度。
如果ll是正数，第二行应包含ll个空间分隔的整数a1a1，a2a2，......，alal（1≤ai<2n1≤ai<2n）--数组aa的元素。
如果有多个解决方案，打印其中任何一个。
例子
输入
拷贝
3 5
输出
复制
3
6 1 3
输入
复制
2 4
输出
复制
3
1 3 1
输入
复制
1 1
输出
拷贝
0
注意
在第一个例子中，子段的位数XOR是{6,7,4,1,2,3}{6,7,4,1,2,3}。
题解:
1.任何子段异或和不为0
2.任何子段异或和不为x
我们可以从小到大枚举i,看i^x是否出现过,出现过则跳过,否则记录下来,
f[0] = 1,因为数组中不能出现x,f[i] = 1
这样的用处是,使得我们记录数组中任意两个数得异或和,不会为x
但是依旧好像没什么用
但是其实我们直接输出,a[i]^a[i-1]就是答案
为啥?
打个比方,数组中存的是,1,2,3,4,5
输出是
1^0
2^1
3^2
4^3
5^4
这样就能比较明显得看出来,任意子段得异或和,答案都相当于,我们记录数组中的两个数得异或和,而我们保证了记录数组中任意两个数得异或和,不会为x,所以成立
#include <cstdio>
#include <cstring>
#include <algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
//#define int long long
int a[1000050];
void solve()
{int n,x;cin >> n >> x;map<int,int> f;f[0] = 1;int cnt = 0;for(int i = 1;i < 1 << n;i++){if(f[i^x])continue;a[++cnt] = i;f[i] = 1;}cout << cnt <<"\\n";for(int i = 1;i <= cnt;i++){cout << (a[i] ^ a[i - 1]) <<" ";}
}
//111
//110
//100
//011signed main()
{
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);int t = 1;
// cin >> t;while(t--){solve(); }
}