https://codeforces.com/contest/1172

A. Nauuo and Cards

 

题意：有n张数字1到n的牌，和n张0牌，手里有n张，队列里有n张，每次操作从手里选一张放进队列尾部，再从队首拿出一张。问最少操作几次使得队列里牌从1到n升序。

模拟

只有当后部分已经从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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const ll mod = 998244353;
int n;
int a[N], b[N], p[N], vis[N];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
	for (int i = 1; i <= n; i++)scanf("%d", &b[i]), p[b[i]] = i;
	int st = 1, flg = 1, cnt = 1, mx = 0;
	for (int i = p[1]; i <= n; i++, cnt++) {
		if (b[i] != cnt) { flg = 0; break; }
	}
	if (flg) {
		for (int i = 1; i <= n; i++)if (b[i] >= cnt) {
			if (i > b[i] - cnt) { flg = 0; break; }
		}
	}
	if (flg)st = cnt;
	for (int i = 1; i <= n; i++) {
		if (b[i] >= st) {
			mx = max(mx, i - p[st] - b[i] + st);
		}
	}
	printf("%d\n", p[st] + n - st + 1 + mx);
	return 0;
}

 

B. Nauuo and Circle

 

题意：一个圈上有n个空格要填入1到n，已知1到n的连边关系是棵树，问有几种填法，使得填入后没有边在非端点处交叉。

组合数学

一个子树一定占用一整块地方，否则连边会交叉。

所以先确定根，再给子节点分配位置，递归下去。

注意还要先确定哪个节点作为根。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const ll mod = 998244353;
int n;
vector<int>G[N];
ll fac[N];
int main() {
	scanf("%d", &n);
	fac[0] = 1;
	for (int i = 1; i <= n; i++)fac[i] = fac[i - 1] * i%mod;
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	ll ans = n * fac[(int)G[1].size()] % mod;
	for (int i = 2; i <= n; i++)ans = ans * fac[(int)G[i].size()] % mod;
	printf("%lld\n", ans);
	return 0;
}

 

C1. Nauuo and Pictures (easy version)

 

题意：有n个照片，每个照片有个喜爱度w，被选的概率为 wi∑j=1nwj\frac{w_i}{\sum_{j=1}^nw_j}，每张照片可能是0或者1，选中0就把它的喜爱度-1，选中1就+1，问选m轮后每张照片的喜爱度期望值。

dp

对每张照片分别考虑，dp[i][j][k]dp[i][j][k] 表示到第 ii 轮，它被选中 jj 次，它的同类被选中 kk 次的概率。

三种转移，第 ii 轮选它，选同类，不选同类。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const ll mod = 998244353;
ll Pow(ll a, ll b) {
	ll res = 1;
	while (b) {
		if (b & 1)res = res * a%mod;
		a = a * a%mod;
		b >>= 1;
	}
	return res;
}
ll inv(ll x) { return Pow(x, mod - 2); }
int n, m, t[N], ad[]{ -1,1 };
ll sum[N], a[N], dp[60][60][60];
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)scanf("%d", &t[i]);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
		sum[t[i]] += a[i];
	}
	for (int p = 1; p <= n; p++) {
		memset(dp, 0, sizeof(dp));
		dp[0][0][0] = 1;
		int ty = t[p], nty = t[p] ^ 1;
		for (int i = 1; i <= m; i++) {
			for (int j = 0; j <= i; j++) {
				for (int k = j; k <= i; k++) {
					if (j > 0) {
						ll s = sum[0] + sum[1] + ad[ty] * (k - 1) + ad[nty] * (i - k);
						ll my = a[p] + ad[ty] * (j - 1);
						dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - 1][k - 1] * max(0ll, my) % mod*inv(s) % mod) % mod;
					}
					if (k > j) {
						ll s = sum[0] + sum[1] + ad[ty] * (k - 1) + ad[nty] * (i - k);
						ll my = a[p] + ad[ty] * j;
						ll mty = sum[ty] + ad[ty] * (k - 1);
						dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k - 1] * max(0ll, mty - my) % mod*inv(s) % mod) % mod;
					}
					if (k < i) {
						ll s = sum[0] + sum[1] + ad[ty] * k + ad[nty] * (i - k - 1);
						ll mty = sum[ty] + ad[ty] * k;
						dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k] * max(0ll, s - mty) % mod*inv(s) % mod) % mod;
					}
				}
			}
		}
		ll ans = 0;
		for (int j = 0; j <= m; j++) {
			ll tmp = 0;
			for (int k = j; k <= m; k++)tmp = (tmp + dp[m][j][k]) % mod;
			if (t[p] == 1)ans = (ans + (a[p] + j)*tmp%mod) % mod;
			else ans = (ans + (a[p] - j + mod)*tmp%mod) % mod;
		}
		printf("%lld\n", ans);
	}
	return 0;
}