ACM下学期第六次周赛

A.疑似最小生成树

这是一道带权最小生成树模型加上贪心策略的题

1. 基础数学逻辑：排序不等式

题目要求我们从图里选出条边（至少条以保证连通），排列成一个序列，并使得总代价最小：

根据经典的排序不等式（或者常识），如果我们手头已经选定了一组边，要让它们除以之后的总和最小，我们必须把权重越小的边放在越前面（即让它除以较小的）。

结论 1：无论我们最终选了哪几条边，它们在计算代价时，必然是按照权重从小到大升序排列的。

2. 连通性保底：最小生成树 (MST)

题目有一个硬性要求：“能使个点联通”。

要把个点连起来，最少需要条边。为了让这必须付出的“保底代价”最小，我们毫无疑问应该使用Kruskal 算法挑出权重最小的条边，构成一棵最小生成树。

结论 2：最小生成树的这条边，是我们构建最终答案的基础班底。其他的边属于“备胎”。

3. 核心突破口：为什么要“多此一举”加边？

既然条边已经能连通图了，题目为什么允许（即可以选多于条边）？加入一条没用的“废边”（甚至会构成环）怎么可能让总代价更小呢？

这就是这道题最精妙的地方！我们来看一个数学推演：

假设我们已经有了一个升序排列的边集序列（比如初始的最小生成树边集），现在我们要强行往里面插入一条原本没被选上的新边，其权重为。

为了保持升序排列，这条边会被插入到第个位置。

• 损失：这会增加一项新的代价。

• 收益：原来排在第个位置及以后的所有边，它们的排名统统往后退了一位（分母从变成了）。也就是说，后面所有边产生的代价变成了，它们变小了！

只要“后面所有边代价变小的总和” > “新增加的代价”，整个大盘的总代价就会下降！

4. 完整的解题算法流程

基于上述推演，我们可以得出最优解的求解流程：

1. 全局排序：把图中所有的边按权重从小到大排序。

2. 构建基底：跑一遍最小生成树算法。

   • 被选中的条边放入集合Tree。

   • 没被选中的边放入集合NonTree（并且天然也是升序的）。

3. 计算初始代价：计算当前集合Tree的总代价。

4. 贪心尝试：按权重从小到大遍历NonTree里的“备胎边”。对于每一条备胎边：

   • 将它插入到Tree集合中（保持升序）。

   • 重新计算加入这条边之后的新总代价。

   • 如果：说明白嫖到了分母变大的红利，保留这条边，更新，继续尝试下一条备胎边。

   • 如果：说明这条边自身权重太大，插入位置太靠后，带来的收益弥补不了它本身的代价。此时立刻停止尝试（因为NonTree后面的边权重更大，插入位置更靠后，绝对不可能再产生正收益了）。

5. 输出结果：将最终收敛的四舍五入即可。

一句话总结：

先求最小生成树拿底薪，然后尝试把没用的边从小到大“塞”进树边序列里去稀释后面大权重边的代价，直到塞入新边的副作用大于稀释带来的收益为止。

