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

Codeforces Round #721 (Div.2)

比赛链接 / 官方题解链接

A. And Then There Were K

答案显然是 $2^{\lfloor\log_2 n\rfloor}-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
#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

int main(){
	int T; for(read(T); T; T--){
		int n; read(n);
		int k = -1, ans = 1;
		while(n){
			n >>= 1;
			k++;
			if(k > 0)	ans <<= 1;
		}
		printf("%d\n", ans-1);
	}
	return 0;
}

B1. Palindrome Game (easy version)

由于初始情况一定是回文串，所以 Alice 只能更改某个 0，于是只要 Bob 更改对称位置的那个 0，Alice 就永远只能进行操作 1。直到最后只剩 2 个 0 时，Bob 在 Alice 更改一个 0 后进行翻转操作就可以胜利。

唯一的例外是 $n$ 是奇数且中心位置是 0 且 0 的数量多于 1 个，那么 Alice 只需要改中心位置的 0，这个困境就交到了 Bob 手里。

B2. Palindrome Game (hard version)

如果是回文串转到 B1，现在只考虑初始串不是回文的情况。

首先证明 Alice 一定不会输：假设初始串在第一步不做翻转的条件下是先手不输的，那么 Alice 一定不输；否则，如果初始串在第一步不做翻转的条件下是先手必输的，那么 Alice 做一次翻转操作，必输态就给到了 Bob 手里，于是 Alice 必胜。（这个证明感觉上很类似于「证明存在一个无理数的无理数次方是有理数」）。

所以我们只需要考虑什么时候会 DRAW 即可。

假设初始串只进行一次更改之后不能变成回文串，那么根据上述分析，现在的先手不输，又由于对手之前进行了一次操作，所以现在的先手必胜。因此，只要 Alice 先做翻转操作，Bob 只能做一次更改操作，那么 Alice 就胜利了。

否则，一次更改之后初始串能变成回文串。那么，当且仅当这个回文串只有一个中心 0 时结果是 DRAW，否则结果一定是 Alice 胜。这是因为：如果变成的回文串是必胜的，那么 Alice 只需要先翻转初始串，然后 Bob 将其变成回文（Bob 一定会这么干，否则 Alice 一直进行翻转操作而 Bob 只能进行更改操作，这对 Bob 不利），然后 Alice 胜利；否则回文串是必败的，那么 Alice 先把初始串变成该回文串，然后 Bob 必败且根据 B1 的分析知至少输 $2，于是 Alice 胜利。

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
#include<bits/stdc++.h>
 
using namespace std;
 
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
 
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
 
const int N = 1005;
 
char s[N];
 
int main(){
	int T; for(read(T); T; T--){
		int n; read(n);
		scanf("%s", s+1);
		int cnt0 = 0, cnt = 0;
		for(int i = 1; i <= n; i++){
			cnt0 += (s[i] == '0');
			cnt += (s[i] != s[n-i+1]);
		}
		cnt >>= 1;
		if(cnt == 0){
			if((n & 1) == 1 && s[n/2+1] == '0' && cnt0 > 1)	puts("ALICE");
			else	puts("BOB");
		}
		else{
			if(cnt == 1 && cnt0 == 2)	puts("DRAW");
			else	puts("ALICE");
		}
	}
	return 0;
}

C. Sequence Pair Weight

把同一个值出现的位置拿出来单独考虑：设 $v$ 出现的位置为 $p_1,\,p_2,\cdots,\,p_m$，则 $v$ 对答案的贡献是：

