CF559C:Gerald and Giant Chess 题解

主要思路

这一道题其实挺好的,我们来分析一下。

首先,我们知道在一个方格纸上,从左上角到右下角的路径的数量是\(C_{H+W-2}^{H-1}\),可以理解为横向路径的选法总数。之后,我们来进行容斥。在本题中,我们需要容斥掉那些经过了至少一次黑点的路径数量。因为本题中黑点个数小于\(5000\),所以我们直接来跑一个\(O(n^2)\)的 DP。设\(F[i]\)为经过了此点的路径数,然后我们把右下角的点设为第\(n+1\)个点,最后答案存在\(F[n+1]\)处。我们可以很快得到一个递推式:

\[ F[i] = C_{x_i + y_i – 2}^{x_i – 1} – \sum_{j = 1}^{i-1} (F[j] * C_{x_i-x_j+y_i-y_j}^{x_i-x_j}),且x_i \geq x_j, y_i \geq y_j. \]

解释:对于到点\(i\)的路径,首先不考虑之前的黑点则有\( C_{x_i + y_i – 2}^{x_i – 1} \)种路;而要容斥掉至少经过过一次的黑点的路径,可以直接对于之前的每一个点进行计算,计算之前的点\(j\)到现在的点\(i\)有多少种路径。

代码

// CF559C.cpp
#include <bits/stdc++.h>
#define ll long long
#define pr pair<ll, ll>
using namespace std;
const int MOD = 1e9 + 7, MAX_N = 2020, LEVEL_RG = 200000;
ll level[200010], inv[200010], n, h, w, F[MAX_N];
pr pts[MAX_N];
ll quick_power(ll bas, ll tim, ll mod)
{
    ll ans = 1;
    while (tim)
    {
        if (tim & 1)
            ans = ans * bas % mod;
        bas = bas * bas % mod;
        tim >>= 1;
    }
    return ans;
}
ll C(ll n, ll m) { return level[n] * inv[n - m] % MOD * inv[m] % MOD; }
int main()
{
    scanf("%d%d%d", &h, &w, &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &pts[i].first, &pts[i].second);
    sort(pts + 1, pts + 1 + n);
    pts[n + 1].first = h, pts[n + 1].second = w;
    level[0] = inv[0] = 1;
    for (int i = 1; i <= LEVEL_RG; i++)
        level[i] = level[i - 1] * i % MOD;
    ll inv_bas = quick_power(level[LEVEL_RG], MOD - 2, MOD);
    for (int i = LEVEL_RG; i >= 1; i--)
        inv[i] = inv_bas, inv_bas = inv_bas * i % MOD;
    for (int i = 1; i <= n + 1; i++)
    {
        F[i] = C(pts[i].first + pts[i].second - 2, pts[i].first - 1) % MOD;
        for (int j = 1; j < i; j++)
            if (pts[j].first <= pts[i].first && pts[j].second <= pts[i].second)
                F[i] = (F[i] - F[j] * C(pts[i].first + pts[i].second - pts[j].first - pts[j].second, pts[i].first - pts[j].first)) % MOD;
    }
    printf("%lld", (F[n + 1] + MOD) % MOD);
    return 0;
}

P3914:染色计数题解

主要思路

这道题比较有趣,一开始我想出了\(O(n^3)\)的复杂度,打上去 TLE 之后思考前缀做差的方法,但是我太 Naive,不太相信(?)模意义下的减法,所以这个思路在我看了题解之后才搞定。

这道题的 DP 方程不难想到,为:

\[ dp[u][i] = \sum_{t \in dst} \sum_{j \in color(t)} dp[t][j], i \neq j \]

其实我们可以把第二维消掉,考虑总和\(tot[]\)数组,得:

\[ dp[u][i] = \sum_{t \in dst} tot[t] – dp[t][i] \]

然后就出来了。

代码

