CF1934D2 题解

sunkuangzheng · 2024-03-02 13:26:40 · 题解

• 有一个整数 n，你和交互库轮流进行拆分。一次拆分指的是一方选择两个整数 p_1,p_2 满足 0 < p_1,p_2 < n,p_1 \oplus p_2 = n，对方从 p_1,p_2 中选择一个替换掉 n，然后对方继续拆分。当一方无法拆分时视为失败。
• 你可以选择先手或者后手和交互库博弈。

记 f(x) = \operatorname{popcount}(x)，容易发现 f(x) = 1 时无法拆分，先手必败；f(x)=2 时可以拆分使得 f(p_1)=f(p_2)=1，先手必胜。

猜测结论：f(x) \bmod 2 = 1 时先手败，否则先手胜。

然后模拟上述过程构造方案即可。注意到我们只会进行拆分偶数操作，我们每次可以直接拆成 \operatorname{hb}(n) 和 n \oplus \operatorname{hb}(n)，其中 \operatorname{hb}(n) 指的是 n 的最高二进制位值。这样拆分一次一定会少一位，操作次数是严格 \mathcal O(\log n) 的。

/**
 *    author: sunkuangzheng
 *    created: 02.03.2024 12:24:54
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
using ll = long long;
const int N = 5e5+5;
using namespace std;
int T; ll n,p1,p2;
void los(){
    cin >> n;
    auto ck = [&](ll x){return __builtin_popcountll(x) & 1;};
    auto lb = [&](ll x){return 1ll << (63 - __builtin_clzll(x));};
    cout << (ck(n) ? "Second" : "First") << endl;
    if(!ck(n)) cout << lb(n) << " " << (n ^ lb(n)) << endl;
    while(1){
        cin >> p1 >> p2; if(p1 == -1) assert(0);
        if(!p1 && !p2) return ;
        if(ck(p1)) cout << lb(p2) << " " << (p2 ^ lb(p2)) << endl;
        else cout << lb(p1) << " " << (p1 ^ lb(p1)) << endl;
    }
}int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    for(cin >> T;T --;) los();
}

请注意，拆成 \operatorname{lowbit} 可能会导致操作次数达到 \mathcal O(\log^2 n) 级别，不满足限制。

UPD：拆成 \operatorname{lowbit} 的操作次数可以达到 \mathcal O(n) 级别。具体的，对于 m 位的二进制数把后 2 位分离，每次后手给前 m -2 位做 -1 操作，并用后两位平衡 1 的数量奇偶性。先手每次只能拆最后两位，无法影响前面 m-2 位，操作数量是 \mathcal O(n) 级别的。感谢 @qweradf 指出 /bx /bx