Lut本科回忆录

摆了好久，开始准备自己的棺材本
更新至D,J,K…

题D

题意：在一个 $n*m$ 且布满巧克力的二维平面上, $A 和 B$ 两个人轮流操作，每次操作选择一个坐$（x, y）$,这时他能将 $(1<=i<=x,1<=j<=y)$ 上的巧克力都吃了，每个人操作时至少吃一个巧克力，谁吃最后一个巧克力则输。

解：当且仅当 $（n == m || n == 1）$ 时$K$吃最后一块。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
#define A puts("Walk Alone")
#define K puts("Kelin")
int main(){
    int n, m; cin >> n >> m;
    if(n == m && n == 1) A;
    else K;
}

题J

题意：$A$ 初始有 $n$ 元，他每次 gamble 花费 $x$ 元赌注，有 $0.5$ 概率获胜，获胜则获得 $2 * x$ 元， 反之无收获，问 $A$ 赚取 $m$ 元的概率是多少。其中 $x$ 初始值为 $1$, 若上一轮获胜则 $x = 1$， 反之 $x = x * 2$, 对于概率 $a = x / y$ 满足 $a * y = x$ $MOD$ $998244353$ ($1<=n,m<=1e9$)

解：由题意得，倘若我们连续输了$i$轮，那么第$i+1$轮获胜的话就可以获得$1$元。对于 $x$ 元钱，最多只能输 $lg = log2(x + 1)$ 次， 此时无法进行下一轮。此时我们必输的概率 $p = \frac{1}{2^{lg}}$, 那么获胜的能获胜的概率即为 $1 - p$。同时我们发现，对于$（1, 2)$、$(3，4，5，6)$、$（7，8，9，10，11，12，13，14）$ ，这一些区间里，必输的场次是一样的，那么对于一个区间内相同的 $p$, 我们可以使得$ans *= pow(p, 场次数)$，这里我们用$mx$计算出每个区间的上限，从而得出场次数，由此解得。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10, MOD = 998244353;
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(){
    ll n, m, ans = 1, sum = 0, x = 0, mx; cin >> n >> m;
    for(ll x = n; x < m + n; x = mx){
        ll lg = log2(x + 1);
        ll p = (1 - qmi(qmi(2, lg), MOD - 2) + MOD) % MOD;
        mx = min((1ll << (lg + 1)) - 1, m + n);
        ans = ans * qmi(p, mx - x) % MOD;
    }
    cout << ans;
}

题K

题意：给定一个无向图和整数 $k$，同时可以在两个已连的点间增加一点，操作次数不限。问距离$1$结点距离不超过$K$的最大点数为多少。
解：由以下数据得出无向图。

8 9 3
1 2
1 3
1 5
3 4
3 6
4 5
5 6
6 7
7 8

其中我们可以将其处理为一颗拓扑型的树，得出每个结点到结点 $1$ 的最短距离，如下图所示。

然后对于那些多余的边，就可以对答案 $ans += k - dist[u]$, 同时对于如该样例的单条叶子结点 $2$ 而言，其对答案的贡献为 $k - dist[2]$。最终得到如下的图，图中除结点 $8$ 以外到结点 $1$ 的距离都 $<=k$。

代码如下

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
vector<int> g[N];
int dist[N], pre[N];
int main(){
    int n, m, k; ll ans = 0; cin >> n >> m >> k;
    for(int i = 1; i <= n; ++ i) dist[i] = -1;
    for(int i = 1; i <= m; ++ i){
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    queue<int> q;
    dist[1] = 0;
    q.push(1);
    while(q.size()){
        int u = q.front(); q.pop();
        //if(dist[u] == -1) continue;
        if(dist[u] <= k) ans ++;
        for(auto &v: g[u]){
            if(dist[v] == -1){
                dist[v] = dist[u] + 1;
                pre[v] = u;
                q.push(v);
            }else if(pre[u] != v) ans += max(k - dist[u], 0);
        }
    }
    for(int i = 2; i <= n; ++ i){
        if(dist[i] != -1 && g[i].size() == 1) ans += max(k - dist[i], 0);
    }
    cout << ans;
}