Gym100078H-History-of-Football题解

发表于 分类于

题目传送门

题意：有 nn 支球队，每两支球队之间都会进行一场较量，赢者积 33 分，输者积 00 分，如果平局则各积 11 分。给出每支球队的最终积分，求方案数。n≤8n\le 8。

首先考虑常规搜索。直接搜索每两支球队的比赛结果，中途可以进行可行性剪枝：如果当前球队剩下的比赛全赢也不能超过目标得分则直接返回；如果当前球队已经超过了目标的分则直接返回。关于搜索的顺序，可以每次只考虑一支球队，搜索时改变第二支球队，搜完这支球队后直接检查是否合法。反映在积分矩阵上则为按行搜索。

以上的做法虽然可以通过本题，但跑得非常慢，于是考虑进一步优化。

首先，我们可以使用两层搜索嵌套的思路来实现：外层搜索考虑“当前球队”，内层搜索考虑“和其他球队如何匹配”。为了代码实现简便，这里外层搜索倒序搜索。搜索的过程中维护一个数组（具体可用 vector），表示每个球队还剩多少积分等待匹配。由于是倒序搜索，每搜一支球队一定是将积分全部耗光（否则不合法），所以可以直接从 vector 里删除最后一个元素。内层搜索时顺序考虑每一支球队，考虑和最后一支球队形成什么结果。递归时改变数组中的值，回溯时恢复即可。

有了框架，考虑如何剪枝。一个直接的剪枝与常规搜索一样，为：如果当前球队剩下的比赛全赢也达不到剩下的目标得分（因为这里数组存的是还剩多少积分等待匹配）。还可以有一个剪枝：搜索时维护当前的剩余积分之和，由于每进行一场比赛都会产生 22 或 33 分的总积分值，所以可以根据剩下的积分和以及剩下的局数进行一次剪枝。

接下来就到了这个做法最核心的地方：这个搜索可以进行记忆化。在外层搜索中，对于固定的“剩余数组”，剩余的匹配方式的方案数不变，而相同的“剩余数组”是非常容易重复计算的，比如 a→c,b−da\to c,b-d 和 a−d,b→ca-d,b\to c 在考虑 c,dc,d 时的剩余数组是相同的（箭头表示打败的情况）。由于记忆化的内容为一个数组，所以可以使用哈希的方式来保存。

By cxm1024, from Myth5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int hsh(vector<int> &a) {
    long long res=0;
    for(int v:a) res=(res*31+v)%mod;
    return res;
}
unordered_map<int,int> mp;
int dfs_out(vector<int> &a,int sum);
int dfs_in(vector<int> &a,int now,int sum) {
    int n=a.size(),res=0;
    if(a.back()>(n-1-now)*3) return 0;
    //剪枝一
    if(sum<(n*(n-1)/2-now)*2||sum>(n*(n-1)/2-now)*3) return 0;
    //剪枝二
    if(now==n-1) {
        vector<int> b(a.begin(),a.end()-1);
        return dfs_out(b,sum);
        //考虑完一支球队，进行下一支
    }
    if(a[now]>0&&a.back()>0) {
        a[now]--,a.back()--;
        if(a[now]<=(n-1-1)*3)//相当于对now提前进行剪枝一
            res+=dfs_in(a,now+1,sum-2);
        a[now]++,a.back()++;
    }//平局
    if(a[now]>=3) {
        a[now]-=3;
        //这里没必要剪枝，因为如果能剪掉，在上一层就已经被剪掉了
        res+=dfs_in(a,now+1,sum-3);
        a[now]+=3;
    }//内层的球队赢
    if(a.back()>=3) {
        a.back()-=3;
        if(a[now]<=(n-1-1)*3)//提前剪枝一
            res+=dfs_in(a,now+1,sum-3);
        a.back()+=3;
    }//当前考虑的外层球队赢
    return res;
}
int dfs_out(vector<int> &a,int sum) {
    if(a.empty()) return 1;
    //已经清空说明经受住了所有剪枝的考验，一定合法
    int tmp=hsh(a);
    if(mp.count(tmp)) return mp[tmp];
    //记忆化
    return mp[tmp]=dfs_in(a,0,sum);
}
signed main() {
    freopen("history.in","r",stdin);
    freopen("history.out","w",stdout);
    int n,sum=0;
    cin>>n;
    vector<int> a;
    for(int i=1;i<=n;i++) {
        int x;
        cin>>x;
        a.push_back(x);
        sum+=x;
    }
    cout<<dfs_out(a,sum)<<endl;
    return 0;
}