Skip to content

「CQOI2009」循环赛

题解710 字
# 2009 # 洛谷 # BZOJ # 搜索 # CQOI
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

nn 支队伍比赛，每两支队伍比赛一次，平 11 胜 33 负 00。

给出队伍的最终得分，求有多少种可能的分数表。

提示

平 11 胜 33 负 00：

  • 若两支队伍打平，则各得到 11 分；
  • 否则，胜利的队伍得到 33 分，被打败的队伍得到 00 分。

#输入格式

第一行包含一个正整数 nn，表示队伍的个数。第二行包含 nn 个非负整数，即每支队伍的得分。

#输出格式

输出仅一行，即可能的分数表数目。保证至少存在一个可能的分数表。

#输入输出样例

样例输入 #1

6
5 6 7 7 8 8

样例输出 #1

121

#数据范围与提示

对于 100%100\% 的数据，n≤8n \le 8。

#思路

搜索卡常题，有几个剪枝：

  1. 如果当前得分已经大于最终得分，则答案一定不合法。

    C++
    12
    13
    14
    15
    16
    17
    void dfs(int x, int y) {
        // 当前得分已经大于最终得分
        if (s[x] > a[x]) return;

        // 如果以后的比赛全赢也小于最终得分
        if (s[x] + (n - y + 1) * 3 < a[x]) return;

  2. 如果以后的比赛全赢也不能达到最终得分，则答案一定不合法。

    C++
    14
    15
    16
    17
    18
    19
    if (s[x] > a[x]) return;

    // 如果以后的比赛全赢也小于最终得分
    if (s[x] + (n - y + 1) * 3 < a[x]) return;

    if (x == n && s[x] == a[x]) {

  3. 最后一场比赛时如果与目标分数的差值为 22，显然无法凑齐，答案不合法。

    96 分代码C++
    25
    26
    27
    28
    29
    30
    31
    if (y == n) {
        int t = a[x] - s[x];

        // 最后一场比赛无法凑出 2 分
        if (t == 2) return;

        t = t == 0 ? 3 : t == 1;

#代码

C++
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <iostream>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 15;
const int mod = 1e9 + 7;

int n, a[N], s[N], ans;

void dfs(int x, int y) {
    // 当前得分已经大于最终得分
    if (s[x] > a[x]) return;

    // 如果以后的比赛全赢也小于最终得分
    if (s[x] + (n - y + 1) * 3 < a[x]) return;

    if (x == n && s[x] == a[x]) {
        if (++ans == mod) ans -= mod;

        return;
    }

    if (y == n) {
        int t = a[x] - s[x];

        // 最后一场比赛无法凑出 2 分
        switch (t) {
            case 0: {
                s[y] += 3;
                dfs(x + 1, x + 2);
                s[y] -= 3;

                break;
            }

            case 1: {
                s[x] += 1;
                s[y] += 1;
                dfs(x + 1, x + 2);
                s[x] -= 1;
                s[y] -= 1;

                break;
            }

            case 3: {
                s[x] += 3;
                dfs(x + 1, x + 2);
                s[x] -= 3;

                break;
            }
        }

        return;
    }

    // x 胜
    s[x] += 3;
    s[y] += 0;
    dfs(x, y + 1);
    s[x] -= 3;
    s[y] -= 0;

    // 平局
    s[x] += 1;
    s[y] += 1;
    dfs(x, y + 1);
    s[x] -= 1;
    s[y] -= 1;

    // y 胜
    s[x] += 0;
    s[y] += 3;
    dfs(x, y + 1);
    s[x] -= 0;
    s[y] -= 3;
}

int main() {
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    dfs(1, 2);

    cout << ans << endl;

    return 0;
}