Wheel of Fortune

题目大意：
给定ab两个人的血量，现在有一个随机的攻击，每次攻击对象是随机的并且每次会使得每个人的血量-10，求最后a活下来的概率期望

input：
30 5 0 0 0 0 0 0
30 5 0 0 0 0 0 0

output：
499122177

解：
令a代表a能抗住多少次攻击，b同理
在对b施加b次攻击的基础上，a已经获胜，枚举a受到攻击的次数，然后用组合数去算出在所有攻击中a受到攻击的时刻，将结果累加

#include<bits/stdc++.h>

#define int long long
using namespace std;

const int mod = 998244353;
int c[10000005];
int c2[10000005];

int qpow(int a, int b) {
    int res = 1;
    for (; b; b >>= 1) {
        if (b & 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
    }
    return res;
}


signed main() {
    int x[18], a, b;
    for (int i = 1; i <= 16; i++) {
        cin >> x[i];
    }
    a = x[1];
    b = x[9];
    a = (a + 9) / 10;
    b = (b + 9) / 10;
    c[b - 1] = 1;
    int res = 0;
    c2[0] = 1;
    for (int i = 1; i <= a + b; i++) {
        c2[i] = c2[i - 1] * 2 % mod;
    }

    for (int i = 0; i <= a - 1; i++) {
        if (i != 0) {
            c[i + b - 1] = (i + b - 1) % mod * c[i + b - 2] % mod * qpow(i, mod - 2) % mod;
        }
        int di = qpow(c2[b + i], mod - 2);
        res += c[i + b - 1] * di % mod;
        res %= mod;
    }
    cout << res << endl;
}

Shannon Switching Game?

题目大意：
给定一张有n个节点的无向图，初始时token在s点，现在a和b两个人轮流操作，a可以选择token所在的点的一条边，删除这条边，接着b可以选择一条边沿着这条边向下走到另一个点并且删除这条边，问b是否能够走到t点

input：
3
2 1 1 2
1 2
2 2 1 2
1 2
1 2
3 3 1 2
1 2
2 3
1 3

output：
Cut Player
Join Player
Cut Player

解：
从t点开始建立集合，如果集合外的点能够有两条边到达集合内的任意一点，则把这个点加进来，因为对于一个点能否走到下一个点，如果这两个点之间会有两条边，那么不管减去哪一条边都是可以到达这个点的。一直建立直到无点可以进入集合，如果s点在集合中，那么就是有解的，否则wuji

#include<bits/stdc++.h>

#define int long long
using namespace std;

vector<int> v[105];
int sets[105];
queue<int> q;
int paths[105];
int n, m, s, t;

void bfs() {
    q.push(t);
    sets[t] = 1;
    while (q.size()) {
        int cur = q.front();
        q.pop();
        for (int to: v[cur]) {
            if (sets[to]) continue;
            paths[to]++;
            if (paths[to] >= 2) {
                sets[to] = 1;
                q.push(to);
            }
        }
    }
}

signed main() {
    int a;
    cin >> a;

    int x, y;
    while (a--) {
        cin >> n >> m >> s >> t;
        for (int i = 1; i <= n; i++) {
            paths[i] = 0;
            sets[i] = 0;
            v[i].clear();
        }
        for (int i = 1; i <= m; i++) {
            cin >> x >> y;
            v[x].push_back(y);
            v[y].push_back(x);
        }
        bfs();
        if (sets[s]) {
            cout << "Join Player" << endl;
        } else {
            cout << "Cut Player" << endl;
        }
    }
}

Yet Another FFT Problem?

题目大意：
给定两个数组a，b，要你找出i,j,k,l使得a[i]+b[k]=a[j]+b[l]，没找到输出-1

input：
4 4
2 4 8 16
3 9 27 81

output：
1 3 1 2

解：

先对a去重然后记录一对重复的值，并且创建一个新的已经对a去重的数组，还要记录好新的数组中的元素在原数组中的下标，在枚举b的时候如果找到了b中重复的对子，那么可以直接输出记录好的东西，否则就枚举去重的a数组中所有的元素，将当前的b数组中的元素与a数组中所有的元素相减再加上1e7，这样就能保证这个值会处在0和1e7之间，如果这个值已经出现过了，根据之前的记录是可以找到这四个数的。

#pragma GCC optimize(3)

#include<bits/stdc++.h>

#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
const int N = 1e6 + 5;
const int MM = 2e7 + 5;

int n, a[N], b[N], m;
int n1, A[N]; // A为去重后的a数组的下标
int nx[MM], ny[MM];
int vis[MM >> 1]; // vis[i]记录i在a/b中的下标
int ggx = 0, ggy; // 记录a中一对相同元素的下标
bool ok = 0;

int main() { // 鸽笼原理。复杂度O(V)。AC
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);

        if (vis[a[i]]) { // a[i]之前已经出现过
            if (ggx == 0) { // 以前没发现对子
                ggx = vis[a[i]]; // 上一个a[i]的下标
                ggy = i; // 这个a[i]的下标
            }
        } else { // a[i]第一次出现
            A[++n1] = i; // 记录去重后的a数组的下标
        }
        vis[a[i]] = i; // 记录a[i]出现的下标
    }
    for (int i = 1; i <= m; i++) {
        scanf("%d", &b[i]); // 读入b[i]
    }


    memset(vis, 0, sizeof vis); // 清空vis,接下来vis[i]用来记录i在b中的下标
    for (int i = 1; i <= m; i++) { // 遍历b[i]
        if (vis[b[i]]) { // b[i]出现过
            if (ggx) { // a中存在"对子"
                printf("%d %d %d %d\n", ggx, ggy, vis[b[i]], i); // 输出两对相同元素
                ok = 1; // 找到了
                break;
            }
            continue;
        }

        // vis[b[i]]==0,b[i]第一次出现
        vis[b[i]] = i;
        for (int j = 1; j <= n1; j++) { // 枚举a中的元素（已通过A[i]去重）
            int u = 1e7; // 偏移量
            int o = b[i] - a[A[j]] + u; // 计算nx的下标
            if (nx[o]) { // 找到一组"碰撞"
                printf("%d %d %d %d\n", nx[o], A[j], ny[o], i);
                ok = 1;
                break;
            }

            nx[o] = A[j];
            ny[o] = i;
        }

        if (ok) break; // 已经找到，提前退出
    }

    if (!ok) puts("-1"); // 没找到，输出-1
}

这段代码来自fn哥哥