Codeforces Round #788 (Div. 2)

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

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

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

D. Very Suspicious

Sample input
4
1
2
3
4567

Sample output
2
2
3
83

题意：

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

思路：

一开始根本没思路，后来自己在画图上贪心的画了一下，看下图

这种隔一个半的是最优的，然后发现又跟三的倍数有关系，就可以发现一个现象，这里面的线可以分成三类，横线，左斜线，右斜线，你每画一条线，多出来的等边三角形就是其他两类的线的和的两倍，那么就可以用一个递推的方式来解决，下面请看代码：

#include
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;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22