CQOI2009循环赛与HNOI2013比赛 —— ylxmf2005的OI教程

CQOI2009 循环赛

Description

$n$ 队伍比赛,每两支队伍比赛一次,平 $1$ 胜 $3$ 负 $0$.

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

$1 \leq n \leq 8$。

Solution

每两个队伍进行一次比赛,显然一共进行了 $\frac{n \times (n-1)}{2}$ 场比赛。

先讲暴搜:

  1. 我们枚举所有的比赛,是谁和谁打,情况怎么样,复杂度 $O(TLE \times TLE)$。
  2. 我们枚举每个人的比赛情况,每一个人与他后面的人进行比赛(假设有 $3$ 个人,那么枚举$1 \ 2, \ 1 \ 3, \ 2 \ 3$),复杂度 $O(TLE)$。与上一个算法有质的改变,下面的算法都是在本算法基础上的改进。

下面开始剪枝:

  1. 数学剪枝:设胜场一共为 $x$,平局一共为 $y$,得分一共为 $sum$。有 $x \times 3 + y \times 2 = sum$,$x + y = \frac{n \times( n + 1)}{2}$。下面闲得没事解一下小学方程:

    $$2 \times(x+ y) = n \times (n + 1)$$

    $$n \times(n + 1) + x = sum$$

    $$x = sum – n \times (n + 1)$$

    $$y = \frac{\frac{n \times( n + 1)}{2} – 3 \times x} {2}$$

    显然,我们胜场和平局都不能超过计算的。

  2. 可行性剪枝:如果当前的人无论怎么赢都打不到要求的分数就返回。假设当前与第 $i$ 个人比赛,那么最多能赢 $(n – i + 1)$ 场。

  3. 最优性剪枝:如果一个人与他后面的人比赛完了,他的得分与题目给定的得分的不同就返回。如果比赛过程中某一场比赛让当前的得分大于了给定的得分,那么也返回。

  4. 搜索顺序剪枝:我们对输入的数据从大到小排序。感性理解一下,我们先算大的,大的状态多,状态多的早早就被我们的各种剪枝剪没了(不加会超时)。

卡卡常就过了。代码略,见下面的数据加强版。

HNOI2013 比赛

Description

$n$ 队伍比赛,每两支队伍比赛一次,平 $1$ 胜 $3$ 负 $0$.

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

$1 \leq n \leq 10$。(注意数据范围)

Solution

这道题数据是经过加强的,原来的做法会超时。下面讲一个神奇的优化:记忆化搜索。

记忆化搜索?为什么要记忆化?怎么记忆化?会不会爆空间?

$a \ b \ c \ d \ e \ f \ g$

假设我们先搜索到了 $d$,我们确定了 $abcd$ 的一种状态。现在的总方案数为 $efg$ 的方案数。显然,$abcd$ 的方案数是前面确定的,那么按照之前的算法,后面的方案数我们需要递归计算,这是没问题的,但是我们发现,$abcd$ 的状态可能不只一种,我们在回溯回来更新 $abcd$ 后,我们发现,我们又要进行一次对 $defg$ 的搜索,我们在搜 $abcde$ 的一种状态,需要 $fg$ 的方案数 。相信现在你已经懂了,那么状态如何设计?因为 $abcd$ 的状态不同,可能会导致 $efg$ 的方案数不同,那么怎么办呢?

我们用初中学过的哈希解决就完事了,手算一下,正好不爆 $long \ long$,用红黑树 map 搞一下就好了。哈希前别忘记排序。复杂度 $O(AC)$。

Code

#include <bits/stdc++.h>
using namespace std;
#define re register
#define F first
#define S second
typedef long long ll;
typedef pair<int, int> P;
const int N = 10 + 5, INF = 0x3f3f3f3f, Base = 28, p = 1e9 + 7;
inline int read() {
    int X = 0,w = 0; char ch = 0;
    while(!isdigit(ch)) {w |= ch == '-';ch = getchar();}
    while(isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48),ch = getchar();
    return w ? -X : X;
}
int n, m, sum, win, draw;
int a[N], b[N], score[N];
unordered_map <ll, int> mp;//黑科技
bool cmp(int a, int b){
    return a > b;
}
inline ll dfs(int x, int y){
    if (score[x] + (n - y + 1) * 3 < a[x]) return 0;
    if (x == n) return 1;
    if (y == n + 1){
        if (score[x] != a[x]) return 0;
        for (int i = x + 1; i <= n; i++) b[i] = a[i] - score[i];
        sort(b + x + 1, b + n + 1);
        ll key = 0;
        for (int i = x + 1; i <= n; i++) key = key * Base + b[i];
        if (mp.find(key) != mp.end()) return mp[key];
        else return mp[key] = dfs(x + 1, x + 2);
    } 
    ll ans = 0;
    if (win && score[x] + 3 <= a[x]){
        score[x] += 3; win--;
        ans += dfs(x, y + 1);
        score[x] -= 3; win++;
    }
    if (draw && score[x] + 1 <= a[x] && score[y] + 1 <= a[y]){
        score[x]++, score[y]++; draw--;
        ans += dfs(x, y + 1);
        score[x]--, score[y]--; draw++;
    } 
    if (win && score[y] + 3 <= a[y]){
        score[y] += 3; win--;
        ans += dfs(x, y + 1);
        score[y] -= 3; win++;
    } 
    return ans % p;
}
int main(){
    n = read(); 
    for (int i = 1; i <= n; i++) a[i] = read(), sum += a[i];
    sort(a + 1, a + n + 1, cmp);
    win = sum - n * n + n;
    draw = (sum - 3 * win) / 2;
    printf("%lld\n", dfs(1, 2) % p);
    return 0;
}

恭喜你 AC 了两道省选题。

© ylxmf2005
All rights reserved.
本文不遵从 CC BY-SA 4.0 协议,转载请联系作者。

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据