2022 CCPC Guangzhou Site

比赛地址 ：Codeforces Gym 104053

待补：ADFGJ

B - Ayano and sequences

数据结构题，胖胖补掉了。链接

*C - Customs Controls 2

给定一个 DAG ，保证所有点都能从 \(1\) 到达，且都能到达 \(n\) 。

要求给每个点分配一个点权，使得从 \(1\) 到 \(n\) 的所有路径经过的点权和相同。

定义 \(dis[u]\) 表示从 \(1\) 到 \(u\) 的距离，如果要符合最终要求，显然首先 \(dis[u]\) 的值要唯一。

考虑对于每个点 \(v\) ，图中存在 \(u\to v\) 的边，那么这样的 \(u\) 的 \(dis[u]\) 也必须相同。

并查集把这样的点缩点，重建图，因为点权是正的，因此如果图中存在环就无解。

否则按照从 \(1\) 开始的拓扑序设定 \(dis[u]\) 即可，\(v\) 的点权就是 \(dis[v] - dis[u]\) 的值（原图中存在 \(u\to v\) ）。

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define N 200007

struct DSU {
	int f[N];
	inline void reset(int x) {for (int i = 1; i <= x; ++i) f[i] = i;}
	int find(int x) {return x == f[x] ? x : f[x] = find(f[x]);}
	bool merge(int u, int v) {
		u = find(u); v = find(v);
		return (u == v ? false : (f[u] = v, true));
	} 
} dsu;

int deg[N], tag[N], val[N];

queue<int> q;

vector<int> in[N], out[N];

inline void work() {
	int n = rd(), m = rd();
	dsu.reset(n);
	for (int i = 1; i <= n; ++i) {deg[i] = 0; in[i].clear(); out[i].clear();}
	for (int i = 1; i <= m; ++i) {
		int u = rd(), v = rd(); in[v].push_back(u);
	}
	for (int u = 1; u <= n; ++u) 
		if (!in[u].empty()) {
			int sy = in[u][0];
			for (auto x : in[u]) dsu.merge(x, sy);
		}
	for (int u = 1; u <= n; ++u) {
		int U = dsu.find(u);
		for (auto v : in[u]) {
			int V = dsu.find(v);
			++deg[U]; out[V].push_back(U);
		}
	}
	int tot = 0, cnt = 0;
	for (int i = 1; i <= n; ++i)
		if (dsu.find(i) == i) {
			++tot;
			if (!deg[i]) q.push(i);
		}
	while (!q.empty()) {
		--tot;
		int u = q.front(); q.pop();
		tag[u] = ++cnt;
		for (auto v : out[u]) {
			--deg[v];
			if (!deg[v]) q.push(v);
		}
	}
	if (tot) {puts("No"); return;}
	puts("Yes");
	for (int i = 1; i <= n; ++i) 
		val[i] = tag[dsu.find(i)];
	for (int i = 1; i <= n; ++i) {
		int ans = val[i];
		if (!in[i].empty()) ans -= val[in[i][0]];
		if (i < n) printf("%d ", ans);
		else printf("%d\n", ans);
	}
}

int main() {
	for (int t = rd(); t; --t) work();
	return 0;
}

E - Elevator

签到题，逆序数。要把 \(x\) 前面的变成 \(> x\) ，后面的变成 \(\ge x\) 。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

vector<int> s, s1;

#define N 500007

int a[N], c[N];

#define lowbit(x) ((x) & -(x))

inline void add(int p) {
	for (; p < N; p += lowbit(p)) ++c[p];
}

inline int sum(int p) {
	int res = 0;
	for (; p; p -= lowbit(p)) res += c[p];
	return res;
}

ll presum[N];

int main() {
	int n = rd(), m = rd() - 2;
	for (int i = 1; i <= n; ++i) {
		a[i] = rd(); s.push_back(a[i]);
	}
	sort(s.begin(), s.end()); s1 = s;
	for (int i = 1; i <= n; ++i) presum[i] = presum[i - 1] + s1[i - 1];
	s.erase(unique(s.begin(), s.end()), s.end());
	auto calc = [&](int x) {
		return lower_bound(s.begin(), s.end(), x) - s.begin() + 1;
	};
	for (int i = 1; i <= n; ++i) {
		int nw = calc(a[i]);
		ll tot = sum(nw); add(nw);
		int p = lower_bound(s1.begin(), s1.end(), a[i]) - s1.begin() + 1;
		tot += 1ll * p * a[i] - presum[p];
		if (tot > m) puts("-1");
		else printf("%lld\n", tot);
	}
	return 0;
}

H - GameX

给定一个数集，双方轮流操作 \(k\) 轮，每个人往数集里加入一个非负整数。

先手想让最终数集 MEX 是偶数，后手想要是奇数，问最终结果。

先手想让最终结果是偶数，则必不会加入偶数，只加入奇数；同理后手只会加入偶数。

再注意到如果小的奇数还没加，加大的奇数是没用的，所以一定会从小到大加。模拟即可。

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;
typedef long long ll;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define N 2000007

bool vis[N];

int a[N];

vector<int> s;