// P3914.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 5050, MOD = 1e9 + 7;
int head[MAX_N], current, n, m, tmpx, tmpy, dp[MAX_N][MAX_N], tot[MAX_N];
struct edge
{
    int to, nxt;
} edges[MAX_N << 1];
void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}
void dfs(int u, int fa)
{
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
            dfs(edges[i].to, u);
    for (int i = 1; i <= m; i++)
    {
        if (!dp[u][i])
            continue;
        for (int e = head[u]; e != -1; e = edges[e].nxt)
        {
            if (edges[e].to == fa)
                continue;
            dp[u][i] = (1LL * dp[u][i] * 1LL * (tot[edges[e].to] - dp[edges[e].to][i])) % MOD;
        }
        while (dp[u][i] < 0)
            dp[u][i] += MOD;
        tot[u] = (1LL * tot[u] + 1LL * dp[u][i]) % MOD;
    }
}
int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &tmpy);
        for (int j = 1; j <= tmpy; j++)
            scanf("%d", &tmpx), dp[i][tmpx] = 1;
    }
    for (int i = 1; i < n; i++)
        scanf("%d%d", &tmpx, &tmpy), addpath(tmpx, tmpy), addpath(tmpy, tmpx);
    dfs(1, 0);
    printf("%d", tot[1] % MOD);
    return 0;
}

用单调队列优化动态规划

Introduction

有的时候我们在日常写题时,会碰见这样的毒瘤 DP 题目,他们一般有以下特性:

  • 多维度动态规划
  • 循环层数很多,在极限数据下无法 AC。
  • 一般出现在区间 DP 中,一般暴力算法复杂度为\(O(n^3)\)。

这个时候我们可以使用单调队列来优化,时间复杂度可以进一步降至\(O(n^2)\)或者是\(O(nm)\)。如果有不会单调队列的同学呢可以去学习以下,顺便可以看看这篇文章:CH1201:最大子序和题解

Overall on this optimization technique

我们来看一道例题:Fence – POJ这道题是一道比较简单的经典 DP。设计状态\(dp[i][j]\)表示前\(i\)个人搞定了前\(j\)个单位的墙。写出方程式:

\[dp[i][j] = min_{S_i – l_i \leq k < S_i}\{dp[i-1][k]+profit_i*(j-k)\}\]

这样的话,整个算法的复杂度是\(O(n^3)\)的。我们能不能将其降为\(O(n^2)\)呢?我们可以把整个方程变个形,之后方程是这样的:

\[dp[i][j] = min_{S_i – l_i \leq k < S_i}\{dp[i-1][k]-profit_i*k\}+profit_i*j\]

我们发现,这样的话整个方程在\(i\)的循环之下,算是只跟变量\(k\)扯上关系了。我们会发现,只要有\(k_1<k_2\)且\(dp[i-1][k_1]-profit_i*k_1<dp[i-1][k_2]-profit_i*k_2\),那么就可以直接排除掉答案\(k_1\)。那么就可以使用单调队列来做到这一点。

下面是核心的 DP 代码:

int calc(int i, int k)
{
    return dp[i - 1][k] - wks[i].p * k;
}

// in ( int main() )
for (int i = 1; i <= k; i++)
{
    deque<int> q;
    for (int j = max(0, wks[i].s - wks[i].l); j <= wks[i].s - 1; j++)
    {
        while (!q.empty() && calc(i, q.back()) <= calc(i, j))
            q.pop_back();
        q.push_back(j);
    }
    for (int j = 1; j <= n; j++)
    {
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        if (j >= wks[i].s)
        {
            while (!q.empty() && q.front() < j - wks[i].l)
                q.pop_front();
            if (!q.empty())
                dp[i][j] = max(dp[i][j], calc(i, q.front()) + wks[i].p * j);
        }
    }
}

In Conclusion

整个单调队列优化会为后面的斜率优化做基础(因为我学这个单调队列优化就是有一道题要求使用斜率优化),所以请务必搞懂这个操作。

P2051:[AHOI2009]中国象棋题解

这是一道比较优秀的方案数 DP 题。乍一看以为是状压 DP,然后发现数据范围过大所以只能重新思考(也就是看题解)。我们可以写出状态格式:

