Loading [a11y]/accessibility-menu.js
发表更新ICPC/CCPC / Contests / Codeforces10 分钟读完 (大约1462个字)

Educational Codeforces Round 105

比赛链接 / 官方题解链接

A. ABC String

枚举各字母对应的括弧即可。

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

int n;
char s[N], t[N];

inline bool check(){
	int cnt = 0;
	for(int i = 1; i <= n; i++){
		if(t[i] == '(')	cnt++;
		else{
			if(cnt > 0)	cnt--;
			else	return false;
		}
	}
	return cnt == 0;
}

int main(){
	int T; for(read(T); T; T--){
		scanf("%s", s+1);
		n = strlen(s+1);
		bool ok = false;
		for(int i = 0; i < 8; i++){
			for(int j = 1; j <= n; j++)
				t[j] = ((i >> (s[j]-'A')) & 1) ? ')' : '(';
			if(check()){ ok = true; break; }
		}
		puts(ok ? "YES" : "NO");
	}
	return 0;
}

B. Berland Crossword

枚举四个顶点的颜色即可。

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
#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 n, u, r, d, l;

inline int get(int x, int i){ return (x >> i) & 1; }

int main(){
	int T; for(read(T); T; T--){
		read(n, u, r, d, l);
		bool ok = false;
		for(int i = 0; i < 16; i++){
			if(u - get(i, 0) - get(i, 1) > n - 2 || u - get(i, 0) - get(i, 1) < 0)	continue;
			if(r - get(i, 1) - get(i, 2) > n - 2 || r - get(i, 1) - get(i, 2) < 0)	continue;
			if(d - get(i, 2) - get(i, 3) > n - 2 || d - get(i, 2) - get(i, 3) < 0)	continue;
			if(l - get(i, 3) - get(i, 0) > n - 2 || l - get(i, 3) - get(i, 0) < 0)	continue;
			ok = true; break;
		}
		puts(ok ? "YES" : "NO");
	}
	return 0;
}

C. 1D Sokoban

仅考虑正方向，负方向做对称即可。

推完之后的箱子一定是这样的清形：往正方向走，先遇到一段连续的箱子，再遇到一些处于原位置没动的箱子。于是我们只需要枚举连续箱子的末尾的位置，就可以通过 lower_bound 等方式算出这种情形下的得分。

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;

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;

map<int, bool> isp;

inline int count(vector<int> &b, int l, int r){
	auto ll = lower_bound(b.begin(), b.end(), l);
	auto rr = lower_bound(b.begin(), b.end(), r);
	return rr - ll + 1;
}

inline int solve(vector<int> &a, vector<int> &b, int k){
	int n = a.size(), m = b.size();
	int res = 0;
	vector<int> sum(n+10), nega(n);
	for(int i = 0; i < n; i++)	nega[i] = -a[i];
	reverse(nega.begin(), nega.end());
	for(int i = 0; i < n; i++) if(isp[k*a[i]]) sum[i]++;
	for(int i = n - 2; i >= 0; i--)	sum[i] += sum[i+1];
	for(int i = m - 1; i >= 0; i--){
		auto ita = lower_bound(nega.begin(), nega.end(), -b[i]);
		int num = nega.end() - ita;
		res = max(res, count(b, b[i] - num + 1, b[i]) + sum[num]);
	}
	return res;
}

int main(){
	int T; for(read(T); T; T--){
		isp.clear();
		int n, m; read(n, m);
		vi a1, a2, b1, b2;
		for(int i = 1; i <= n; i++){
			int a; read(a);
			if(a < 0)	a1.pb(-a);
			else	a2.pb(a);
		}
		for(int i = 1; i <= m; i++){
			int b; read(b); isp[b] = true;
			if(b < 0)	b1.pb(-b);
			else	b2.pb(b);
		}
		reverse(a1.begin(), a1.end());
		reverse(b1.begin(), b1.end());
		printf("%d\n", solve(a1, b1, -1) + solve(a2, b2, 1));
	}
	return 0;
}

