题解 P3154 【[CQOI2009]循环赛】

Celtic · 2020-11-27 19:32:27 · 题解

upd on 2025.8.18 修复 latex

算法：深度优先搜索（暴力（逃
观察到 n\leq 8，所以我们可以用搜索来解决这道题。
如果爆搜的话可以拿到 84 分的好成绩~
但这是不够的，我们需要剪枝。
很明显，对于每场结束的比赛，双方的得分都是不减的，所以当前搜到的这个人如果得分要比他的最终得分大的话就可以剪枝。
从 IDA* 方面考虑，设当前搜到 (x,y)的比赛，假如 x 和 y~n比赛全都胜利，得到的分将是 now_x+3(n-y+1)（ now_i 表示 i 搜索到现在得分是多少）。
加上这两个剪枝，根据你的卡常水平可以拿到 92-96 分的高分。
接下来考虑优化搜索顺序，显然先搜最终得分大的一定状态少，因为得分少的会被得分大的影响，从大的开始搜后面的无用状态会尽可能的少，所以我们按从大到小的顺序将得分排序进行搜索。
然后，我们可以发现胜场和负场对总分来说是等价的，贡献都是 3 ，平场贡献是 2。我们还知道总得分（\sum_{i=1}^{n}a_i）和总场数（ \frac{n\times(n+1)}{2}）。于是我们可以设胜场（负场）一共有 x 场，平场一共有 y 场，可以列出方程组

\begin{cases} 3x+2y=\sum_{i=1}^n a_i\\ x+y=\frac{n\times(n-1)}{2}\\ \end{cases}

解之可得

\begin{cases} x=-n\times(n-1)+\sum_{i=1}^n a_i\\ y=\frac{3n\times(n-1)}{2}-\sum_{i=1}^na_i\\ \end{cases}

现在我们还能优化吗？
答案是：能。
有个东西叫做记忆化搜索，就是把搜到的结果记录下来，下次如果再要搜同样的状态时直接用就可以了。
那对于这道题，剩余需要得的分数数组相同时，搜索的结果是一定的，所以用哈希记录一下就可以了。
至此，所有剪枝完毕。

\sf{Code}

#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define re register
#define N 101001
#define MAX 2001
#define inf 1e18
using namespace std; 
typedef int ll;
typedef double db;
const ll mod=1000000007;
inline void read(re ll &ret)
{
    ret=0;re char c=getchar();re bool pd=false;
    while(!isdigit(c)){pd|=c=='-';c=getchar();}
    while(isdigit(c)){ret=(ret<<1)+(ret<<3)+(c&15);c=getchar();};
    ret=pd?-ret:ret;
    return;
}
ll n,a[N],ans,allx,ally,val[N],st[N];
ll b[MAX][MAX];
map<ll,ll>mp;
inline bool cmp(re ll x,re ll y)
{
    return x>y;
}
inline ll dfs(re ll x,re ll y,re ll nowx,re ll nowy)
{
    if(x==n)
        return 1;
    if(val[x]+(n-y+1)*3<a[x])
        return 0;
    if(y>n)
    {
        for(re int i=x+1;i<=n;i++)
            st[i]=a[i]-val[i];
        sort(st+x+1,st+n+1);
        re ll now=0;
        for(re int i=x+1;i<=n;i++)
            now=now*28+st[i];
        if(mp.find(now)!=mp.end())
            return mp[now];
        return mp[now]=dfs(x+1,x+2,nowx,nowy);
    }
    re ll ret=0;
    if(val[y]+3<=a[y]&&nowx)
        val[y]+=3,ret+=dfs(x,y+1,nowx-1,nowy),ret%=mod,val[y]-=3;
    if(val[x]+1<=a[x]&&val[y]+1<=a[y]&&nowy)
        val[x]++,val[y]++,ret+=dfs(x,y+1,nowx,nowy-1),ret%=mod,val[x]--,val[y]--;
    if(val[x]+3<=a[x]&&nowx)
    val[x]+=3,ret+=dfs(x,y+1,nowx-1,nowy),ret%=mod,val[x]-=3;
    return ret;
}
ll sum;
signed main()
{
    read(n);
    for(re int i=1;i<=n;i++)
        read(a[i]),sum+=a[i];
    allx=sum-n*n+n;
    ally=((sum-3*allx)>>1);
    sort(a+1,a+n+1,cmp);
    printf("%d\n",dfs(1,2,allx,ally));
    exit(0);
}