20140403 训练。比赛地址
A题。枚举，注意细节。
int main()
{
int nc;scanf("%d",&nc);
while(nc--){
int n;
cin>>n;
if(n<=1||n==5||n==6)puts("Unknown");
else if(n<=3)puts("Spring Training");
else if(n==4)puts("Spring Training"),puts("BNU Contest");
else if(n==7)puts("Practice Week"),puts("Summer Training");
else if(n==8)puts("Summer Training");
else if(n>=9&&n<=10)puts("Regional Contest");
else if(n==11)puts("Basic Training"),puts("Regional Contest");
else if(n==12)puts("Basic Training"),puts("Rookie Contest");
}
}
B题。问题可抽象成在一个数列中找出四个数使得他们的和等于一个给定的数。以前做过三个数的=-=
int vis[2222];
int a[1111];
int main()
{
int nc;
scanf("%d",&nc);
while(nc--)
{
int l,x,n;
cin>>l>>x>>n;
l-=x;
memset(vis,false,sizeof(vis));
for(int i=0; i<n; i++)cin>>a[i];
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
vis[a[i]+a[j]]=true;
bool fl=false;
for(int i=0; i<=l; i++)
if(vis[i]&&vis[l-i])
{
fl=true;
break;
}
if(fl)puts("Yes");
else puts("No");
}
}
C题。博弈。每次都撕成相等的两半，并且长和宽只能是整数。最后的状态肯定是长和宽都是奇数，不管双方采取什么样的策略最后肯定会到达这个最后的状态。只需要统计长和宽分别可以折多少次并求和。如果是奇数的话，后手胜，否则先手胜。
int main()
{
int nc;
scanf("%d",&nc);
while(nc--)
{
int n,m;
cin>>n>>m;
int ans=0;
while(n%2==0)ans++,n/=2;
int ans2=0;
while(m%2==0)ans2++,m/=2;
if((ans+ans2)%2==1)puts("Adidas loses");
else puts("Adivon prevails");
}
return 0;
D题。trie树
int child[maxn][28];
int siz;
int sum=0;
int val[maxn];
void ini()
{
memset(child[1],0,sizeof(child[1]));
memset(val,0,sizeof(val));
siz=1;
}
void insert(char * s)
{
int len=strlen(s);
int cur=1;
for(int i=0;i<len;i++){
if(!child[cur][s[i]-'a']){
child[cur][s[i]-'a']=++siz;
memset(child[siz],0,sizeof(child[siz]));
}
cur=child[cur][s[i]-'a'];
val[cur]++;
}
cur=1;
sum+=2*len;
for(int i=len-1;i>=0;i--){
if(!child[cur][s[i]-'a']){
child[cur][s[i]-'a']=++siz;
memset(child[siz],0,sizeof(child[siz]));
}
cur=child[cur][s[i]-'a'];
val[cur]++;
}
}
int main()
{
// re;
int nc;
cin>>nc;
ll ans=0;
char s[maxn];
while(nc--){
int n;
ini();
scanf("%d",&n);
sum=0;
for(int i=0;i<n;i++){
scanf("%s",s);
insert(s);
}
ans=0;
for(int i=2;i<=siz;i++)
ans+=(ll)val[i]*(ll)(2*n-val[i]);
printf("%lld\n",ans);
}
return 0;
}
E题。
F题。看题解懂得。可以通过dp方程得到每项的通项。
int main()
{
int nc;
scanf("%d",&nc);
while(nc--){
double p;
int n;
cin>>n>>p;
double k=p;
double ans=0;
for(int i=n;i>=1;i--){
ans+=i*k;k*=p;}
printf("%.6lf\n",ans);
}
return 0;
}
G题。
H题。概率题。比赛的时候推不出方程来，蒙出来的。
int main()
{
int nc;
scanf("%d",&nc);
while(nc--)
{
double t;
cin>>t;
printf("%.2lf\n",1.0/(t*(1-t)));
}
return 0;
}
I题。
J题。dp[i][j]表示第i天的时候运用j次忍术可以得到的最大值。
int main()
{
int nc;
//re;
int c,n;
while( scanf("%d%d",&c,&n)==2)
{
for(int i=1; i<=n; i++)
scanf("%d",&a[i]);
memset(dp,-1,sizeof(dp));
dp[0][0]=c;
for(int i=1; i<=n; i++)
for(int j=0; j<=4; j++)
{
dp[i][j]=max(dp[i][j],dp[i-1][j]);
if(j==1&&dp[i-1][0]-a[i]>=0)
dp[i][j]=max(dp[i][j],dp[i-1][0]-a[i]);
if(j==2&&dp[i-1][1]!=-1)
dp[i][j]=max(dp[i][j],dp[i-1][1]+a[i]);
if(j==3&&dp[i-1][2]-a[i]>=0)
dp[i][j]=max(dp[i][j],dp[i-1][2]-a[i]);
if(j==4&&dp[i-1][3]!=-1)
dp[i][j]=max(dp[i][j],dp[i-1][3]+a[i]);
}
int ans=-1;
for(int i=0; i<=4; i+=2)
ans=max(ans,dp[n][i]);
printf("%d\n",ans);
}
return 0;
}
K题。概率dp，用矩阵快速幂搞。
#define re freopen("in.txt","r",stdin)
double dp[6][1111];
int main()
{
int n,m,k,s;
int nc;
re;
scanf("%d",&nc);
while(nc--)
{
scanf("%d%d%d%d",&n,&m,&k,&s);
for(int i=1; i<=n; i++)
dp[0][i]=0;
dp[0][s]=1;
int tt=m*k;
int t=0;
while(tt--)
{
dp[t^1][1]=dp[t][2]*0.5;
dp[t^1][2]=dp[t][1]*1+dp[t][3]*0.5;
for(int i=3; i<n-1; i++)
dp[t^1][i]=dp[t][i-1]*0.5+dp[t][i+1]*0.5;
dp[t^1][n]=dp[t][n-1]*0.5;
dp[t^1][n-1]=dp[t][n]*1+dp[t][n-2]*0.5;
t^=1;
}
for(int i=1; i<n; i++)
printf("%.4lf ",dp[t][i]);
printf("%.4lf\n",dp[t][n]);
}
return 0;
}
矩阵快速幂
int n;
struct mar
{
double ma[22][22];
void put(int n)
{
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
printf("%.3lf ",ma[i][j]);
puts("");
}
puts("");
}
void ini(int n)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
ma[i][j]=0;
}
}E;
mar mul(mar A,mar B)
{
mar D;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
D.ma[i][j]=0;
for(int k=1;k<=n;k++)
D.ma[i][j]+=A.ma[i][k]*B.ma[k][j];
}
return D;
}
mar mapow(mar A,int k)
{
mar ans=A,tmp=A;
while(k){
if(k&1){
ans=mul(ans,tmp);
}
k>>=1;
tmp=mul(tmp,tmp);
}
return ans;
}
mar C;
int main()
{
int nc;
//freopen("in.txt","r",stdin);
cin>>nc;
while(nc--){
int k,m,s;
cin>>n>>k>>m>>s;
memset(C.ma,0,sizeof(C.ma));
if(n==1){puts("1.0000");continue;}
for(int i=2;i<n;i++){
C.ma[i][i-1]=C.ma[i][i+1]=0.5;
}
if(n>1)C.ma[1][2]=C.ma[n][n-1]=1;
C=mapow(C,k*m-1);
for(int i=1;i<n;i++)
printf("%.4lf ",C.ma[s][i]);
printf("%.4lf\n",C.ma[s][n]);
}
return 0;
}
L题。几何题。判断各种情况。
int main()
{
int nc;
// freopen("in.txt","r",stdin);
scanf("%d",&nc);
while(nc--)
{
int x1,x2,y1,y2;
int a,b,c;
cin>>x1>>y1>>x2>>y2>>a>>b>>c;
double ans=0;
double tot=(x2-x1)*(y2-y1);
if(a==0)
ans=(y2+1.0*c/b)*(x2-x1);
else if(b==0){
ans=(y2-y1)*(x2+c*1.0/a);
}
else{
double ty1=-(a*x1+c)*1.0/b;
double ty2=-(a*x2+c)*1.0/b;
// cout<<ty1<<' '<<ty2<<endl;
if(ty1<=y1){
if(ty2>=y2)
ans=b*1.0/a*(y1-y2)*(y2-y1)*0.5+(y2-y1)*(x2+(b*y2+c)*1.0/a);
else if(ty2>=y1&&ty2<=y2)
ans=(ty2-y1)*0.5*(x2+(b*y1+c)*1.0/a);
// cout<<ans<<endl;
}
else if(ty1>=y2){
if(ty2>=y1&&ty2<=y2)
ans=(x2+(b*y2+c)*1.0/a)*(y2-ty2)*0.5;
else if(ty2<=y1)
ans=(y2-y1)*0.5*(y2-y1)*(b*1.0/a)+(y2-y1)*(-x1-(b*y2+c)*1.0/a);
}
else{
if(ty2>=y2)
ans=(-x1-1.0*(b*y2+c)/a)*(y2-ty1)*0.5;
else if(ty2<=y1)
ans=(-x1-1.0*(b*y1+c)/a)*(-y1+ty1)*0.5;
else if(ty2>=y1&&ty2<=y2)
ans=(ty2-ty1)*0.5*(x2-x1)+(x2-x1)*(ty1-y1);
}
}
printf("%.3lf\n",min(ans,tot-ans));
}
return 0;
}