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

热门相关:神秘总裁小小妻   重生成偏执霍少的小仙女   精灵掌门人   我成了暴戾帝君的小娇包   重生之嫡女祸妃