题解 P3230 【[HNOI2013]比赛】

· · 题解

首先考虑最暴力的方法，我们依次枚举n(n-1)/2场比赛的结果，按照1V2,1V3...1Vn,2V3...2Vn...n-1Vnd的顺序枚举。最后判断解是否可行

接下来上剪枝

剪枝们：

  1. 考虑到最后再来判太浪费，索性在搜索时就限制每人的得分不超过总分。

  2. 如果对于一个人u来说，他赢下所有以后的比赛也打不出自己的总分，剪枝。（最后分数也需等于总分）

  3. 以上两条剪枝都是很弱智的。考虑Sx表示分出胜负的总场数，Sy表示平局的总场数,Su表示所有队总得分。那么显然有：Sx+Sy=n(n-1)/2且3Sx+2Sy=Su 由此可以解出Sx,Sy。在搜索时，在可利用其限制胜利场次。

  4. 此题中心方法楼上已经说的很清楚了，大致利用的是人数为X,分数集合为A[]的比赛方案数一定，它与某人具体的得分是无关的。因此可以利用记忆化搜索（这好像不能叫剪枝）。把最后几个人剩余的分数哈希起来存就好了。

#include<iostream>
#include<cstdio>
#include<map>
#include<algorithm>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef unsigned long long ll;
const ll B=28,P=1e9+7;
const int N=1000;
int n,a[N],b[N],s[N],su,sx,sy; 
map<ll,ll>h;
bool cmp(int x,int y){return x>y;}
ll dfs(int u,int v){
    ll ret=0;
    if(u==n) return 1;
    if(a[u]+3*(n-v+1)<s[u]) return 0;//保证u打满了总分
    if(v>n){
        FOR(i,u+1,n) b[i]=s[i]-a[i];
        sort(b+u+1,b+n+1);
        ll sta=0;
        FOR(i,u+1,n) sta=sta*B+b[i];//hash
        if(h.find(sta)!=h.end()) return h[sta];
        else return h[sta]=dfs(u+1,u+2);
    }
    if(a[u]+3<=s[u] && sx) 
        a[u]+=3,sx--,ret+=dfs(u,v+1),a[u]-=3,sx++; //u win
    if(a[u]+1<=s[u] && a[v]+1<=s[v] && sy) 
        a[u]++,a[v]++,sy--,ret+=dfs(u,v+1),a[u]--,a[v]--,sy++;//draw
    if(a[v]+3<=s[v] && sx) 
        a[v]+=3,sx--,ret+=dfs(u,v+1),a[v]-=3,sx++;//v win
    return ret%P;
}//一场u-v的比赛 
int main(){
    scanf("%d",&n);
    FOR(i,1,n) scanf("%d",&s[i]),su+=s[i];
    sx=su-n*n+n;sy=(su-3*sx)>>1;//算出sx,sy
    sort(s+1,s+n+1,cmp);
    printf("%lld",dfs(1,2)%P);
}