题解 P3230 【[HNOI2013]比赛】

zrz_orz · 2018-11-01 21:29:40 · 题解

这是一道搜索题

不要尝试复制代码，我说过了。。

看到数据范围为 N <= 10 就自然而然想到搜索，或者，状压DP

不过作为菜鸡，只会DFS

首先想到的是枚举 1 vs 2 ,1 vs 3 , 1 vs 4 ...

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：

显然当一支球队当前得分已经超过他本来分数时，由于没有减分的选择，所以这显然不合法。

if (a[i] > s[i]) return;

剪枝2：

如果发现当前枚举的这支队伍后面的比赛无论怎么赢都凉了，显然这也不合法

if (a[i] + 3 * (n - v + 1) < s[i]) return;

剪枝3：

设分出胜负的比赛场次的次数为 cnt_win，平局的场次 cnt_draw

那么必然有

这两个线性方程组显然有通解

  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就可以了，自然溢出一般是不会爆炸的。

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

总代码

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