你最愿意做的哪件事，才是你的天赋所在

0%

Codeforces Round #632 (Div. 2)

发表于 Valine：

题目链接

Codeforces Round #632 (Div. 2)
当时被C题卡了很久，最后20分钟把D的思路想好了却想不到把答案输出的方法，还是思维转变不够快的原因

A

思路

构造题，发现只要构造出

wb
bw

这种[2,2]的形状就可以了

代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n,m;
		scanf("%d %d",&n,&m);
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				if(i==0&&j==0)printf("W");
				else printf("B");
			}
			printf("\n");
		} 
	}
}

B

思路

我们发现从后面往前面找的话，比较b数组当前的值与a数组的值，大的话找-1，小的话找1即可，维护一个-1的个数和1的个数，如果需要却找不到的情况就输出NO，其他就YES即可

代码实现
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;
#define ll long long
const int N =1e5+10;
int a[N];
int b[N];
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		int add=0,sub=0;
		for(int i=0;i<n;i++){
			scanf("%d",&a[i]);
			if(a[i]==-1)sub++;
			else if(a[i]==1)add++;
		}
		bool flag = 0;
		for(int i=0;i<n;i++)scanf("%d",&b[i]);
		for(int i=n-1;i>=0;i--){
			if(a[i]==1)add--;
			else if(a[i]==-1)sub--;
			if(b[i]==a[i])continue;
			if(b[i]<a[i]&&sub==0){
				flag=1;
				break;
			}
			if(b[i]>a[i]&&add==0){
				flag=1;
				break;
			}
		}
		if(!flag)printf("YES\n");
		else printf("NO\n");
	}
}

C

思路

用队列写这道题，考虑第k个加入队列中，能否满足所有子序列都不等于零，但是有可能出现这种情况1 2 3 -5的话，它仅仅中间一段为0，即｛2，3，-5｝,处理这种情况的时候使用前缀和，只要前缀和相等，那么中间这一段肯定不可，就pop直到剩下最左端点的右边一个。上述情况就要pop到[3,-5]了，用一个pos数组记录与当前点前缀和相等的最左端最接近的点，然后再出栈的时候判断即可。

代码实现
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;
#define ll long long
const int N = 2e5+10;
int a[N];
int pos[N];
map<ll,int>mp;
struct node{
	int pos;
	int num;
	node(){}
	node(int pos_,int num_){
		pos=pos_;
		num=num_;
	}
};
queue<node>st;
int main(){
	int n;
   	scanf("%d",&n);
   	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
   	ll sum = 0;
   	for(int i=1;i<=n;i++){
   		sum+=a[i];
   		if(mp[sum])pos[i]=mp[sum];
   		mp[sum]=i+1;
	}
   	ll ans=0,now=0;
   	for(int i=1;i<=n;i++){
   		now+=a[i];
   		if(pos[i]!=-1){
   			while(!st.empty()&&st.front().pos<=pos[i])
			   {
			   	st.pop();
			   }
		}
   		if(a[i]==0){
   			now=0;
   			while(!st.empty())st.pop();
   			continue;
		}
   		while(now==0&&!st.empty()){
   			node t= st.front();
   			now-=t.num;st.pop();
		}
		ans+=st.size()+1;
		st.push(node(i,a[i]));
	}
   	printf("%lld\n",ans);
}

D

思路

题意就是给一个序列RL组成，然后RL可以交换位置，每一秒可以选择多个交换，目的就是把L全部移动到左边，很显然，序列长度仅2000，这样的话我们就可以暴力，最多的次数就是RRRRLLLL这种情况，不超过2000*2000，就模拟这种操作，得到命令的序列，输出答案的时候，如果k大于所需要的步数，我们就从前面拆，一步一步走，当k==当前所需要的步数时，我们就输出答案。

代码实现
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;
#define ll long long
vector<int>ans[4000000];
vector<int>tans;
vector<pair<int,int>>sw;
char s[3050];
int main(){
   	int n,k;
   	scanf("%d %d",&n,&k);
   	scanf("%s",s+1);
   	int mx=0,sum=0,now=1,cnt=0;
   	bool flag=true;
   	while(flag){
   		flag=false;
   	for(int i=n;i>=1;i--){
   		if(s[i]=='L'&&s[i-1]=='R'){
   			sw.push_back(make_pair(i,i-1));
   			flag=true;
   		if(i!=now)ans[mx].push_back(i-1);	
		}
	}
	for(auto k:sw){
		swap(s[k.first],s[k.second]);
	}
	sw.clear();
	if(flag)
	sum+=ans[mx++].size();
    }
	if(k<mx||k>sum)return 0*printf("-1");
	int i=0,j=0;
	while(k!=mx-i){
		printf("1 %d\n",ans[i][j]);
		k--;
		j++;
		if(j==ans[i].size())i++,j=0;
	}
	for(int p=i;p<mx;p++){
		if(p==i){
			printf("%d ",ans[p].size()-j);
		    for(int s=j;s<ans[p].size();s++)printf("%d ",ans[p][s]);
		    printf("\n");
		}
		else {
			printf("%d ",ans[p].size());
			for(auto k:ans[p])printf("%d ",k);
			printf("\n");
		}
	}
}

F

思路

考虑长度为n的序列，值肯定为n/2，然后我们考虑n-1的序列，也就是从n的序列中删除一个数字，我们贪心的删除长度为n序列中含有(n/2)这个因子的最大值，例如52的序列中，我们就删除52，然后剩下51的gcd最大值为25，我们就删除n中含有银子25的最大的数50
为什么删除最大的数？，因为我们要使得当前的权变小，肯定权的倍数，倍数越大，那么之后剩余的选择就越少。
如果按照上述的直接做法，复杂度应该是炸的，我们就考虑正面做，考虑小于等于n/2的值作为最大因子出现在序列中的个数，然后从后往前减去即可，例如num[16]=2而不是等于3是因为16 32是1️以16为最大因子的，而48则是以24为最大因子的。处理出这个数组就可以找到答案了，具体操作看代码。

代码实现
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;
#define ll long long
const int N = 5e5+10;
int num[N];
int ans[N];
bool vis[N];
int main(){
	int n;
	scanf("%d",&n);
	for(int i=n/2;i>=2;i--){
		int cnt = 1;
		while(cnt*i<=n&&cnt<=i){
			if(!vis[cnt*i]){
				num[i]++;
				if(cnt!=1)vis[cnt*i]=1;
			}
			cnt++;
		}
	} 
	int now = n/2;
	for(int i=n;i>=2;i--){
		ans[i]=now;
		num[now]--;
		if(num[now]==1&&now!=1)now--;
	}
	for(int i=2;i<=n;i++)printf("%d ",ans[i]);
}
-------------你最愿意做的哪件事才是你的天赋所在-------------