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

Educational Codeforces Round 104

比赛链接 / 官方题解链接

A. Arena

显然只有最小的数没法增大，而其他数都能无限增大。

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

int n, a[N];

int main(){
	int T; for(read(T); T; T--){
		read(n);
		for(int i = 1; i <= n; i++)	read(a[i]);
		sort(a+1, a+n+1);
		int cnt = 0;
		for(int i = 1; i <= n; i++){
			if(a[i] == a[1])	cnt++;
			else	break;
		}
		printf("%d\n", n - cnt);
	}
	return 0;
}

B. Cat Cycle

如果 $n$ 是偶数，那么 $A,B$ 永远不会冲突，答案很好计算。

否则，自上一次冲突后，$A,B$ 的下一次冲突将发生在 $\frac{n-1}{2}$ 步后，也就是说，$B$ 会先以步长为 $1$ 走 $\frac{n-3}{2}$ 次，然后以步长为 $2$ 走 $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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#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)

LL n, k;

int main(){
	int T; for(read(T); T; T--){
		read(n, k);
		if(n % 2 == 0){
			printf("%lld\n", (k - 1) % n + 1);
			continue;
		}
		if(k * 2 <= n - 1){
			printf("%lld\n", k);
			continue;
		}
		if(k * 2 == n + 1){
			printf("%lld\n", k + 1);
			continue;
		}
		k -= (n + 1) / 2;
		LL t = (n - 3) / 2;
		LL st = (n + 1) / 2 + 1;
		st += k / (t + 1) * (t + 2);
		st += k % (t + 1);
		st = (st - 1) % n + 1;
		printf("%lld\n", st);
	}
	return 0;
}

C. Minimum Ties

以步长 $1$ 转着圈赢：$1\to2,\,2\to3,\,3\to4,\ldots$；

然后以步长为 $2$ 转着圈赢：$1\to3,\,2\to4,\,3\to5,\ldots$；

然后以步长为 $3$ 转着圈赢：$1\to4,\,2\to5,\ldots$；

如果 $n$ 是奇数，这样就保证了每个点出度和入度相等；如果 $n$ 是偶数，多的出度/少的入度变成平局即可。

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)

int main(){
	int T; for(read(T); T; T--){
		int n; read(n);
		if(n & 1){
			for(int l = n - 1; l >= 1; l--)
				for(int i = 1; i <= l; i++)
					printf("%d ", i <= n / 2 ? 1 : -1);
			puts("");
		}
		else{
			for(int l = n - 1; l >= 1; l--)
				for(int i = 1; i <= l; i++)
					printf("%d ", i == n / 2 ? 0 : (i < n / 2 ? 1 : -1));
			puts("");
		}
	}
	return 0;
}

D. Pythagorean Triples

为满足 $1\leqslant a\leqslant b\leqslant c\leqslant n$，首先需要：$n\geqslant 5$，其次 $a=2k+1$ 是奇数，再次：$c=2k^2+2k+1\leqslant n$. 可以直接解方程，不过为了避免奇怪的精度问题，我这里采用二分。

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<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--){
		LL n; read(n);
		if(n < 5){ printf("%d\n", 0); continue; }
		LL l = 1, r = n;
		while(l < r){
			LL mid = (l + r + 1) >> 1;
			if(2 * mid * mid + 2 * mid + 1 <= n)	l = mid;
			else	r = mid - 1;
		}
		printf("%lld\n", l);
	}
	return 0;
}

E. Cheap Dinner

按当前代价顺序考虑当前层的点，向下一层可以转移到的点转移即可。使用堆进行处理，由于每个点最多转移一次，每个限制条件最多被遍历一次，所以转移个数是 $O(n+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
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 = 150005;

int n1, n2, n3, n4, a[N], b[N], c[N], d[N], m[5];
set<int> edge[5][N];
set<int> s1, s2, s3, s4;

int main(){
	read(n1, n2, n3, n4);
	for(int i = 1; i <= n1; i++)	read(a[i]), s1.insert(i);
	for(int i = 1; i <= n2; i++)	read(b[i]), s2.insert(i);
	for(int i = 1; i <= n3; i++)	read(c[i]), s3.insert(i);
	for(int i = 1; i <= n4; i++)	read(d[i]), s4.insert(i);
	for(int i = 1; i <= 3; i++){
		read(m[i]);
		for(int j = 1; j <= m[i]; j++){
			int u, v; read(u, v);
			edge[i][u].insert(v);
		}
	}
	priority_queue< pii, vector<pii>, greater<pii> > q, tmp1, tmp2, tmp3;
	for(int i = 1; i <= n1; i++)	q.push(mp(a[i], i));
	
	while(!q.empty()){
		pii cur = q.top(); q.pop();
		vi ers;
		for(auto &elem : s2){
			if(edge[1][cur.second].find(elem) == edge[1][cur.second].end()){
				tmp1.push(mp(cur.first + b[elem], elem));
				ers.pb(elem);
			}
		}
		for(auto &e : ers)	s2.erase(e);
		if(s2.empty())	break;
	}
	q = tmp1;

	while(!q.empty()){
		pii cur = q.top(); q.pop();
		vi ers;
		for(auto &elem : s3){
			if(edge[2][cur.second].find(elem) == edge[2][cur.second].end()){
				tmp2.push(mp(cur.first + c[elem], elem));
				ers.pb(elem);
			}
		}
		for(auto &e : ers)	s3.erase(e);
		if(s3.empty())	break;
	}
	q = tmp2;

	while(!q.empty()){
		pii cur = q.top(); q.pop();
		vi ers;
		for(auto &elem : s4){
			if(edge[3][cur.second].find(elem) == edge[3][cur.second].end()){
				tmp3.push(mp(cur.first + d[elem], elem));
				ers.pb(elem);
			}
		}
		for(auto &e : ers)	s4.erase(e);
		if(s4.empty())	break;
	}
	q = tmp3;

	if(q.empty())	puts("-1");
	else	printf("%d\n", q.top().first);
	return 0;
}

Educational Codeforces Round 104

http://xyfjason.github.io/blog-xcpc/2021/02/17/Educational-Codeforces-Round-104/

作者

xyfJASON

发布于

2021-02-17

更新于

2021-02-17

许可协议

#

评论

关注我

分类

最新文章

标签

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