https://codeforces.com/contest/1158

A. The Party and Sweets

 

题意：n个男生，m个女生，每个男生送每个女生礼物，给出每个男生送出的礼物的最小价值和每个女生的收到的礼物的最大价值。问所有男生花的钱之和最少是多少。

贪心

让价值最高的男生送所有女生她们收到的最贵的礼物，其他男生只送最便宜的。

但是也不能让最高的男生送所有，因为可能他的最小值就不对了，所以如果不对了就让第二个男生送最小的女生。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;
int n, m;
int a[N], b[N];
ll sum, ans;
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
	for (int i = 1; i <= m; i++)scanf("%d", &b[i]), sum += b[i];
	sort(a + 1, a + n + 1, greater<int>());
	sort(b + 1, b + m + 1);
	if (b[1] < a[1]) { puts("-1"); return 0; }
	ans += sum - b[1] + a[1];
	if (b[1] != a[1])ans += 1ll * a[2] * (m - 1) + b[1];
	else ans += 1ll * a[2] * m;
	for (int i = 3; i <= n; i++)ans += 1ll * m*a[i];
	printf("%lld\n", ans);
	return 0;
}

 

B. The minimal unique substring

 

题意：如果一个子串只出现一次，它是奇特的子串，要求构造一个长为n的01串，使得最短的奇特的子串长度为k。

以(n-k)/2+1为周期，打印000···01.

这样就会有两个完整周期，和k个可能不完整的字符。

那么最小的奇特字串一定是以第一个周期末尾那个1开头的，因为只有它有足够的1，不可能重复，并且由于有2个完整的周期，所以再小的子串一定有重复。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;
int n, k;
int main() {
	scanf("%d%d", &n, &k);
	int a = (n - k) / 2;
	for (int i = 1; i <= n; i++)printf("%c", i % (a + 1) == 0 ? '1' : '0');
	puts("");
	return 0;
}

 

C. Permutation recovery

 

题意：有一个排列，给出每个位置后面第一个大于它的数的下标，如果没有，就是n+1，也有可能遗失了，就是-1。要求构造出排列。

线段树优化建图+拓扑排序

i+1到后面第一个大于它的数下标之间的数都小于p[i+1]，所以连边，拓扑排序之后按照顺序构造，但是由于区间连边，时间不够。

区间连边可以用线段树优化，线段树中每个节点先和它的父节点连边。当要区间连边时直接和查询一样分成几个小区间，和他们的父节点连边。

注意记录下标在线段树中的位置，每次都是以线段树中节点连边。

最终一定只有叶节点会没有入度，这些也是代表一个下标的点，正常求拓扑序，注意只有在节点是叶节点时才赋值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5e5 + 10;
const int INF = 0x3f3f3f3f;
int T, n, nx;
#define mid ((l+r)>>1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
int id[N], rid[N<<2];
int ind[N<<2], ans[N];
queue<int>q;
vector<int>G[N<<2];
void build(int l, int r, int rt) {
	if (l == r) {
		id[l] = rt, rid[rt] = l;
		return;
	}
	G[rt << 1].push_back(rt); ind[rt]++;
	G[rt << 1 | 1].push_back(rt); ind[rt]++;
	build(lson); build(rson);
}
void upda(int ql, int qr, int l, int r, int rt, int v) {
	if (ql > qr)return;
	if (ql <= l && qr >= r) {
		G[rt].push_back(v); ind[v]++;
		return;
	}
	if (ql <= mid)upda(ql, qr, lson, v);
	if (qr > mid)upda(ql, qr, rson, v);
}
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		while (!q.empty())q.pop();
		for (int i = 0; i <= (n << 2); i++)G[i].clear();
		fill(ind, ind + (n << 2) + 1, 0);
		fill(rid, rid + (n << 2) + 1, 0);
		build(1, n, 1);
		for (int i = 1; i <= n; i++) {
			scanf("%d", &nx);
			if (nx == -1)continue;
			upda(i + 1, nx - 1, 1, n, 1, id[i]);
			if (nx <= n)G[id[i]].push_back(id[nx]), ind[id[nx]]++;
		}
		for (int i = 1; i <= n; i++) {
			if (!ind[id[i]])q.push(id[i]);
		}
		int cnt = 0;
		while (!q.empty()) {
			int u = q.front(); q.pop();
			if (rid[u])ans[rid[u]] = ++cnt;
			for (int v : G[u]) {
				if (--ind[v] == 0)q.push(v);
			}
		}
		if (cnt != n)puts("-1");
		else {
			for (int i = 1; i <= n; i++)printf("%d%c", ans[i], " \n"[i == n]);
		}
	}
	return 0;
}