Preface
难得有下午的CF，而且是连着两场！
但是可惜第二场要去做四级模拟打不了了有点可惜（妈的听力错9个属实逆天）
这场是手速场，但对于我这种纯老年人来说WA两发加上写的慢还是掉分了，而且错估了E的难度看了一眼就摸鱼去了，本来最后半个小时应该可以Rush出来的（今天上大英的时候两下就想出来了）
唉连着掉了好几场分了，能不能支棱起来啊
A. Technical Support
SB题，统计下到每个时刻Q减去A的数量，如果是负数就归到\(0\)，最后看下是否有多余的Q剩下即可
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=105;
int t,n; char s[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; int pfx=0; for (scanf("%d%s",&n,s+1),i=1;i<=n;++i)
{
pfx+=s[i]=='A'?1:-1; if (pfx>0) pfx=0;
}
if (pfx<0) puts("No"); else puts("Yes");
}
return 0;
}
B. Kevin and Permutation
刚开始奇数的情况弱智了，写了个暴力拍了一下才发现
首先考虑偶数的情况，考虑令\(x=\frac{n}{2},y=\frac{n}{2}+1\)，则不难发现我们可以进行如下构造：
接下来考虑下奇数的情况，只要把\(1\)单独拿出来，把后面的\(n-1\)个数按偶数的做法做一遍，做后把\(1\)放到最后面即可
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=1005;
int t,n,a[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; if (scanf("%d",&n),n&1)
{
int k=2; for (a[1]=1,i=n-1;i;i-=2) a[i]=k++;
for (i=n;i>1;i-=2) a[i]=k++;
} else
{
int k=n>>1; for (i=1;i<=n;i+=2) a[i]=k--;
for (k=(n>>1)+1,i=n;i;i-=2) a[i]=k++;
}
for (i=1;i<=n;++i) printf("%d%c",a[i]," \n"[i==n]);
}
return 0;
}
C1. Make Nonzero Sum (easy version)&&C2. Make Nonzero Sum (hard version)
感觉C1和C2没什么区别啊，直接讲C2的做法了
首先不难发现区间的长度只能是\(1/2\)，更长的区间肯定可以分成这两种
初始时不妨假设所有区间长度都是\(1\)，统计出此时的总和为\(sum\)
不难发现若\(sum<0\)，我们可以对所有数字取反，现在只要考虑\(sum\ge 0\)的情况
首先我们发现每次进行取反不会改变奇偶性，因此若\(sum\)为奇数，显然是无解的
考虑此时我们需要把若干个\(1\)变成\(-1\)，但是不能修改连续的两个位置
因此直接贪心即可，从前往后考虑每个为\(1\)的位置，能翻转就翻转，直到\(sum=0\)
#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,n,a[N],pos[N],cnt,sum,l[N],r[N],tot; bool rev[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d",&n),cnt=sum=0,i=1;i<=n;++i)
scanf("%d",&a[i]),rev[i]=0,sum+=a[i];
if (abs(sum)&1) { puts("-1"); continue; }
if (sum<0) for (sum=-sum,i=1;i<=n;++i) a[i]=-a[i];
for (i=1;i<=n;++i) if (a[i]==1) pos[++cnt]=i;
int pre=0; for (i=1;i<=cnt&∑++i)
if (pos[i]!=pre+1) sum-=2,rev[pos[i]]=1,pre=pos[i];
for (tot=0,rev[n+1]=0,i=1;i<=n;++i)
if (rev[i+1]) ++tot,l[tot]=i,r[tot]=i+1,++i; else ++tot,l[tot]=r[tot]=i;
for (printf("%d\n",tot),i=1;i<=tot;++i)
printf("%d %d\n",l[i],r[i]);
}
return 0;
}
D. Factorial Divisibility
感觉我的做法比较奇怪啊，但是还是比较简单的说
考虑对于所有分子，找出其中的最大值\(a_m\)，先考虑判断分子能否整除\(a_m\)
不难发现此时值等于\(a_m\)的数都变成了\(1\)，那么剩下的小于\(a_m\)的数的部分就变成了和原问题类似的子问题，可以递归处理
若可以整除，考虑求出其商\(x\)，和\(a_m\)的个数\(y\)相加后，只要判断\(x+y\)能否整除\((a_m+1)\times (a_m+2)\times \cdots \times x\)即可
总复杂度浅浅分析一下发现是\(O(\max a_i+x)\)级别的，可以轻松通过
#include<cstdio>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=500005;
int n,x,a[N];
inline int solve(CI n,CI x) //-1:unavailable; otherwise:multiple
{
if (!n) return 0; int cur=0; for (;cur<n&&a[n-cur]==a[n];++cur);
int pre=solve(n-cur,a[n]); if (!~pre) return -1; cur+=pre;
for (RI i=a[n]+1;i<=x;++i) if (cur%i) return -1; else cur/=i;
return cur;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%d%d",&n,&x),i=1;i<=n;++i) scanf("%d",&a[i]);
return sort(a+1,a+n+1),puts(~solve(n,x)?"Yes":"No"),0;
}
原文地址：http://www.cnblogs.com/cjjsb/p/16823105.html
