题解 P3230 【[HNOI2013]比赛】
zrz_orz
2018-11-01 21:29:40
> 这是一道搜索题
# 不要尝试复制代码，我说过了。。
看到数据范围为 N <= 10 就自然而然想到搜索，或者，~~状压DP~~
不过作为菜鸡，只会DFS
首先想到的是枚举 1 vs 2 ,1 vs 3 , 1 vs 4 ...
```cpp
void dfs(int u, int v) {
if (u > n) {
for (int i = 1; i <= n; i++) if (a[i] == s[i]) return;
ans++;
return;
}
a[u] += 3;
dfs(u, v + 1);
a[u] -= 3;
a[v] += 3;
dfs(u, v + 1);
a[v] -= 3;
a[v]++, a[u]++;
dfs(u, v + 1);
a[v]--, a[u]--;
}
```
但这样毫无疑问会超时，考虑如何剪枝
### 剪枝1：
显然当一支球队当前得分已经超过他本来分数时，由于没有减分的选择，所以这显然不合法。
```cpp
if (a[i] > s[i]) return;
```
### 剪枝2：
如果发现当前枚举的这支队伍后面的比赛无论怎么赢都凉了，显然这也不合法
```cpp
if (a[i] + 3 * (n - v + 1) < s[i]) return;
```
### 剪枝3：
设分出胜负的比赛场次的次数为 cnt\_win，平局的场次 cnt\_draw
那么必然有
$$
cnt_win + cnt_draw = n \* (n - 1) / 2
3 \* cnt_win + 2 \* cnt_draw = sum_score
$$
这两个线性方程组显然有通解
```cpp
for (int i = 1; i <= n; i++) {
scanf ("%d", &s[i]);
sum += s[i];
}
cnt_win = sum - n * (n - 1);
cnt_draw = (sum - 3 * cnt_win) >> 1;
```
### 剪枝4 ：
因为比赛的分数与顺序无关，所以我只需要掌握某一种分数集合的方案数，在以后的过程中就可以直接用，避免重复预算。考虑如何储存，暴力hash就可以了，自然溢出一般是不会爆炸的。
```cpp
if (y > n) {
for (int i = x + 1; i <= n; i++) b[i] = s[i] - a[i];
sort(b + 1 + x, b + n + 1, cmp);
ll hash_now = 0;
for (int i = x + 1; i <= n; i++) hash_now = hash_now * 27 + b[i];
if (hash.find(hash_now) != hash.end()) return hash[hash_now];
else return hash[hash_now] = dfs(x + 1, x + 2);
}
```
### 总代码
```cpp
#include <bits/stdc++.h>
#define ll long long
#define N 101
#define MOD 1000000007
using namespace std;
int n, cnt_win, cnt_draw;
int s[N], a[N], b[N], sum;
map<ll, ll>hash;
bool cmp(int x, int y) {
return x > y;
}
ll dfs(int x, int y) {
ll res = 0;
if (x == n) return 1;
if (a[x] + (n - y + 1) * 3 < s[x]) return 0;
if (y > n) {
for (int i = x + 1; i <= n; i++) b[i] = s[i] - a[i];
sort(b + 1 + x, b + n + 1, cmp);
ll hash_now = 0;
for (int i = x + 1; i <= n; i++) hash_now = hash_now * 27 + b[i];
if (hash.find(hash_now) != hash.end()) return hash[hash_now];
else return hash[hash_now] = dfs(x + 1, x + 2);
}
if (3 + a[x] <= s[x] && cnt_win) {
cnt_win--;
a[x] += 3;
(res += dfs(x, y + 1)) %= MOD;
cnt_win++;
a[x] -= 3;
}
if (1 + a[x] <= s[x] && 1 + a[y] <= s[y] && cnt_draw) {
cnt_draw--;
a[x]++, a[y]++;
(res += dfs(x, y + 1)) %= MOD;
cnt_draw++;
a[x]--, a[y]--;
}
if (3 + a[y] <= s[y] && cnt_win) {
cnt_win--;
a[y] += 3;
(res += dfs(x, y + 1)) %= MOD;
cnt_win++;
a[y] -= 3;
}
return res % MOD;
}
int main() {
scanf ("%d", &n);
for (int i = 1; i <= n; i++) {
scanf ("%d", &s[i]);
sum += s[i];
}
cnt_win = sum - n * (n - 1);
cnt_draw = (sum - 3 * cnt_win) >> 1;
sort(s + 1, s + n + 1, cmp);
printf("%lld\n", dfs(1, 2));
return 0;
}
```