\[dp[ln][opit][tpit],其中 ln 为行号,opit 代表第 ln 行内一个棋子的列数,tpit 代表第 ln 行内两个棋子的列数。\]

然后我们就可以根据不同情况来进行转移了。我们来看下面几组代码,其中每组都会有对应方程的意义。我们记\(dp[ln+1]\)为当前行号。首先,我们先要判定转移源的方案数不为\(0\),之后再进行转移。

// 不放置棋子的情况;
// Situation without placing;
dp[ln + 1][opit][tpit] = (dp[ln + 1][opit][tpit] + dp[ln][opit][tpit]) % MOD;
// 在不放置棋子的位置上放置一个棋子;
// Situation of placing one on empty lines;
if (M - opit - tpit >= 1)
    dp[ln + 1][opit + 1][tpit] = (dp[ln + 1][opit + 1][tpit] + dp[ln][opit][tpit] * (M - opit - tpit)) % MOD;
// 在放置了一个棋子的位置上放置一个棋子;
// Situation of placing one on lines with only piece;
if (opit >= 1)
    dp[ln + 1][opit - 1][tpit + 1] = (dp[ln + 1][opit - 1][tpit + 1] + dp[ln][opit][tpit] * opit) % MOD;
// 在两个没有放置棋子的位置上放置两个棋子,其中 C2(num) = C^num_2;
// Situation of placing two pieces on the two empty slots;
if (M - opit - tpit >= 2)
    dp[ln + 1][opit + 2][tpit] = (dp[ln + 1][opit + 2][tpit] + dp[ln][opit][tpit] * C2(M - opit - tpit)) % MOD;
// 在一个没有棋子的位置和一个有一个棋子的位置放置共两个棋子;
// Situation of placing one on the empty and another on the only slot;
if (M - opit - tpit >= 1 && opit >= 1)
    dp[ln + 1][opit][tpit + 1] = (dp[ln + 1][opit][tpit + 1] + dp[ln][opit][tpit] * (M - opit - tpit) * opit) % MOD;
// 在两个一个棋子的位置放置共两个棋子;
// Situation of placing two on two only slots;
if (opit >= 2)
    dp[ln + 1][opit - 2][tpit + 2] = (dp[ln + 1][opit - 2][tpit + 2] + dp[ln][opit][tpit] * C2(opit)) % MOD;

完整源码:

// P2051.cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;
const int MX_N = 102, MOD = 9999973;
ll dp[MX_N][MX_N][MX_N], N, M;
ll C2(ll num)
{
    return (num * (num - 1)) / 2;
}
int main()
{
    scanf("%lld%lld", &N, &M);
    dp[0][0][0] = 1;
    for (int ln = 0; ln < N; ln++)
        for (int opit = 0; opit <= M; opit++)
            for (int tpit = 0; tpit + opit <= M; tpit++)
                if (dp[ln][opit][tpit])
                {
                    // 不放置棋子的情况;
                    // Situation without placing;
                    dp[ln + 1][opit][tpit] = (dp[ln + 1][opit][tpit] + dp[ln][opit][tpit]) % MOD;
                    // 在不放置棋子的位置上放置一个棋子;
                    // Situation of placing one on empty lines;
                    if (M - opit - tpit >= 1)
                        dp[ln + 1][opit + 1][tpit] = (dp[ln + 1][opit + 1][tpit] + dp[ln][opit][tpit] * (M - opit - tpit)) % MOD;
                    // 在放置了一个棋子的位置上放置一个棋子;
                    // Situation of placing one on lines with only piece;
                    if (opit >= 1)
                        dp[ln + 1][opit - 1][tpit + 1] = (dp[ln + 1][opit - 1][tpit + 1] + dp[ln][opit][tpit] * opit) % MOD;
                    // 在两个没有放置棋子的位置上放置两个棋子,其中 C2(num) = C^num_2;
                    // Situation of placing two pieces on the two empty slots;
                    if (M - opit - tpit >= 2)
                        dp[ln + 1][opit + 2][tpit] = (dp[ln + 1][opit + 2][tpit] + dp[ln][opit][tpit] * C2(M - opit - tpit)) % MOD;
                    // 在一个没有棋子的位置和一个有一个棋子的位置放置共两个棋子;
                    // Situation of placing one on the empty and another on the only slot;
                    if (M - opit - tpit >= 1 && opit >= 1)
                        dp[ln + 1][opit][tpit + 1] = (dp[ln + 1][opit][tpit + 1] + dp[ln][opit][tpit] * (M - opit - tpit) * opit) % MOD;
                    // 在两个一个棋子的位置放置共两个棋子;
                    // Situation of placing two on two only slots;
                    if (opit >= 2)
                        dp[ln + 1][opit - 2][tpit + 2] = (dp[ln + 1][opit - 2][tpit + 2] + dp[ln][opit][tpit] * C2(opit)) % MOD;
                }
    ll ans = 0;
    for (int i = 0; i <= M; i++)
        for (int j = 0; i + j <= M; j++)
            ans = (ans + dp[N][i][j]) % MOD;
    printf("%lld\n", ans);
    return 0;
}

 