前缀和一下就可以做到 $O(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
#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 100005;

int n;
LL a[N], t[N], ans;
vector<LL> p[N], s[N];

inline void init(){
	ans = 0;
	for(int i = 1; i <= n; i++)
		p[i].clear(), s[i].clear();
}

int main(){
	int T; for(read(T); T; T--){
		read(n);
		init();
		for(int i = 1; i <= n; i++)	read(a[i]), t[i] = a[i];
		sort(t+1, t+n+1);
		int len = unique(t+1, t+n+1) - (t+1);
		for(int i = 1; i <= n; i++){
			a[i] = lower_bound(t+1, t+len+1, a[i]) - t;
			p[a[i]].pb(i);
		}
		for(int v = 1; v <= n; v++){
			if(p[v].empty())	break;
			int m = p[v].size();
			s[v].pb(p[v][0]);
			for(int i = 1; i < m; i++)
				s[v].pb(s[v][i-1] + p[v][i]);
			for(int i = 0; i < m; i++){
				ans += 1ll * (n+1) * (m-i-1) * p[v][i];
				ans -= p[v][i] * (s[v][m-1] - s[v][i]);
			}
		}
		printf("%lld\n", ans);
	}
	return 0;
}

D. MEX Tree

把 $0$ 视为树的根，那么 $\text{mex}=0$ 的答案就是各个子树内部配对的数量。

求 $\text{mex}=i$ 时采取 $\text{mex}\geqslant i$ 的数量减去 $\text{mex}>i$ 的数量的方法。由于 $\text{mex}\geqslant i$ 就是 $\text{mex}>i-1$，所以现在只需要解决如何求解 $\text{mex}>i$ 的数量即可。

$\text{mex}>i$ 意味着必须要经过 $0,1,\cdots,i$ 这些点，如果它们不在一条链上，那么一定无解；否则，维护这条链，经过这条链的路径数量可以简单的算出来，这就是 $\text{mex}>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
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;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 200005;

int n, fa[N];
vi edge[N];
LL ans[N], sz[N];
bool vis[N];

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

inline void init(){
	for(int i = 0; i <= n; i++){
		ans[i] = fa[i] = sz[i] = 0;
		vis[i] = false;
		edge[i].clear();
	}
}

int main(){
	int T; for(read(T); T; T--){
		read(n);
		init();
		for(int i = 1; i < n; i++){
			int u, v; read(u, v);
			edge[u].pb(v), edge[v].pb(u);
		}
		dfs(0, -1);
		for(auto &to : edge[0])
			ans[0] += sz[to]*(sz[to]-1)/2;
		vis[0] = true;
		LL P = 1ll*n*(n-1)/2 - ans[0];
		int edl = 0, edr = 0;
		for(int i = 1; i <= n; i++){
			if(vis[i])	continue;
			int now = i, pre = 0;
			while(!vis[now]){
				vis[now] = true;
				pre = now;
				now = fa[now];
			}
			sz[now] -= sz[pre];
			if(now != edl && now != edr){
				ans[i] = P; break;
			}
			if(now == edl)	edl = i;
			else if(now == edr)	edr = i;
			ans[i] = P - sz[edl] * sz[edr];
			P = sz[edl] * sz[edr];
		}
		for(int i = 0; i <= n; i++)
			printf("%lld%c", ans[i], " \n"[i==n]);
	}
	return 0;
}

E. Partition Game

和前一天刚做到的这道题如出一辙，可惜比赛的时候没时间看了，血亏～

题解参考之前的博客，不单独对这道题写一遍了。

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

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 35005;
const int K = 105;

struct segTree{
	int l, r;
	LL mn, lazy;
}tr[N<<2];
#define lid (id<<1)
#define rid (id<<1|1)
#define mid ((tr[id].l + tr[id].r) >> 1)
inline void pushup(int id){
	tr[id].mn = min(tr[lid].mn, tr[rid].mn);
}
inline void pushdown(int id){
	if(tr[id].l == tr[id].r)	return;
	if(tr[id].lazy){
		tr[lid].lazy += tr[id].lazy;
		tr[lid].mn += tr[id].lazy;
		tr[rid].lazy += tr[id].lazy;
		tr[rid].mn += tr[id].lazy;
		tr[id].lazy = 0;
	}
}
void build(LL a[], int id, int l, int r){
	tr[id].l = l, tr[id].r = r;
	tr[id].lazy = 0, tr[id].mn = 0;
	if(l == r){ tr[id].mn = a[l]; return; }
	build(a, lid, l, mid), build(a, rid, mid+1, r);
	pushup(id);
}
void add(int id, int l, int r, LL val){
	pushdown(id);
	if(tr[id].l == l && tr[id].r == r){
		tr[id].lazy += val;
		tr[id].mn += val;
		return;
	}
	if(r <= mid)	add(lid, l, r, val);
	else if(l > mid)	add(rid, l, r, val);
	else	add(lid, l, mid, val), add(rid, mid+1, r, val);
	pushup(id);
}
LL query(int id, int l, int r){
	pushdown(id);
	if(tr[id].l == l && tr[id].r == r)	return tr[id].mn;
	if(r <= mid)	return query(lid, l, r);
	else if(l > mid)	return query(rid, l, r);
	else	return min(query(lid, l, mid), query(rid, mid+1, r));
}

int n, k;
LL a[N], dp[K][N], pos[N], pre[N];

int main(){
	read(n, k);
	for(int i = 1; i <= n; i++){
		read(a[i]);
		pre[i] = pos[a[i]];
		dp[1][i] = dp[1][i-1] + (i - pos[a[i]]) * (pos[a[i]] != 0);
		pos[a[i]] = i;
	}
	for(int j = 2; j <= k; j++){
		build(dp[j-1], 1, 1, n);
		for(int i = j; i <= n; i++){
			if(1 <= pre[i] - 1)
				add(1, 1, pre[i]-1, i - pre[i]);
			dp[j][i] = query(1, 1, i-1);
		}
	}
	printf("%lld\n", dp[k][n]);
	return 0;
}

Codeforces Round #721 (Div.2)

http://xyfjason.github.io/blog-xcpc/2021/05/21/Codeforces-Round-721-Div-2/

作者

xyfJASON

发布于

2021-05-21

更新于

2021-05-21

许可协议

#

评论

关注我

分类

最新文章

标签

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