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

Codeforces Global Round 10

比赛链接 / 官方题解链接

A. Omkar and Password

Solution

如果全部相同，则答案是序列长度；否则，答案一定是 $1$，因为我可以选择序列中最大的元素，不断加给它（如果有多个相同的最大元素，由于不全相同，一定有某个最大元素与不同的元素相邻，它们相加后成为了序列中的唯一最大元素）。

Code

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
#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, a[N], T;

int main(){
	for(read(T); T; T--){
		read(n);
		bool same = true;
		read(a[1]);
		for(int i = 2; i <= n; i++){
			read(a[i]);
			if(a[i] != a[1])	same = false;
		}
		if(same)	printf("%d\n", n);
		else	puts("1");
	}
	return 0;
}

B. Omkar and Infinity Clock

Solution

画画图就知道，在一次操作之后，剩下的操作就是在两种状态之间来回变，判断 $k-1$ 的奇偶性即可。

Code

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
#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;
LL k, a[N];

int main(){
	int T; for(read(T); T; T--){
		read(n, k);
		LL mx = -1e14, mn = 1e14;
		for(int i = 1; i <= n; i++){
			read(a[i]);
			mx = max(mx, a[i]);
			mn = min(mn, a[i]);
		}
		for(int i = 1; i <= n; i++)	a[i] = mx - a[i];
		mn = mx - mn;
		k--;
		if(k & 1){
			for(int i = 1; i <= n; i++)	a[i] = mn - a[i];
		}
		for(int i = 1; i <= n; i++)	printf("%lld ", a[i]); puts("");
	}
	return 0;
}

C. Omkar and Waterslide

Solution

感觉这道题是最简单的呢。。。每次把整个后缀一起上移就行了，所以答案就是 $\sum\limits_{i=2}^n\max(0,a_{i-1}-a_{i})$.

Code

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
#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;
LL a[N];

int main(){
	int T; for(read(T); T; T--){
		read(n);
		LL ans = 0;
		read(a[1]);
		for(int i = 2; i <= n; i++){
			read(a[i]);
			if(a[i] < a[i-1])	ans += a[i-1] - a[i];
		}
		printf("%lld\n", ans);
	}
	return 0;
}

D. Omkar and Bed Wars

Solution

画画图，手玩一下可以知道，只有 $LR,LLR,LRR,LLRR$ 是合法的（它们都是以 $LR$ 为“核”，向两边最多扩展一位）。把它们删掉，剩下的部分被分成了几段，每一段形如 $R\cdots RL\cdots L$，设 $R$ 有 $c_R$ 个，$L$ 有 $c_L$ 个，那么这一段需要改变的次数就是 $\left\lfloor\frac{c_R}{3}\right\rfloor+\left\lfloor\frac{c_L}{3}\right\rfloor$. （因为 $3$ 个一组改一次可以合法，如果最后单出一个，改与之相邻的合法片段即可，答案还是除以 $3$ 下取整不变）

Code

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
#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;
char s[N], t[N];
bool b[N], c[N];

inline int get(int x){
	x = x % n;
	if(x == 0)	x = n;
	return x;
}

inline void expand(int i){
	if(!b[get(i+2)] && s[get(i+2)] == 'R')
		b[get(i+2)] = true;
	if(!b[get(i-1)] && s[get(i-1)] == 'L')
		b[get(i-1)] = true;
}

inline int solve(int i, int j){
	int cntR = 0, cntL = 0;
	for(int k = i; k <= j; k++){
		cntR += t[k] == 'R';
		cntL += t[k] == 'L';
	}
	int res = cntR / 3 + cntL / 3;
	if(cntR % 3)	res++;
	if(cntL % 3)	res++;
	return res;
}

int main(){
	int T; for(read(T); T; T--){
		int ans = 0;
		read(n);
		for(int i = 1; i <= n; i++){
			b[i] = c[i] = false;
		}
		scanf("%s", s+1);
		for(int i = 1; i <= n; i++){
			if(b[i] || b[get(i+1)])	continue;
			if(s[i] == 'L' && s[get(i+1)] == 'R'){
				b[i] = b[get(i+1)] = true;
				expand(i);
			}
		}
		int ed = 1;
		for(ed = 1; ed <= n; ed++)
			if(b[ed])	break;
		ed--;
		int tid = 0;
		for(int i = ed + 1; i <= n; i++)
			t[++tid] = s[i], c[tid] = b[i];
		for(int i = 1; i <= ed; i++)
			t[++tid] = s[i], c[tid] = b[i];
// for(int i = 1; i <= n; i++)
// 	printf("%c %d\n", t[i], c[i]);
		for(int i = 1; i <= n; i++){
			if(c[i])	continue;
			int j = i;
			while(j < n && !c[j+1])	j++;
			ans += solve(i, j);
			i = j;
		}
		printf("%d\n", ans);
	}
	return 0;
}

E. Omkar and Duck

构造题鲨我啊～

Solution

构造矩阵：

例如，$n=8$ 时构造如下（复制于官方题解）：

走到一个位置判断下一步的方向即可。

Code

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
#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 = 30;

int n;
LL a[N][N];

int main(){
	read(n);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			a[i][j] = (i & 1) ? 0 : (1ll << (i + j));
			printf("%lld ", a[i][j]);
		}
		puts("");
	}
	fflush(stdout);
	int q; read(q);
	while(q--){
		LL s; read(s);
		int nowx = 1, nowy = 1;
		printf("%d %d\n", 1, 1);
		while(!(nowx == n && nowy == n)){
			if(nowx == n)	nowy++;
			else if(nowy == n)	nowx++;
			else{
				if((s>>(nowx+nowy+1))&1){
					if(a[nowx+1][nowy])	nowx++;
					else	nowy++;
				}
				else{
					if(a[nowx+1][nowy])	nowy++;
					else	nowx++;
				}
			}
			printf("%d %d\n", nowx, nowy);
		}
		fflush(stdout);
	}
	return 0;
}

F. Omkar and Landslide

Solution

关键性质：答案中最多只含有一对相等的数，其他数都是以 $1$ 严格递增。

证明：题设“滑坡”操作其实等价于依次考虑每一个高度，一次性把这个高度滑到头。注意初始情况严格递增，没有相等的数。每滑一次，如果之前没有相等的数，那最多新增一对相等的数；如果之前有相等的数 $a_{i-1}=a_i,a_{i+1}=a_i+1$，那么 $a_i$ 加一后与 $a_{i-1}$ 不等了，但是与 $a_{i+1}$ 相等了。所以整个过程始终保证相等的数最多只有一对。证毕。

既然如此，我们知道所有数的总和，就可以唯一构造出这个答案序列。为什么？考虑以 $1$ 递增的等差数列，总和一定介于两个首项差 $1$ 的等差数列的和之间，取小者，多出来多少，前多少个数就加一即可。

Code

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;

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 = 1000005;

int n;
LL h, sumh;

int main(){
	read(n);
	for(int i = 1; i <= n; i++)	read(h), sumh += h;
	LL x = ((2 * sumh) / n - n + 1) / 2;
	LL sum = (x + x + n - 1) * n / 2;
	LL diff = sumh - sum;
	for(int i = 1; i <= n; i++)
		printf("%lld ", x + i - 1 + (i <= diff));
	puts("");
	return 0;
}

Codeforces Global Round 10

http://xyfjason.github.io/blog-xcpc/2020/08/17/Codeforces-Global-Round-10/

作者

xyfJASON

发布于

2020-08-17

更新于

2020-12-20

许可协议

#

评论

关注我

分类

最新文章

标签

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