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 = 29;
int N, w[maxn];
int main() 
{
    scanf("%d", &N);
    w[0] = 0;
    for(int i = 1; i <= N; i++)
     {
        scanf("%d", w + i);
        w[i] += w[i - 1];
    }
    if(w[N] & 1) 
    {
        puts("0"); return 0;
    }
    int ans = 0;
    for(int i = 1; i <= N; i++)
        for(int j = i + 1; j <= N; j++)
            if(w[j] - w[i] == (w[N] >> 1)) ans++;
    printf("%d", ans * (ans - 1) >> 1);
    return 0;
}

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[101][101][101];
int main()
{
    freopen("cannon.in","r",stdin);
    freopen("cannon.out","w",stdout);
    scanf("%d%d",&n,&m);
    f[0][0][0]=1;
    for(int i=1;i<=n;i++)//hang
     for(int j=0;j<=m;j++)//you j lie fang le 1 ge
      for(int k=0;j+k<=m;k++)//you k lie fang le 2 ge
       {
             f[i][j][k]=f[i-1][j][k];//bufang
             if(j>=1) f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k]*(m-j-k+1))%mod;//kong lie fang 1 ge
             if(k>=1) f[i][j][k]=(f[i][j][k]+f[i-1][j+1][k-1]*(j+1))%mod;//you 1 ge de lie chu fang 1 ge
             if(j>=2) f[i][j][k]=(f[i][j][k]+f[i-1][j-2][k]*((m-j-k+2)*(m-j-k+1)/2))%mod;//kong lie fang 2 ge
             if(k>=1) f[i][j][k]=(f[i][j][k]+f[i-1][j][k-1]*(m-j-k+1)*j)%mod;//kong 1 lie ge fang 1 ge
             if(k>=2) f[i][j][k]=(f[i][j][k]+f[i-1][j+2][k-2]*((j+1)*(j+2)/2))%mod;//you 1 ge de lie chu fang 2 chu
       }
    long long ans=0;
    for(int j=0;j<=m;j++)
      for(int k=0;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[2][4][4][4][4];
char s[N];
bool v[4];
int y[26],df[200];
int main()
{
    int n;
    scanf("%d%s",&n,s);
    y['M'-'A']=1;
    y['B'-'A']=2;
    y['F'-'A']=3;
    int st;
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            for(int k=0;k<4;k++)
            {
                v[i]=v[j]=v[k]=true;
                st=(i<<4)+(j<<2)+k;
                for(int l=1;l<4;l++) df[st]+=v[l];
                v[i]=v[j]=v[k]=false;
            }
    int t;
    t=y[s[0]-'A'];
    memset(dp[1],-63,sizeof(dp[1]));
    dp[1][t][0][0][0]=1;
    dp[1][0][0][t][0]=1;
    int now=1,nxt=0;
    for(int h=1;h<n;h++,swap(now,nxt))
    {
        memset(dp[nxt],-63,sizeof(dp[nxt]));
        for(int i=0;i<4;i++)
            for(int j=0;j<4;j++)
                for(int k=0;k<4;k++)
                    for(int l=0;l<4;l++)
                    {
                        if(dp[now][i][j][k][l]<0) 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<<4)+(i<<2)+j]);
                            dp[nxt][i][j][t][k]=max(dp[nxt][i][j][t][k],dp[now][i][j][k][l]+df[(t<<4)+(k<<2)+l]);
                        }
                    }
    }
    long long ans=0;
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            for(int k=0;k<4;k++)
                for(int l=0;l<4;l++)
                    ans=max(ans,dp[now][i][j][k][l]);
    printf("%lld",ans);
}