#include <bits/stdc++.h> #define int long long using namespace std; struct Edge { // 定义边的类型 int u, v, w; }; vector<int> parent; // 并查集，用于Kruskal判断连通性 int find(int x) { return x == parent[x] ? x : parent[x] = find(parent[x]); // 路径压缩查找根节点 } // 计算当前边集产生的总代价 // 注意传参用了引用 vector<Edge>& use，避免拷贝开销 double price(vector<Edge>& use) { int i = 1; double all = 0; for (auto& [u, v, w] : use) { all += 1.0 * w / i; // 公式：w_i / i i++; } return all; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n, m; cin >> n >> m; vector<Edge> graph(m); for (auto& [u, v, w] : graph) { cin >> u >> v >> w; } // 1. 将所有边按照权重升序排序 sort(graph.begin(), graph.end(), [](const Edge& a, const Edge& b) { return a.w < b.w; }); parent.assign(n + 1, 0); for (int i = 0; i <= n; i++) parent[i] = i; vector<Edge> use, unuse; // 2. Kruskal 算法求最小生成树 for (auto& [u, v, w] : graph) { int ru = find(u), rv = find(v); if (ru != rv) { // 连通两个分离的集合，将边加入最小生成树 parent[ru] = rv; use.push_back({u, v, w}); } else { // 如果已经在同一个集合，说明构成了环，不属于最小生成树的边 unuse.push_back({u, v, w}); } } // 计算仅仅使用最小生成树的基础代价 double ans = price(use); // 自定义 lower_bound 的比较函数：根据权重 w 查找第一个 >= k 的位置 auto cmp = [](const Edge& p, int k) { return p.w < k; }; // 3. 贪心尝试插入非树边（unuse已经是升序的了，从小到大尝试） for (auto& [u, v, w] : unuse) { // 利用二分查找，在 use 数组中找到这条新边应该插入的位置，保持升序 auto it = lower_bound(use.begin(), use.end(), w, cmp); if (it != use.end()) { use.insert(it, {u, v, w}); // 插入该边 double s = price(use); // 重新计算代价 if (s < ans) { // 如果插入后总代价变小了，赚了！更新答案，这属于有效的冗余边 ans = s; } else { // 如果代价变大了，说明当前边的自身权重过大，导致惩罚 > 收益 // 因为 unuse 是升序的，后面的边只会更大，绝对不可能更优，直接退出循环！ break; } } else { // 如果找不到 >= w 的位置（说明它比目前所有边都大，加在最后面）， // 加在最后面分母最大，且无法移动任何现有的边，纯纯的增加代价，直接结束。 break; } } // 题目要求四舍五入到整数 // double 转 int 是向零取整，加上 0.5 就可以巧妙实现四舍五入 cout << (int)(ans + 0.5) << "\n"; return 0; }

B.整理漫画

本题为一道签到题

题中说真寻搜集了各种漫画书，然后给每个书按照位置依次赋予编号，有的时候真寻会把书借出去，借出去的位置就会被空下来，当书被还回来时就按照从小到大的顺序给放上。

题目指出，书架上漫画书位置的范围为(0-1e9)且严格递增，我们正常遍历一遍肯定是会TLE的，但是我们注意到，由于有n本书且位置严格递增，第一个空位一定出现在[0, n]范围内。因为如果前n个位置(0到n-1)全部被占，那么第n个位置就是第一个空位；如果前n个位置中有空缺，那么第一个空位一定≤n-1。因此我们只需要检查到n即可，而n≤1000，所以不会超时。

#include<bits/stdc++.h> #define int long long using namespace std; signed main(){ int n;cin>>n; for (int i=0;i<1000;i++) { int k;cin>>k; if (k!=i) { cout<<i; return 0; } } cout<<n; return 0; }

C.亏本买卖

本题是一个模拟题

真寻在玩一个运营游戏，初始的余额为0，让你求经过n个环节之后还剩多少余额。

题中已经告诉我们每个环节的余额变化公式x+X-(x+X)/K（向下取整），我们看下数据范围，n的范围最大为1e18，所以纯模拟肯定会TLE。这时我们可能会想着去推数学公式，用O(1)的时间去解，可是当我们将x代入上一次x进行嵌套，会发现是一个等比数列求和。推出公式之后进行计算，发现与答案不符，我们再次读题，发现公式是向下取整，如果我们用公式求的话，会忽略掉每一步向下取整带来的误差。模拟也不行，公式法也不行，这个时候我们就得需要通过打表看数据了，我们将每一个环节x的变化输出，我们可以发现，在经历若干次操作后，x将不再变化，所以我们只需要模拟每一个环节，直到上一个环节的x等于下一个环节的x时就退出循环，直接输出答案。

#include<bits/stdc++.h> #define int long long using namespace std; signed main(){ int n,X,K;cin>>n>>X>>K; int x=0; while(n--){ int cmp=x; x=x+X-(x+X)/K; if(cmp==x)break; } if(x-X>0)cout<<'+'; cout<<x-X; }

D.阶乘之和？乘之和？之和？和？？

本题也是一道模拟题

给你一个整数n，让你求阶乘求和的项数。看到题目，你可能想到直接模拟进行求和，可是你会发现就算是O(n)的模拟也是会TLE，可能你会想有没有公式解？发现也没有，那么我们再读一下题，发现题目让我们对10000取模，你说这对10000取模有说法吗？显然有，要不通过打表看一下？我们打表之后会发现当阶乘到20左右，后面的数都为0了所以，我们只需要跑到20就可以退出模拟了。为什么？其实也很好想，每当我们对偶数数乘5或者任意数乘10，他们都会使当前位变成0，比如14*5=70，个位就变为0了，此后阶乘个位就一直是0，根据这个我们可以推出到第20位，阶乘的末尾4位将全是0，此后末尾4位也都将是0，对10000取余，必然也是0了。

