开题情况
还是很吃教训的一场比赛，被博弈论硬控两小时（很好的一个博弈论题），dijkstra被卡map，最终三题。
自己不会的东西还是太多了，还得多多练习多多长见识。
1001 - 签到
题如其名，签到题，问给出的字符串第一次出现的位置。
点击查看代码
void solve() { int n;cin >> n; string s;cin >> s; bool ck = false; for(int i = 1;i <= n;i ++) { string t;cin >> t; if(s == t) { cout << i << 'n'; ck = true; } } if(!ck)cout << -1 << 'n'; } 1006 - 密码
移项可得：(x = (c - b) / a)，那么只要枚举一下 (u, v, w) 的两两组合，组合起来的作差取绝对值，剩下那一个也取绝对值，若能整除则添加贡献，对于求得的所有值，贡献为 (n) 的就是答案（注意对于每一组 (u, v, w) 要去重一下只能算一次贡献，否则难以计数）。
点击查看代码
void solve() { map<int, int> mp; int n;cin >> n; for(int i = 1;i <= n;i ++)cin >> a[i] >> b[i] >> c[i]; set<int> st; for(int i = 1;i <= n;i ++) { st.clear(); if(abs(a[i] - b[i]) % abs(c[i]) == 0) { st.insert(abs(a[i] - b[i]) / abs(c[i])); } if(abs(a[i] - c[i]) % abs(b[i]) == 0) { st.insert(abs(a[i] - c[i]) / abs(b[i])); } if(abs(b[i] - c[i]) % abs(a[i]) == 0) { st.insert(abs(b[i] - c[i]) / abs(a[i])); } for(auto &i : st) { mp[i] ++; } } for(auto &[u, v] : mp) { if(v == n) { cout << u << 'n'; break; } } } 1007 - 分配宝藏
很好的一道博弈论题，之前遇到的博弈论，都是两个人博弈，分析必胜态和必败态就行了。
这里我们要分析的就不是必胜态和必败态了，而是 (n) 个人的诉求。
关于这 (n) 个人的诉求，题目有一句话很凝练：保证自己不被杀死的前提下企图获得更大的利益。
也就是说，既要保全自己，又要尽可能让自己有尽可能多的钱。
也就是说，对于船长，要尽可能给少，对于其他人，要尽可能拿多。
对于此题，我们可以用类似两人博弈的思路来思考，从结局往回推。
我们将所有船员从后往前编号为 (1, 2, 3, ..., n)。
对于 (n = 1)，此时无论如何染染一定不会被杀，因此不用给钱，分到的钱为 (0)。
对于 (n = 2)，我们必须贿赂一个船员举手不杀染染，才能保全染染，那对于 (1) 号船员和 (2) 号船员，贿赂谁呢？
注意到，如果染染被杀，此时人数变为 (1)，那么此时的船长就会按照 (n = 1) 时的最优策略来分配宝藏，也就是 (1) 号船员会分到 (0) 元，我们死了过后，(1) 号船员无法获得金币，因此，我们给他 (1) 个金币，对他来说就是赚的，那他也一定不会杀掉染染，此时过半，染染存活，而对于 (2) 号船员，如果染染死掉，他会成为船长，他可以随意选择给自己留多少金币，因此就算贿赂了他他也会杀掉染染，因此不能贿赂 (2) 号船员，因此 (n = 2) 时的答案为 (0,1)。
我们继续按上述思路分析，当 (n = 3) 时，如果染染被杀，此时人数变为 (2)，那么此时的船长就会按照 (n = 2) 时的最优策略来分配宝藏，也就是 (0,1)，那么回到 (n = 3) 的情况，如果染染被杀，(2) 号船员无法获得金币，因此，我们给他 (1) 个金币，对他来说就是赚的，那他也一定不会杀掉染染，而对于 (1) 号船员，如果染染被杀，他仍能获得一个金币，若要贿赂他需要花费 (2) 金币，不优，因此不能贿赂 (1) 号船员，对于 (3) 号船员，如果染染死掉，他会成为船长，他可以随意选择给自己留多少金币，因此就算贿赂了他他也会杀掉染染，因此不能贿赂 (3) 号船员，因此 (n = 3) 时的答案为 (0,1,0)。
按这个逻辑推下去我们会发现，其实我们要贿赂的，就是染染死掉之后，得不到金币的，此时只需要花费一个金币就能贿赂到他不杀自己，并且这个数量加上染染后一定会过半（我们可以通过分析染染贿赂的人数少了过后对下一位船长的决策优越性的影响来证明这个事情，见下方），否则对于染染死后下一个船长的最优解会不成立，所以答案就构造出来了，可以发现获得金币为 (1) 的船员的序号序列就是一个公差为 (2) 的等差数列，只需要找好首项和末项即可。
简单证明一下：首先无论奇偶，需要贿赂的人都是 (lfloor n / 2 rfloor)。
- 若 (n) 是奇数，则 (lfloor n / 2 rfloor = lfloor (n - 1) / 2 rfloor)，那么如果这一轮染染贿赂到的人少于 (lfloor n / 2 rfloor)，那么说明染染死后下一位船长贿赂到的人就多于 (lfloor n / 2 rfloor)，对下一位船长来说这个结果一定不优。
- 若 (n) 是偶数，则 (lfloor n / 2 rfloor = lfloor (n - 1) / 2 rfloor + 1)，由上面的分析可得，染染一定不会贿赂下一位船长，因此染染的贿赂考虑人数范围实际上是 (n - 1) 人，这与下一位船长之后的人数相同，在这些人里面，如果染染少贿赂一个，那么说明下一位船长就多贿赂了一个，对下一位船长来说这个结果一定不优。
再仔细复盘一下，其实这个和两个人的博弈是类似的，两个人的博弈，会存在一个必胜态和必败态的转化，每个人的行为都是为了让自己获胜，那在这个题里面，对于每一个人单独分析，也就存在一个杀掉船长后，自己是获利还是亏损，也就是题目说的“更大的利益”，要不要杀当前的船长，自然也就出来了，并且对于每一个船长，为了保全自己，也就是题目说的“保证自己不被杀死”，自然也就会选择最优选择，那么杀掉染染之后的分金币情况也就出来了。
红温记录：
点击查看代码（省略了逆元）
void solve() { int n;cin >> n; int sum = n / 2; int ans = 0; if(n & 1)n --; ans = (n + n - (sum - 1) * 2) % M * sum % M * inv(2); cout << (ans % M + M) % M << 'n'; } 1005 - 航线
很明显的dijkstra求最短路，博弈论做不出来的时候十分钟就出思路了，但是！！被卡map了...有亿点点无语啊啊啊！！！
做这个题需要明确一点，dijkstra的本质是数据结构优化DP，因此状态很重要，每一个点的四个方向作为dijkstra每个点的四种状态！然后用dijkstra进行转向和移动就行，具体看代码吧，一看就懂，但是被卡map真的很难受啊啊啊啊QWQ，以后能开数组绝不用map了。
点击查看代码
struct Node { int x, y, t, di; bool operator < (const Node &v) const { return t > v.t; } }; int n, m; bool inmp(int x, int y) { return x >= 1 && x <= n && y >= 1 && y <= m; } int dijk(vector<vector<int>> &t, vector<vector<int>> &d) { priority_queue<Node> pq; vector<vector<vector<int>>> vis(n + 2, vector<vector<int>>(m + 2, vector<int>(4, 0))); pq.push({1, 1, t[1][1], 1}); while(pq.size()) { auto [x, y, pret, predi] = pq.top(); pq.pop(); if(x == n && y == m && predi == 0) { return pret; } if(vis[x][y][predi])continue; vis[x][y][predi] = true; pq.push({x, y, pret + d[x][y], (predi + 1) % 4}); pq.push({x, y, pret + d[x][y], (predi + 2) % 4}); pq.push({x, y, pret + d[x][y], (predi + 3) % 4}); if(predi == 0 && inmp(x + 1, y)) { pq.push({x + 1, y, pret + t[x + 1][y], predi}); } if(predi == 1 && inmp(x, y + 1)) { pq.push({x, y + 1, pret + t[x][y + 1], predi}); } if(predi == 2 && inmp(x - 1, y)) { pq.push({x - 1, y, pret + t[x - 1][y], predi}); } if(predi == 3 && inmp(x, y - 1)) { pq.push({x, y - 1, pret + t[x][y - 1], predi}); } } } void solve() { cin >> n >> m; vector<vector<int> > t(n + 2, vector<int>(m + 2, 0)), d(n + 2, vector<int>(m + 2, 0)); for(int i = 1;i <= n;i ++) { for(int j = 1;j <= m;j ++) { cin >> t[i][j]; } } for(int i = 1;i <= n;i ++) { for(int j = 1;j <= m;j ++) { cin >> d[i][j]; } } cout << dijk(t, d) << 'n'; } 
![洛谷 P11345 [KTSC 2023 R2] 基地简化 题解](http://www.itfaba.com/wp-content/themes/kemi/timthumb.php?src=http://www.itfaba.com/wp-content/themes/kemi/img/random/2.jpg&w=218&h=124&zc=1)
