2023“钉耙编程”中国大学生算法设计超级联赛（4）
1003 Simple Set Problem
题意：
分别从k个集合中选一个元素组成一个数组\((a_1, a_2, a_3,..., a_k)\)，求max\((a_1, a_2, a_3,..., a_k)\) - min\((a_1, a_2, a_3,..., a_k)\)的最小值。
分析：
我们给每个集合中的元素添加一个id标识它属于哪个集合，然后将所有集合合并并按数值大小从小到大排序，这样问题就转化成：找一个最小区间，该区间满足每个id都至少出现一次，求这些最小区间右端点的值减去左端点的值的最小值是多少？显然可以用双指针来做，用st数组维护[i, j]不同id的出现次数，cnt统计区间[i, j]内的id种类数，当st[x]从0到非0时cnt++，st[x]从非0到0时cnt--，我们在cnt等于k时维护答案。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 4e6 + 5;
struct Node {
LL a;
int id;
}q[N];
bool cmp(Node &A, Node &B) {
if (A.a != B.a)
return A.a < B.a;
else
return A.id < B.id;
}
int st[N];
signed main() {
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --) {
int k, m = 0;
cin >> k;
for (int i = 1; i <= k; i ++)
st[i] = 0;
for (int i = 1; i <= k; i ++) {
int n;
cin >> n;
for (int j = 0; j < n; j ++) {
LL num;
cin >> num;
q[++ m] = {num, i};
}
}
sort(q + 1, q + m + 1, cmp);
LL res = 2e18;
int cnt = 0;
for (int i = 1, j = 1; i <= m; i ++) {
while (j <= m && cnt < k) {
if (st[q[j].id] == 0)
cnt ++;
st[q[j].id] ++;
j ++;
}
if ((j > m && cnt != k) || res == 0) {
break;
}
if (cnt == k) {
res = min(res, q[j - 1].a - q[i].a);
}
st[q[i].id] --;
if (st[q[i].id] == 0) {
cnt --;
}
}
cout << res << "\n";
}
}
代码：
1006 PSO
题意：
n个点，其中一个点是leader，其余点与leader之间连有边，leader负责收集和传递信息给其他点。问任意两个点交换信息所需的边数的期望和最大值是多少。
分析：
①当n = 2时，期望和最大值都是1
②当n > 2时：
边数可取1或者2，期望为\(\frac{2}{n} + \frac{2(n - 1)}{C_n^2} = \frac{2n - 2}{n}\), 最大值为2。
代码：
#include <bits/stdc++.h>
using namespace std;
int main() {
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --) {
int n;
cin >> n;
if (n == 2) {
cout << fixed << setprecision(9) << 1.0 << " " << 1.0 << "\n";
} else {
cout << fixed << setprecision(9) << 1.0 * (2 * n - 2) / n << " " << 2.0 << "\n";
}
}
return 0;
}
1011 Circuit
题意：
求有向图（无重边，自环）的最小环长度以及数量
分析：
对于有向图，如果a, b之间存在最小环，可以发现最小环就是a->b的最短路径加上b指向a的边。由于数据范围不大，因此求最短路可以考虑用实现上更简单的floyd来做，这样最小环便也可以求出来。现在讨论如何不重不漏的求出最小环的数量。我们注意floyd的状态定义：d[i][j]表示i到j经过 <= k的点的最短路，因此我们可以用环上的最大点以及最大点出边指向的点（确定方向）来标识一个环，在做完每一轮floyd之后枚举所有小于等于k的点来更新最小环长度以及最小环的个数，这样我们便能不重不漏地得到最小环的数量。
顺便总结一下最小环的内容：
1.有向图：
最小环即a指向b的边加上b到a的最短路径。
（1）djikstra（删边法）:
枚举每一条边(a, b)，断开a到b的边（实际上是d[a][b]赋为正无穷），求a->b的最短路dist，dist加上a与b的边权即为通过边(a, b)的最小环长度。
int dijkstra(int a, int b) {
memset(dist, 0x3f, sizeof dist);
d[a] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, a});
while (heap.size()) {
auto t = heap.top();
heap.pop();
int ver = t.second, dist = t.first;
if (dist >= ans) //剪枝优化
break;
if (st[ver]) continue;
st[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if (d[j] > dist + w[i])
{
d[j] = dist + w[i];
heap.push({d[j], j});
}
}
}
}
（2）floyd:也就是本题解法。
void floyd() {
for (int k = 1; k <= n; k ++) {
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= n; j ++) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
for (int i = 1; i < k; i ++) {
ans = min(ans, g[i][k] + d[k][i]);
}
}
}
2.无向图：
在无向图中，最小环至少应当包含3个顶点。也就是说，将无向边拆分为两条有向边，以此形成的2顶点环，不能视作最小环。
（1）dijkstra（删边法）
对于（a, b），把a指向b和b指向a的边都删掉，由于a到b的最短路无法通过a到b，因此必须经过第三个点，因此d[a][b] + w即为求出来的最小环。代码与上面类似。
（2）floyd：
当最外层恰好循环到k时，代表着目前所求出的最短路所含的点集为[1, k)。在第k次循环的内层循环刚开始时，如果存在边(a, k)和(k, b)，由于a到b的最短路必然不会经过k，所以这两条边加上最短路径便可形成一个最小环，且至少包含a, b, k三个点，符合定义。
void floyd() {
for (int k = 1; k <= n; k ++) {
for (int i = 1; i < k; i ++) {
for (int j = i + 1; j < k; j ++) {
ans = min(ans, g[i][k] + g[k][j] + d[j][i]);
}
}
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= n; j ++) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
}
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 510, mod = 998244353;
LL g[N][N], d[N][N], cnt[N][N];
int n, m;
LL ans1, ans2;
void init() {
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= n; j ++) {
if (i == j) {
g[i][j] = d[i][j] = 0;
} else {
g[i][j] = d[i][j] = 2e18;
}
cnt[i][j] = 0;
}
}
}
void floyd() {
for (int k = 1; k <= n; k ++) {
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= n; j ++) {
if (d[i][j] > d[i][k] + d[k][j]) {
d[i][j] = d[i][k] + d[k][j];
cnt[i][j] = cnt[i][k] * cnt[k][j] % mod;
} else if (d[i][j] == d[i][k] + d[k][j]) {
cnt[i][j] = (cnt[i][j] + cnt[i][k] * cnt[k][j] % mod) % mod;
}
}
}
for (int i = 1; i < k; i ++) {
if (ans1 > g[k][i] + d[i][k]) { // k-i,i-k都行，统一方向即可
ans1 = g[k][i] + d[i][k];
ans2 = cnt[i][k];
} else if (ans1 == g[k][i] + d[i][k]) {
ans2 = (ans2 + cnt[i][k]) % mod;
}
}
}
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --) {
cin >> n >> m;
ans1 = 2e18, ans2 = 0;
init();
while (m --) {
int a, b, c;
cin >> a >> b >> c;
g[a][b] = d[a][b] = c;
cnt[a][b] = 1;
}
floyd();
if (ans1 == 2e18) {
cout << "-1 -1" << "\n";
} else {
cout << ans1 << " " << ans2 << "\n";
}
}
return 0;
}
1012 a-b Problem
题意:
有n个石头，每个石头有两种分数A和B。Alice如果拿了一块石头，她将获得该石头的A点分数，同理Bob将获得B点分数。他们都想让自己的总得分减去对方的总得分最大。Alice先手，问最后Alice的总得分减去Bob的总得分的值是多少？
分析：
不妨令Bob一开始拥有所有石头，那么问题就转化成了Alice从Bob那拿走石头，Bob留下石头不让Alice拿。对于Alice，她每拿走一块石头就会缩小A+B点分差，因此Alice一定会优先拿A+B最大的那块石头。对于Bob，为了避免Alice缩小分差，他一定会优先把A+B最大的那块石头留下。综上，可以将石头按照A+B的大小从大到小排序，然后轮流选取即可。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
struct Stone {
int a, b;
}s[N];
bool cmp(Stone &A, Stone &B) {
return A.a + A.b > B.a + B.b;
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --) {
int n;
cin >> n;
for (int i = 0; i < n; i ++) {
cin >> s[i].a >> s[i].b;
}
sort(s, s + n, cmp);
LL res1 = 0, res2 = 0;
for (int i = 0; i < n; i ++) {
if (i & 1) {
res2 += s[i].b;
} else {
res1 += s[i].a;
}
}
cout << res1 - res2 << "\n";
}
return 0;
}