洛谷3230 [HNOI2013]比赛

Luogu

BZOJ

分析

首先考虑暴力。对每一场比赛的结果爆搜,最后再判断即可。

再加上一些玄学剪枝:

  • 搜索时,限制每个人的得分不超过总分。
  • 如果一个人赢了之后的所有比赛也达不到总分,直接return
  • 设比赛的总分为$su$,分出胜负的有$sx$场,平局的有$sy$场,那么得到:

$\begin{cases}3\times sx+2\times sy=su\\sx+sy=\frac{n(n-1)}{2}\end{cases}$

于是可以解出$sx$和$sy$,然后可以限制场数了。

加上这些剪枝后,大概有$60$分。考虑怎么进一步优化。

发现所有队伍是没有区别的,也就是说人数为$s$,分数集合为$\{a\}$的方案数是相同的。

于是可以记忆化,hash一下存到unordered_map里去就行了。

然后就可以过了。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <tr1/unordered_map>
#define re register
typedef long long ll;
using namespace std;
using namespace std::tr1;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=10+10;
const int MOD=1e9+7;
const int BASE=28;

inline int cmp(const int x,const int y) { return x>y; }
inline void add(int& x,int y) { x+=y; if (x>=MOD) x-=MOD; }

int n,s[N],a[N],b[N];
unordered_map<ll,int> mem;
unordered_map<ll,int> vis;
int su,sx,sy;

inline int dfs(int u,int v) { //u VS v
    if (u==n) return 1;
    if (a[u]+3*(n-v+1)<s[u]) return 0;
    int rt=0;
    if (v>n) {
        for (re int i=u+1;i<=n;++i) b[i]=s[i]-a[i];
        sort(b+u+1,b+n+1);
        ll S=0;
        for (re int i=u+1;i<=n;++i) S=S*BASE+b[i];
        if (vis[S]) return mem[S];
        else return vis[S]=1,mem[S]=dfs(u+1,u+2);
    }
    if (a[u]+3<=s[u]&&sx)
        a[u]+=3,--sx,add(rt,dfs(u,v+1)),++sx,a[u]-=3;
    if (a[u]+1<=s[u]&&a[v]+1<=s[v]&&sy)
        ++a[u],++a[v],--sy,add(rt,dfs(u,v+1)),++sy,--a[v],--a[u];
    if (a[v]+3<=s[v]&&sx)
        a[v]+=3,--sx,add(rt,dfs(u,v+1)),++sx,a[v]-=3;
    return rt;
}

int main() {
    n=read();
    for (re int i=1;i<=n;++i) s[i]=read(),su+=s[i];
    sx=su-n*n+n,sy=(su-sx*3)/2;
    sort(s+1,s+n+1,cmp);
    printf("%d\n",dfs(1,2));
    return 0;
}
最后修改:2019 年 09 月 24 日 10 : 26 PM

发表评论