https://codeforces.com/contest/1363

C. Game On Leaves

 

题意：给定一棵树和一个目标节点，两个人轮流操作，每次选一个叶子拿掉，先拿掉目标节点的赢。

以目标节点为根，拿完只剩一条链的肯定输了，所以都是拿长链或者拿完还有边的节点。最后剩下目标节点和另一个节点。拿掉的个数只与结点数有关。所以判断节点数奇偶。

一直读错题了，以为拿完一条链就能拿目标节点了，实际是要变成叶子才能拿，搞成了尼姆游戏。。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 10;
int T;
int main() {
	scanf("%d", &T);
	while (T--) {
		int n, x, d = 0;
		scanf("%d%d", &n, &x);
		for (int i = 1; i < n; i++) {
			int u, v;
			scanf("%d%d", &u, &v);
			if (u == x || v == x)d++;
		}
		if (d <= 1)puts("Ayush");
		else {
			if (n & 1)puts("Ashish");
			else puts("Ayush");
		}
	}
	return 0;
}

 

D. Guess The Maximums

 

题意：交互题，有一个长度n的数组，给定k个不相交的下标集，对每个集合猜出不在集合里的最大的数。每次询问一个任意的自己构造的下标集，可以得到集合里的数的最大值。询问次数最大为log。

看到询问次数应该就能猜出二分。

由于这k个集合不相交，所以数组中最大的数必定最多在一个集合里，那么对于其他的集合，不在集合里的最大的数就是数组的最大值。而对于包含最大值的那个集合，直接询问它的结果。

所以只要求出数组的最大值即可。

就类似线段树那样二分，先问整个集合，得到最大值大小，再问左区间，如果左区间最大值等于整个区间最大值，就说明在左区间里，否则右区间。保证了询问次数卡在一个log。

如果数组有两个最大值也是一样的。只要找到一个最大值就好了。

注意清空，还有大写的Correct！！

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 INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 10;
int T;
vector<int>vc[N];
int ans[N], nt[1010];
string s;
int main() {
	cin >> T;
	while (T--) {
		int n, k;
		cin >> n >> k;
		for (int i = 1; i <= k; i++) {
			vc[i].clear();
			int m, x;
			cin >> m;
			for (int j = 0; j < m; j++) {
				cin >> x;
				vc[i].push_back(x);
			}
		}
		int mx;
		cout << "? " << n;
		for (int i = 1; i <= n; i++)cout << ' ' << i;
		cout << endl;
		cin >> mx;
		int L = 1, R = n, tmp;
		while (L < R) {
			int mid = (L + R) / 2;
			cout << "? " << mid - L + 1;
			for (int i = L; i <= mid; i++)cout << ' ' << i;
			cout << endl;
			cin >> tmp;
			if (tmp == mx)R = mid;
			else L = mid + 1;
		}
		for (int i = 1; i <= k; i++) {
			bool ys = 0;
			for (int j : vc[i]) {
				if (j == L) { ys = 1; break; }
			}
			if (ys) {
				cout << "? " << n - (int)vc[i].size();
				memset(nt, 0, sizeof(nt));
				for (int j : vc[i])nt[j] = 1;
				for (int j = 1; j <= n; j++)if (!nt[j])cout << ' ' << j;
				cout << endl;
				cin >> ans[i];
			}
			else {
				ans[i] = mx;
			}
		}
		cout << "!";
		for (int i = 1; i <= k; i++)cout << ' ' << ans[i];
		cout << endl;
		cin >> s;
		if (s[0] != 'C')return 0;
	}
	return 0;
}

 

E. Tree Shuffling

 

题意：给定一棵树，每个节点为0或1，且每个节点有权值，每次操作选一个节点u，从它的子树里选一些节点重排01，花费为选的结点数*u的权值，要求最终每个点的01值都为规定的值。求最小花费。

贪心

选择一个点u，再选一些子树里的点，则选的每个点的花费都是u的权值。所以只要贪心地选择最便宜的节点，把它子树里所有不符合规定的节点都处理完。

