2015/06/25

[Codeforces Round #309 (Div. 2)] #ABC题解

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

题目链接:Codeforces Round #309 (Div. 2)

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.
[Ans]
[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;
}

--By Foggy
2015.6.25