枚举+组合数？+DP+数学问题
http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=582
QAQ许久没打过比赛，来一发BC，结果还是只能做前两题……too young too naive了……
不过这场比赛前两题被hack&FST的人挺多的？蒟蒻手太慢，造数据也慢，玩不来hack……抢不到QAQ
A
给5张牌，问最少换多少张可得到同花顺。
其实是枚举花色，以及最小的是哪张（其实就是枚举换完以后，得到的是哪五张）看手里有多少张是已经得到的= =
开个have[i][j]表示手里有花色为 i 数字为 j 的牌（其中，如果手里有A，那么1和14都置为true）
hack点？没啥吧……可能有的同学是看手里连续拥有最大段是多长，比如手里最长的连续牌是123，那ans=2，但是135也是只需要换两张……
//BestCoder #41 A
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
inline int getint(){
int v=,sign=; char ch=getchar();
while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}
return v*sign;
}
const int N=1e5+,INF=~0u>>;
typedef long long LL;
/******************tamplate*********************/ int a[],b[];
char s[][];
bool have[][];
int main(){
#ifndef ONLINE_JUDGE
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
#endif
int T=getint();
while(T--){
memset(have,,sizeof have);
memset(a,,sizeof a);
memset(b,,sizeof b);
memset(s,,sizeof s);
F(i,,) scanf("%s",s[i]);
F(i,,) a[i]=s[i][]-'A';
F(i,,){
b[i]=s[i][]-'';
if (s[i][]>) b[i]=b[i]*+s[i][]-'';
have[a[i]][b[i]]=;
if (b[i]==) have[a[i]][]=;
}
#ifdef debug
F(i,,) printf("%d %d\n",a[i],b[i]);
#endif
int ans=;
rep(i,){
int mx=,now=;
F(j,,){
now=now+have[i][j]-have[i][max(j-,)];
mx=max(mx,now);
}
ans=max(ans,mx);
}
printf("%d\n",-ans);
}
return ;
}
B
一开始看错题了[捂脸熊]
其实就是问有多少种情况下选出两个字符串你能赢。
容易发现赢的情况是：两个字符串完全相同；或者两个字符串长度和为奇数。第一种情况只需一次B操作就赢了……第二种情况只要努力拿短的那个，最后一个肯定是你的。
那么记录一下奇数长度和偶数长度的字符串有多少个，以及每个字符串有多少个与它相同（map大法吼！其实map存的是一个pair……first是key，second就是val）
然后组合数算一下就好了。（然而蒟蒻在快结束的时候发现记录「有多少个奇/偶长度的字符串」的变量用的是int……而不是像ans一样用的是LL……感觉乘的时候要爆炸啊，果断重交了一发，分数&rank瞬间就下来了……QAQ（不过没有FST&被hack应该还是算赚了吧）
//BestCoder #41 B
#include<map>
#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
inline int getint(){
int v=,sign=; char ch=getchar();
while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}
return v*sign;
}
const int N=1e5+,INF=~0u>>;
typedef long long LL;
/******************tamplate*********************/
map<string,int>s;
LL gcd(LL a,LL b){return b ? gcd(b,a%b) : a;}
string s1;
int main(){
#ifndef ONLINE_JUDGE
freopen("B.in","r",stdin);
freopen("B.out","w",stdout);
#endif
int T=getint();
while(T--){
s.clear();
LL cnt0=,cnt1=;
LL n=getint();
F(i,,n){
cin >>s1;
if (s1.length()&) cnt1++;
else cnt0++;
if (s.find(s1)!=s.end()) s[s1]=s[s1]+;
else s[s1]=;
}
LL fz=(LL)cnt0*cnt1,fm=n*(n-)/;
for(map<string,int>::iterator it=s.begin();it!=s.end();it++){
LL v=it->second;
fz+=v*(v-)/;
}
LL d=gcd(fz,fm);
printf("%lld/%lld\n",fz/d,fm/d);
}
return ;
}
C
其实有一道题跟它是很相似的QAQ 【BZOJ】【3612】【HEOI 2014】平衡
然而蒟蒻没有想到……
并且这题卡空间！但是又由于有一些特殊性质，可以优化= =
其实，每个数最多只能拆分成$O(\sqrt{n})$个数，因为有$\frac{x*(x+1)}{2}=n \rightarrow x=2*\sqrt{n}$
所以其实在转移的时候，i-j 不会很远……所以之前很多的计算结果都不用保留了……所以？滚动数组！
//BestCoder #41 C
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
inline int getint(){
int v=,sign=; char ch=getchar();
while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}
return v*sign;
}
const int N=1e5+,INF=~0u>>,mod=;
typedef long long LL;
/******************tamplate*********************/
int f[][];
int main(){
#ifndef ONLINE_JUDGE
freopen("C.in","r",stdin);
freopen("C.out","w",stdout);
#endif
int T=getint(),n,c,l,r;
f[][]=;
while(T--){
n=getint(); c=getint(); l=getint()-c; r=getint()-c;
LL ans=l==; if (r==n) ans--;
F(i,,r){
int now=i%;
memset(f[now],,sizeof f[now]);
f[now][]=;
for(int j=;j*(j+)/<=i;j++){
int fa=now-j;
if (fa<) fa+=;
f[now][j] = f[fa][j]+f[fa][j-];
if (f[now][j]>=mod) f[now][j]-=mod;
}
if (i>=l)
for(int j=;j*(j+)/<=i;j++){
ans+=f[now][j];
if (ans>=mod) ans-=mod;
}
}
printf("%lld\n",ans);
}
return ;
}
D
SXBK的数学题>_>当然是果断弃疗啊……