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

Codeforces Round #649 (Div.2)

比赛链接 / 官方题解链接

A. XXXXX

Solution

如果所有数都是 $x$ 的倍数，则答案为 $0$；否则，如果所有数的和不是 $x$ 的倍数，答案是 $n$；否则，找到第一个和最后一个不是 $x$ 的倍数的数，删去前缀或后缀。

Code

>folded
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)

int T, n, x;

int main(){
	for(read(T); T; T--){
		read(n, x);
		int mx = -1, mn = 1e9, sum = 0;
		for(int i = 1; i <= n; i++){
			int a; read(a); sum += a;
			if(a % x)	mx = max(mx, i), mn = min(mn, i);
		}
		if(mx == -1)	puts("-1");
		else if(sum % x)	printf("%d\n", n);
		else	printf("%d\n", n - min(mn, n - mx + 1));
	}
	return 0;
}

B. Most socially-distanced subsequence

Solution

保留“山峰”和“山谷”，以及第一个和最后一个数。

Code

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

int main(){
	for(read(T); T; T--){
		read(n);
		for(int i = 1; i <= n; i++)	read(a[i]);
		vi ans;
		ans.pb(a[1]);
		for(int i = 2; i < n; i++){
			if(a[i] > a[i-1] && a[i] > a[i+1])	ans.pb(a[i]);
			else if(a[i] < a[i-1] && a[i] < a[i+1])	ans.pb(a[i]);
		}
		ans.pb(a[n]);
		printf("%d\n", (int)ans.size());
		for(auto &k: ans)	printf("%d ", k);
		puts("");
	}
	return 0;
}

C. Ehab and Prefix MEXs

Solution

如果 $a_i\neq a_{i-1}$，那么必有 $b_i=a_{i-1}$。然后只需要把未出现在 $a$ 中的其他数依次填到空缺的位置上去。

Code

>folded
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
#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, a[N], b[N];
bool exi[1000005];

int main(){
	memset(b, -1, sizeof b);
	read(n);
	for(int i = 1; i <= n; i++){
		read(a[i]);
		if(i > 1 && a[i] != a[i-1])	b[i] = a[i-1];
		exi[a[i]] = true;
	}
	queue<int> q;
	for(int i = 0; i <= 1e6; i++)
		if(!exi[i])	q.push(i);
	for(int i = 1; i <= n; i++)
		if(b[i] == -1)
			b[i] = q.front(), q.pop();
	for(int i = 1; i <= n; i++)
		printf("%d ", b[i]);
	return 0;
}

D. Ehab’s Last Corollary

Solution

我们只需要找到一个内部没有边的回路（也就是说，对于回路 $a_1\to a_2\to\cdots\to a_m\to a_1$，$a_i$ 和 $a_j$ 之间没有边，$i,j$ 不相邻）就行了，因为如果这个回路长度小于等于 $k$，那么满足条件 $2$；否则，隔一个选一个可以选出大小至少是 $\left\lceil\frac{k}{2}\right\rceil$ 的独立集。

如何找到这样的回路？考虑 $dfs$ 树，只要我们取第一个返祖边与树边构成的回路即可。

Code

>folded
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
#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;
const int M = 200005;

int n, m, k;
vi edge[N];

bool ins[N], vis[N];
int dep[N];
stack<int> sta;
void dfs(int x, int f, int depth){
	vis[x] = ins[x] = true;
	sta.push(x);
	dep[x] = depth;
	for(auto &to: edge[x]){
		if(to == f)	continue;
		if(ins[to]){
			for(auto &t: edge[x])
				if(ins[t] && dep[t] > dep[to] && t != f)
					to = t;
			if(dep[x] - dep[to] + 1 <= k){
				puts("2");
				printf("%d\n", dep[x] - dep[to] + 1);
				while(!sta.empty()){
					if(dep[sta.top()] >= dep[to])
						printf("%d ", sta.top());
					sta.pop();
				}
				exit(0);
			}
			else{
				puts("1");
				vi ans; bool take = true; int cnt = 0;
				while(!sta.empty()){
					if(dep[sta.top()] >= dep[to]){
						if(take){
							printf("%d ", sta.top());
							cnt++;
							if(cnt == (k + 1) / 2)	exit(0);
						}
						take ^= 1;
					}
					sta.pop();
				}
			}
		}
		if(!vis[to])	dfs(to, x, depth + 1);
	}
	ins[x] = false;
	sta.pop();
}

