九洲建设集团网站,网站系统的运营和维护,建筑设计院,织梦做网站的详情题意就是给我们两个数n,x。让我们构造个数组#xff0c;数组有三个条件
1.要有尽可能多的元素
2.要其中任何一段数字的异或和不等于0和x
3.元素的范围是[ 1, 2n2^n2n#xff09;
分析#xff1a;如果对异或足够敏感的话 应该能想到其中第二个条件的意思#xff0c;其实…题意就是给我们两个数n,x。让我们构造个数组数组有三个条件
1.要有尽可能多的元素
2.要其中任何一段数字的异或和不等于0和x
3.元素的范围是[ 1, 2n2^n2n
分析如果对异或足够敏感的话 应该能想到其中第二个条件的意思其实就是说目标数组中的元素的异或前缀和不能有相等的两个数如果有相等的两个异或和说明其中可以中间的一段数是可以用异或得到0的也就是违反了条件2。 那么对于x其实就是如果异或和中有一个x说明这其中有段数的异或和等于x所以违反2那么也就是说其中任意两个前缀和数字异或不能为x。 那么也就是我们可以枚举[ 1, 2n2^n2n中的每一个数然后对其中每一个数i进行处理如果当前的i^x的数之前出现过作为异或和数组中的元素了根据异或运算的性质: a^b c, 那么 c^a b, c^b a 所以就说明i^x之前出现过那么如果我们要把i确定为最新的异或和数组中的元素就会形成 i^x ^ i x的异或性质那么违反规则2. 所以本题我们可以根据异或的特点将这个问题转化为构造异或前缀和数组而数组的构造方法是根据异或的性质来的如果a^x ^a x 就不选这个数 最后根据异或数组ai-1^ai得到那个原数组元素 如果异或熟练这个解法可以很快想到
#includeiostream
#includecstring
#includealgorithm
#includeset
using namespace std;
const int maxn 119;
int cnt,S[maxn];
int main()
{int n,x;scanf(%d%d,n,x);// 不能存在两相等 也不能存在和x异或为0的数setints;s.insert(0);for(int i1;i(1n);i){if(!s.count(i^x)){//已存在一个0 如果与x相等会得到0 保证不会有相同的元素 尽可能变大三个条件s.insert(i);S[cnt]i;}}printf(%d\n,cnt);for(int i1;icnt;i){printf(%d,S[i]^S[i-1]);if(icnt)puts();else putchar( );}return 0;
}
