成都市网站建设_网站建设公司_导航菜单_seo优化

CSP-S 第二轮算法比赛已于昨日结束；下面分享我的题解。

第一题，难度为普及+/提高，后悔贪心，难度还好，即使不会可以得到 70 分。

第二题，难度为提高+/省选−，剪枝或者多路合并，会卡住不少人，不过被卡了可以得 80 分。

第三题，难度为省选/NOI−，哈希与 AC 自动机会简单一些，暴力可以得 80 分。

第四题，难度为省选/NOI−，三维动态规划，难度非常大，属于 noi 级别的题目了，暴力只能得 28 分。

这样看来，不会高端算法，暴力可以得70+80+80+28=258分。

PS1：我觉得第四条应该有 NOI 级别黑题了，毕竟三维动态规划，还涉及到排列组合，太复杂了。

PS2：后面我会基于这次比赛的题型，来展开介绍最小生成树、字符串、动态规划等相关算法专题。

一、社团招新（club）

题意：我们学校的算法协会招募了n名新成员，其中n是一个偶数。

现在需要将这些新成员分配到协会的三个部门中。

每个新成员对这三个部门都有一个满意度得分。

我们的目标是找到一个分配方案，使得所有成员的满意度之和最大。

但是，分配有一个限制条件：任何一个部门分配到的新成员数量都不能超过n/2。

简而言之，就是要在限制每个部门人数不超过总人数一半的前提下，最大化总满意度。

最优解：后悔贪心

思路1：动态规划

状态定义：dp[i][j][k]表示前i名新成员中，分配到部门 1 的人数为j、分配到部门 2 的人数为k时的最大满意度（注意部门 3 的人数为i - j - k）。

状态转移方程：第 i 个人枚举分配到哪个部门（下面用 j,k 表示部门 1/2 的人数，c 表示部门 3）：

// 假设 c = i - j - k dp[i][j][k] = -INF; // 或者初始化为 -1 表示不可达 // 选择 A（部门1） if (j > 0 && dp[i - 1][j - 1][k] != -1) { dp[i][j][k] = max(dp[i - 1][j - 1][k] + a1, dp[i][j][k]); } // 选择 B（部门2） if (k > 0 && dp[i - 1][j][k - 1] != -1) { dp[i][j][k] = max(dp[i - 1][j][k - 1] + a2, dp[i][j][k]); } // 选择 C（部门3） int c = i - j - k; if (c > 0 && dp[i - 1][j][k] != -1) { dp[i][j][k] = max(dp[i - 1][j][k] + a3, dp[i][j][k]); }

答案：枚举所有情况，求最大值。

for (int a = 0; a <= n; a++) { for (int b = 0; b <= n; b++) { ans = max(ans, dp[n][a][b]); } }

复杂度：O(n^3)

得分：55 分

特殊性质 A：a2 和 a3 全为 0

思路：在这种情况下只需从 a1 中选择最大的 n/2 个，其余分配为 0

得分：60 分

// 特殊性质 A: a2 和 a3 全为 0 if (sum2 == 0 && sum3 == 0) { // a1 中选择最大的 n/2 个，其他选 0 sort(a.begin(), a.end(), greater<tuple<ll, ll, ll>>()); ll ans = 0; for (int i = 0; i < n / 2; i++) { ans += get<0>(a[i]); } printf("%lld\n", ans); }

特殊性质 C：独立均匀随机生成

思路：当样本是独立均匀随机生成时，直接对每个人选择三项中的最大值（不考虑 n/2 限制）通常能取得较好结果。

得分：70 分

// 特殊性质 C：贪心选择 ll ans = 0; for (auto& [a1, a2, a3] : a) { ans += max(a1, max(a2, a3)); } printf("%lld\n", ans);

最优解：后悔贪心

根据容忍与鸽巢原理，可以得到几个性质。

性质1：最多有一个部门的人数超过n/2（若两部门都超过n/2，则两者之和 > n，矛盾）。

性质2：如果将某个超过n/2的部门通过调整（按最小代价把多余成员转出）降到n/2，则调整结束后不会让其他部门超过n/2（因为总人数固定为n）。

根据上面的两个性质，可以先贪心，再反悔贪心。

贪心：不考虑n/2限制，贪心选择最大值。

反悔：对于超过n/2的部门，选择一些人反悔选择这个部门，改为选择其他部门（选择哪个不重要，根据性质2其他部门不会超过限制）。

所以这里就需要决策哪些人反悔。

定义反悔代价：假设一个人当前部门的满意度是 a1（贪心的最大值），另外两个部门的满意度是 a2 和 a3，那么反悔代价就是a1 - max(a2, a3)。

显然，需要选择反悔代价最小的那些人，直到该部门人数不超过n/2。

复杂度：O(n log(n))

得分：100 分

vector<ll> g[3]; // g[0].push_back(a1 - max(a2, a3)); // 输入与贪心选择，代码省略 // 后悔贪心, 找到超过 n/2 的部门 i int sz = g[i].size(); sort(g[i].begin(), g[i].end()); for (int j = 0; j < sz - n / 2; j++) { ans -= g[i][j]; }

二、道路修复（road）

题意：我们有一个由N个城市和M条双向道路构成的交通系统。

最初，所有M条道路都已损坏，修复第i条道路的费用是w_i。

此外，还有K个乡镇可以进行城市化改造。对第j个乡镇进行城市化改造的费用是c_j。

改造后，可以在该乡镇和原有的N个城市之间修建道路，乡镇j到城市i的修建费用是a_{j,i}。

我们的目标是：选择任意多个乡镇进行城市化改造（可以选择0个）。

修复一些原有道路，并修建一些新的乡镇-城市道路。

最终使得原有的N个城市两两连通。

求出达成这一目标的最小总费用（乡镇改造费 + 道路修复/新建费）。

最优解：最小生成树+剪枝

思路1：暴力枚举

暴力枚举所有乡镇的选择方案，合并所有边，排序，最后求最小生成树。

关于如何枚举所有子集，请关注博客。

const int MASK = (1 << k) - 1; for (int sub = MASK; sub; sub = (sub - 1) & MASK) { townSelectEdges = baseEdges; ll subCost = 0; int selectNum = 0; for (int i = 0; i < k; i++) { if ((sub >> i) & 1) { selectNum++; // 选择第 i 个乡镇 s