codeforces 768c Jon Snow And His Favourite Number

题意：

给出一个数列，和一种操作，以及两个数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 + 10;
int a[N],b[105][N];

int judge(int cu,int n)
{
    for (int i = 0;i < cu;i++)
    {
        bool f = 0;
        for (int j = 0;j < n;j++)
        {
            if (b[i][j] != b[cu][j])
            {
                f = 1;
                break;
            }
        }
        
        if (!f) return i;
    }
    
    return -1;
}

int main()
{
    int n,k,x;
    
    scanf("%d%d%d",&n,&k,&x);
    
    for (int i = 0;i < n;i++) scanf("%d",&a[i]);
    for (int i = 0;i < n;i++) b[0][i] = a[i];
    
    int cnt = 1;
    int pre = cnt-1;
    
    for (;cnt <= k;cnt++)
    {
        for (int i = 0;i < n;i++)
        {
            b[cnt][i] = b[cnt-1][i];
        }
        
        sort(b[cnt],b[cnt]+n);
        
        for (int i = 0;i <= n;i+=2)
        {
            b[cnt][i] ^= x;
        }
        
        pre = judge(cnt,n);
        
        if (pre != -1) break;
    }
    
    if (cnt >= k)
    {
        sort(b[k],b[k]+n);
        
        printf("%d %d
",b[k][n-1],b[k][0]);
    }
    else
    {
        int ti = cnt - pre;
        
        k = (k - pre) % ti; 
        
        k += pre;
        
        sort(b[k],b[k]+n);
        
        printf("%d %d
",b[k][n-1],b[k][0]);
    }
    
    return 0;
}

思路2代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
const int N = 2000;

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 = 0;i < n;i++)
    {
        int y;
        scanf("%d",&y);
        a[y]++;
    } 
    
    for (int i = 0;i < k;i++)
    {
        memset(nex,0,sizeof(nex));
        pre[0] = 0;
        
        for (int j = 1;j < 1500;j++)
        {
            pre[j] = pre[j-1] + a[j-1];
        }
        
        for (int j = 0;j < 1500;j++)
        {
            if (a[j])
            {
                if (pre[j] % 2)
                {
                    if (a[j] % 2)
                    {
                        nex[j^x] += a[j] / 2;
                        nex[j] += a[j] / 2 + 1;
                    }
                    else
                    {
                        nex[j^x] += a[j] / 2;
                        nex[j] += a[j] / 2;
                    }
                }
                else
                {
                    if (a[j] % 2)
                    {
                        nex[j^x] += (a[j]/2) + 1;
                        nex[j] += a[j]/2;
                    }
                    else
                    {
                        nex[j^x] += a[j]/2;
                        nex[j] += a[j]/2;
                    }
                }
            }
        }
        
        for (int j = 0;j < 1500;j++)
        {
            a[j] = nex[j];
        }
    }
    
    int mx,mn;
    
    for (int i = 0;i < 1500;i++)
    {
        if (a[i])
        {
            mn = i;
            break;
        }
    }
    
    for (int i = 1500;i >= 0;i--)
    {
        if (a[i])
        {
            mx = i;
            break;
        }
    }
    
    printf("%d %d
",mx,mn);
    
    return 0;
}