C/C++每日一练5

1.游游的 you

题意

游游有a个y，b个o，c个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\)

贪心思路

1. 最多能凑出k = min(a,b,c)组you
   • 每组消耗 1 个 o，剩余 o 数量：rest_o = b - k
   • you 总分：k * 2
2. 剩下的rest_o全部连成一串，能得到rest_o - 1分；如果rest_o < 2，oo 得分为 0。 \(\text{oo得分} = \max(rest_o - 1,\ 0)\)
3. 总答案：\(ans = k\times2 + \max(b-k-1,\ 0)\)

⚠️ 数据极大，必须使用 long long！

C++ 完整代码

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; }

样例验证

输入：

plaintext

3 1 1 1 2 3 2 1 5 2

1. a=1,b=1,c=1\(k=1,\;rem=0,\;ans=2+0=\boldsymbol{2}\)
2. a=2,b=3,c=2\(k=2,\;rem=1,\;ans=4+0=\boldsymbol{4}\)
3. a=1,b=5,c=2\(k=1,\;rem=4,\;ans=2 + (4-1)=\boldsymbol{5}\)

输出和样例完全一致：

plaintext

2 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

1. 初始把所有腐烂苹果同时入队（多个起点一起扩散）
2. 逐层向外扩散，记录扩散耗时
3. 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; vector<vector<int>> g(n, vector<int>(m)); queue<Node> 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; }

关键点说明

1. 多源 BFS 不能用 DFS：DFS 会串行扩散，无法模拟 “同时腐烂”，结果错误。
2. 提前统计新鲜苹果总数，BFS 中每腐烂一个就减一，最后判断有无剩余。
3. 边界：没有新鲜苹果时答案为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, t+1)) 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; }

举个例子

n=5，m=3 序列：0,1,2,3,4

1. 淘汰 2
2. 淘汰 0
3. 淘汰 4
4. 淘汰 1 最后剩下 3 运行代码：输出 3 ✔

补充说明

1. 如果题目中人编号从1 开始，最后答案res + 1
2. 数据范围很大时（\(10^6\)）迭代写法完全没问题；递归不要用
3. 原理简单理解： 去掉一个人之后，把新环重新编号，逆推回原环坐标。