鉴于本人水平有限，两小时只A了三道，剩下的又不想看了，无聊写写前三题题解。

A. Kyoya and Photobooks

Description

给定一个只有小写字母的字符串，可以在任意位置插入任意一个小写字母，求得到的字符串种数。

Solution

枚举+哈希水题

Code

#include<map>
#include<string>
#include<iostream>
using namespace std;

map<string,bool> M;

int main(){
 int ans=0;
 string s,s1;
 cin>>s;
 for(int i=0;i<=s.size();i++)
  for(char j='a';j<='z';j++){
   s1.resize(0);
   s1+=s.substr(0,i);
   s1+=j;
   s1+=s.substr(i,s.size()-i);
   if(!M[s1]) M[s1]=true,ans++;
  }
 cout<<ans;
 return 0;

}

B. Ohana Cleans up

Description

给定一个01矩阵，每次可以改变一列，使0变成1,1变成0,问最多可以把几行变成全1。

Solution

我们发现，初始相同的行经过操作之后仍然相同，答案即为相同行数的最大值。

Code

#include<map>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;

map<string,int> M;

int main(){
 int n,ans=0; cin>>n;
 for(int i=0;i<n;i++){
  string s; cin>>s;
  ans=max(ans,++M[s]);
 }
 cout<<ans;
 return 0;
}

C. Kyoya and Colored Balls

Description

有k个颜色的求分别c1…ck个，把他们放在袋子中，依次取出。当第一种一色没取完时不能去玩后面的颜色，问总共有多少种取法（排列方式）。

Solution

要保证去i种颜色最后一个球时之前1~i种球都要取完，可以这样看，先把第一种球排好，把第二种球拿一个出来，其余任意插到第一种中，把拿出的那个放在最后，得到满足条件的序列，再将第三种球拿一个出来，其余任意任意插到之前的序列中，把拿出的放在最后…依此类推，可得到这个序列，方案即为没步插球的组合数之积。
插入第i中球的方案数即为在cnt(前i-1个球的总和)+1个缝里插入ci-1个球，两个球可以在同一个缝里，等价于在cnt+1+(x-1)-1个缝里插入ci-1个球，每个球必须单独占一个空，方案数为，注意cnt不会超过1000.
故答案为
，注意cnt不会超过1000.

Code

#include<cstdio>
#include<algorithm>
using namespace std;

typedef long long LL;
const int p=1000000007;

const int maxn=1001;
int c[maxn][maxn];
int C(int m,int n){
 if(m<n || m<0 || n<0) return 0;
 if(m==0)
  if(n==0) return 1;
  else return 0;
 return c[m][n]?c[m][n]:c[m][n]=(C(m-1,n)+C(m-1,n-1))%p;
}

int main(){
 LL ans=1;
 int n,cnt,x;scanf("%d%d",&n,&cnt);
 for(int i=2;i<=n;i++){
  scanf("%d",&x);
  LL t=C(cnt+x-1,x-1)%p;
  ans=ans*t%p;
  cnt+=x;
 }
 printf("%d",ans);
 return 0;
}

杂记

这是人生第一次打codeforces啊…前前后后发生了很多事，手一抖又写了篇Blog.

…其实前几天就有所准备，昨天晚上大约7点才发现当晚有比赛qwq,租的房子又没网 = = ，只能凌晨待在学校打啊！！！瞬间大家就就纷纷打电话回家说今晚不回去了 = = 然后有家长打电话给cy问了问情况，然后那个爆炸啊 = = ，cy勒令我们回家，还扬言要到学校来抓人–，然后我们就决定在机房关灯锁门，装作不在 = = 还花了半个小时堵了门。

结果cy始终没来–中间xyx和一个学校领导莫名来了机房 = = 吓得我们一跳一跳，始终不是个办法啊 = = 于是我们决定先去一机房睡到0:15，起来再打。

然后找了几个凳子躺下了 = = 然而还是有点小激动啊，硬是睡不着，后来就用强行睡觉术睡了大约有一个小时，起来的时候果然比较清醒，回到小机房开打啊啊啊啊 = =

然后到0:30网站突然卡住了 = = 原来还以为是因为当时访问的人太多了进不去，但tb说以前并是没有这样过，然后就不停刷啊刷，刷了5分钟才把题目刷出来。

然后英文题硬是要花五分钟看懂–。然后第一道题就傻逼了，准备STL水过去，结果gdb不知道怎么挂了 = = ，开始我还以为我STL打挂了，切到dev上就过了。当时想骂人啊！！！然而已经过去20分钟，都有几百个人切了第二题了，而且又得知分数是按提交时间算的，qaq…

打第一题的时候听到有人说第二题dp什么的，鉴于我的深度dp恐惧症，我看完题想都没想直接跳第三题，还在看题，tb突然激动地说第二题是傻逼题啊！然后就迅速报了题解，然后一想想很有道理，自己想应该也是想得出来，于是又用STL水过 = =

然后tb秒破了第三题，不准备再跟我们share,开始看第四题。我们其余人一直在想第三题，想了大概半小时未果，我换了三种思路，最后终于想到了一种很有道理的方法，跟lfw share了一下，他开始否认，后来查证了两个样例发现可以，我就放心打了。

期间需要求组合数，我开始准备记忆化递推的（因为只会这个），但是发现m有1000000（是我看错题，其实只有1000），然后就呵呵了，完全不会打啊。问tb，然后根本不理 = = 想了半天未果，发现只有20分钟了。那个着急啊 = = 于是作弊去网上急忙查了下组合数的递推打法交了，结果没有取模 = = [1WA],畸形lfw急切要我发程序给他他帮我加组合数 = = 结果[2WA],最后我还是自己找了一个lucas定理的改了，就过了pretext。

开心的大叫（smg…）,然后lfw想抄我代码让我发给他–我就发给他了–他就发给了Awesome,这样我们三个人就A了三道题了。

到家已经3点了，倒头就睡，看了看比赛，成绩还没出。

…

第二天一早，来到机房就打开codeforce,发现昨晚绿色的版面（AC）变红了，吓了一跳，以为没过大数据，结果TB告诉我------

你们相互抄代码被封号了！！！！！！！！！！！！！！！！！！！！！！！！！！！！

我简直日了g啊！！我没抄啊！！是他们抄我的啊！！！我报警了啊！！！！

sad本来还想涨一涨rating,结果根本就没给我评测啊！！不说是第一个交的不算抄吗！！

sooooooooooosad…

虽然我不知道是被封号了还是只是这次比赛不算，我已然创了个新号。欸…还好这件事发现的早，不然搞了几次之后再被封号就不好玩了。

总之，现在想分分钟a掉lfw.

Comment