inline void work() {
	s.clear();
	int n = rd(), k = rd();
	for (int i = 1; i <= n; ++i) {
		a[i] = rd(); vis[a[i]] = true;
	}
	int A = 1, B = 0;
	for (int i = 1; i <= k; ++i) {
		while (vis[A]) A += 2; vis[A] = true; s.push_back(A);
		while (vis[B]) B += 2; vis[B] = true; s.push_back(B);
	}
	int mx = 0;
	while (vis[mx]) ++mx;
	puts((mx & 1) ? "Bob" : "Alice");
	for (int i = 1; i <= n; ++i) vis[a[i]] =false;
	for (auto x : s) vis[x] = false;
}

int main() {
	for (int t = rd(); t; --t) work();
	return 0;
}

*I - Infection

给一棵树，每个点有 \(\frac{a_i}{\sum a_i}\) 的概率被选作根，然后被染黑。

若 \(u\) 父节点被染黑，则 \(u\) 被染黑的概率为 \(p_u = \frac{b_u}{c_u}\) ，问染黑 \(k=1,2,\dots, n\) 个点的概率模 \(10^9+7\) 。

考虑一个树上连通点集对答案的贡献： \[ contri_S = \sum_{root\in S}\bigg(\frac{a_{root}}{\sum a}\prod_{u\in S,u\ne root} p_u\prod_{(u,v)\in Tree, v\not\in S,u\in S}(1-p_v)\bigg) \] 设 \(F[i][j]\) 表示以 \(i\) 为根的点集中有 \(j\) 个点，且未选定初始感染点的贡献和。 \(G[i][j]\) 表示已选定初始感染点的贡献和。

树形背包转移，复杂度 \(\mathcal{O}(n^2)\) 。每个点把 \(G\) 数组贡献到答案中即可。树形背包实现还是很精细的...

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
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define N   2007
#define mod 1000000007

vector<int> e[N];

inline int fpow(int x, int t = mod - 2) {
	int res = 1;
	for (; t; t >>= 1, x = 1ll * x * x % mod)
		if (t & 1) res = 1ll * res * x % mod;
	return res;
}

// f[u][v] : choose j nodes in subtree u, without root
// g[u][v] : choose j nodes in subtree u, already choose a root

int a[N], p[N], sz[N], f[N][N], g[N][N], ans[N];

void dfs(int u, int fa, int pfa) {
		f[u][0] = 1;
    for (auto v : e[u])
        if (v != fa) {
            dfs(v, u, p[u]);
            for (int j = sz[u] + sz[v]; j >= 0; --j) { 
            	// 这里本来应该开一个另外的数组来存值，最后再赋值回去的，但是注意到k=0的转移非常好写就直接赋值了
            	// failed at v
            	f[u][j] = (ll)f[u][j] * (mod + 1 - p[v]) % mod; 
            	g[u][j] = (ll)g[u][j] * (mod + 1 - p[v]) % mod;
            	// choose k nodes in subtree v
            	for (int k = max(1, j - sz[u]); k <= min(j, sz[v]); ++k) {
                    f[u][j] = (f[u][j] + (ll)f[u][j - k] * f[v][k]) % mod;
                    g[u][j] = (g[u][j] + (ll)g[u][j - k] * f[v][k] + (ll)f[u][j - k] * g[v][k]) % mod;
            	}
           	}
           	sz[u] += sz[v];
        }
    ++sz[u];
    for (int j = sz[u]; j; --j) {
    	f[u][j] = (ll)f[u][j - 1] * p[u] % mod;
    	g[u][j] = (ll)f[u][j - 1] * a[u] % mod;
    	if (j > 1) g[u][j] = (g[u][j] + (ll)g[u][j - 1] * p[u]) % mod;
    	ans[j] = (ans[j] + (ll)g[u][j] * (mod + 1 - pfa)) % mod; // 注意要保证父亲没有选
    }
}

int main() {
	int n = rd();
	for (int i = 1; i < n; ++i) {
		int u = rd(), v = rd(); 
		e[u].push_back(v); e[v].push_back(u);
	}
	int sum = 0;
	for (int i = 1; i <= n; ++i) {
		a[i] = rd(); sum += a[i];
		p[i] = rd(); p[i] = (ll)p[i] * fpow(rd()) % mod;
	}
	sum = fpow(sum);
	for (int i = 1; i <= n; ++i) a[i] = (ll)a[i] * sum % mod;
	dfs(1, 1, 0);
	for (int i = 1; i <= n; ++i) printf("%d\n", ans[i]);
	return 0;
}

K - Middle Point Graph

给一幅图，对每个顶点，在三维立方体区域 \([0,0,0]\sim[1,1,1]\) 中随机一个坐标。

对每条边，定义他的坐标是连接的两个顶点的中点。这样就得到了 \(n+m\) 个坐标。

问这 \(n+m\) 个坐标中，选出四点共平面的方案数的期望。

首先得知道三维空间里随机一个平面的概率是 \(0\) ，因为是连续概率。所以四个点都取自原图顶点的期望是 \(0\) 。

