http://codeforces.com/contest/1209

B. Koala and Lights

 

题意：n个灯，从第b[i]秒开始变，周期为a[i]，问最多有几个灯同时亮。

数字不大，直接枚举时间，周期很小。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int n;
int a[N], b[N], c[110][1010];
char s[N];
int main() {
	scanf("%d", &n);
	scanf("%s", s + 1);
	for (int i = 1; i <= n; i++)scanf("%d%d", &a[i], &b[i]);
	int ans = 0;
	for (int t = 0; t < 1000; t++) {
		int tmp = 0;
		for (int i = 1; i <= n; i++) {
			if (t < b[i])tmp += (s[i] - '0'), c[i][t] = (s[i] - '0');
			else {
				c[i][t] = c[i][max(0, t - a[i])] ^ 1;
				tmp += c[i][t];
			}
		}
		ans = max(ans, tmp);
	}
	printf("%d\n", ans);
	return 0;
}

 

C. Paint the Digits

 

题意：给定一串数字，要求分成两个序列，再拼起来后非递减。

单调栈

一个数字前面如果有比它大的数字，那么这两个数字一定不能在一个序列里，且大的那个一定在第二个序列，小的那个一定在第一个序列。

单调栈维护非递减序列，作为第一个序列，同时要保证单调栈里的数不大于第二个序列的最小值，这样保证了第一个序列不能再加了，再判断第二个序列是否合法。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int T;
int n;
char s[N];
typedef pair<int, int>pii;
pii S[N]; int top, c[N];
vector<pii>vc;
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		scanf("%s", s + 1);
		top = 0; vc.clear();
		int mn = INF;
		for (int i = 1; i <= n; i++) {
			if (s[i] - '0' > mn) {
				vc.push_back(pii(s[i] - '0', i));
				mn = min(mn, s[i] - '0');
				continue;
			}
			while (top&&S[top].first > (s[i] - '0'))
				vc.push_back(S[top]), mn = min(mn, S[top--].first);
			S[++top] = pii(s[i] - '0', i);
		}
		bool ok = 1;
		fill(c + 1, c + n + 1, 1);
		sort(vc.begin(), vc.end());
		for (int i = 0; i < (int)vc.size(); i++) {
			if (i > 0 && vc[i].second < vc[i - 1].second) { ok = 0; break; }
			c[vc[i].second] = 2;
		}
		if (!ok)puts("-");
		else {
			for (int i = 1; i <= n; i++)printf("%d", c[i]);
			puts("");
		}
	}
	return 0;
}

 

D. Cow and Snacks

 

题意：n个人，每人有两个要的食物，每种食物只有一个，每个人会贪心地拿走他要的两种食物，问怎么安排顺序使得一个食物都没有的人数最少。

最大流啊，但是复杂度不够。

生成树

把食物作为点，一个人连接两个点，不同连通分量之间无关，对于一个连通分量，可以构造出最优顺序，使得有东西吃的人数为点数-1：先随便挑一条边，吃两个，再bfs出去，每次吃一个，由于每个点只能被吃一次，所以这一定是最优解。

也就是连通分量的生成树边数，那么没东西吃的人数就是连通分量里非树边的边数，并查集维护即可。

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 N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int par[N];
void init(int n) { for (int i = 0; i <= n; i++)par[i] = i; }
int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
void uni(int x, int y) { par[find(x)] = find(y); }
int n, m, ans;
int main() {
	scanf("%d%d", &n, &m);
	init(n);
	while (m--) {
		int u, v;
		scanf("%d%d", &u, &v);
		if (find(u) == find(v))ans++;
		else uni(u, v);
	}
	printf("%d\n", ans);
	return 0;
}