发表更新ICPC/CCPC / Contests / CCPC12 分钟读完 (大约1766个字)

CCPC-2020 威海站记录

第一块银牌留念！

继秦皇岛站打铜过后，终于有所进步了。接下来的日子里继续冲！

A. Golden Spirit

毫无疑问先把 $2n$ 个老人全运到对面去，假设人刚开始在 $A$ 岸，那么 $2nt$ 的时间后现在人仍在 $A$ 岸。现在，如果第一个到达 $A$ 岸的人（已经休息了 $2nt-t$ 时间）已经休息好了（$2nt-t\geqslant x$），那么再花 $2nt$ 的时间吧所有人运回对面即可；否则有两种选择，要么在 $A$ 岸等待第一个到达 $A$ 岸的人休息好，要么走到 $B$ 岸等第一个到 $B$ 岸的人休息好，二者取 $\min$ 即可。

（刚开始想成了 $2nt$ 时间后人在 $B$ 岸，贡献了全场我队唯一一发罚时。。。）

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;

typedef long long LL;
typedef unsigned long long ULL;

ULL n, x, t;

int main(){
	int T; for(scanf("%d", &T); T; T--){
		scanf("%llu%llu%llu", &n, &x, &t);
		if(x+2*t <= 2*n*t)	printf("%llu\n", 4*n*t);
		else{
			ULL ans = x+2*t+2*n*t;
			if(x >= 2ll*n*t)	ans = min(ans, x+2*n*t+t);
			else	ans = min(ans, t+4*n*t);
			printf("%llu\n", ans);
		}
	}
	return 0;
}

C. Recontre

只需注意到一个极其重要的性质：树上三个点到某点的最短距离之和等于三个点两两距离之和的一半。

于是问题变成了在树上取两个点，求期望长度。这个及其套路地考虑边的贡献可以轻松解决。

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
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 200005;

int n;
int sz[N][4];
vector< pair<int, LL> > edge[N];

void dfs(int x, int f){
	for(auto &to : edge[x]){
		if(to.first == f)	continue;
		dfs(to.first, x);
		sz[x][1] += sz[to.first][1];
		sz[x][2] += sz[to.first][2];
		sz[x][3] += sz[to.first][3];
	}
}

double ans;
int k[4];
void calc(int x, int f, int a, int b){
	for(auto &to : edge[x]){
		if(to.first == f)	continue;
		ans += 1.0 * to.second * sz[to.first][a]*(sz[1][b]-sz[to.first][b]) / k[a] / k[b];
		calc(to.first, x, a, b);
	}
}

int main(){
	scanf("%d", &n);
	for(int i = 1; i < n; i++){
		int u, v; LL w;
		scanf("%d%d%lld", &u, &v, &w);
		edge[u].pb(mp(v, w));
		edge[v].pb(mp(u, w));
	}
	for(int j = 1; j <= 3; j++){
		scanf("%d", &k[j]);
		for(int i = 1; i <= k[j]; i++){
			int u; scanf("%d", &u);
			sz[u][j]++;
		}	
	}
	dfs(1, 0);
	calc(1, 0, 1, 2);
	calc(1, 0, 2, 1);
	calc(1, 0, 1, 3);
	calc(1, 0, 3, 1);
	calc(1, 0, 2, 3);
	calc(1, 0, 3, 2);
	ans = ans / 2.0;
	printf("%.12f\n", ans);
	return 0;
}

D. ABC Conjecture

重现一下考试时的思考过程：设 $d=\gcd(a,c),a=dk_1,c=dk_2,k_1<k_2$，则 $b=d(k_2-k_1)$，

故要使 $\text{rad}(abc)<c$，只需找到 $k_1\perp k_2$ 使得 $k_1(k_2-k_1)<\frac{c}{\text{rad}(c)}$，如果 $\frac{c}{\text{rad}(c)}\neq 1$，那就取 $k_2=\frac{c}{\text{rad}(c)},k_1=1$ 即可；否则无解。

所以问题变成了判断 $c$ 是否有平方因子。比赛的时候直接莽上 Pollard-Rho 了，但事实上没有必要。

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
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

LL gcd(LL a, LL b){ return b == 0 ? a : gcd(b, a % b); }