D. Dogeforces

递归。考察当前矩阵，其中的最大数必然是根结点的值，于是最大数对应的行和列必定处于根结点的不同子树中，如此我们可以得到各个叶节点所在的子树，然后分别对各子树递归处理即可。

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

int n, a[N][N], tot, fa[N], salary[N];
bool vis[N];
vi edge[N];

void dfs(int x, vi &sub){
	vis[x] = true;
	sub.pb(x);
	for(auto &to : edge[x]){
		if(vis[to])	continue;
		dfs(to, sub);
	}
}

int solve(vi v){
	if(v.size() == 1){
		salary[v[0]] = a[v[0]][v[0]];
		return v[0];
	}
	int mxa = -1;
	for(auto &i : v){
		for(auto &j : v)	mxa = max(mxa, a[i][j]);
		vis[i] = false, edge[i].clear();
	}
	for(auto &i : v)
		for(auto &j : v)
			if(a[i][j] < mxa && i != j)
				edge[i].pb(j), edge[j].pb(i);
	vector<vi> sub;
	for(auto &i : v){
		if(!vis[i]){
			sub.pb(vi());
			dfs(i, sub.back());
		}
	}
	vi ids;
	for(auto &sv : sub)	ids.pb(solve(sv));
	tot++;
	for(auto &id : ids)	fa[id] = tot;
	salary[tot] = mxa;
	return tot;
}

int main(){
	read(n); tot = n;
	vi v;
	for(int i = 1; i <= n; i++){
		v.pb(i);
		for(int j = 1; j <= n; j++)	read(a[i][j]);
	}
	solve(v);

	printf("%d\n", tot);
	for(int i = 1; i <= tot; i++)
		printf("%d ", salary[i]); puts("");
	printf("%d\n", tot);
	for(int i = 1; i <= tot - 1; i++)
		printf("%d %d\n", i, fa[i]);
	return 0;
}

E. A-Z Graph

首先，要存在这样的路径，必然至少有一对 $(u,v)$ 满足有向边 $u\to v$ 和 $v\to u$ 同时存在。

这时，如果 $k$ 是奇数，那么 $u\to v\to u\to\cdots\to v\to u$ 就是一条合法路径；

如果 $k$ 是偶数，假设 $a_1\to\cdots\to a_k$ 是一条合法路径，则必然其正中间的那条边 $u\to v$ 要和 $v\to u$ 的权重相同，也就是说存在一对 $(u,v)$ 满足 $u\to v$ 和 $v\to u$ 同时存在且相等；于是我们取 $u\to v\to\cdots\to 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
#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, m, cnt, cnteq;
map<pii, char> edge;

int main(){
	read(n, m);
	while(m--){
		char opt[10];
		scanf("%s", opt);
		if(opt[0] == '+'){
			int u, v; char c[10];
			scanf("%d%d%s", &u, &v, c);
			edge[mp(u, v)] = c[0];
			if(edge.find(mp(v, u)) != edge.end()){
				cnt++;
				if(edge[mp(v, u)] == c[0])	cnteq++;
			}
		}
		else if(opt[0] == '-'){
			int u, v; read(u, v);
			if(edge.find(mp(v, u)) != edge.end()){
				cnt--;
				if(edge[mp(v, u)] == edge[mp(u, v)])	cnteq--;
			}
			edge.erase(mp(u, v));
		}
		else{
			int u; read(u);
			if((u & 1) && cnt > 0)	puts("YES");
			else if(!(u & 1) && cnteq > 0)	puts("YES");
			else	puts("NO");
		}
	}
	return 0;
}

Educational Codeforces Round 105

http://xyfjason.github.io/blog-xcpc/2021/03/06/Educational-Codeforces-Round-105/

作者

xyfJASON

发布于

2021-03-06

更新于

2021-03-06

许可协议

#

评论

来发评论吧~
Powered By Valine
v1.4.14
关注我

分类

最新文章

标签

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