E. Guess Game

2023-08-27 22:12:01
刚刚看了下，有点思路，这里记一下我目前分析，有空再来把代码补掉：

前言

2023-08-29 21:37
下午上班的时候就已经推出正确的公式了，但是因为字典树的子树大小那部分写丑了，搞得我一直以为公式有问题，越想越觉得复杂。

晚上又来看了看，感觉公式无比正确，于是看了下字典树，果然是贡献算错了。

思路

先不管最终的期望，如果选定了两个数 $x$，$y$，聪明的他俩把这个游戏玩下去的呢？

观察了下样例的解释，大概能推导出 $Alice$ 和 $Bob$ 是这样判定的：

令 $p = x | y$，$Alice$ 看 $p$ 的最高位是不是与自己一致，如果不是，她就能断定 $Bob$ 的数比她大了；如果是，那么她还不能推断 $Bob$ 的数是怎么样的大小关系，于是 say son’t konw.

$Bob$ 根据 $Alice$ 的回答，就能知道 $Alice$ 拥有最高位的 $1$，然后他看向自己的数字的最高位，如果不是 $1$，那么他也会 say don’t konw；如果是，他还会观察自己的数字的下一个 $1$，如果刚好对上 $p$ 的下一个 $1$，那么游戏就会进入下一轮；否则本轮结束

以此类推，当 $Alice$ 和 $Bob$ 的某一位不一致时，游戏便会结束。

问题在于，进行了多少轮呢，这个要分类讨论下：

先总结 $Alice$ < $Bob$ 的情况，那么一定会出现 $Alice$ 某一位是 $0$，而 $Bob$ 是 $1$：

Alice: 110
Bob:   111

Alice: 100
Bob:   111

这两种情况，游戏都会进行 $3$ 轮。

同理，$Alice$ > $Bob$ 的情况：

Alice: 111
Bob:   100

Alice: 111
Bob:   110

这两种情况，游戏都会进行 $4$ 轮。

其实可以划横线来找轮次的规律，$Alice$ 的第一个 $1$ 画一根横线，代表第一轮，此后每两个 $1$ 画一条横线，代表一轮，直到画到决定大小的那一位。

总结：

1、若 $Alice$ < $Bob$，$Alice$ 枚举到决定大小的那一位之前已经拥有 $cnt$ 个 $1$ 时，游戏共进行 (cnt + 1)|1 轮。

2、若 $Alice$ > $Bob$，$Alice$ 枚举到决定大小的那一位之前已经拥有 $cnt$ 个 $1$ 时，游戏共进行 (cnt + 1)/2*2 轮。

3、若相等，游戏会进行 cnt+1 轮，cnt 代表 $Alice$ 有多少个 $1$。

剩下的就是字典树了，很简单，插入数字的时候就在叶子结点 $+1$，这样就知道了子树的大小了。

int a[N];
int trie[N * 30 + 2][2], f[N * 30 + 2];
int tot = 1;
int sum = 0;
void insert(int x)
{
    int p = 1;
    for (int i = 30; i >= 0; i--) {
        int ch = x >> i & 1;
        if (trie[p][ch] == 0) trie[p][ch] = ++tot;
        p = trie[p][ch];
    }
    f[p]++;
}
void dfs1(int x, int fa) 
{
    if (trie[x][0]) {
        dfs1(trie[x][0], x);
        f[x] += f[trie[x][0]];
    }
    if (trie[x][1]) {
        dfs1(trie[x][1], x);
        f[x] += f[trie[x][1]];
    }
}
void dfs2(int val)
{
    int p = 1;
    int cnt = 0;
    for (int i = 30; i >= 0; i--) {
        int ch = val >> i & 1;

        int brother = trie[p][ch ^ 1];
        if (ch == 0) {
            sum += f[brother] * ((cnt + 1) | 1) % mod;
        }
        else {
            cnt++;
            sum += f[brother] * ((cnt + 1) / 2 * 2) % mod;
        }

        if (i == 0) {
            sum += f[trie[p][ch]] * (cnt + 1);
            // cout << "f = " << f[trie[p][ch]] << "\n";
        }
        sum %= mod;
        p = trie[p][ch];
    }
}
int qpow(int x, int n)
{
    int ret = 1;
    while(n) {
        if (n & 1) ret = ret * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return ret;
}
void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    tot = 1;
    sum = 0;
    for (int i = 1; i <= n; i++) {
        insert(a[i]);
    }
    dfs1(1, 0);
    for (int i = 1; i <= n; i++) {
        dfs2(a[i]);
        // cout << "sum = " << sum << "\n";
    }
    // cout << sum << "\n";
    int ans = sum * qpow(n * n % mod, mod - 2) % mod;
    cout << ans << "\n";

    for (int i = 1; i <= tot; i++) {
        trie[i][0] = trie[i][1] = 0;
        f[i] = 0;
    }
}

