1.游游的 you题意游游有a个yb个oc个u。连续三个字符you→ 获得2 分每组消耗 1y、1o、1u连续两个字符oo→ 获得1 分注意ooo有两处相邻 oo得 2 分oooo得 3 分。也就是一段连续 k 个 o 能贡献k-1分。求最多能拿到多少分数。 数据范围 \(1\le q\le 10^5,\quad 1\le a,b,c\le 10^9\)贪心思路最多能凑出k min(a,b,c)组you每组消耗 1 个 o剩余 o 数量rest_o b - kyou 总分k * 2剩下的rest_o全部连成一串能得到rest_o - 1分如果rest_o 2oo 得分为 0。 \(\text{oo得分} \max(rest_o - 1,\ 0)\)总答案\(ans k\times2 \max(b-k-1,\ 0)\)⚠️ 数据极大必须使用 long longC 完整代码cpp运行#include iostream #include algorithm using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int q; cin q; while (q--) { ll a, b, c; cin a b c; ll k min({a, b, c}); ll ans k * 2; ll rem b - k; ans max(rem - 1, 0LL); cout ans \n; } return 0; }样例验证输入plaintext3 1 1 1 2 3 2 1 5 2a1,b1,c1\(k1,\;rem0,\;ans20\boldsymbol{2}\)a2,b3,c2\(k2,\;rem1,\;ans40\boldsymbol{4}\)a1,b5,c2\(k1,\;rem4,\;ans2 (4-1)\boldsymbol{5}\)输出和样例完全一致plaintext2 4 5补充说明很多人会疑惑能不能少凑几组 you腾出更多 o 拿更高 oo 分数 简单证明 一组 you 价值 2 分消耗 1 个 o 1 个 o 最多只能增加 1 分oo。 所以优先凑 you 永远最优不存在牺牲 you 换取更多 oo 的情况。2.腐烂的苹果多源 BFS 经典题题目大意有一个n × m的网格0空地1新鲜苹果2腐烂苹果每一分钟腐烂苹果会向上下左右四个方向扩散相邻新鲜苹果变成腐烂。 求全部苹果腐烂需要的最少时间 如果最后还有新鲜苹果无法腐烂输出-1。核心思路多源广度优先搜索 BFS初始把所有腐烂苹果同时入队多个起点一起扩散逐层向外扩散记录扩散耗时BFS 结束后遍历网格若仍存在新鲜苹果 →-1否则输出最大时间C 完整代码cpp运行#include iostream #include queue #include vector using namespace std; struct Node { int x, y, t; }; int dx[] {-1, 1, 0, 0}; int dy[] {0, 0, -1, 1}; int main() { int n, m; cin n m; vectorvectorint g(n, vectorint(m)); queueNode q; int apple 0; for (int i 0; i n; i) { for (int j 0; j m; j) { cin g[i][j]; if (g[i][j] 2) { q.push({i, j, 0}); } else if (g[i][j] 1) { apple; } } } int maxTime 0; while (!q.empty()) { auto cur q.front(); q.pop(); int x cur.x, y cur.y, t cur.t; maxTime max(maxTime, t); for (int d 0; d 4; d) { int nx x dx[d]; int ny y dy[d]; if (nx 0 nx n ny 0 ny m g[nx][ny] 1) { g[nx][ny] 2; apple--; q.push({nx, ny, t 1}); } } } if (apple 0) cout -1 endl; else cout maxTime endl; return 0; }关键点说明多源 BFS 不能用 DFSDFS 会串行扩散无法模拟 “同时腐烂”结果错误。提前统计新鲜苹果总数BFS 中每腐烂一个就减一最后判断有无剩余。边界没有新鲜苹果时答案为0。Python 版本python运行from collections import deque n, m map(int, input().split()) grid [] q deque() cnt 0 for i in range(n): row list(map(int, input().split())) grid.append(row) for j in range(m): if row[j] 2: q.append((i, j, 0)) elif row[j] 1: cnt 1 dirs [(-1,0),(1,0),(0,-1),(0,1)] res 0 while q: x, y, t q.popleft() res max(res, t) for dx, dy in dirs: nx x dx ny y dy if 0 nx n and 0 ny m and grid[nx][ny] 1: grid[nx][ny] 2 cnt - 1 q.append((nx, ny, t1)) print(res if cnt 0 else -1)3.孩子们的游戏圆圈中最后剩下的数经典约瑟夫环问题题目描述有0 ~ n-1共n个小朋友围成一圈。 从数字 0 开始报数报到m-1的小朋友出列下一个继续从 0 开始报数。 不断循环求最后剩下的小朋友编号。公式推导递推设 \(f(n)\) n 个人时最后存活的位置 递推公式\(f(1) 0\) \(f(n) (f(n-1)m) \bmod n\)C 代码迭代写法推荐无栈溢出cpp运行#include iostream using namespace std; int main() { int n, m; cin n m; int res 0; for(int i 2; i n; i) { res (res m) % i; } cout res endl; return 0; }递归版本便于理解n 很大会栈溢出cpp运行int f(int n, int m) { if(n 1) return 0; return (f(n-1,m) m) % n; }举个例子n5m3 序列0,1,2,3,4淘汰 2淘汰 0淘汰 4淘汰 1 最后剩下 3 运行代码输出 3 ✔补充说明如果题目中人编号从1 开始最后答案res 1数据范围很大时\(10^6\)迭代写法完全没问题递归不要用原理简单理解 去掉一个人之后把新环重新编号逆推回原环坐标。谢谢
