牛客小白月赛119
赛时成绩如下(最近打的比较好的一次)：
A. 来！选！队！长
你选择了 5 个角色组成小队，TA们的战力按照降序排列分别是 a1,a2,a3,a4,a5。而你的好友也用 5 个角色组了一个小队，TA们的战力按照降序排列分别是 b1,b2,b3,b4,b5。一个小队的总实力，等于队长战力的两倍，加上其余四个队员的战力之和。
你的好友是个萌新，TA打算从五个角色中随机取出一个当队长。你想知道，你是否存在一种选队长的方案，使得你的小队总实力有可能严格大于你的好友。
解题思路：
题目中说有可能严格大于, 见下面代码
#include <bits/stdc++.h>
using namespace std;
void solve() {vector<int> a(5), b(5);int sum_a = 0, sum_b = 0;for (int i = 0; i < 5; i++) {cin >> a[i];sum_a += a[i];}for (int i = 0; i < 5; i++) {cin >> b[i];sum_b += b[i];}int a_max_num = *max_element(a.begin(), a.end());int b_min_num = *min_element(b.begin(), b.end());if (a_max_num + sum_a > b_min_num + sum_b)cout << "YES" << '\n';elsecout << "NO" << '\n';
}
int main() {int t = 1;while (t--) {solve();}
}B. 抽我选的效率曲
多人游戏由五个玩家组成，现在假设游戏内存在 1000 首歌曲，它们的代号分别是 [1,1000] 之间的整数。现在五个玩家分别进行了决定，它们分别选择了代号为 a1,a2,a3,a4,a5 的歌曲。特别地，如果 ai=0 代表第 i 个玩家决定放弃选歌。
在每个人作出决定之后，如果至少有一人有选歌，系统会随机从有选歌的玩家中等概率抽取一位，以 TA 挑选的歌曲进行游玩；而如果所有人都放弃选歌，系统就会从 1000 首歌中等概率随机抽取一首歌进行游玩。
现在，给定整数 k，请问系统最终抽出代号为 k 的歌曲的概率是多少？请用最简分数表示。
特殊地，如果概率是 0，那么请输出 0/1；如果概率是 1，那么请输出 1/1。
解题思路：统计5个人选中代号的为k的歌曲的个数, 如果ai=0, 那么就随机从1000首选, 选中的概率为1/1000
#include <bits/stdc++.h>
using namespace std;
void solve() {vector<int> a(5);int k;for (int i = 0; i < 5; i++) {cin >> a[i];}cin >> k;int cnt = 0;int cnt_1 = 0;for (int x : a) {if (x != 0) {cnt++;if (x == k)cnt_1++;}}if (cnt == 0) {cout << "1/1000" << '\n'; return;}if (cnt_1 == 0) {cout << "0/1" << '\n'; return;}if (cnt_1 == cnt) {cout << "1/1" << '\n'; return;}int g = gcd(cnt_1, cnt);cout << (cnt_1 / g) << "/" << (cnt / g) << '\n';
}
int main() {int t;cin >> t;while (t--) {solve();}return 0;
}C. 睡前床边看LIVE
一共有 n 个豆腐人，每个豆腐人都染上了一个颜色。它们能看见其它 n−1 个豆腐人的颜色，但是无法知道自己是什么颜色。现在你对每个豆腐人都问了相同的问题：“在你看见的这 n−1 个豆腐人中，最多有多少个豆腐人，它们的颜色是一样的？”每个豆腐人都向你回答了一个整数。
请问，你是否能根据以上的信息，判断出一定有豆腐人说谎了？补充说明：在本题中，一定有豆腐人说谎了，等价于不存在任何一种染色方案使得每个豆腐人的回答与实际相符。
解题思路：
先进行排序, 如果数组a中最小值比最大值至少小2, 就输出“Lie”
这是因为所有豆腐人看到的其他颜色的频率最多相差1，取决于自己的颜色是否属于最大频率的颜色
eg: 4 4 4 5 5 5 5/4 4 4 5 5 5 5 5 => 站在4的角度为4/5，站在5的角度为3/4
最多不会相差1
然后统计最大值和次大值,
设最大频率的颜色为A，频率为m。那么：
1.如果一个豆腐人自己是颜色A，那么它看到的其他颜色A的频率是m-1
2.如果一个豆腐人自己不是颜色A，那么它看到的其他颜色A的频率是m
情况 1：cnt_1 == 0（所有回答都是 m）:
这意味着所有豆腐人看到的 m 个同色豆腐人，说明：
要么所有豆腐人颜色相同（此时 m = n-1，因为自己看不到自己）
要么 m 足够小，使得即使某些豆腐人不是 A，也能看到 m 个 A（即 n >= 2 * m）
情况 2：cnt_1 > 0（存在回答 m - 1）：
这些回答必须来自 A 颜色的豆腐人（因为它们看到 m-1 个 A）
所以 A 颜色的豆腐人数量 = cnt_1（因为每个 A 颜色的豆腐人都回答 m-1）
但 A 颜色的实际数量是 m（因为 m 是 m）
所以必须 cnt_1 == m
#include <bits/stdc++.h>
using namespace std;
void solve() {int n;cin >> n;vector<int> a(n);for (int i = 0; i < n; i++) {cin >> a[i];}sort(a.begin(), a.end());if (a[0] < a[n - 1] - 1) {cout << "Lie" << '\n';return;}int cnt = 0, cnt_1 = 0;for (int x : a) {if (x == a[n - 1])cnt++;if (x == a[n - 1] - 1)cnt_1++;}bool f = false;if (cnt_1 == 0) {if (n == a[n - 1] + 1 || n >= 2 * a[n - 1]) {f = true;}} else {if (cnt_1 == a[n - 1]) {f = true;}}if (f)cout << "Other" << '\n';elsecout << "Lie" << '\n';
}int main() {int t;cin >> t;while (t--) {solve();}return 0;
}D.世界树上找米库
一共有 n个地点，它们由 n−1 条长度为 1 的双向道路连成了一棵无根树结构。其中，如果一个地点只延伸出了一条道路，那么这个地点将称为 Sekai 点。
Miku 点的定义如下：Miku 点一定不是 Sekai 点。
Miku 点是符合上一个条件的所有地点中，与相距最近的 Sekai 点距离最大的点。根据以上信息，请你找出所有的 Miku 点吧！
解题思路：
构建邻接表并记录每个节点的度数。
将所有 Sekai 点（度数为 1 的叶子节点）作为多源，执行 BFS，计算每个节点到最近 Sekai 点的最短距离 dist[i]。
在所有非 Sekai 点（度数 > 1）中，找到距离最近 Sekai 点距离的最大值 md，所有满足 dist[i] == md 的节点就是 Miku 点。
输出它们的数量和从小到大的编号。
#include <bits/stdc++.h>
using namespace std;
void solve() {int n;cin >> n;vector<vector<int>> g(n + 1);vector<int> d(n + 1, 0);for (int i = 1; i < n; i++) {int u, v;cin >> u >> v;g[u].push_back(v);g[v].push_back(u);d[u]++;d[v]++;}queue<int> q;vector<int> dt(n + 1, -1);for (int i = 1; i <= n; i++) {if (d[i] == 1) {dt[i] = 0;q.push(i);}}while (!q.empty()) {int u = q.front();q.pop();for (int v : g[u]) {if (dt[v] == -1) {dt[v] = dt[u] + 1;q.push(v);}}}int max_num = 0;for (int i = 1; i <= n; i++) {if (d[i] > 1) {max_num = max(max_num, dt[i]);}}vector<int> ans;for (int i = 1; i <= n; i++) {if (d[i] > 1 && dt[i] == max_num) {ans.push_back(i);}}int ans_n = ans.size();cout << ans_n << endl;for (int x : ans)cout << x << " ";cout << '\n';
}
int main() {int t;cin >> t;while (t--) {solve();}return 0;
}E, 森友会里打音游
你的背包有 n 个物件，现在你按顺序依次将它们放在了草坪上，从左到右第 i 个物品的大小为 ai。
现在你可以移除一些物件（也允许不移除），请问你最多可以保留多少个物件，使得剩下的物件中，对于任意相邻的两个物件，二者大小均有整除关系？（如果只剩一个物件默认符合条件）
在此，我们称两个正整数 a,b 有「整除关系」，当且仅当 a∣b 或 b∣a 成立，即 a 是 b 的约数或 a 是 b 的倍数。
解题思路：
DP 数组定义：
dp[x] 表示以数值 x 结尾的最长符合条件的序列的长度
初始化时，dp 数组的所有元素都为 0，因为还没有处理任何物件
动态规划更新：
遍历每个物件 x：
1：找到 x 的所有约数（包括 x 本身），并计算这些约数对应的 dp 值的最大值 k
对于每个约数 i（i 是 x 的约数），更新 k = max(k, dp[i])
同时，检查 x / i 是否也是约数（避免重复计算），如果是，也更新 k
2：找到 x 的所有倍数（不超过 max_num），并计算这些倍数对应的 dp 值的最大值 k。
对于 x 的倍数 m（m = x, 2x, 3x, ..., <= max_num），更新 k = max(k, dp[m])。
步骤 3：更新 dp[x] 为 k + 1（因为当前物件 x 可以接在最长序列的后面）
步骤 4：更新全局最大值 ans，记录当前的最长序列长度
#include <bits/stdc++.h>
using namespace std;
void solve() {int n;cin >> n;vector<int> a(n);for (int i = 0; i < n; i++) {cin >> a[i];}int max_num = *max_element(a.begin(), a.end());vector<int> dp(max_num + 1, 0);int ans = 1;for (int x : a) {int k = 0;for (int i = 1; i * i <= x; i++) {if (x % i == 0) {k = max(k, dp[i]);int j = x / i;if (j != i) {k = max(k, dp[j]);}}}for (int m = x; m <= max_num; m += x) {k = max(k, dp[m]);}dp[x] = max(dp[x], k + 1);ans = max(ans, k + 1);}cout << ans << '\n';
}
int main() {int t;cin >> t;while (t--) {solve();}return 0;
}F. 这招太狠了烤学妹
你找出了朋友的一个长度为 n 的音游打击序列，为了简化模型，这个序列只有 o（命中）和 x（不命中）。
下面定义音游打击序列每个位置的当前连击数：
有一个累加器，初始值设为 0。
将序列从左到右依次扫描，对于当前某个字符，若它是 o\text{o}o，那么累加器加 111，否则累加器重置为 0。
序列每个位置的当前连击数，等于扫描过这个位置后累加器的值。
例如，对于音游打击序列 oooxoo，每个位置的当前连击数依次是 1,2,3,0,1,2。整个音游打击序列的分数，等于打击序列每个位置的当前连击数之和。例如，对于音游打击序列 oooxoo，分数等于 1+2+3+0+1+2=9。
现在你有 k 次动手脚的机会，每次机会可以将这个打击序列的一个 o 修改为 x。k 次机会可以全部使用、部分使用或完全不使用。你想知道所有修改方案中，分数的最小值可以是多少。
解题思路：
对于一段连续的o, 在中间进行x一次是最优的
对于一个极长连续 o 段，我们想通过修改 k 处让分数最小，那么分割出来的若干段长度要尽可能平均。
证明：
假设切出的两个连续 o 段，长度均为 a；此时把修改的地方往相邻处移动一格，切出的两段长度就变为 a−1,a+1。
那么两种情况的分数分别为 a2+a和 a2−a+a2+3a+2/2=a2+a+1，显然前者更小。
相似的情况同样可以计算得知，长度尽量靠近时分数更小，这里就不写了。
所以我们可以定义一个函数 F(i,j) 表示把一个长度为 i 的连续 o 段修改 j 处得到的最小分数。
定义 s(x)=x(x+1)/2，即一个长度为 x 的连续 o 段的分数。
那么 F(i,j) 相当于有 j 处被抹掉了，要把剩余的 i−j 处切成 j+1 段，且尽可能切得均匀。
设 k=⌊i−jj+1⌋, r=(i−j)−(j+1)k, p=(j+1)−r。三个量 k,r,p 分别代表切割出的最小段的长度、切出长度为 k+1 的段数量、切出长度为 k 的段数量。
那么 F(i,j)=p×s(k)+r×s(k+1)。
对于一般的情况，我们会出现多个连续 o 段。我们可以设计一个贪心的策略，希望每多切一刀，答案就会减少得尽可能多。那我们要怎么切呢？
一个很常见的误区就是每次选一段，切成均等的两半。这是不对的，原因可以看上面的结论。假设你可以切两刀，最优的分割方案是三等分，而不是对半后再在某一段对半。
所以对于初始情况的每个极长连续 o 段，我们假设记录它初始长度 L，当前已经被切的次数 kkk。那么对于这被切了 k 次的段，多给你一次切一刀的机会，带来的减少量是 F(L,k)−F(L,k+1)。这是一个反悔贪心式的操作，将补偿量作为更换方案的指标。
如果让你选择多个原始连续段的其中一个切，你需要挑出减少量最大的一个原始段。切完以后，把当前的减少量更新为 F(L,k+1)−F(L,k+2)，然后在这些原始段内重新选减少量最大的段，进行下一次切割。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll get(int len, int k) {ll ans = 0;int block = (len - k) / (k + 1);int lft = len - k - (k + 1) * block;int cnt = k + 1 - lft;ans = 1ll * block * (block + 1) / 2 * cnt + 1ll * (block + 1) * (block + 2) / 2 * lft;return ans;
}void solve() {int n, k;cin >> n >> k;string s;cin >> s;s = " " + s;ll ans = 0;priority_queue<array<ll, 3>> q;int cnt = 0;for (int i = 1; i <= n; i++) {if (s[i] == 'o') {cnt++;}else {if (cnt) {ans += 1ll * cnt * (cnt + 1) / 2;q.push({get(cnt, 0) - get(cnt, 1), cnt, 0});}cnt = 0;}}if (cnt) {ans += 1ll * cnt * (cnt + 1) / 2;q.push({get(cnt, 0) - get(cnt, 1), cnt, 0});}while (k-- && q.size()) {auto [v, len, k] = q.top();q.pop();ans -= v;k++;if (k + 1 <= len) {q.push({get(len, k) - get(len, k + 1), len, k});}}cout << ans << endl;
}int main() {int t = 1;cin >> t;while (t--) solve();return 0;
}
感谢大家的点赞和关注，你们的支持是我创作的动力！