题意：
给出一个数列，和一种操作，以及两个数x和k。
这个操作有两个步骤：
首先把这个数列按照升序排序，然后把所有奇数位上的数字与x异或。
问执行k次操作之后，这个数列的最大值和最小值是多少。
思路：
由于每个数字异或两次之后会变回本身，所以猜测这个数列有可能会循环，所以就可以暴力计算周期，对于每一次出现的数列，看看是否与前面某次出现过的数列相同，这是暴力的思路。玄学复杂度。
更优雅的思路：
发现a[i]的最大值为1000，任意1000以内的两个数字异或不会超过1023，所以可以统计0到1023当中每个数字出现的次数，然后利用前缀和的思想，计算这个数字在下一次操作中对其他数字出现次数的贡献。
假设这个数字之前有n个数字出现，这个数字的出现次数为y，当前数字为cur，操作后的数列为nex：
1.当n为偶数，y为奇数：
nex[cur^x] += (y/2)+1;nex[cur] += y/2;
2.当n为偶数，y为偶数：
nex[cur^x] += (y/2);nex[cur] += y/2;
3.当n为奇数，y为奇数：
nex[cur^x] += (y/2);nex[cur] += y/2+1;
4.当n为奇数，y为偶数：
nex[cur^x] += (y/2);nex[cur] += y/2;
这个思路的复杂度为O(k*1024)。
思路1代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <map>
using namespace std; const int N = 1e5 + ;
int a[N],b[][N]; int judge(int cu,int n)
{
for (int i = ;i < cu;i++)
{
bool f = ;
for (int j = ;j < n;j++)
{
if (b[i][j] != b[cu][j])
{
f = ;
break;
}
} if (!f) return i;
} return -;
} int main()
{
int n,k,x; scanf("%d%d%d",&n,&k,&x); for (int i = ;i < n;i++) scanf("%d",&a[i]);
for (int i = ;i < n;i++) b[][i] = a[i]; int cnt = ;
int pre = cnt-; for (;cnt <= k;cnt++)
{
for (int i = ;i < n;i++)
{
b[cnt][i] = b[cnt-][i];
} sort(b[cnt],b[cnt]+n); for (int i = ;i <= n;i+=)
{
b[cnt][i] ^= x;
} pre = judge(cnt,n); if (pre != -) break;
} if (cnt >= k)
{
sort(b[k],b[k]+n); printf("%d %d\n",b[k][n-],b[k][]);
}
else
{
int ti = cnt - pre; k = (k - pre) % ti; k += pre; sort(b[k],b[k]+n); printf("%d %d\n",b[k][n-],b[k][]);
} return ;
}
思路2代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
const int N = ; int a[N];
int pre[N];
int nex[N]; int main()
{
int n,k,x; scanf("%d%d%d",&n,&k,&x); for (int i = ;i < n;i++)
{
int y;
scanf("%d",&y);
a[y]++;
} for (int i = ;i < k;i++)
{
memset(nex,,sizeof(nex));
pre[] = ; for (int j = ;j < ;j++)
{
pre[j] = pre[j-] + a[j-];
} for (int j = ;j < ;j++)
{
if (a[j])
{
if (pre[j] % )
{
if (a[j] % )
{
nex[j^x] += a[j] / ;
nex[j] += a[j] / + ;
}
else
{
nex[j^x] += a[j] / ;
nex[j] += a[j] / ;
}
}
else
{
if (a[j] % )
{
nex[j^x] += (a[j]/) + ;
nex[j] += a[j]/;
}
else
{
nex[j^x] += a[j]/;
nex[j] += a[j]/;
}
}
}
} for (int j = ;j < ;j++)
{
a[j] = nex[j];
}
} int mx,mn; for (int i = ;i < ;i++)
{
if (a[i])
{
mn = i;
break;
}
} for (int i = ;i >= ;i--)
{
if (a[i])
{
mx = i;
break;
}
} printf("%d %d\n",mx,mn); return ;
}