但是u的子树处理完后可能会有剩下的没有配对的节点，这些节点只能留给它的祖先们处理了，所以要通知祖先们u的子树的变化。但也不能直接遍历通知，否则复杂度不够，所以要在选到节点u时，向下dfs统计不符合规定的结点数。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 10;
int n;
ll a[N], ans;
int b[N], c[N], fa[N], die[N], cnt[N][2];
typedef pair<ll, int>pii;
vector<pii>vc;
int st[N], to[N << 1], nx[N << 1], tot;
inline void add(int u, int v) { to[++tot] = v, nx[tot] = st[u], st[u] = tot; }
void dfs(int u, int _fa) {
	fa[u] = _fa;
	if (b[u] == 0 && c[u] == 1)cnt[u][0] = 1;
	if (b[u] == 1 && c[u] == 0)cnt[u][1] = 1;
	for (int i = st[u]; i; i = nx[i]) {
		int v = to[i];
		if (v == _fa)continue;
		dfs(v, u);
		cnt[u][0] += cnt[v][0];
		cnt[u][1] += cnt[v][1];
	}
}
int del(int u) {
	if (die[u])return min(cnt[u][0], cnt[u][1]);
	int ans = 0;
	die[u] = 1;
	for (int i = st[u]; i; i = nx[i]) {
		int v = to[i];
		if (v != fa[u])ans += del(v);
	}
	return ans;
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld%d%d", &a[i], &b[i], &c[i]);
		vc.push_back(pii(a[i], i));
	}
	sort(vc.begin(), vc.end());
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		add(u, v);
		add(v, u);
	}
	dfs(1, 0);
	if (cnt[1][0] != cnt[1][1]) { puts("-1"); return 0; }
	for (pii p : vc) {
		if (die[p.second])continue;
		int u = p.second;
		int tmp = min(cnt[u][0], cnt[u][1]);
		ans += 2 * (tmp - del(u)) * p.first;
	}
	printf("%lld\n", ans);
	return 0;
}

 

F. Rotating Substrings

 

题意：给定字符串s，t，每次操作选s的一个子串，把子串的结尾移到子串开头，要使得s=t，问最少操作次数。

dp

可以看成每次从末尾拿一个，插到前面，使得开头等于t，并逐渐扩大相等的部分。每次从末尾选的字符可以放在任意位置，所以可以先存着，等需要时再放。

dp[i][j]dp[i][j] 表示用 s[i+1⋯n]s[i+1\cdots n] 中的某些字符插入 s[1⋯i]s[1\cdots i]，凑出 t[1⋯j]t[1\cdots j] ，的最少操作次数。

三种转移

最基本的是把 s[i]s[i] 存起来，变成用 s[i⋯n]s[i\cdots n] 插入 s[1⋯i−1]s[1\cdots i-1]，凑出 t[1⋯j]t[1\cdots j]。

第二种，如果 s[i]=t[j]s[i]=t[j]，则只要凑出 s[1⋯i−1]=t[1⋯j−1]s[1\cdots i-1]=t[1\cdots j-1]。

第三种，把之前存的放到 s[i+1]s[i+1]，使得 s[i+1]=t[j]s[i+1]=t[j]，则只要再凑出 s[1⋯i]=t[1⋯j−1]s[1\cdots i]=t[1\cdots j-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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 10;
int T;
char s[N], t[N];
int cnt[30], dp[2020][2020], ts[N][30], ss[N][30];
bool ck() {
	memset(cnt, 0, sizeof(cnt));
	for (int i = 1; s[i]; i++)cnt[s[i] - 'a']++;
	for (int i = 1; t[i]; i++)cnt[t[i] - 'a']--;
	for (int i = 0; i < 26; i++)if (cnt[i] != 0)return false;
	return true;
}
int main() {
	scanf("%d", &T);
	while (T--) {
		int n;
		scanf("%d", &n);
		scanf("%s%s", s + 1, t + 1);
		if (!ck()) { puts("-1"); continue; }
		memset(ss[n + 1], 0, sizeof(ss[n + 1]));
		memset(ts[n + 1], 0, sizeof(ts[n + 1]));
		for (int i = n; i >= 1; i--) {
			memcpy(ss[i], ss[i + 1], sizeof(ss[i]));
			memcpy(ts[i], ts[i + 1], sizeof(ts[i]));
			ss[i][s[i] - 'a']++;
			ts[i][t[i] - 'a']++;
		}
		for (int i = 1; i <= n; i++) {
			for (int j = i; j <= n; j++) {
				dp[i][j] = dp[i - 1][j] + 1;
				if (s[i] == t[j])
					dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
				if (ss[i + 1][t[j] - 'a'] > ts[j + 1][t[j] - 'a'])
					dp[i][j] = min(dp[i][j], dp[i][j - 1]);
			}
		}
		printf("%d\n", dp[n][n]);
	}
	return 0;
}