NOIP模拟赛14

期望得分：0+100+100=200

实际得分：0+100+100=200

T1 [Ahoi2009]fly 飞行棋

http://www.lydsy.com/JudgeOnline/problem.php?id=1800

利用矩形对角线相等，所以n^2枚举可以凑成对角线的点

假设有k对

ans=C（k，2）=k*（k-1）/2

#include<cstdio>

using namespace std;

const int maxn = ;

int N, w[maxn];

int main()

{

    scanf("%d", &N);

    w[] = ;

    for(int i = ; i <= N; i++)

     {

        scanf("%d", w + i);

        w[i] += w[i - ];

    }

    if(w[N] & )

    {

        puts(""); return ;

    }

    int ans = ;

    for(int i = ; i <= N; i++)

        for(int j = i + ; j <= N; j++)

            if(w[j] - w[i] == (w[N] >> )) ans++;

    printf("%d", ans * (ans - ) >> );

    return ;

}

T2 炮

在一个 n*m 的棋盘上，炮可随意放，问有多少种放置方案

f[i][j][k] 前i行，有j列放了1个，有k列放了2个

分类讨论

#include<cstdio>

#define mod 999983

#ifdef WIN32

#define ll "%I64d"

#else

#define ll "%lld"

#endif

using namespace std;

int n,m;

long long f[][][];

int main()

{

    freopen("cannon.in","r",stdin);

    freopen("cannon.out","w",stdout);

    scanf("%d%d",&n,&m);

    f[][][]=;

    for(int i=;i<=n;i++)//hang

     for(int j=;j<=m;j++)//you j lie fang le 1 ge

      for(int k=;j+k<=m;k++)//you k lie fang le 2 ge

       {

             f[i][j][k]=f[i-][j][k];//bufang

             if(j>=) f[i][j][k]=(f[i][j][k]+f[i-][j-][k]*(m-j-k+))%mod;//kong lie fang 1 ge

             if(k>=) f[i][j][k]=(f[i][j][k]+f[i-][j+][k-]*(j+))%mod;//you 1 ge de lie chu fang 1 ge

             if(j>=) f[i][j][k]=(f[i][j][k]+f[i-][j-][k]*((m-j-k+)*(m-j-k+)/))%mod;//kong lie fang 2 ge

             if(k>=) f[i][j][k]=(f[i][j][k]+f[i-][j][k-]*(m-j-k+)*j)%mod;//kong 1 lie ge fang 1 ge

             if(k>=) f[i][j][k]=(f[i][j][k]+f[i-][j+][k-]*((j+)*(j+)/))%mod;//you 1 ge de lie chu fang 2 chu

       }

    long long ans=;

    for(int j=;j<=m;j++)

      for(int k=;j+k<=m;k++)

       ans=(ans+f[n][j][k])%mod;

    printf(ll,ans);

}

T3 [Ioi2007]Miners 矿工配餐

#include<cstdio>

#include<cstring>

#include<algorithm>

#define N 100001

using namespace std;

long long dp[][][][][];

char s[N];

bool v[];

int y[],df[];

int main()

{

    int n;

    scanf("%d%s",&n,s);

    y['M'-'A']=;

    y['B'-'A']=;

    y['F'-'A']=;

    int st;

    for(int i=;i<;i++)

        for(int j=;j<;j++)

            for(int k=;k<;k++)

            {

                v[i]=v[j]=v[k]=true;

                st=(i<<)+(j<<)+k;

                for(int l=;l<;l++) df[st]+=v[l];

                v[i]=v[j]=v[k]=false;

            }

    int t;

    t=y[s[]-'A'];

    memset(dp[],-,sizeof(dp[]));

    dp[][t][][][]=;

    dp[][][][t][]=;

    int now=,nxt=;

    for(int h=;h<n;h++,swap(now,nxt))

    {

        memset(dp[nxt],-,sizeof(dp[nxt]));

        for(int i=;i<;i++)

            for(int j=;j<;j++)

                for(int k=;k<;k++)

                    for(int l=;l<;l++)

                    {

                        if(dp[now][i][j][k][l]<) continue;

                        else

                        {

                            t=y[s[h]-'A'];

                            dp[nxt][t][i][k][l]=max(dp[nxt][t][i][k][l],dp[now][i][j][k][l]+df[(t<<)+(i<<)+j]);

                            dp[nxt][i][j][t][k]=max(dp[nxt][i][j][t][k],dp[now][i][j][k][l]+df[(t<<)+(k<<)+l]);

                        }

                    }

    }

    long long ans=;

    for(int i=;i<;i++)

        for(int j=;j<;j++)

            for(int k=;k<;k++)

                for(int l=;l<;l++)

                    ans=max(ans,dp[now][i][j][k][l]);

    printf("%lld",ans);

}