「HNOI 2013」比赛

题目链接

戳我

\(Solution\)

这道题观察数据范围发现很小,再看看题目可以发现是搜索.

这题纯搜索会\(T\)所以要加入适当剪枝

• 如果一个人后面的比赛都赢却依旧到不了目标分数,则直接\(return\)
• 限制每个人的分数,使他的分数不超过目标分数
• 我们用\(fx\)当做分出胜负的场次,\(fy\)当做平的场,ans当做总分数.则可以列出如下方程:

\[ \left\{
\begin{array}
fx+fy=n*(n-1)/2\\
3*fx+2*fy=ans \
\end{array}
\right.
\]

• 利用的是人数为\(X\),分数集合为\(A\)的比赛方案数一定,与某人详细的得分是没有关系的.所以可以用记搜.把最后几个人剩余的分数的方案数存下就好了

\(Code\)

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int mod=1e9+7;

int read(){

    int x=0,f=1;char c=getchar();

    while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();

    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();

    return x*f;

}

map<int,int> hah;

int aim[20],now[20],fx,fy,ans,b[11],n,m,js;

int dfs(int x,int y){

    if(x==n) return 1;

    if((n-y+1)*3<aim[x]-now[x]) return 0;

    if(y==n+1){

    for(int i=x+1;i<=n;i++)

        b[i]=aim[i]-now[i];

    sort(b+x+1,b+1+n),ans=0;

    for(int i=x+1;i<=n;i++)

        ans=ans*28+b[i];

    if(hah.find(ans)!=hah.end()) return hah[ans];

    else return hah[ans]=dfs(x+1,x+2);

    }

    int res=0;

    if(now[x]+2<aim[x]&&fx)

    now[x]+=3,fx--,res+=dfs(x,y+1),now[x]-=3,fx++;

    if(now[x]<aim[x]&&now[y]<aim[y]&&fy)

    now[x]++,now[y]++,fy--,res+=dfs(x,y+1),now[x]--,now[y]--,fy++;

    if(now[y]+2<aim[y]&&fx)

    now[y]+=3,fx--,res+=dfs(x,y+1),now[y]-=3,fx++;

    return res%mod;

}

main(){

    n=read(),m=n*(n-1);

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

    aim[i]=read(),js+=aim[i];

    sort(aim+1,aim+1+n);

    fx=js-m,fy=(m-2*fx)>>1;

    printf("%lld",dfs(1,2)%mod);

}