Skip to content

「CQOI2009」循环赛

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

nn 支队伍比赛,每两支队伍比赛一次,平 113300

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

提示

113300

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

#输入格式

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

#输出格式

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

#输入输出样例

样例输入 #1

6
5 6 7 7 8 8

样例输出 #1

121

#数据范围与提示

对于 100%100\% 的数据,n8n \le 8

#思路

搜索卡常题,有几个剪枝:

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

    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. 如果以后的比赛全赢也不能达到最终得分,则答案一定不合法。

    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 分代码
    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;

#代码

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;
}