https://codeforces.com/contest/1369

C. RationalLee

 

题意：有n个数，m个人，每个人分 w[i]w[i] 个数，每个人的值为他所拿数的最大值和最小值之和，要求所有人的值之和最大，求该和。

贪心

所有数的最小值一定是某人的最小值，然后要考虑最大化其它最小值，所以要隔尽量多的位置取下一个最小值，同时还要保证最大值最大，所以最大值一定要是所有数里最大的m个。

虽然看上去隔 w[i]w[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
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int N = 3e5 + 10;
int T;
int n, m;
int w[N];
ll a[N];
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n; i++)scanf("%lld", &a[i]);
		for (int i = 1; i <= m; i++)scanf("%d", &w[i]);
		sort(a + 1, a + n + 1);
		sort(w + 1, w + m + 1, greater<int>());
		ll ans = 0;
		int p = 1;
		for (int i = 1; i <= m && w[i] > 1; i++) {
			ans += a[p];
			p = p + w[i] - 1;
		}
		int cnt = 0;
		for (int i = 1; i <= m; i++)if (w[i] == 1)cnt++;
		for (int i = 0; i < cnt; i++)ans += a[n - i];
		for (int i = n; i >= n - m + 1; i--)ans += a[i];
		printf("%lld\n", ans);
	}
	return 0;
}

 

D. TediousLee

 

题意：leivel i 由 level i-1 的图形叶节点生长一个儿子，有一个儿子的节点生长2个儿子，得到。多次询问，问一个level的图上有几个不相交的爪形。

爪形

level 1, 2 and 3

找规律

level 4

level 5

可以看到level 5由2个level 3和1个level 4拼成，再看其他的也是这样。

level i 由2个 level i-2 和1个 level i-1 拼出。

并且这几个部分是不会有公共部分的，除了在最顶端的一个爪形。

在i=3时取顶端的爪，所以i=4和i=5时都不能取顶端的爪，如果非要取，下面的部分必定会少1，所以不取。

i=6由i=4和5拼成，由于4，5都不取顶端的爪，所以i=6时多出了一个顶端的爪要取。

所以还有个规律就是当 i 是 3 的倍数时，会多出一个爪。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 2e6 + 10;
int T;
int n;
ll c[N];
int main() {
	for (int i = 3; i < N; i++)c[i] = (c[i - 1] + 2 * c[i - 2] + 4 * (i % 3 == 0)) % mod;
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		printf("%lld\n", c[n]);
	}
	return 0;
}

 

E. DeadLee

 

题意：有n种食物，每种有 w[i]w[i] 个，有m个人，每人有2种不同的喜欢吃的食物，要求把所有人排序，按照顺序吃，每人吃自己喜欢吃的且每种吃1个（没有就不吃），问能否使每个人至少吃1个。

考虑如果某一种食物足够多，那么喜欢这种食物的人排最后，因为他们一定可以吃到东西，并且以后就不需要考虑他们了。

这样足够多的食物一定是存在的。假设现在已经排好了，那么排在最后的那个人，一定在每种食物的选择权上都是最后，所以如果每种食物都要抢的话，他一定吃不到任何一种。

不仅仅是初始时这样，在任何时间都必须要求至少一种食物足够多，否则gg。

由于不考虑的人不会再影响结果，所以不考虑的人越多越好，并且选择足够多的食物的顺序也没关系，所以这样安排最优。

所以可以向求拓扑序一样求了，先把所有足够多的食物压入队列，取出一种，把所有喜欢它的人压入stack（因为最后要倒序取答案），再把这些人从其它食物里删掉，同时判断是否有新的食物足够多。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 2e5 + 10;
int n, m;
int w[N];
set<int>st[N];
queue<int>q;
stack<int>ans;
int vis[N], cle[N], x[N], y[N];
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)scanf("%d", &w[i]);
	for (int i = 1; i <= m; i++) {
		scanf("%d%d", &x[i], &y[i]);
		st[x[i]].insert(i);
		st[y[i]].insert(i);
	}
	for (int i = 1; i <= n; i++) {
		if ((int)st[i].size() <= w[i])q.push(i), cle[i] = 1;
	}
	while (!q.empty()) {
		int t = q.front(); q.pop();
		for (int u : st[t]) {
			if (!vis[u]) {
				vis[u] = 1;
				ans.push(u);
				if (!cle[x[u]]) {
					st[x[u]].erase(u);
					if((int)st[x[u]].size()<=w[x[u]])q.push(x[u]), cle[x[u]] = 1;
				}
				if (!cle[y[u]]) {
					st[y[u]].erase(u);
					if ((int)st[y[u]].size() <= w[y[u]])q.push(y[u]), cle[y[u]] = 1;
				}
			}
		}
	}
	for (int i = 1; i <= m; i++)if (!vis[i]) { puts("DEAD"); return 0; }
	puts("ALIVE");
	while (!ans.empty()) {
		printf("%d ", ans.top());
		ans.pop();
	}
	return 0;
}

 

F. BareLee

 

题意：有n轮游戏，每轮游戏给定一个s和t，一次操作可以把s乘2或加1，两个人轮流操作，如果操作后s大于t了，则输。上一轮游戏输了的一方在这一轮先手，问第一轮先手的人能否在最后一轮必胜或必败。

博弈+dfs

如果能知道每一轮先手能否必胜/必败，则一定可以由最后一轮推到第一轮，所以关键在于要根据s和t求出一轮的先手能否必胜/必败。

如果 t 为奇数，则若 s 为奇数先手无法必胜，若s为偶数，则先手可以必胜。这是因为若只能+1，则面对偶数的必胜。而若先手为偶数，则后手不论怎么操作，得到的都是偶数，所以始终保持先手为偶数，先手只要+1即可。

如果 t 为偶数，则当 s 大于t/2时，需要s为奇数。当s大于t/4时，先手必胜。因为先手可以乘2，使得后手面对大于t/2的偶数，则后手必败。当s小于t/4时，相当于s不变，t变为t/4。因为先使得s大于t/4的人就可以利用前面那条规则。

如果s大于t/2，先手可以必败，否则相当于询问s不变，t为t/2时先手能否必胜。因为先达到大于t/2的人就可以利用前面的规则。

注意非必胜不一定必败，因为如果要追求败，则对面也会调整策略。

也可以sg函数找规律，从t开始向1分log段，每次除2为一段，可以发现一段里的sg是类似的。但是写的时候要分类的太多了，一下午也写不完。。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 2e5 + 10;
int n;
ll s[N], t[N];
bool can[N][2];
int ck(int x) {
	for (int i = n; i > 1; i--) {
		if (can[i][x])x = 0;
		else x = 1;
	}
	return can[1][x];
}
bool dfs(ll s, ll t) {
	if (t & 1) {
		if (s & 1)return false;
		else return true;
	}
	else {
		if (s > t / 2) {
			if (s & 1)return true;
			else return false;
		}
		else if (s > t / 4 && s <= t / 2)return true;
		else return dfs(s, t / 4);
	}
}
bool dfs2(ll s, ll t) {
	if (s > t / 2)return true;
	else return dfs(s, t / 2);
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%lld%lld", &s[i], &t[i]);
	for (int i = 1; i <= n; i++) {
		can[i][1] = dfs(s[i], t[i]);
		can[i][0] = dfs2(s[i], t[i]);
	}
	printf("%d %d\n", ck(1), ck(0));
	return 0;
}