#include<bits/stdc++.h> using namespace std; const int mod=10000; int main(){ int ans=0; int n;cin>>n; int num=1; for(int i=1;i<=n;i++){ num=(i*num)%mod; ans=(ans+num)%mod; if(i>19)break; } cout<<ans; }

E.糖果博弈

本题是一道博弈论（Nim博弈变体）的题

题目大意

• 桌上有堆糖果，第堆有颗糖果。

• 两人轮流操作（真寻先手）。每次操作，玩家可以选择至少一个糖果数为偶数的堆，将选中的每一堆均分为两堆（即如果一堆有个，就变成两堆个）。

• 当所有堆的糖果数都变为奇数时，无法再进行任何操作，当前玩家输。

• 判断在双方都采取最优策略下，谁会获胜。

核心分析与博弈转化

1. 拆解单堆糖果的“寿命”

任何一个正整数都可以唯一地写成的形式，其中是一个奇数，是包含的质因子 2 的个数（即连续除以 2 直到变成奇数的次数）。

由于每次操作是把一个偶数堆均分成两个，这就意味着：

• 如果 $k$ 是偶数，它依然可以继续被均分。

• 如果 $k$ 变成了奇数，这两堆就永远不能再被操作了。

因此，一堆糖果能够被操作的“总次数”是完全固定的，就是它包含的质因子 2 的个数。而且每次操作，由于是把一堆变成两堆，实际上是将其中一个变成了两个。如果我们只关注“还能除以多少次 2”这个属性，操作前是，操作后变成了两个。

2. 转换为 Nim 博弈模型

这看起来很像可以进行多次分割的游戏，但注意题目中的关键规则：“每次操作时，玩家需要选择至少一个……的堆”。

这意味着，你可以同时操作多个堆！

我们可以找到判定方法：

只要存在任何一堆糖果，其（质因子 2 的个数）为奇数，则先手（Mahiro）必胜；如果所有堆的均为偶数，则后手（Momiji）必胜。

为什么会是这样呢？

我们可以把每一堆的看作是该堆的“石子数”。

• 当为偶数时，它是后手的“安全状态”。

• 当为奇数时，它是先手的“必胜机会”。

因为题目允许同时选择多个堆进行操作：

• 如果存在某个堆的为奇数：先手总可以通过只操作这些为奇数的堆，把它们的都减 1（变成偶数）。这样就把一个所有堆的都为偶数的局面留给了后手。

• 如果当前所有堆的都是偶数：无论后手怎么操作，由于他必须选择至少一堆，操作后被选中的堆的都会减 1 变成奇数。也就是说，后手无可奈何地一定会把一个“存在奇数”的局面留给先手。

这就构成了标准的奇偶性必胜策略：

• 必胜态（非平衡态）：存在至少一堆的为奇数。此时先手可以通过操作所有为奇数的堆，将其全部变为偶数，从而把必败态留给对方。

• 必败态（平衡态）：所有堆的都是偶数。此时无论怎么操作，都会至少把一堆的变成奇数，从而把必胜态留给对方。

因此，游戏胜负完全取决于：是否存在一堆糖果，它连续除以 2 的次数为奇数。如果存在，真寻（Mahiro）胜；如果不存在（即全为偶数次），小椛（Momiji）胜。

#include<bits/stdc++.h> using namespace std; void solve(){ int n; cin >> n; bool mahiro_win = false; for(int i = 0; i < n; i++){ int a; cin >> a; int cnt = 0; // 计算当前这堆糖果最多能除以多少次 2（即质因子 2 的个数） while(a % 2 == 0 && a){ a /= 2; cnt++; } // 只要存在任意一堆的 cnt 是奇数，先手就可以通过一次操作掌控全局 if(cnt % 2 != 0){ mahiro_win = true; // 注意：这里由于只需要判断是否存在， // 实际上直接输出 "Mahiro" 并 return 即可。 } } if(mahiro_win) { cout << "Mahiro"; } else { cout << "Momiji"; } } int main() { ios::sync_with_stdio(false); // 建议加上快读优化 cin.tie(nullptr); int t = 1; while(t--){ solve(); } return 0; }