mt19937 rnd(time(NULL));
namespace Miller_Rabin{
	inline LL fpow(LL bs, LL idx, LL mod){
		bs %= mod;
		LL res = 1;
		while(idx){
			if(idx & 1)	res = (__int128)res * bs % mod;
			bs = (__int128)bs * bs % mod;
			idx >>= 1;
		}
		return res;
	}
	bool test(LL n){
		if(n < 3)	return n == 2;
		if(!(n & 1))	return false;
		LL u = n - 1, t = 0;
		while(u % 2 == 0)	u /= 2, t++;
		int testTime = 10;
		while(testTime--){
			LL v = rnd() % (n - 2) + 2;
			v = fpow(v, u, n);
			if(v == 1 || v == n - 1)	continue;
			int j; for(j = 0; j < t; j++, v = (__int128)v * v % n)
				if(v == n - 1)	break;
			if(j >= t)	return false;
		}
		return true;
	}
}
namespace Pollard_Rho{
	vector<LL> factors;
	inline LL solve(LL n){
		LL c = rnd() % (n - 1) + 1;
		LL x = 0, y = 0, val = 1;
		for(LL k = 1; ; k <<= 1, y = x, val = 1){
			for(int i = 1; i <= k; i++){
				x = ((__int128)x * x + c) % n;
				val = (__int128)val * abs(x - y) % n;
				if(val == 0)	return n;
				if(i % 127 == 0){
					LL g = gcd(val, n);
					if(g > 1)	return g;
				}
			}
			LL g = gcd(val, n);
			if(g > 1)	return g;
		}
	}
	void factorize(LL n){
		if(n < 2)	return;
		if(Miller_Rabin::test(n)){
			factors.emplace_back(n);
			return;
		}
		LL p = n;
		while(p == n)	p = solve(n);
		while(n % p == 0)	n /= p;
		factorize(p), factorize(n);
	}
}

int main(){
	int T; for(scanf("%d", &T); T; T--){
		LL c; scanf("%lld", &c);
		Pollard_Rho::factors.clear();
		Pollard_Rho::factorize(c);
		bool ok = false;
		for(auto &fac : Pollard_Rho::factors){
			if((c / fac) % fac == 0){
				ok = true;
				break;
			}
		}
		puts(ok ? "yes" : "no");
	}
	return 0;
}

G. Caesar Cipher

分块+哈希。

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <bits/stdc++.h>

using namespace std;

#define N 500005
#define mod 65536
const long long P = 1000000007;
const long long Base = 70000;


inline int read () {
	register int s = 0, f = 1; 
	register char ch = getchar ();
	for ( ; ch < '0' || ch > '9'; f = (ch == '-') ? -1 : f, ch = getchar ());
	for ( ; ch >= '0' && ch <= '9'; s = s * 10 + (ch ^ 48), ch = getchar ());
	return s * f;
}

long long Belong[N], L[N], R[N], C[N], bl, a[N], cnt;

long long Hash[N], f[755][65540], power[N], inv;

long long qpow (long long a, long long x) {
	long long ans = 1;
	while (x) {
		if (x & 1) ans = (ans * a) % P;
		a = (a * a) % P;
		x >>= 1;
	} return ans;
}

int n, q;