Dilworth定理和拦截导弹问题

这道题目是我思考了很久的一道题目,可能是因为我太弱了吧。我们先来分析题目。

第一问

这一问是求一套系统能最大拦截的导弹数量。抽象化后,我们可以得出,其实这一问就是让我们求这个序列中最长的不上升序列。我们先来分析样例输入。

389 207 155 300 299 170 158 65

显然,对于这个序列,他的最长不上升序列是{389,300,299,170,158,65}。那么,我们如何用最佳的算法求出此子序列呢?

贪心策略

我们先设定一个指向变量cursor = 0,这个变量记录当前算法在序列S中的位置。我们再设定一个pos = 0的变量,记录我们子序列H的尾部位置。

如果S[cursor]>H[pos],我们可以直接把S[cursor]置于H的尾部,即H[++pos] = S[cursor]。而如果不是这样,我们则可以在H[0:pos],即0到pos这段区间内,总可以找到第一个小于S[cursor]的的量(事实上,我们可以使用二分搜索来查找这个量,因为序列H是拍好了顺序的),我们就让H[bias] = S[cursor]。反复如此。

为什么要把第一个在序列H中小于S[cursor]的赋为S[cursor]?因为当我们把这个值赋入后,我们后续需要插入数据的时候,便会更容易地加入数字(因为在相同位置下,值越大,后续加入的数字的限制也会缩小),也就会使这个子序列最长。

而如果我们要追求O(n log n)的做法时,便需要二分查找。接下来我来介绍两个函数。

lower_bound(start, end, key, [cmp])

该函数调用后会返回一个有序序列中第一个大于等于(如果有cmp函数传入,那就是另外一回事)key的元素地址。

upper_bound(start, end, key, [cmp])

该函数调用后会返回一个有序序列中第一个大于(如果有cmp函数传入,那就是另外一回事)key的元素地址。

奇怪的是,这两个函数跟字面上的完全不同,upper_bound和lower_bound在没有cmp参数传入的情况下,默认的序列排序情况是一致的。搭配之后,便可以获得O(n log n)的神奇速度。

第二问

Dilworth定理

在一个数字序列中,最大不上升子序列的个数为最大上升子序列的长度。亦而反之。

对于我这种蒟蒻而言,Dilworth定理能帮助到我的只是这句话。我曾经翻阅过很多博客,也翻阅过《组合数学》,我并没有找到易于理解的语句。而在我翻阅到一篇绝世神作之后,我便把我的理解归于这一句话。对于OIer而言,Dilworth最有力的部分便是这句话了。

解题思路

第二问的疑问是求出导弹防御系统的套数,根据Dilworth定理,套数应该等于最大不下降子序列的长度。所以,按照第一问的贪心思路,我们很容易类比出本题求最大不上升子序列的贪心策略。所以,在这里,我便不再赘述。