2022 年牛客多校第十场签到题题解

F Shannon Switching Game?

题意：给定一个多重无向图 $G(V,E)G(V,E)$ 和一对点 $s,ts,t$，起始时 $ss$ 处有一个令牌。先手可以选择删除图上的一条边，后手可以选择删除令牌所在点 $uu$ 邻接的一条边 $(u,v)(u,v)$，然后将令牌移动到 $vv$。当令牌移动到 $tt$ 时后手获胜，否则先手胜。问最终结局。$\mathrm{\mid }V\mathrm{\mid }\le 100,\mathrm{\mid }E\mathrm{\mid }\le 1\times 10^3|V|\; \backslash leq\; 100,|E|\; \backslash leq\; 1\backslash times\; 10^3$。

解法：若令牌所处的位置确定，则胜负已分。显然若令牌在 $tt$ 处为一个必胜态，若某个节点能到达两个及以上的必胜态，则该节点也为必胜态——因为先手没办法删完该点通向必胜态的边。所以倒过来从 $tt$ 开始 bfs 找必胜态节点即可。总时间复杂度 $\mathcal{O}(\mathrm{\mid }V\mathrm{\mid }+\mathrm{\mid }E\mathrm{\mid })\backslash mathcal\; O(|V|+|E|)$。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int caset, n, m, s, t;
    scanf("%d", &caset);
    while (caset--)
    {
        scanf("%d%d%d%d", &n, &m, &s, &t);
        vector<vector<int>> deg(n + 1, vector<int>(n + 1, 0));
        vector<vector<int>> g(n + 1);
        for (int i = 1, u, v; i <= m; i++)
        {
            scanf("%d%d", &u, &v);
            deg[u][v]++;
            deg[v][u]++;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        vector<int> vis(n + 1), in(n + 1, 0);
        queue<int> q;
        vis[t] = 1;
        q.push(t);
        while (!q.empty())
        {
            int tp = q.front();
            q.pop();
            for (auto i : g[tp])
            {
                if (deg[tp][i] > 1)
                {
                    if (!vis[i] && vis[tp])
                    {
                        vis[i] = 1;
                        q.push(i);
                    }
                }
                else if (deg[tp][i] == 1 && vis[tp])
                    in[i]++;
                if (in[i] >= 2 && !vis[i])
                {
                    vis[i] = 1;
                    q.push(i);
                }
            }
        }
        if (vis[s])
            printf("Join Player\n");
        else
            printf("Cut Player\n");
    }
    return 0;
}

H Wheel of Fortune

题意：给定 $1616$ 个数字 $A,B,a_1,a_2,\cdots ,a_7,b_1,b_2,\cdots ,b_{7}A,B,a\_1,a\_2,\backslash cdots,a\_7,b\_1,b\_2,\backslash cdots,b\_7$，从中随机选择一个数字 $xx$ 使得 $x\leftarrow x-10x\; \backslash leftarrow\; x-10$，直到 $A\le 0A\; \backslash leq\; 0$ 或者 $B\le 0B\; \backslash leq\; 0$。问有多大概率 $B\le 0B\; \backslash leq\; 0$ 的结束游戏。

解法：显然随机选择数字只和 $A,BA,B$ 有关。记 $x=\lceil {\displaystyle \frac{A}{10}}\rceil x=\backslash left\backslash lceil\; \backslash dfrac\{A\}\{10\}\; \backslash right\; \backslash rceil$，$y=\lceil {\displaystyle \frac{B}{10}}\rceil y=\backslash left\backslash lceil\; \backslash dfrac\{B\}\{10\}\; \backslash right\; \backslash rceil$，则只需要让 $BB$ 被选择 $yy$ 次之前 $AA$ 不被选择到 $xx$ 次即可，且最后一击必须是抽中 $BB$。答案为 ${\displaystyle \sum _{i=0}^{x-1}\left(\genfrac{}{}{0px}{}{i+y-1}{i}\right)2^{-(i+y)}}\backslash displaystyle\; \backslash sum\_\{i=0\}^\{x-1\}\; \{i+y-1\; \backslash choose\; i\}2^\{-(i+y)\}$。

I Yet Another FFT Problem?

