Codeforces Round 779 div.2 D2F

D2. 388535 (Hard Version)

题意：给出两个数 \(l,r\) 和一个数字集合 \(a\)，有某个 \(x\)，使得 \([l,r]\) 范围内的这些数分别异或上 \(x\) 之后，结果恰好能组成序列 \(a\)。要求找到一个合法的 \(x\)，保证有解。

对于每一位去考虑：如果在某一个二进制位上，两边集合0和1的个数不相等，比如 \(l...r\) 中共有3个0，2个1；序列 \(a\) 中共有2个0，3个1，那么必须要让数量对调，可以直接得出 \(x\) 在这一二进制位上必为1。不能对调则这一位上必为0

从高位到低位依次进行，每次把 \(l,r\) 和 \(a\) 分别分为高位为0和1的四组，然后根据数量对应上，分开递归向下求解。

但如果两边集合0和1的个数全部相等呢？那么在这一位上，无法确定取0还是取1，有没有可能都可以呢？

接下来证明：在最高位处，如果0和1的个数相等，不论怎么取，都不影响解的存在。

因为 \(l,r\) 是一个连续的区间，我们考虑最高位为1的分界线，其实也就是 \(l,r\) 的中点（因为要0和1一样多）

随便举个例子：

l=5   0101
6     0110
7     0111
8     1000
9     1001
r=10  1010

在最高位上，我们遇到了0和1个数相等的情况，将它们分为两组，我们发现后面的位置上数字恰好是相反的。

因为一个是从000开始加，另一个是从111开始减，当然是完全相反的。

也就是说，此时对调这两组分配给 \(a\) 的方式，仅仅只是让后续答案对调，该有解还是有解，不用担心此处取值的伏笔。另外，分配到 \(a\) 的子 \(l,r\) 仍然是连续的。我们只需要在最高位处做完之后把最高位抹去，后续仍然满足这个条件。

具体实现上，先将 \(a\) 插入字典树，然后递归向下求解会比较方便

struct node{
    int cnt;
    int ch[2];
}t[maxn << 5];
int tcnt = 1;
 
void insert(int x){
    int p = 1;
    for(int k=17;k>=0;k--){
        int v = (x >> k) & 1;
        if(!t[p].ch[v]){
            t[p].ch[v] = ++tcnt;
            t[tcnt].cnt = 0;
            t[tcnt].ch[0] = t[tcnt].ch[1] = 0;
        }
        p = t[p].ch[v];
        t[p].cnt++;
    }
}
 
int ans = 0;
void work(int p, int lv, int l, int r){
    if(lv < 0) return;
    int mid = r;
    for(int i=l;i<=r;i++){
        if((i >> lv) & 1){
            mid = i-1;
            break;
        }
    }
    if(mid-l+1 == t[t[p].ch[0]].cnt){
        if(mid >= l) work(t[p].ch[0], lv-1, l, mid);
        if(mid < r) work(t[p].ch[1], lv-1, (mid+1)^(1<<lv), r^(1<<lv));
    }else{
        if(mid >= l) work(t[p].ch[1], lv-1, l, mid);
        if(mid < r) work(t[p].ch[0], lv-1, (mid+1)^(1<<lv), r^(1<<lv));
        ans |= (1 << lv);
    }
}
 
void solve(){
    tcnt = 1;
    ans = 0;
    t[1].ch[0] = t[1].ch[1] = 0;
 
    int l, r;
    cin >> l >> r;
    for(int i=l;i<=r;i++){
        int x; cin >> x;
        insert(x);
    }
    work(1, 17, l, r);
    cout << ans << '\n';
}

E. Gojou and Matrix Game

题意：有一个 \(n\times n\) 的网格，每个格子上有一个分数 \(1...n^2\)，不重复。接下来两个人玩游戏，第一名玩家首先占据 \(sx, sy\) 格，随后轮流选择格子占据，要求满足以下条件：

• 选取的格子距离另一名玩家上次占据的格子的曼哈顿距离不超过 \(k\)
• 可以重复占据，每次占据都能获得该格子上的分数（可重复获得）

请问对于每个起始坐标 \(sx,sy\)，玩 \(10^{100}\) 轮，谁能获胜？

首先不难发现，分数是不重复的，那么分数最高的格子只有一个，谁先占到谁就赢了。

游戏规则是不能选取距对方上次选取位置 \(k\) 格以内的，双方有可能互相僵持，都占不到最高分的点

那么再去考虑次高分的位置：如果次高分的控制范围内包括了最高分，那么这也是一个先手必胜点（即使对方跟你僵持都拿不到最高，但你拿的是次高，所以也是必胜）。否则这就是先手必败点。

如此考虑下去，我们发现：对于一个包含 \(x\) 分的点来说，只要它的掌控范围内包含了所有比 \(x\) 大的必胜点，\(x\) 就是必胜点。否则为必败点。

---

另外再给出一种博弈论常用的思路：如果我选择了分数为 \(x\) 的点后，对方不得不选择分数小于 \(x\) 的点，那么我就是必胜的，因为我可以继续选择当前点，这个逻辑在双方都进行最优策略下是完全正确的。

---

那么问题就变成了如何判断。我们按照权值从大到小枚举，每遇到一个必胜点，都将它的位置丢进一个集合，只要集合中是否存在到当前枚举点距离 \(\gt k\) 的位置就可以了。

当然暴力判断怎么样都是 \(n^3\) 的，此处又有一个神奇的“放宽解空间”思想：

想判断 \(|i-i'|+|j-j'|\le k\) ，它等价于 \(max(|i+j-(i'+j')|, |i-j-(i'-j')|)\)

然后就只需要记录 \(i+j\)，\(i-j\) 的最大最小值即可...

难想...

本质上是放宽了解空间，使得更容易维护

感觉这种东西都挺难发现的，记一下吧（