期望得分：0+100+100=200
实际得分：0+100+100=200
T1 [Ahoi2009]fly 飞行棋
利用矩形对角线相等，所以n^2枚举可以凑成对角线的点
假设有k对
ans=C（k，2）=k*（k-1）/2
#includeusing 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#define mod 999983#ifdef WIN32#define ll "%I64d"#else #define ll "%lld"#endifusing 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#include #include #define N 100001using 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