inline void Maintain (int l, int r) {
	if (r <= R[Belong[l]]) {
		for (int i = l; i <= r; ++i) {
			Hash[Belong[i]] = (Hash[Belong[i]] - a[i] * power[R[Belong[i]] - i] % P + P) % P;
			f[Belong[i]][a[i]] =  (f[Belong[i]][a[i]] - power[R[Belong[i]] - i] + P) % P;
			a[i] = (a[i] + 1) % mod;
			f[Belong[i]][a[i]] =  (f[Belong[i]][a[i]] + power[R[Belong[i]] - i]) % P;
			Hash[Belong[i]] = (Hash[Belong[i]] + a[i] * power[R[Belong[i]] - i] % P) % P;
		} return ;
	}
	for (int i = l; i <= R[Belong[l]]; ++i) {
		Hash[Belong[i]] = (Hash[Belong[i]] - a[i] * power[R[Belong[i]] - i] % P + P) % P;
		f[Belong[i]][a[i]] =  (f[Belong[i]][a[i]] - power[R[Belong[i]] - i] + P) % P;
		a[i] = (a[i] + 1) % mod;
		f[Belong[i]][a[i]] =  (f[Belong[i]][a[i]] + power[R[Belong[i]] - i]) % P;
		Hash[Belong[i]] = (Hash[Belong[i]] + a[i] * power[R[Belong[i]] - i] % P) % P;
	}
	for (int i = L[Belong[r]]; i <= r; ++i) {
		Hash[Belong[i]] = (Hash[Belong[i]] - a[i] * power[R[Belong[i]] - i] % P + P) % P;
		f[Belong[i]][a[i]] =  (f[Belong[i]][a[i]] - power[R[Belong[i]] - i] + P) % P;
		a[i] = (a[i] + 1) % mod;
		f[Belong[i]][a[i]] =  (f[Belong[i]][a[i]] + power[R[Belong[i]] - i]) % P;
		Hash[Belong[i]] = (Hash[Belong[i]] + a[i] * power[R[Belong[i]] - i] % P) % P;
	} 
	for (int i = Belong[l] + 1; i < Belong[r]; ++i) {
		C[i] = (C[i] + 1) % mod;
		Hash[i] = (Hash[i] + ((power[R[i] - L[i] + 1] - 1 + P) % P) * inv % P) % P;
		Hash[i] = (Hash[i] - mod * f[i][(mod - C[i]) % mod] % P + P) % P;
	} return ;
} 
inline long long Query (int l, int r) {
	long long ans = 0;
	if (r <= R[Belong[l]]) {
		for (int i = l; i <= r; ++i) {
			ans = (ans + (a[i] + C[Belong[i]]) % mod * power[r - i] % P) % P; 
		} return ans;
	}
	for (int i = l; i <= R[Belong[l]]; ++i) {
		ans = (ans + (a[i] + C[Belong[i]]) % mod * power[R[Belong[i]] - i] % P) % P; 
	} 
	for (int i = Belong[l] + 1; i < Belong[r]; ++i) {
		ans = (ans * power[R[i] - L[i] + 1] % P + Hash[i]) % P;
	} int tmp2 = 0;
	for (int i = L[Belong[r]]; i <= r; ++i) {
		tmp2 = (tmp2 + (a[i] + C[Belong[i]]) % mod * power[r - i] % P) % P; 
	} ans = (ans * power[r - L[Belong[r]] + 1] % P + tmp2) % P;
	return ans;
}
int main () {
	n = read (), q = read ();
	inv = qpow (Base - 1, P - 2);
	power[0] = 1;
	bl = sqrt (n + 1);
	for (int i = 1; i <= n; ++i) {
		power[i] = power[i - 1] * Base % P;
		a[i] = read ();
		Belong[i] = (i - 1) / bl + 1;
		R[Belong[i]] = i;
		cnt = Belong[i];
	} for (int i = n; i; --i) L[Belong[i]] = i;
	power[n + 1] = power[n] * Base % P;
	for (int i = 1; i <= cnt; ++i) {
		for (int j = L[i]; j <= R[i]; ++j) {
			Hash[i] = (Hash[i] * Base + a[j]) % P;
			(f[i][a[j]] += power[R[i] - j]) %= P;
		}
	} 
	for (int opt, x, y, l, i = 1; i <= q; ++i) {
		opt = read ();
		if (opt == 1) {
			x = read (), y = read ();
			Maintain (x, y);
		} else {
			x = read (), y = read (), l = read ();
			long long ans1 = Query (x, x + l - 1);
			long long ans2 = Query (y, y + l - 1);
			puts (ans1 == ans2 ? "yes" : "no");
		}
	} return 0;
}

H. Message Bomb

队友做的，没看题。。。

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
#include<cstdio>
#include<set>
using namespace std;
const int N = 1e5 + 2;
typedef long long ll;
ll stu[N << 1], group[N];
set<ll>st[N << 1];
int main(){
	ll n, m, s, i, j, k;set<ll>::iterator it;
	scanf("%lld%lld%lld", &n, &m, &s);
	while(s--){
		scanf("%lld%lld%lld", &i, &j, &k);
		if(i == 1){
			st[j].insert(k);
			stu[j] -= group[k];
		}else if(i == 2){
			st[j].erase(k);
			stu[j] += group[k];
		}else{
			if(st[j].find(k) != st[j].end())stu[j]--;
			group[k]++;
		}
	}for(i = 1;i <= m;i++)
		for(it = st[i].begin();it != st[i].end();it++)
			stu[i] += group[*it];
	for(i = 1;i <= m;i++)printf("%lld\n", stu[i]);
	return 0;
}

L. Clock Master

同队友做的，没看题。

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
#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
const int N = 30000;
int v[N + 2], p[N + 2];double f[N + 2];
int main(){
	int T, n, i, j, k, alpha;double s;
	for(i = 2;i <= N;i++){
		if(!v[i])p[++p[0]] = i;
		for(j = 1;j <= p[0] && i * p[j] <= N;j++){
			v[i * p[j]] = 1;
			if(!(i % p[j]))break;
		}
	}
	for(i = 1;i <= p[0];i++)
		for(j = N, s = log(p[i]);j;j--)
			for(k = 1, alpha = 0;k <= j;k *= p[i], alpha++)
				f[j] = max(f[j], f[j - k] + alpha * s);
	scanf("%d", &T);
	while(T--){
		scanf("%d", &n);
		printf("%.9lf\n", f[n]);
	}
	return 0;
}

CCPC-2020 威海站记录

http://xyfjason.github.io/blog-xcpc/2020/11/02/CCPC-2020-威海站记录/

作者

xyfJASON

发布于

2020-11-02

更新于

2021-08-28

许可协议

#

评论

关注我

分类

最新文章

标签

AtCoder2
CCPC2
Codeforces57
EOJ1
GMCPC1
HDU11
ICPC3
Nowcoder12
POI1
hihoCoder1
学习笔记17
随笔1
×