Codeforces Round #829 (Div. 2)部分题解A B C1 E

原题地址：Dashboard - Codeforces Round #829 (Div. 2) - Codeforces

A. Technical Support

题意：

有一个只包含“Q”和"A"的字符串，Q代表问题，A代表回答，有问必有答，也就是Q后面一定有n个A（n>=0）

代码：

#include<bits/stdc++.h> 
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<string.h> 
#include<map>
typedef long long ll;
using namespace std;
const int N = 2e5+10;
ll a[N],b[N],c[N];
//string s1[N],s2[N],s3[N];
int main(void)
{int t;cin >> t;while(t--){int n;cin >> n;string s;cin >> s;int c1=0,c2=0;for(int i=0;i<n;i++){if(s[i]=='Q')c1++;elsec2++;}//如果Q比A多if(c1>c2)cout << "no" << endl;else{int cc=0;//cc表示当前有多少个Qfor(int i=0;i<n;i++){//遇到Q,cc++if(s[i]=='Q'){cc++;}//遇到A，cc--表示解决了多少个Qelse{cc--;if(cc<=0)cc=0;}}//最后如果cc>0，表示问题没有解决完，输出NOif(cc>0){cout << "no" << endl;}elsecout << "yes" << endl;} } return 0;}

B. Kevin and Permutation

题意：

给定一个长度为n的序列，元素值包含1~n,让你通过改变顺序使俩个数字只差的最小值最大.

当n等于偶数时,如n = 6时,原序列看成 1 2 3 4 5 6,我们可以变成 3 6 2 5 1 4一组,这样就能保证最大

当n等于奇数时,如n = 7时,原序列看出 1 2 3 4 5 6 7 ，我们可以拿出中间的元素4，然后剩下的6个,按照 7 3 6 2 5 1 4 中间数字4放在最后的顺序排序即可

代码：

#include<bits/stdc++.h> 
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<string.h> 
#include<map>
typedef long long ll;
using namespace std;
const int N = 2e5+10;
int a[N],b[N],c[N];
//string s1[N],s2[N],s3[N];
int main(void)
{int t;cin >> t;while(t--){int n;cin >> n;for(int i=1;i<=n;i++)a[i] = i;int i1 = 1;if(n%2){int i2 = n;int i3 = n/2;int index = n/2+1;while(i2>index){b[i1] = a[i2];b[i1+1] = a[i3];i1 += 2;i2--;i3--;}b[n] = a[index];}else{int i2=n/2;int i3 = n;int index = n/2;while(i2>=1){b[i1] = a[i2];b[i1+1] = a[i3];i1+=2;i2--;i3--;}}for(int i=1;i<=n;i++)cout << b[i] << " ";cout << endl;} return 0;}

C1. Make Nonzero Sum (easy version)

题意：

给定一个只包含1和-1的序列，将他们分成任意个字串,最后所以字串加起来之和等于0.

我的思路是

首先确保长度n为偶数，因为n为奇数时，怎么变换都不能得到0，输出-1。

当遇到偶数个元素相同时,比如 s = 1 1 1 1,那么直接将这四个合并即可等于0,

当遇到元素不同的分界点时，分俩种情况

第一种情况：

如s = 1 1 1 1 -1 1时,第4，5个元素是1和-1,因为前面有四个1即偶数个1，那我们就先合并前面4个1，然后第5个元素-1,第六个元素是1，那么它们就各成一个字串1和-1，保证它们相加等于0

如果第五个元素是-1，第六个元素是-1,它们相同，那么就将它们俩个合成一个字符-1 -1即可。

第二种情况：

如s = 1 1 1 -1 1 1时,第3,4个元素是1和-1,因为前面只有三(奇数)个1，所以我们选择合并前俩个1，然后3,4号位置各自成一个字串1和-1，保证它们相加等于0即可

代码：

#include<bits/stdc++.h> 
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<string.h> 
#include<map>
typedef long long ll;
using namespace std;
const int N = 2e5+10;
int a[N],b[N][2];//b[i][0]代表字串的左下标,b[i][1]代表字串的右下标
//string s1[N],s2[N],s3[N];
int main(void)
{int t;cin >> t;while(t--){int n;cin >> n;for(int i=1;i<=n;i++){cin >> a[i];}if(n%2)cout << "-1" << endl;else{int index=1;int l=1,r=0;//L表示当前待处理下标，r表示字串的长度int num=0;int flag=1;for(int i=1;i<=n;i++){if(flag==1){num = a[i];l=i;r=1;flag=0;continue;}if(a[i]!=num){if(r%2){if(r!=1){b[index][0] = l;b[index][1] = l+r-2;index++;}b[index][0] = i-1;b[index][1] = i-1;index++;b[index][0] = i;b[index][1] = i;index++;l = i+1;flag=1;}else{b[index][0] = l;b[index][1] = i-1;index++;l = i;}num = a[i];r = 1;}else{r++;}}//如果l没有处理完if(l<n){//	cout << l << " " << r << endl;b[index][0] = l;b[index][1] = n;index++;}cout << index-1 << endl;for(int i=1;i<index;i++){cout << b[i][0] << " " << b[i][1] << endl;}}} return 0;}

D. Factorial Divisibility

题意:

给定一个长度为n的数组a，让里面每一个元素的ai的阶乘相加的结果是否能够整除给定x的阶乘。所以思路是模拟里面的数组a的各个元素相加，如3 3 3 2 2 2,有3个2的阶乘加起来就是3!,然后四个3！加起来等于4!,那么现在x = 4时,就可以整除,如果数组a变为3 3 3 2 2 2 1,那么相加就变成4!+1!，x=4时就不能够整除，因为有1！的干扰,所以我们只要遍历一下小于x时有无干扰即可

代码：

#include<bits/stdc++.h> 
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<string.h> 
#include<map>
typedef long long ll;
using namespace std;
const int N = 5e5+10;
int a[N],b[N];
//string s1[N],s2[N],s3[N];
int main(void)
{int n,x;scanf("%d%d",&n,&x);int maxn=0;for(int i=1;i<=n;i++){int num;scanf("%d",&num);a[num]++;}for(int i=1;i<=5e5;i++){//cout << a[i] << endl;a[i+1] += a[i]/(i+1);a[i] = a[i]%(i+1);}int flag=1;for(int i=1;i<x;i++){if(a[i]!=0){//cout << i << " " << a[i] << endl;flag=0;break;}}if(flag)cout << "Yes" << endl;elsecout << "No" << endl;return 0;}

接下来我想求助一下大佬们这题为什么我的思路或者代码哪里错了，如果有的话万分感谢

C2. Make Nonzero Sum (hard version)

我的思路：

就是俩个俩个的去组合，首先先计算0的个数c0，如果n-c0是奇数，输出-1.

然后如果遇到1 1或-1,-1俩个相同的，则直接合并

遇到1 -1俩个不相同的，就各成字串,保证相加等于0

当遇到0时分为俩种情况

第一种情况

是前面的已经处理完了，如s = 1 1 1 1 0,前面四个已经合并完成，那么第五个0，则直接自成字串即可

第二种情况

是前面的未处理，如 s = 1 0 1，那么此时可以变成俩个字串 "1"和"0 1"让它们和等于0，如果是 s = 1 0 -1,此时可以变成三个字串"1" ,"0","-1"使它们和为0.

还有一种特殊情况

如s = 1 0 0 0 1,那么此时前俩个0是不用管的，即变成4个字串 "1"，“0”,"0","0 1"即可

我的提交错误代码：

#include<bits/stdc++.h> 
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<string.h> 
#include<map>
//typedef long long ll;
using namespace std;
const int N = 5e5+10;
int a[N],b[N];
int r[N][2];
//string s1[N],s2[N],s3[N];
int main(void)
{int t;cin >> t;while(t--){int n;cin >> n;int c0 = 0;for(int i=1;i<=n;i++){cin >> a[i];if(a[i]==0)c0++;}if((n-c0)%2){cout << "-1" << endl;}else{int flag=1;int index=1;int num=0;int ll=1;//ll表示待处理的下标int len0 = 0;//表示中间多余0的个数，如1 0 0 0 -1中间多余0为2个for(int i=1;i<=n;i++){if(a[i]==0){//如果前面已经处理完，则此时0直接自成字串if(i<=ll){r[index][0] = i;r[index][1] = i;num++;index++;ll = i+1;continue; }if(a[i+1]==0){len0++;}else{if(a[ll] == a[i+1]){r[index][0] = ll;r[index][1] = ll;index++;num++;for(int j=1;j<=len0;j++){r[index][0] = ll+j;r[index][1] = ll+j;index++;num++;}r[index][0] = i;r[index][1] = i+1;index++;num++;ll = i+2;i++;}else{r[index][0] = ll;r[index][1] = ll;index++;num++;for(int j=1;j<=len0;j++){r[index][0] = ll+j;r[index][1] = ll+j;index++;num++;}r[index][0] = i;r[index][1] = i;index++;num++;r[index][0] = i+1;r[index][1] = i+1;index++;num++;ll = i+2;i++;}}}else{if(a[i+1] == 0){ll = i;continue;}if(a[i+1]!=a[i]){r[index][0] = i;r[index][1] = i;index++;num++;r[index][0] = i+1;r[index][1] = i+1;index++;num++;ll = i+2;i++;}else{r[index][0] = i;r[index][1] = i+1;index++;num++;ll = i+2;i++;}}}cout << num << endl;for(int i=1;i<index;i++){cout << r[i][0] << " " << r[i][1] << endl;}}} return 0;}