D.Matrix Cascade

题意

给定一个 0 和 1 组成的矩阵，目标是使用操作，让整个矩阵全变成 0 .操作是选取一个 1，然后反转他，以及他两侧以及以下的点。

做法

很容易想到从上到下开始模拟，因为同一行的 $1$ 并不会互相影响。所以遇见 $1$ 一定要操作一次。

所以这题核心在于怎么维护好标记。

考虑这种情况：

101
000
000

他们均会影响到左下角的那个 $0$，如果只打一种标记，便很容易忽略掉这个左下角。所以打三种标记，一种是往左下，一种是垂直往下，最后一种是右下。

对于一个 $a_{i,j}$，他要异或上三种标记还是 $1$ 的话，那么这个点的下面三个点的标记就要更新。

int l[N][N], mid[N][N], r[N][N];
char s[N][N];
int a[N][N];
void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> (s[i] + 1);
        for (int j = 1; j <= n; j++) a[i][j] = s[i][j] - '0';
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[i][j] ^ l[i][j] ^ r[i][j] ^ mid[i][j]) {
                l[i + 1][j - 1] ^= 1;
                mid[i + 1][j] ^= 1;
                r[i + 1][j + 1] ^= 1;
                ans++;
            }
            if (l[i][j]) {
                l[i + 1][j - 1] ^= 1;
                mid[i + 1][j] ^= 1;
            }
            if (mid[i][j]) {
                mid[i + 1][j] ^= 1;
            }
            if (r[i][j]) {
                r[i + 1][j + 1] ^= 1;
                mid[i + 1][j] ^= 1;
            }
        }
    }
    cout << ans << "\n";

    for (int i = 0; i <= n + 1; i++) {
        for (int j = 0; j <= n + 1; j++) {
            a[i][j] = l[i][j] = r[i][j] = mid[i][j] = 0;
        }
    }
}

C.Divisor Chain

题意

给定一个数 $x$，每次选择一个 $x$ 的因子，然后减去这个因子，同一个因子不可以使用超过两次，让 $x$ 最终变成 $1$。

做法

很容易想到偶数就直接除以 $2$，然后就联想到二进制下的 $0$ 和 $1$，然后问题就来了，如果二进制下全都是 $1$ 该怎么处理呢？

那么只能先减一，变成偶数，接下来就能发现，减去 $2$，二进制下就能少一个 $1$，那这个数就变成了 $4$ 的倍数，就可以减 $4$ 了，以此类推，$x$ 最终就能变成 $1$。

void solve()
{
    int x;
    cin >> x;
    vector<int> ans;
    ans.emplace_back(x);
    if (x & 1) {
        ans.emplace_back(x - 1);
        x--;
    }
    for (int i = 1; i <= 30; i++) {
        if (x > (1ll << i) && (x >> i & 1)) {
            x -= (1ll << i);
            ans.emplace_back(x);
        }
    }
    while(x != 1) {
        ans.emplace_back(x / 2);
        x /= 2;
    }
    cout << ans.size() << "\n";
    for (auto &i : ans) cout << i <<  " ";
    cout << "\n";
}

B.Swap and Reverse

题意

给定一个字符串，可以交换位置 $i$ 和 位置 $i+2$ 的字符；除此之外，还可以翻转长度为 $k$ 的区间，问最终字符串最小字典序。

做法

一开始没看清题，看成了可以交换位置 $i$ 和 位置 $i+3$ 的字符，感觉就要上并查集，以此来将每个点加入他们对应的集合最后排序。但是这才 $B$ 题，这样做未免也太复杂了，然后又看一遍题，果然是读假题了。

首先看他的条件翻转长度为 $k$ 的区间，这个操作其实可以看 $k$ 的奇偶，如果是偶数，那么一个位置 $x$，经过一次操作后，其奇偶性就会改变；反之则不会改变。

然后再结合条件“可以交换位置 $i$ 和 位置 $i+2$ 的字符”，就可以推断出，一旦 $k$ 是偶数，那么位置 $x$ 可以经过操作，去任意位置；奇数，那么只能去任意与 $x$ 同奇偶性的位置。

于是这题就做完了。

char s[N];
void solve()
{
    int n, k;
    cin >> n >> k;
    cin >> (s + 1);
    if (k % 2 == 0) {
        sort(s + 1, s + 1 + n);
    }
    else {
        vector<char> v[2];
        for (int i = 1; i <= n; i++) {
            v[i & 1].emplace_back(s[i]);
        }
        for (int i = 0; i < 2; i++) {
            sort(v[i].begin(), v[i].end());
        }
        int cnt[2] = {0, 0};
        for (int i = 1; i <= n; i++) {
            s[i] = v[i & 1][cnt[i & 1]++];
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << s[i];
    }
    cout << "\n";
}

A 纯模拟，不想写他的题解了