KYOCERA Programming Contest 2021（AtCoder Beginner Contest 200） 题解
KYOCERA Programming Contest 2021（AtCoder Beginner Contest 200） 题解
哦淦我已经菜到被ABC吊打了。
A - Century
首先把当前年份减去\(1\)，对应的世纪也减去\(1\)，然后我们就发现第\(0\)到\(99\)年对应第\(0\)世纪，第\(100\)到\(199\)年对应第\(1\)世纪，以此类推。
答案就是\(\lfloor \frac {N-1} {100} \rfloor\)。这里\(\lfloor x \rfloor\)表示不超过\(x\)的最大整数。
#include
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
cout<<(n-1)/100+1< B - 200th ABC-200
乍一看答案会很大，然后爆long long。
其实假如当前数不是\(200\)的倍数的时候，把它后面连接上\(200\)，结果一定是\(200\)的倍数，因为\(1000\)一定是\(200\)的倍数。
所以答案其实不会很大，最多就是\(976555175781\)（\(N=99999, K=20\)）。
然后暴力做就好了。
#include
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
long long n;
int k;
cin>>n>>k;
while(k){
if(n%200==0)n/=200,k--;
else n=n*1000+200,k--;
}
cout< C - Ringo's Favorite Numbers 2
假如两个数相减是\(200\)的倍数，他们对\(200\)取模后，得到的结果一定相同。
然后就用前缀和记录在当前的位置之前有多少个数对\(200\)取模得到的结果和这个数对\(200\)取模的结果相同，并且把这个加入答案中就可以了。
只有我一开始以为差一定要是非负数然后被坑了么。
#include
using namespace std;
int n,a[200005],c[205];
long long ans;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
ans+=c[a[i]%200];
c[a[i]%200]++;
}
cout< D - Happy Birthday! 2
首先还是把所有的数都对\(200\)取模。
然后我们可以想出来一种DP的状态表示方法：\(f_{i,j}\)表示已经处理了前\(i\)个数，选出来的\(B\)序列和\(C\)序列的差对\(200\)取模等于\(j\)。
这种状态的转移，可以枚举当前的数是放进\(B\)中还是\(C\)中，亦或是两个序列都不放。输出方案也只需要记录上一个状态的\(j\)，然后反着操作一遍就好了。
但是它有一个问题，就是不能保证两个序列都是非空的。
我们可以再开一维，记录两个序列当中是不是有元素了：\(f_{i,j,k}\)表示已经处理了前\(i\)个数，选出来的\(B\)序列和\(C\)序列的差对\(200\)取模等于\(j\)，\(k\)以子集的位掩码的形式记录两个序列是否非空。
子集的位掩码这个表述非常有点奇怪，具体来说就是：
- \(k=0\)表示两个序列都是空的。
- \(k=1\)表示一个序列都是空的。
- \(k=2\)表示另一个序列都是空的。
- \(k=3\)表示两个序列都是非空的。
（“一个”和“另一个”的表述是因为这不重要，我就懒得想了）
然后为了输出方案还要记录上一个状态的\(k\)是多少。
#include
using namespace std;
int n,a[205],g[205][205][4],h[205][205][4];
bool f[205][205][4];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]%=200;
}
f[0][0][0]=1;
for(int i=1;i<=n;i++){
f[i][0][0]=1;
for(int j=0;j<200;j++){
for(int k=1;k<=3;k++){
if(f[i-1][(j+a[i])%200][k&1]){
f[i][j][k]=1;
g[i][j][k]=-1;
h[i][j][k]=k&1;
}
if(f[i-1][(j+a[i])%200][k]){
f[i][j][k]=1;
g[i][j][k]=-1;
h[i][j][k]=k;
}
if(f[i-1][j][k]){
f[i][j][k]=1;
}
if(f[i-1][(j-a[i]+200)%200][k&2]){
f[i][j][k]=1;
g[i][j][k]=1;
h[i][j][k]=k&2;
}
if(f[i-1][(j-a[i]+200)%200][k]){
f[i][j][k]=1;
g[i][j][k]=1;
h[i][j][k]=k;
}
}
}
}
if(!f[n][0][3]){
cout<<"NO";
return 0;
}
int x=n,y=0,z=3;
cout<<"YES\n";
vector u,v;
while(x){
if(g[x][y][z]==1){
u.emplace_back(x);
z=h[x][y][z];
y=(y-a[x]+200)%200;
}else if(g[x][y][z]==-1){
v.emplace_back(x);
z=h[x][y][z];
y=(y+a[x])%200;
}
x--;
}
reverse(u.begin(),u.end());
cout< E - Patisserie ABC 2
这里我们可以想到先枚举三种属性的和是多少。然后我们可以定义\(tot(m)\)，表示和为\(m\)的时候，一共有多少种组合方式。
然后由于每个属性的值都是\(1\)到\(n\)的限制，又到了激动人心的分类讨论环节。
首先我们把第一属性的值叫做\(i\)，那么后两个属性的和就是\(m-i\)。
- \(2\leq m-i\leq n+1\)：那么第二属性的取值范围就是\(1\)到\(m-i-1\)，答案就是\(\sum_{\max(m-n-1,1)}^{\min(n,m-2)}m-i-1\)
- \(n+2\leq m-i\leq 2n\)：那么第二属性的取值范围就是\(m-i-n\)到\(n\)，答案就是\(\sum_{\max(1,m-2*n)}^{\min(n,m-n-2)}2n-(m-i)+1\)
那么：
\[tot(i)=\sum_{\max(m-n-1,1)}^{\min(n,m-2)}(m-i-1)+\sum_{\max(1,m-2*n)}^{\min(n,m-n-2)}(2n-(m-i)+1) \]然后就可以枚举\(m\)，快速的削减\(k\)的值，直到\(k\)小于等于\(tot(m)\)了，这时候我们就枚举第一属性\(i\)，然后根据上文的分类讨论计算第二属性和第三属性的取值即可（同样是先快速削减\(k\)，然后\(k\)小于等于当前第一属性对应取值种类数时输出答案）。
#include
using namespace std;
typedef long long ll;
int n;
ll k;
ll sum(int l,int r,int lv,int rv){
return (ll)(lv+rv)*(r-l+1)/2;
}
ll tot(int m){
ll res=0;
if(m<=2*n+1){
int l=max(1,m-n-1),r=min(n,m-2);
res+=sum(l,r,m-l-1,m-r-1);
}
if(m>n+2){
int l=max(1,m-2*n),r=min(n,m-n-2);
res+=sum(l,r,2*n-(m-l)+1,2*n-(m-r)+1);
}
return res;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>k;
for(int m=3;m<=3*n;m++){
if(k>tot(m)){
k-=tot(m);
continue;
}
for(int i=1;i<=n;i++)if(m-i<=n*2){
if(m-i<=n+1){
if(k>m-i-1){
k-=m-i-1;
continue;
}
cout<2*n-(m-i)+1){
k-=2*n-(m-i)+1;
continue;
}
cout< F - Minflip Summation
由于我是看了题解才把这题做出来的，所以就照着题解翻译吧（还好意思讲）。
假如\(S\)不包含?同时\(K=1\)的解法
我们把所有左右相邻的，一个是\(0\)一个是\(1\)的位置（也就是\(S_i\neq S_{i+1}\)的位置\(i\)）都数出来（比如10100能数出来\(3\)个）。
为了叙述方便，我们把它叫做“切换位置”（毕竟是从\(0\)切换到\(1\)或者从\(1\)切换到\(0\)）。
然后发现一次操作，最多把它减少\(2\)（选择两个切换位置去操作），也可以减少\(1\)（选择一个切换位置，和一个开头/结尾）。
那么假如数出来\(D\)个位置，就需要\(\lfloor \frac D 2 \rfloor\)次操作解决。
这道题的解法
然后对于所有的这样的位置，我们记录他们的总和是\(A\)：（主要是从AtCoder的题解上搬的，但是修了一点小锅）
\[A = 2^{Kq} \times ( ( K \times \displaystyle \sum_{i=1}^{|S|-1} f(S_i,S_{i+1}) ) + (K-1) \times f(S_1,S_{|S|})) \]\[\begin{eqnarray} f(a,b) = \begin{cases} \frac{1}{2} & \text{(if at least one of }a\text{ and }b\text{ is ?)} \\ 1 & \text{(if neither }a\text{ nor }b\text{ is ? and }a\neq b\text{)} \\ 0 & \text{(if neither }a\text{ nor }b\text{ is ? and }a = b\text{)} \\ \end{cases} \end{eqnarray} \]然后答案似乎应该是\(\frac A 2\)，不过还有一点问题：假如说一个串数出来奇数个切换位置，这种算法对于这个串会不会少算了半次操作？
我们可以发现，对于有奇数个切换位置的串，多添加一个切换位置后答案相同。
然后假如给\(A\)添加上这些串的个数，答案就是\(\frac A 2\)了。
这些串有一个性质：他们的开头和结尾，是不同的（毕竟切换了奇数次）。
然后这些串的个数就是\(2^{Kq} \times f(S_1,S_{|S|})\)。
然后答案就是\(\frac {A+2^{Kq} \times f(S_1,S_{|S|})} 2\)，也就是：
\[2^{Kq} \times K \times \sum_{i=1}^{|S|} f(S_i,S_{i+1}) \]（特别地，这里把\(S_{|S|+1}\)看作是\(S_1\)）
#include
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int inv2=5e8+4;
ll qpow(ll a,ll n){
ll res=1;
while(n){
if(n&1)res=res*a%mod;
a=a*a%mod;
n>>=1;
}
return res;
}
int n,m,k,ans;
char s[100005];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>s>>k;
n=strlen(s);
if(n*k==1){cout<<0;return 0;}
for(int i=0;i