摆了好久，开始准备自己的棺材本
更新至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;
}