题意：给定长度分别为 $n,mn,m$ 的序列 $\{a_n\},\{b_m\}\backslash \{a\_n\backslash \},\backslash \{b\_m\backslash \}$，问是否存在四个下标 $i,j,k,li,j,k,l$ 满足 $1\le i\le j\le n,1\le k\le l\le m1\; \backslash leq\; i\; \backslash leq\; j\; \backslash leq\; n,1\; \backslash leq\; k\; \backslash leq\; l\; \backslash leq\; m$ 且 $\mathrm{\mid }{a}_i-a_j\mathrm{\mid }=\mathrm{\mid }{b}_k-b_l\mathrm{\mid }|a\_i-a\_j|=|b\_k-b\_l|$。$a_i,b_i\le 1\times 10^{7}a\_i,b\_i\; \backslash leq\; 1\backslash times\; 10^7$，$n,m\le 1\times 10^{6}n,m\; \backslash leq\; 1\backslash times\; 10^6$。

解法：不妨减少限制 $i\le ji\; \backslash leq\; j$ 和 $k\le lk\; \backslash leq\; l$，则可脱去绝对值有 $a_i-a_j=b_k-b_{l}a\_i-a\_j=b\_k-b\_l$，即 $a_i+b_l=a_j+b_{k}a\_i+b\_l=a\_j+b\_k$。那么问题转化为，从 $\{a_n\},\{b_m\}\backslash \{a\_n\backslash \},\backslash \{b\_m\backslash \}$ 中分别选一个数使得他们碰撞。由于 $a_i,b_i\le 1\times 10^{7}a\_i,b\_i\; \backslash leq\; 1\backslash times\; 10^7$，则 $a_i+b_j\in [1,2\times 10^7]a\_i+b\_j\; \backslash in\; [1,2\backslash times\; 10^7]$，因而用鸽巢原理可得，$\{b\}\backslash \{b\backslash \}$ 序列长度不超过 $\lceil {\displaystyle \frac{2\times 10^7}{n}}\rceil \backslash left\backslash lceil\; \backslash dfrac\{2\backslash times\; 10^7\}\{n\}\backslash right\; \backslash rceil$ 就必然产生碰撞。所以仅需要保留 $bb$ 序列的前 $\lceil {\displaystyle \frac{2\times 10^7}{n}}\rceil \backslash left\backslash lceil\; \backslash dfrac\{2\backslash times\; 10^7\}\{n\}\backslash right\; \backslash rceil$ 项即可。总时间复杂度 $O(V)O(V)$，其中 $VV$ 代表 $a,ba,b$ 的值域。

#include <bits/stdc++.h>
#define fp(i, a, b) for (int i = a, i##_ = (b) + 1; i < i##_; ++i)
#define fd(i, a, b) for (int i = a, i##_ = (b) - 1; i > i##_; --i)

using namespace std;
const int N = 2e7 + 5;
using pii = pair<int, int>;
int n, m;
pii w[N];
unordered_map<int, vector<int>> A, B;
void Solve() {   
    scanf("%d%d", &n, &m);
    for (int x, i = 1; i <= n; ++i) scanf("%d", &x), A[x].push_back(i);
    for (int x, i = 1; i <= m; ++i) scanf("%d", &x), B[x].push_back(i);
    vector<pii> a, b;
    pii ma, mb;
    for (auto &[i, v] : A) {
        a.push_back({i, v[0]});
        if (v.size() > 1) ma = {v[0], v[1]};
    }
    for (auto &[i, v] : B) {
        b.push_back({i, v[0]});
        if (v.size() > 1) mb = {v[0], v[1]};
    }
    if (ma.first && mb.first)
        return printf("%d %d %d %d\n", ma.first, ma.second, mb.first, mb.second), void();
    b.resi***(b.size(), size_t(2e7 / a.size())));
    for (auto &[x, i] : a)
        for (auto &[y, k] : b) {
        auto [j, l] = w[x + y];
        if (j && i != j && k != l) {
            printf("%d %d %d %d\n", i, j, k, l);
            return;
        } else w[x + y] = {i, k};
    }
    puts("-1");
}
int main() {
    int t = 1;
    while (t--) Solve();
    return 0;
}