題解：2012 ACM-ICPC Asia Dhaka Regional Contest

Wedding of Sultan

#include<stdio.h>
char s[];
int t,k,kase=,ans[];
void dfs(char u)
{
    for(; s[++k]!=u; dfs(s[k]))++ans[s[k]],++ans[u];
}
int main()
{
    for(scanf("%d",&t); t--;)
    {
        scanf("%s",s);
        for(char c='A'; c<='Z'; ++c)
            ans[c]=;
        dfs(s[k=]);
        printf("Case %d\n",++kase);
        for(char c='A'; c<='Z'; ++c)
            if(ans[c])
                printf("%c = %d\n",c,ans[c]);
    }
}
           

Memory Overflow

#include<stdio.h>
char s[];
int t,n,k,kase=,ans,pre[];
int main()
{
    for(scanf("%d",&t); t--; printf("Case %d: %d\n",++kase,ans))
    {
        scanf("%d%d%s",&n,&k,s);
        for(char c='A'; c<='Z'; ++c)pre[c]=-;
        for(int i=ans=; i<n; ++i)
        {
            if(~pre[s[i]]&&i-pre[s[i]]<=k)++ans;
            pre[s[i]]=i;
        }
    }
}
           

Poker End Games

#include<stdio.h>
typedef double lf;
const lf EPS=;
int t,kase=,a,b;
lf ans0,ans1;
void dfs(int a,int b,lf c,int d)
{
    if(c+c*d<EPS)return;
    if(!b)ans1+=c;
    if(!a||!b)
    {
        ans0+=c*d;
        return;
    }
    int e=a<b?a:b;
    dfs(a-e,b+e,c/,d+),dfs(a+e,b-e,c/,d+);
}
int main()
{
    for(scanf("%d",&t); t--; printf("Case %d: %.6f %.6f\n",++kase,ans0,ans1))
        scanf("%d%d",&a,&b),dfs(a,b,,ans0=ans1=);
}
           

Overlapping Characters

#include<bits/stdc++.h>
using namespace std;
const int N=,M=;
typedef bitset<N*M> bs;
bs b[];
char s[M],t[N*M+];
int n,q,kase=;
int main()
{
    scanf("%d%d%s",&n,&q,s);
    for(int i=; i<n; ++i)
    {
        for(int j=; j<N; ++j)
            scanf("%s",t+j*M);
        b[s[i]]=bs(t,N*M,'.','*');//c++11
    }
    for(; q--; printf("\n"))
    {
        scanf("%s",s);
        printf("Query %d: ",++kase);
        for(int i=; s[i]; ++i)
        {
            bs d=b[s[i]];
            for(int j=; s[j]; ++j)
                if(s[j]!=s[i])
                    d&=~b[s[j]];
            printf(d.none()?"N":"Y");
        }
    }
}
           

Learning Vector

#include<bits/stdc++.h>
using namespace std;
const int INF=-e9;
struct Vec
{
    int X,Y;
    bool operator<(const Vec &v)const
    {
        return v.Y*X<Y*v.X;
    }
} v[];
int t,n,k,kase=,f[][][*51];
int main()
{

    for(scanf("%d",&t); t--;)
    {
        scanf("%d%d",&n,&k);
        for(int i=; i<n; ++i)
            scanf("%d%d",&v[i].X,&v[i].Y);
        sort(v,v+n);
        for(int i=; i<n; ++i)
            for(int j=; j<=k; ++j)
                for(int h=*51; h--;)
                {
                    if(i)
                    {
                        f[i][j][h]=f[i-][j][h];
                        if(j&&h>=v[i].Y)
                            f[i][j][h]=max(f[i][j][h],
                                           f[i-][j-][h-v[i].Y]+v[i].X*(*h-v[i].Y));
                    }
                    else
                    {
                        if(j==)f[i][j][h]=h==v[i].Y?v[i].X*v[i].Y:INF;
                        else if(j==)f[i][j][h]=h?INF:;
                        else f[i][j][h]=INF;
                    }
                }
        int ans=;
        for(int h=*51; h--;)ans=max(ans,f[n-][k][h]);
        printf("Case %d: %d\n",++kase,ans);
    }
}