Codeforces Round #829 (Div. 2)

A. Technical Support

题目链接：Problem - A - Codeforces

样例输入：

5
4
QQAA
4
QQAQ
3
QAA
1
Q
14
QAQQAQAAQQQAAA

样例输出：

Yes
No
Yes
No
Yes

题意：给定一个长度为n的字符串，字符串中的所有字符都是Q或者A，Q代表一次询问，A代表回答问题，一次询问可以对应着多次回答，问这个字符串是否满足每个询问都被回答了

分析：容易发现，对于任意位置我们都需要满足从当前位置开始的询问数目是要小于等于回答次数的，否则在此之后一定至少存在一次询问是没有回答的，按照这个方法我们直接从1~n遍历一边即可。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int N=2e5+10;
char s[N];
int main()
{int T;cin>>T;while(T--){int n;scanf("%d",&n);scanf("%s",s+1);bool flag=true;int cntq=0,cnta=0;for(int i=1;i<=n;i++)if(s[i]=='Q') cntq++;else cnta++;for(int i=1;i<=n;i++){if(cnta<cntq){flag=false;break;}if(s[i]=='Q') cntq--;else cnta--;}if(flag) puts("YES");else puts("NO");}return 0;
}

B. Kevin and Permutation

题目链接：Problem - B - Codeforces

样例输入：

2
4
3

2 4 1 3
1 2 3

题意：给定一个n，让我们构造一个1~n的排列使得的值最大。

分析：对于这种题目我们分类讨论一下就行：
对于n是偶数的情况，我们直接按照如下方式构造：

n/2,(n/2+n/2),(n/2-1),(n/2-1+n/2)……,1,(1+n/2)

对于n是奇数的情况，我们直接让n在第一个位置，然后剩下的就按照偶数的方式构造即可。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int N=2e5+10;
int main()
{int T;cin>>T;while(T--){int n;scanf("%d",&n);if(n&1){printf("%d ",n);for(int i=n/2;i>=1;i--)printf("%d %d ",i,i+n/2);puts("");}else{for(int i=n/2;i>=1;i--)printf("%d %d ",i,i+n/2);puts("");}}return 0;
}

C1. Make Nonzero Sum (easy version)

题目链接：Problem - C1 - Codeforces

样例输入：

4
4
1 1 1 1
6
-1 1 1 1 1 1
3
1 -1 1
1
1

样例输出：

题意：给定一个长度为n的数组a,里面的元素全部都是1或者-1，让我们把这个长度为n的区间分为若干个不相交的区间，区间总长度和是n，使得所有区间的贡献和为0，每个区间的贡献计算规则：当前位置的权值乘以1或者-1再求和，如果当前位置相对于区间起始位置的长度是奇数，那么就乘以1，否则乘以-1.

分析：我们首先把这n个数中的每一个数都单独看成一个区间，这个时候我们计算一下当前情况下的总贡献，如果总贡献为0，那我们就把每个数单独看成一个区间即可。我们可以发现的一点是如果当前点贡献由1变为-1，那么总贡献就减少2，如果贡献由-1变为1，那么总贡献就增加2，总之贡献的变化一定是偶数，所以对于总贡献是奇数的情况我们直接输出-1即可。

下面以总贡献为正数的情况进行分析：

我们的目的是要降低总贡献，所以当遇到一个1满足其左边的一个数不被某个已操作区间包含的话那么我们就可以把这两个数看成一个区间进行一次操作，这样我们就能够使得总贡献-2，按照这个思路我们使得总贡献减少至0即可。这样我们就记录下了长度为2的操作区间，1~n中不被包含的数都是独自成一个区间的，最后直接进行输出即可

总贡献为负数的情况与上面正好相反，这里就不赘述了

细节见代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int N=2e5+10;
int a[N],l[N],r[N];
int main()
{int T;cin>>T;while(T--){int n;scanf("%d",&n);int ans=0;for(int i=1;i<=n;i++)scanf("%d",&a[i]),ans+=a[i];int tt=0;if(ans&1){puts("-1");continue;}else if(ans>0){for(int i=2;i<=n;i++){if(a[i]==1){ans-=2;l[++tt]=i-1;r[tt]=i;i++;}if(!ans) break;}}else if(ans==0){printf("%d\n",n);for(int i=1;i<=n;i++)printf("%d %d\n",i,i);puts("");continue;}else{for(int i=2;i<=n;i++){if(a[i]==-1){ans+=2;l[++tt]=i-1;r[tt]=i;i++;}if(!ans) break;}}if(r[tt]!=n){int p=tt;for(int i=r[p]+1;i<=n;i++)l[++tt]=i,r[tt]=i;}if(l[1]!=1) for(int i=1;i<l[1];i++)l[++tt]=i,r[tt]=i;sort(l+1,l+tt+1);sort(r+1,r+tt+1);n=tt;for(int i=2;i<=n;i++)if(l[i]!=r[i-1]+1)for(int j=r[i-1]+1;j<l[i];j++)l[++tt]=j,r[tt]=j;sort(l+1,l+tt+1);sort(r+1,r+tt+1);printf("%d\n",tt);for(int i=1;i<=tt;i++)printf("%d %d\n",l[i],r[i]);}return 0;
}