所以哪些点共面其实是确定的。分讨组成情况即可。我的分讨和题解不太一样：

  • 一条边的两顶点 + 中点 + 额外的一个点：额外的点在哪里都和一条线共面，方案数是 \(m(n+m-3)\) 。
  • 三个点通过两条边相连，选择两条边终点 + 外侧的两个端点：方案数是 \(\sum_u \frac{deg_u(deg_u- 1)}{2}\) ，即每个点选两条边。
  • 三元环三条边中点 + 某个顶点：方案数是 \(3\times\) 三元环个数。
  • 四元环的四个中点：方案数是四元环个数。

求三元环和四元环的复杂度是 \(\mathcal{O}(m\sqrt m)\) 的，科技不再赘述。

其实如果讨论情况想不全的话，可以暴力随机统计然后找规律（注释掉的代码就是赛时找规律用的）。

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define N 500007

// struct vec {
// 	double x, y, z;
// 	vec operator + (const vec &b) {return {x + b.x, y + b.y, z + b.z};}
// 	vec operator - (const vec &b) {return {x - b.x, y - b.y, z - b.z};}
// 	vec operator / (const double &b) {return {x / b, y / b, z / b};}
// } p[N];

// bool det(vec a, vec b, vec c) {
// 	double res = a.x * b.y * c.z +
// 				 b.x * c.y * a.z + 
// 				 c.x * a.y * b.z - 
// 				 a.x * c.y * b.z -
// 				 b.x * a.y * c.z - 
// 				 c.x * b.y * a.z;
// 	return abs(res) <= 1e-8; 
// }

// inline double randp() {
// 	return 1.0 * rand() / RAND_MAX;
// }

// inline void work() {
// 	int n = rd(), m = rd();
// 	int k = n;
// 	for (int i = 1; i <= n; ++i) {
// 		p[i].x = randp();
// 		p[i].y = randp();
// 		p[i].z = randp();
// 	}
// 	for (int i = 1; i <= m; ++i) {
// 		int u = rd(), v = rd();
// 		p[++n] = (p[u] + p[v]) / 2;
// 	}
// 	int ans = 0;
// 	for (int a = 1; a <= k; ++a)
// 		for (int b = a + 1; b <= k; ++b)
// 			for (int c = b + 1; c <= n; ++c)
// 				for (int d = c + 1; d <= n; ++d) 
// 					if (det(p[b] - p[a], p[c] - p[a], p[d] - p[a])) {
// 						++ans; printf("%d %d %d %d\n", a, b, c, d);
// 					}
// 	printf("%d\n", ans);
// }

int n,m,X[N],Y[N],d[N],ti,vis[N],cnt[N];
vector<int> e[N],h[N];
ll ans3,ans4;
inline bool cmp(const int &i,const int &j) {return d[i]<d[j] || (d[i]==d[j] && i<j);}
void workz(){
	n=rd();m=rd();
	for (int i=1;i<=n;i++) d[i]=0,cnt[i]=0,e[i].clear(),h[i].clear();
	for (int i=1;i<=m;i++){
		X[i]=rd();Y[i]=rd();d[X[i]]++;d[Y[i]]++;
		h[X[i]].push_back(Y[i]);h[Y[i]].push_back(X[i]);
	}
	for (int i=1;i<=m;i++) cmp(X[i],Y[i])?e[X[i]].push_back(Y[i]):e[Y[i]].push_back(X[i]);
	ans3=0;
	for (int i=1;i<=m;i++){
		ti++;for (auto x:e[X[i]]) vis[x]=ti;
		for (auto x:e[Y[i]]) if (vis[x]==ti) ans3++;
	}
	ans4=0;
	for (int x=1;x<=n;x++){
		for (auto y:h[x])
			for (auto z:e[y])
				if (cmp(x,z)) ans4+=cnt[z],cnt[z]++;
		for (auto y:h[x])
			for (auto z:e[y])
				cnt[z]=0;
	}
	ll ans=(ll)m*(n+m-3);
	for (int i=1;i<=n;i++) ans+=(ll)d[i]*(d[i]-1)/2;
	ans+=3*ans3;ans+=ans4;
	printf("%lld\n", ans%MOD);
}
int main() {
	for (int t = rd(); t; --t) workz();
	return 0;
}

L - Station of Fate

\(n\) 个人分成 \(m\) 个可区分的非空队列的方案数。

顺序有 \(n!\) 种，插板法划分成 \(m\) 个非空序列，总方案数为 \(n!{n-1\choose m - 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
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 100007
#define mod 998244353

int fac[N], ifac[N];

inline int fpow(int x, int t) {
    int res = 1;
    for (; t; t >>= 1, x = 1ll * x * x % mod)
        if (t & 1) res = 1ll * res * x % mod;
    return res;
}

inline int C(int n, int m) {
    return 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}

inline void work() {
    int n = rd(), m = rd();
    printf("%lld\n", 1ll * fac[n] * C(n - 1, m - 1) % mod);
}

int main() {
    fac[0] = ifac[0] = 1;
    for (int i = 1; i < N; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
    ifac[N - 1] = fpow(fac[N - 1], mod - 2);
    for (int i = N - 2; i; --i) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;
    for (int t = rd(); t; --t) work();
    return 0;
}