首页 > 编程学习 > Codeforces Round #788 (Div. 2)

Codeforces Round #788 (Div. 2)

发布时间:2022/10/1 22:16:00

A. Prof. Slim

在这里插入图片描述
Sample input
4
7
7 3 2 -11 -13 -17 -23
6
4 10 25 47 71 96
6
71 -35 7 -4 -11 -25
6
-45 9 -48 -67 -55 7

Sample output
NO
YES
YES
NO

题意:

给你一个长度为n的数组,每个元素都是不为0的数,你可以执行一步操作将这个数组的两个数的正负号互换,现在问你能不能通过无限次的交换使得这个数组是一个不降的

思路:

一定是把负号都交换到最前面,就统计一下负数的数量为cnt,前cnt个数的绝对值一定是不升的,从cnt+1到n的数一定是不降的,那么这个数组就是YES,否则就是NO,代码如下:

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
void solve(){
	int n,cnt=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		cnt += (a[i] < 0);
	}
	for(int i=1;i<cnt;i++){
		if(abs(a[i]) < abs(a[i+1])){
			puts("NO");
			return;
		}
	}
	for(int i=cnt+1;i<n;i++){
		if(abs(a[i]) > abs(a[i+1])){
			puts("NO");
			return;
		}
	}
	puts("YES");
}
int main(){
	int _;
	for(cin>>_;_;_--) solve();
	return 0;
} 

B. Dorms War

在这里插入图片描述
Sample input:
10
9
iloveslim
1 s
7
joobeel
2 o e
7
basiozi
2 s i
6
khater
1 r
7
abobeih
6 a b e h i o
5
zondl
5 a b c e f
6
shoman
2 a h
7
shetwey
2 h y
5
samez
1 m
6
mouraz
1 m

Sample output:
5
2
3
5
1
0
3
5
2
0

题意:

你有一个长度为n的字符串,还有k(k<=26)个特殊字符,每一秒这个字符串里面特殊字符的前一个字符都会被消除,问多少秒之后字符串就是永恒不变的了

思路:

做法就是找出每两个相邻的特殊字符之间的最大距离,因为会发现到了最后的时候只剩下的是最后一个特殊字符了,最后那个特殊字符它能消灭的字符就是那个最长的区间,这个可以当做是继承的关系,就是假设本来字母x要消灭10个字符,字母y消灭了5个之后就把x这个字母给消灭掉了,那么剩下的5个还是让字母y收拾,所以说字母y最后也是消灭了10个字符。还有需要注意的是默认最前面有一个特殊字符,下面请看代码吧:

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N],mp[200];
char s[N];
void solve(){
	int n,cnt=0;
	scanf("%d%s",&n,s+1);
	int tt;
	scanf("%d",&tt);
	for(int i=0;i<26;i++) mp['a'+i] = 0;
	for(int i=1;i<=tt;i++){
		char s[2];
		scanf("%s",s);
		mp[*s] = 1;
	}
	int ans = 0,l = 1;
	for(int i=1;i<=n;i++){
		if(mp[s[i]]) ans = max(ans,i-l),l = i;
	}
	printf("%d\n",ans);
}
int main(){
	int _;
	for(cin>>_;_;_--) solve();
	return 0;
} 

C. Where is the Pizza?

在这里插入图片描述
Sample input
9
7
1 2 3 4 5 6 7
2 3 1 7 6 5 4
2 0 1 0 0 0 0
1
1
1
0
6
1 5 2 4 6 3
6 5 3 1 4 2
6 0 0 0 0 0
8
1 6 4 7 2 3 8 5
3 2 8 1 4 5 6 7
1 0 0 7 0 3 0 5
10
1 8 6 2 4 7 9 3 10 5
1 9 2 3 4 10 8 6 7 5
1 9 2 3 4 10 8 6 7 5
7
1 2 3 4 5 6 7
2 3 1 7 6 5 4
0 0 0 0 0 0 0
5
1 2 3 4 5
1 2 3 4 5
0 0 0 0 0
5
1 2 3 4 5
1 2 3 5 4
0 0 0 0 0
3
1 2 3
3 1 2
0 0 0