C2. Make Nonzero Sum (hard version)

题目链接：Problem - C2 - Codeforces

样例输入：

5
4
0 0 0 0
7
-1 1 0 1 0 1 0
5
0 -1 1 0 1
3
1 0 1
1
1

样例输出：

题意：给定一个长度为n的数组a,里面的元素全部都是1或者-1或者0，让我们把这个长度为n的区间分为若干个不相交的区间，区间总长度和是n，使得所有区间的贡献和为0，每个区间的贡献计算规则：当前位置的权值乘以1或者-1再求和，如果当前位置相对于区间起始位置的长度是奇数，那么就乘以1，否则乘以-1.

分析：这道题与上一道题的唯一区别就是这道题的数组元素含有0，但是我们能够发现0根本不影响我们的贡献，所以我们还是按照同样的思路进行分析即可，代码是完全相同的

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int N=2e5+10;
int a[N],l[N],r[N];
int main()
{int T;cin>>T;while(T--){int n;scanf("%d",&n);int ans=0;for(int i=1;i<=n;i++)scanf("%d",&a[i]),ans+=a[i];int tt=0;if(ans&1){puts("-1");continue;}else if(ans>0){for(int i=2;i<=n;i++){if(a[i]==1){ans-=2;l[++tt]=i-1;r[tt]=i;i++;}if(!ans) break;}}else if(ans==0){printf("%d\n",n);for(int i=1;i<=n;i++)printf("%d %d\n",i,i);puts("");continue;}else{for(int i=2;i<=n;i++){if(a[i]==-1){ans+=2;l[++tt]=i-1;r[tt]=i;i++;}if(!ans) break;}}if(r[tt]!=n){int p=tt;for(int i=r[p]+1;i<=n;i++)l[++tt]=i,r[tt]=i;}if(l[1]!=1) for(int i=1;i<l[1];i++)l[++tt]=i,r[tt]=i;sort(l+1,l+tt+1);sort(r+1,r+tt+1);n=tt;for(int i=2;i<=n;i++)if(l[i]!=r[i-1]+1)for(int j=r[i-1]+1;j<l[i];j++)l[++tt]=j,r[tt]=j;sort(l+1,l+tt+1);sort(r+1,r+tt+1);printf("%d\n",tt);for(int i=1;i<=tt;i++)printf("%d %d\n",l[i],r[i]);}return 0;
}

D. Factorial Divisibility

题目链接：Problem - D - Codeforces

样例输入：

6 4
3 2 2 2 3 3

样例输出：

Yes

题意：给定一个x，和一个长度为n的数组a,问是否满足 $\sum_{i=1}^{n}(a[i]!)$ %(x!)==0

分析：这里需要注意一个不等式： $\sum_{i=1}^{n-1}(i*i!)<n!$

下面用归纳法证明这个结论：

当n=2时显然有1*1！<2!

那么我们假设当n=k时有结论成立，那么对于n=k+1时

有 $\sum_{i=1}^{k-1}(i*i!)$ +k*k!<(k!)+k*k!

即 $\sum_{i=1}^{k+1}(i*i!)$ <(k+1)!

证毕

那么我们发现对于a[i]>=x的位置我们没必要进行统计，因为这个数对x！取余的结果是0，不影响最后的余数，所以我们就用一个cnt统计一下所有的a[i]<x的出现次数，然后对于出现次数大于i+1次的i!，我们就可以转化为一个(i+1)！，按照这个思路我们就可以把所有的i<x的位置全部算出最终代价，通过上面的不等式我们可以发现就算所有的阶乘都满阶，也是小于x!的，所以也就是说对于所有的i<x,如果i!出现次数如果不为0，那么最后对x！取余的结果和一定是小于x且不为0的，所以一定不可能整除，否则就可以整除。

细节见代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int N=5e5+10;
int cnt[N];
int main()
{int n,x;cin>>n>>x;for(int i=1;i<=n;i++){int t;scanf("%d",&t);cnt[t]++;}for(int i=0;i<x;i++){cnt[i+1]+=cnt[i]/(i+1);cnt[i]%=(i+1);}bool flag=true;for(int i=0;i<x;i++)if(cnt[i]){flag=false;break;}if(flag) puts("YES");else puts("NO");return 0;
}