比赛链接
本文发布于博客园，会跟随补题进度实时更新，若您在其他平台阅读到此文，请前往博客园获取更好的阅读体验。
跳转链接：https://www.cnblogs.com/TianTianChaoFangDe/p/18809665
开题 + 补题情况
这场被自己唐到了，有点着急了，没能冷静下来思考，导致签到题一错再错，最后甚至完全偏离了自己原本的思路。
1001 - 小凯逛超市
很明显的无穷背包，但一开始没有好好读题，打成 01 背包了，不仔细的下场。
点击查看代码（省略了取模类）
void solve() { int n, m, v;std::cin >> n >> m >> v; std::vector<i64> a(n + 1); for(int i = 1;i <= n;i ++) { std::cin >> a[i]; } std::vector<std::vector<Z>> dp(v + 1, std::vector<Z>(m + 1)); dp[0][0] = 1; for(int i = 1;i <= n;i ++) { for(int j = a[i];j <= v;j ++) { for(int k = 1;k <= m;k ++) { dp[j][k] += dp[j - a[i]][k - 1]; } } } Z ans = 0; for(int i = 0;i <= v;i ++) { ans += dp[i][m]; } std::cout << ans << 'n'; } 1010 - 小凯做梦
这个题还是很好的，要做出这个题，我们首先需要知道一个重要的计算树上两点路径距离的公式。
记 (dep_x) 为点 (x) 到根的距离，(d_{i,j}) 为点 (i) 到点 (j) 之间的距离，则有：
如果将这个式子对 (2) 取模，又会发生什么呢：
而对于三个点 (i, j, k)，要有 (d_{i, j} = d_{j, k} = d_{i, k} (mod 2))，我们可以列出下面这几个式子：
消元可得：
然后这个问题就转化为一个很简单的组合数问题了。
点击查看代码
using i64 = long long; using u64 = unsigned long long; using u32 = unsigned int; const int N = 2e5 + 9; struct Node { int v; int w; }; void solve() { int n;std::cin >> n; std::vector<std::vector<Node>> g(n + 1); for(int i = 1;i < n;i ++) { int u, v, w;std::cin >> u >> v >> w; w %= 2; g[u].push_back({v, w}); g[v].push_back({u, w}); } std::vector<int> dis(n + 1, 0); auto dfs = [&](auto &&self, int st, int fa) -> void { for(auto &[v, w] : g[st]) { if(v == fa)continue; dis[v] = (dis[st] + w) % 2; self(self, v, st); } }; dfs(dfs, 1, 0); std::array<i64, 2> sum{0, 0}; for(int i = 1;i <= n;i ++) { sum[dis[i]] ++; } i64 ans = 0; ans += sum[0] * sum[0] * sum[0]; ans += sum[1] * sum[1] * sum[1]; std::cout << ans << 'n'; } 1006 - 小凯在长跑
这个题是真的唐，不小心写出了一个 (sqrt{a^2 + b^2} = sqrt{a^2} + sqrt{b^2}) 然后被硬控两小时，记录于此，引以为戒，之后做题的时候一定要一步一步好好思考，式子想好了再写代码，不要凭空瞎造。
题目思路还是很简单的，中学数学题，就不多写思路了。
点击查看代码
void solve() { int d, r, x, y;std::cin >> d >> r >> x >> y; x = abs(x); y = abs(y); if(y <= d) { std::cout << abs(r - x) << 'n'; } else if(x * x + (y - d) * (y - d) <= r * r){ long double d1 = (long double)(x * x + (y - d) * (y - d)); std::cout << roundl(r - sqrtl(d1)) << 'n'; } else { long double d1 = sqrtl(x * x + (y - d) * (y - d)) - sqrtl(r * r); long double d2 = sqrtl((x - r) * (x - r) + (y - d) * (y - d)); long double d3 = sqrtl(x * x + (y - d - r) * (y - d - r)); std::cout << roundl(std::min(d1, std::min(d2, d3))) << 'n'; } } 1009 - 小凯取石子
个人认为这个题题目没有写清楚，对于小凯而言，应该是尽可能让自己获胜率高，但题目并没有对此进行说明也没有进行样例解析。
这个题可以打表找规律，但赛时没能找到规律，因此没能开出（也受到了长跑那个题的影响吧，心态不太稳定，一直忍不住在想那个题，但及时换题才是正确之道）。
用很常用的博弈手段来分析，我们从结果往回推，逐步分析博弈状态的转化，这里要注意，对于 Kc0，拿 (1) 个和拿 (4) 个都要分析，各有 (1/2) 的概率，对于小凯，要选择的是转化后得到的新概率更大的状态，并乘上操作后转化得到的新状态的概率，就是当前的概率，打表过程可以自行尝试（还是很考验人的细心的），这里仅给出结论：
- 当 (n % 5 = 0) 或 (n % 5 = 2) 时，必胜。
- 当 (n = 1 时)，(1 / 2) 的概率获胜。
- 当 (n % 5 = 1) 并且 (n neq 1) 时，有 (1 - (1/2) ^ {n / 5}) 的概率获胜。
- 当 (n % 5 = 3) 时，有 (1 - (1/2) ^ {n / 5 + 2}) 的概率获胜。
- 当 (n % 5 = 4) 时，有 (1 - (1/2) ^ {n / 5 + 1}) 的概率获胜。
至于为什么是对 (5) 取模呢，其实打表过程也是有迹可循的，打表打着打着就会出现一些抉择是 Kc0 拿 (1) 小凯拿 (4) 和 Kc0 拿 (4) 小凯拿 (1)，感觉多多少少和这个有关系，至于严谨证明就暂时想不到了。
点击查看代码（省略了取模类）
void solve() { i64 n;std::cin >> n; Z ans; Z t = 2; if(n % 5 == 0 || n % 5 == 2) { ans = 1; } else if(n == 1) { ans = Z(1) / 2; } else if(n % 5 == 1) { ans = Z(1) - Z(1) / t.Pow(n / 5); } else if(n % 5 == 3) { ans = Z(1) - Z(1) / t.Pow(n / 5 + 2); } else if(n % 5 == 4) { ans = Z(1) - Z(1) / t.Pow(n / 5 + 1); } std::cout << ans << 'n'; } 