Sample output
4
1
2
2
1
8
1
2
2

题意:

现在有三个长度为n的数组a,b,d,你需要构造出一个C数组,其中Ci = ai 或者是bi,a,b,c数组都为排列,d数组表示的是当前c数组已经填上的值,di为0表示ci还是未知的,否则就是di表示的数,现在问你有多少种构造方法。

思路:

先来看两个数组:
1 2 3 4 5
2 3 4 5 1
因为满足的是ai和bi其中的一个,所以说这种情况的话如果说有一个数是确定的,那么其他数也都确定了。就只有一种情况,但是如果都没有确定的话就是两种情况,那么就会发现一个现象, 就是长度为n的a,b数组中,能以这种循环的形式划分成一段段区间,每一段区间都是循环的,那么对于每一个区间只需要统计一下是否有数是确定的就行,统计的时候可以用并查集来做,下面请看代码:

#include<bits/stdc++.h>
using namespace std;
const int N = 100010,mod = 1e9+7;
int a[N],b[N],d[N];
int fa[N],ans[N],cnt[N];
int find(int x){
	if(x != fa[x]) fa[x] = find(fa[x]);
	return fa[x];
}
void solve(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int t;
		scanf("%d",&t);
		a[t] = i;
		fa[i] = i;
		cnt[i] = 1;
	}
	for(int i=1;i<=n;i++){
		int t;
		scanf("%d",&t);
		b[t] = i;
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&d[i]);
	}
	int idx = 0;
	for(int i=1;i<=n;i++){
		int u = find(a[i]);
		int v = find(b[i]);
		fa[v] = u;
		cnt[u] += cnt[v];
	}
	for(int i=1;i<=n;i++){
		if(cnt[find(i)] > 2) ans[find(i)] = 2;
		else ans[find(i)] = 1;
	}
	for(int i=1;i<=n;i++){
		if(d[i] > 0) ans[find(i)] = 1;
	}
	int res = 1;
//	printf("res = %d\n",res);
	for(int i=1;i<=n;i++){
		res = 1ll*res*ans[find(i)]%mod;
		ans[find(i)] = 1;
//		printf("i = %d ans[i] = %d\n",i,ans[i]);
	}
	printf("%d\n",res);
}
int main(){
	int _;
	for(cin>>_;_;_--) solve();
	return 0;
} 

D. Very Suspicious

在这里插入图片描述
Sample input
4
1
2
3
4567

Sample output
2
2
3
83

题意:

现在给你一个无边界的由正六边形组成的网格,每一次询问给出你一个x,问你最少需要画多少条线才能构成至少x个等边三角形

思路:

一开始根本没思路,后来自己在画图上贪心的画了一下,看下图
在这里插入图片描述
这种隔一个半的是最优的,然后发现又跟三的倍数有关系,就可以发现一个现象,这里面的线可以分成三类,横线,左斜线,右斜线,你每画一条线,多出来的等边三角形就是其他两类的线的和的两倍,那么就可以用一个递推的方式来解决,下面请看代码:

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
long long sum[N],cnt[3],n;
void solve(){
	int x;
	scanf("%d",&x);
	int ans = lower_bound(sum+1,sum+1+n,x) - sum;
	printf("%d\n",ans);
}
int main(){
	for(int i=1;i<N;i++){
		int u = i%3;
		cnt[u]++;
		sum[i] = cnt[(u+1)%3]*2 + cnt[(u+2)%3]*2 + sum[i-1];
		n = i;
		if(sum[i] > 1e9) break;
	}
	int _;
	for(cin>>_;_;_--) solve(); 
	return 0;
} 
Copyright © 2010-2022 kler.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号