《信息学奥赛一本通·高手专项训练》集训 Day 5

· · 个人记录

我博弈论和概率论能力为 0……

博弈论

\color{Red}0\color{Black}+\color{#FFC116}65\color{Black}+\color{Red}0\color{Black}=\color{Orange}65\color{Black}\text{/Rank 12}

\color{Black}\text{A. 染色游戏}

题目

Alice 和 Bob 在一棵有根树上玩一个游戏。初始状态下这棵树的每个结点被染成了黑色或者白色。

游戏时两人反复轮流进行以下操作：选一个目前仍然为白色的结点，将这个点以及它到根的路径上的所有点都染为黑色。当前的操作结束后整棵树都变黑的一方胜利。

先手的 Alice 想知道自己是否存在必胜策略，如果是，她进而希望知道在确保胜利的前提下第一步可以采取的行动。

题解

SP11414 COT3 - Combat on a tree

设 SG(x) 为以 x 为根的子树的 SG 值，对于点 x，可以枚举其子树内的每一个白点，删去该点到 x 的所有点，然后以 x 为根的子树会分裂为一个森林，也就是 x 状态可以转移到这个森林的状态，一个森林的 SG 值为每棵树的 SG 值异或和。SG(x) 即为子树内所有白点删去后形成的森林对应的 SG 值取 mex.

也就是说，求 SG(x) 的方法为：

  1. 一个森林内所有树的 SG 值的异或和 \rightarrow 该森林的 SG 值；
  2. 所有可能构成的森林的 SG 值取 mex\rightarrow SG(x)。

所有可能构成的森林的 SG 值就是 x 和它子节点的 SG 值的中间状态。

考虑用数据结构来优化这个过程，每个节点上都用一个 \texttt{01 Trie} 来维护其子树内所有白点删去后对应的森林的 SG 值。设 y 为 x 的一个儿子，那么 y 对应的 \texttt{01 Trie} 中维护的信息还需再异或上 x 其他儿子的 SG 值的异或和才是其正确的信息——删去 y 中某一白点对应的森林的 SG 值。整体异或一个值可以用打标记，交换左右儿子来实现。加上 y 的贡献即为将 y 对应的 \texttt{01 Trie} 合并到 x 上。

最后再 \text{DFS} 一遍，若一个点的后继状态为必败状态，则该点可以作为第一步选的点。

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;
long long read() {
    long long x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
void write(long long x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const int N = 2e6 + 10;
int n, c[N], sg[N], ans[N], cnt, rt[N], ch[N << 1][2], tag[N << 1], cov[N << 1];
int head[N], ver[N << 1], nxt[N << 1], tot;
void add(int x, int y) {
    ver[++tot] = y;
    nxt[tot] = head[x];
    head[x] = tot;
}
void pushtag(int p, int k, int x) {
    if (k == -1)
        return;
    if ((x >> k) & 1)
        swap(ch[p][0], ch[p][1]);
    tag[p] ^= x;
}
void pushdown(int p, int k) {
    if (!tag[p])
        return;
    pushtag(ch[p][0], k - 1, tag[p]);
    pushtag(ch[p][1], k - 1, tag[p]);
    tag[p] = 0;
}
void insert(int &p, int k, int x) {
    if (!p)
        p = ++tot;
    if (k == -1) {
        cov[p] = 1;
        return;
    }
    insert(ch[p][x >> k & 1], k - 1, x);
    cov[p] = cov[ch[p][0]] & cov[ch[p][1]];
}
int merge(int x, int y, int k) {
    if (!x || !y)
        return x + y;
    if (k == -1) {
        cov[x] |= cov[y];
        return x;
    }
    pushdown(x, k);
    pushdown(y, k);
    ch[x][0] = merge(ch[x][0], ch[y][0], k - 1);
    ch[x][1] = merge(ch[x][1], ch[y][1], k - 1);
    cov[x] = cov[ch[x][0]] & cov[ch[x][1]];
    return x;
}
int mex(int p, int k) {
    if (!p || k == -1)
        return 0;
    pushdown(p, k);
    if (cov[ch[p][0]])
        return (1 << k) | mex(ch[p][1], k - 1);
    return mex(ch[p][0], k - 1);
}
void dfs1(int x, int fa) {
    int v = 0;
    for (int i = head[x]; i; i = nxt[i]) {
        int y = ver[i];
        if (y == fa)
            continue;
        dfs1(y, x);
        v ^= sg[y];
    }
    for (int i = head[x]; i; i = nxt[i]) {
        int y = ver[i];
        if (y == fa)
            continue;
        pushtag(rt[y], 20, v ^ sg[y]);
        rt[x] = merge(rt[x], rt[y], 20);
    }
    if (!c[x])
        insert(rt[x], 20, v);
    sg[x] = mex(rt[x], 20);
}
void dfs2(int x, int fa, int v) {
    for (int i = head[x]; i; i = nxt[i]) {
        int y = ver[i];
        if (y == fa)
            continue;
        v ^= sg[y];
    }
    if (!v && !c[x])
        ans[++cnt] = x;
    for (int i = head[x]; i; i = nxt[i]) {
        int y = ver[i];
        if (y == fa)
            continue;
        dfs2(y, x, v ^ sg[y]);
    }
}
int main() {
    n = read();
    for (int i = 1; i <= n; i++) {
        c[i] = read();
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        u = read();
        v = read();
        add(u, v);
        add(v, u);
    }
    dfs1(1, 0);
    if (!sg[1]) {
        puts("-1");
        return 0;
    }
    dfs2(1, 0, 0);
    sort(ans + 1, ans + cnt + 1);
    for (int i = 1; i <= cnt; i++) {
        write(ans[i]);
        putchar('\n');
    }
    return 0;
}

\color{#52C41A}\text{B. 日历游戏}

题目

小 A 和 TA 的宠物正在玩一个日历游戏，开始时，他们从 1900 年 1 月 1 日到 2012 年 12 月 22 日选一个日期开始，依次按照如下规则之一向后跳日期：

跳到日历上的下一天。 跳到日历上的下个月的同一天（如果不存在，则不能这么做）。 要是谁正好到达 2012 年 12 月 22 日那么他就赢了，如果到达这天之后的日期那他就输了。

每次都是小 A 先走的。

现在，给你一个日期，请问小 A 一定能赢吗？

题解

考虑计算日期 x 的 SG 值，因为他最多只有两个后继状态，所以暴力记忆化搜索预处理再暴力取 mex 即可。

日期要写对，不然会像我一样得到玄学分数。

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;
long long read() {
    long long x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
void write(long long x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const int N = 6e4 + 10;
int month[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }, tot, f[N];
struct asdf {
    int y, m, d;
    vector<int> nxt;
} a[N], e, g;
map<int, int> has;
bool pd(asdf x) {
    if (x.y < 1900 || x.y > 2012)
        return 0;
    if (x.m < 1 || x.m > 12)
        return 0;
    if (x.d < 1 || x.d > 31)
        return 0;
    if (x.y == 2012) {
        if (x.m > 12)
            return 0;
        if (x.m == 12 && x.d > 22)
            return 0;
    }
    if (x.m == 2) {
        if ((x.y % 400 == 0) || (x.y % 100 != 0 && x.y % 4 == 0))
            return x.d <= 29;
        return x.d <= 28;
    }
    return x.d <= month[x.m];
}
int dfs(int x) {
    if (f[x] != -1)
        return f[x];
    for (int i = 0; i <= 3; i++) {
        bool ff = 1;
        for (int j = 0; j < a[x].nxt.size(); j++) {
            if ((dfs(has[a[x].nxt[j]])) == i)
                ff = 0;
        }
        if (ff)
            return f[x] = i;
    }
}
int main() {
    for (e.y = 1900; e.y <= 2012; e.y++) {
        for (e.m = 1; e.m <= 12; e.m++) {
            for (e.d = 1; e.d <= 31; e.d++) {
                if (!pd(e))
                    continue;
                has[e.y * 10000 + e.m * 100 + e.d] = ++tot;
                a[tot] = e;
                g = e;
                g.d++;
                if (g.m == 12 && g.d == 32) {
                    g.y++;
                    g.m = 1;
                    g.d = 1;
                } else if (!pd(g)) {
                    g.m++;
                    g.d = 1;
                }
                if (pd(g))
                    a[tot].nxt.push_back(g.y * 10000 + g.m * 100 + g.d);
                g = e;
                g.m++;
                if (g.m > 12) {
                    g.y++;
                    g.m = 1;
                }
                if (pd(g))
                    a[tot].nxt.push_back(g.y * 10000 + g.m * 100 + g.d);
            }
        }
    }
    memset(f, -1, sizeof(f));
    f[has[2012 * 10000 + 12 * 100 + 22]] = 0;
    int Y, M, D;
    while (cin >> Y && Y) {
         M = read();
        D = read();
        cout << (dfs(has[Y * 10000 + M * 100 + D]) == 0 ? "NO" : "YES") << endl;
    }
    return 0;
}

\color{#52C41A}\text{C. 棋盘游戏}

题目

Alice 和 Bob 在玩一个游戏，给出一张 n\times m 的棋盘，上面有一些点是障碍，游戏的开始，Alice 选定棋盘上任意一个不是障碍的格子，并且将一枚棋子放在其中，然后 Bob 先手，两人轮流操作棋子，每次操作必须将棋子从当前位置移动到一个相邻的无障碍且未经过的格子（即每个格子不允许经过两次），不能操作的人输，如果两人都按照最优策略操作，请问初始时 Alice 将棋子放在哪些格子上有必胜策略。

题解

将棋子黑白染色，棋盘就变成了一张二分图，对它求最大匹配。

如果一个点不一定在最大匹配中，那么这个点 Alice 必胜。证明：任选一个这个点未匹配的最大匹配，Alice 只要一直走匹配边，Bob 就只能走非匹配边，如果 Bob 获胜说明找到了一条增广路，矛盾。

如果一个点一定在最大匹配中，那么这个点 Bob 必胜。证明：任选一个最大匹配，Bob 只要一直走匹配边，Alice 就只能走非匹配边，如果 Alice 获胜就可以构造一个这个点未匹配的最大匹配，矛盾。

所以判断每个点是否一定在最大匹配里即可。

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;
long long read() {
    long long x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
void write(long long x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const int N = 110, M = 1e5 + 10;
int n, m, a[N][N], v[M], match[M], vis[M], nid, z[M], t;
int head[M], ver[M << 1], nxt[M << 1], tot;
int fx[4] = { 0, 0, 1, -1 }, fy[4] = { 1, -1, 0, 0 };
string s;
void add(int x, int y) {
    ver[++tot] = y;
    nxt[tot] = head[x];
    head[x] = tot;
}
int b(int x, int y) { return (x - 1) * m + y; }
int kmdfs(int x) {
    for (int i = head[x]; i; i = nxt[i]) {
        int y = ver[i];
        if (vis[y] == nid)
            continue;
        vis[y] = nid;
        if (!match[y] || kmdfs(match[y])) {
            match[y] = x;
            return 1;
        }
    }
    return 0;
}
void kmdfs2(int x) {
    v[x] = 1;
    for (int i = head[x]; i; i = nxt[i]) {
        int y = ver[i];
        if (match[y] && !v[match[y]])
            kmdfs2(match[y]);
    }
}
int main() {
    n = read();
    m = read();
    for (int i = 1; i <= n; i++) {
        cin >> s;
        for (int j = 0; j < m; j++) {
            if (s[j] == '.')
                a[i][j + 1] = 1;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (!a[i][j])
                continue;
            for (int k = 0; k < 4; k++) {
                int x = i + fx[k], y = j + fy[k];
                if (x < 1 || y < 1 || x > n || y > m || !a[x][y])
                    continue;
                add(b(i, j), b(x, y) + n * m);
                add(b(x, y) + n * m, b(i, j));
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j]) {
                nid++;
                if (!kmdfs(b(i, j)))
                    z[++t] = b(i, j);
            }
        }
    }
    if (t) {
        for (int i = 1; i <= t; i++) kmdfs2(z[i]);
        t = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                if (v[b(i, j)])
                    z[++t] = b(i, j);
        cout << t << endl;
        for (int i = 1; i <= t; i++) {
            cout << (z[i] - 1) / m + 1 << " " << (z[i] - 1) % m + 1 << endl;
        }
    } else
        write(0);
    return 0;
}

期望问题

\color{Orange}10\color{Black}+\color{Red}0\color{Black}+\color{Red}0\color{Black}=\color{Red}10\color{Black}\text{/Rank 14}

\color{#52C41A}\text{A. 数列期望}

题目

随机生成一个 m+1 个数的数列，第一个数为 0，生成第 i 个数时，找出前 i-1 个数中所有小于 n 的数，从中等概率选择一个数 k，第 i 个数为 k+1 。每个数都有一个对应的权值 a_i，求数列的权值的和的期望模 998244353 的值。

题解

读题后，显然 n 是没有用的。设 dp_{i,j} 表示第 i+1 个数（数的序号在题中是从 1 开始的，第一个数是 0）成为 a_j 的概率，那么：

dp_{i,j}=\sum_{k=0}^{k<i}\frac{dp_{k,j-1}}{i}\bmod 998244353

答案为 \sum_{i=1}^{m}\sum_{j=1}^i\times a_j\bmod 998244353。

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;
long long read() {
    long long x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
void write(long long x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const int N = 30;
const ll mod = 998244353;
ll n, m, a[120000], dp[N][N], ans, jc = 1;
ll qmi(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
int main() {
    n = read();
    m = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    for (int i = 1; i <= m; i++) jc = jc * i % mod;
    dp[0][0] = 1;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= i; j++) {
            for (int k = 0; k < i; k++) dp[i][j] = (dp[i][j] + dp[k][j - 1] * qmi(i, mod - 2)) % mod;
            ans = (ans + dp[i][j] * a[j] % mod) % mod;
        }
    write(ans);
    return 0;
}

\color{#52C41A}\text{B. 彩球抽取}

题目

袋子里有 n 个球。每次依次取出两个，把第二个球涂成第一个球的颜色，然后放回袋里搅匀。你的任务是算出让所有球的颜色相同所需要的取球次数期望。

题解

把颜色改成 0\sim 25，设 f_{i,j,k} 表示第 i 次取球后，颜色为 j 的球有 k 个的概率，目标状态就是 \sum f_{i,j,n}，即 n 个球的颜色都是 j。

但是次数 i 的上限无法确定，但因为本题精度要求不高，所以我们可以认为定一个上限 50000。对于 f_{i,j,k}，有三种情况：

  1. 取出的第一个球的颜色是 j，第二个不是，f_{i,j,k}\leftarrow f_{i-1,j,k-1}\times\frac{k}{n}\times\frac{n-k}{n-1}。
  2. 取出的第一个球的颜色不是 j，第二个是，f_{i,j,k}\leftarrow f_{i-1,j,k+1}\times\frac{n-k}{n}\times\frac{k}{n-1}。
  3. 取出的两个球的颜色都是或都不是 j，球的个数不变，f_{i,j,k}\leftarrow f_{i-1,j,k}\times(1-2\times\frac{k}{n}\times\frac{n-k}{n-1})。
### 代码 ```cpp #include <bits/stdc++.h> #define ll long long using namespace std; long long read() { long long x = 0, f = 1; char ch = getchar(); while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)) { x = x * 10 + ch - 48; ch = getchar(); } return x * f; } void write(long long x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); } const int N = 30; int n; double f1[N][N], f2[N][N], ans; int cnt[N]; string c; int main() { cin >> c; n = c.size(); for (int i = 0; i < n; i++) cnt[c[i] - 'A']++; for (int i = 0; i < 26; i++) if (cnt[i]) f2[i][cnt[i]] = 1; for (int step = 0; step < 50000; step++) { for (int i = 0; i < 26; i++) ans += step * f2[i][n]; memcpy(f1, f2, sizeof(f1)); memset(f2, 0, sizeof(f2)); for (int i = 0; i < 26; i++) { for (int j = 1; j < n; j++) { double v = double(j) * (n - j) / n / (n - 1); f2[i][j + 1] += f1[i][j] * v; f2[i][j - 1] += f1[i][j] * v; f2[i][j] += f1[i][j] * (1.0 - 2 * v); } } } printf("%.6lf\n", ans); return 0; } ``` ## $\color{#3498DB}\text{C. 取牌游戏}

题目

这里有一个简单的例子： 例如一共有 $4$ 个玩家，有四张卡片分别写着 $3,4,5,6$。 - 第一回合，庄家是玩家 $1$，假设他选择了一张写着数字 $5$ 的卡片。那么按顺时针数 $1,2,3,4,1$，最后玩家 $1$ 被踢出游戏。 - 第二回合，庄家就是玩家 $1$ 的下一个人，即玩家 $2$。假设玩家 $2$ 这次选择了一张数字 $6$，那么 $2,3,4,2,3,4$，玩家 $4$ 被踢出游戏。 - 第三回合，玩家 $2$ 再一次成为庄家。如果这一次玩家 $2$ 再次选了 $6$，则玩家 $3$ 被踢出游戏，最后的胜者就是玩家 $2$。 ### 题解 考虑逆序 $\text{DP}$，设 $f_{i,j}$ 表示倒数第 $i$ 轮，存活下的第 $j$ 个玩家赢的概率，玩家 $j$ 要赢只要倒数第 $i-1$ 轮的第 $j-k$ 个玩家赢即可，$k$ 是卡片上的数字。 为什么呢？我们在倒数第 $i$ 轮把玩家编号改为 $0\sim i-1$，我们始终设庄家为玩家 $0$，那么第 $k-1\pmod i$ 个玩家就会出局，新庄家编号为 $k\pmod i$，由于庄家编号应为 $0$，所以 $k\rightarrow 0$，相当于把每个玩家的编号减 $k$，玩家 $j$ 的编号就变为 $j-k\pmod i$。 于是有 $f_{i,j}\leftarrow \frac{f_{i-1,j-k}}{m}$。 ### 代码 ```cpp #include <bits/stdc++.h> #define ll long long using namespace std; long long read() { long long x = 0, f = 1; char ch = getchar(); while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)) { x = x * 10 + ch - 48; ch = getchar(); } return x * f; } void write(long long x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); } const int N = 310; int n, m, c[N]; double dp[N][N]; int main() { n = read(); m = read(); for (int i = 1; i <= m; i++) c[i] = read() - 1; dp[1][0] = 100.0; for (int i = 2; i <= n; i++) { for (int j = 0; j < i; j++) { for (int k = 1; k <= m; k++) { if (c[k] % i != j) dp[i][j] += dp[i - 1][(j - (c[k] % i + 1) + i) % i] * 1.0 / m; } } } for (int i = 0; i < n; i++) printf("%.2lf%% ", dp[n][i]); return 0; } ```