int main(){
	read(n, m, k);
	for(int i = 1; i <= m; i++){
		int u, v; read(u, v);
		edge[u].pb(v), edge[v].pb(u);
	}
	dfs(1, 0, 1);
	puts("1");
	vi ans, _ans;
	for(int i = 1; i <= n; i++)
		if(dep[i] & 1)	ans.pb(i);
		else	_ans.pb(i);
	if(ans.size() < (k + 1) / 2)
		ans = _ans;
	for(int i = 0; i < (k + 1) / 2; i++)
		printf("%d ", ans[i]);
	return 0;
}

E. X-OR

Solution

【参考官方题解】如果我们找到了 $0$ 的位置，那么用它去询问其他位置就可以得到整个数列。所以问题在于如何找到 $0$ 的位置。

如果我们知道了第一个位置的数字是 $val$，那么顺序遍历下去，如果当前位置的数是 $val$ 的子集，那么把 $val$ 改为当前位置的数，存下当前位置 $idx$。如此遍历结束后，$idx$ 位置上就是 $0$。所以问题转化为如何求某一个位置上的数。

考虑数列 $z[i]$，存储任一个第 $i$ 位是 $0$ 的数的位置。那么位置 $r$ 的值就是 $(p_r\text{ OR }p_{z[0]})\text{ AND }(p_r\text{ OR }p_{z[1]})\text{ AND }\cdots\text{ AND }(p_r\text{ OR }p_{z[10]})$。

如何构造数列 $z[]$？随机取两个数进行询问，设结果的第 $r$ 位是 $0$，那么取 $z[r]$ 为这两个数中任一个位置。重复该过程直到 $z[]$ 被填满。由于每一位至少有一半的数为 $0$，所以这个过程比较快。

Code

>folded
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
#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 = 2500;

int n, z[20];
bool asked[N][N];

inline int ask(int x, int y){
	printf("? %d %d\n", x, y); fflush(stdout);
	int res = -1; read(res);
	if(res == -1)	exit(0);
	else	return res;
}

inline int get(int x){
	int res = (1 << 11) - 1;
	for(int i = 0; i <= 10; i++){
		if(x != z[i])
			res &= ask(x, z[i]);
		else if(res & (1 << i))
			res ^= (1 << i);
	}
	return res;
}

int main(){
	default_random_engine generator;
	read(n);
	memset(z, -1, sizeof z);
	while(count(z, z+11, -1)){
		int a = uniform_int_distribution<int> (1, n)(generator);
		int b = uniform_int_distribution<int> (1, n)(generator);
		if(a == b || asked[a][b])	continue;
		asked[a][b] = asked[b][a] = true;
		int res = ask(a, b);
		for(int i = 0; i <= 10; i++)
			if(((res >> i) & 1) == 0 && z[i] == -1)
				z[i] = a;
	}
	int idx = 1, val = get(1);
	for(int i = 2; i <= n; i++)
		if(ask(idx, i) == val)
			val = get(i), idx = i;
	vi ans;
	for(int i = 1; i <= n; i++){
		if(i == idx)	ans.pb(0);
		else	ans.pb(ask(i, idx));
	}
	printf("! ");
	for(auto &k: ans)	printf("%d ", k);
	fflush(stdout);
	return 0;
}

Codeforces Round #649 (Div.2)

http://xyfjason.github.io/blog-xcpc/2020/06/14/Codeforces-Round-649-Div-2/

作者

xyfJASON

发布于

2020-06-14

更新于

2020-12-20

许可协议

#

评论

关注我

分类

最新文章

标签

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