Oiclass 新 C 班选拔测试题解

终于考完了

额，这次一共 6 题，3 个小时，时间还是有点紧张，但是由于题目太难，最后还是比较舒服的拿了 15 名（总共多少人就不说了）。但是，满分 600 只骗拿到了 150。确实菜了点，下面总结一下每一道题目

A. #P3256. 排队

这一题一看就是打卡题，但是也是正常比赛我唯一 AC 的一题，呜呜。这道题又是一道 oiclass 从其他地方搬运的题，好像是来自 JZOI 的，但是我没有找到。直接进入正题

先看题目

一共有 \(n\) 个 TYoier ，有一些是巨佬一些是蒟蒻，然后因为巨佬比较喜欢打架，所以巨佬时间必须有 \(≥k\) 个的蒟蒻隔着，才不会打架。然后这个时候，闲得发慌的 CXL 就想让我们把不会打架的方案个数算出来（幸好不用输出每一种方案）。

看完题目

分析样例

样例的情况是 \(n=4,\ \ k=2\) 也就是说至少要隔开两个蒟蒻，大佬们才不会打架。那么我们分析一下究竟是哪几种方案是不会打架的

• 首先是没有大佬的情况，这个时候只有一种可能，即全是蒟蒻。
• 其次是有一位大佬的情况，这个时候有以下几种可能（B 为大佬，C 为蒟蒻）：\(\left\{\begin{array}{lr}CBBB\\BCBB\\BBCB\\BBBC \end{array} \right.\) 一共四种情况。
• 在最后是有两位大佬的情况，这是只有一种可能，即：\(BCCB\)。

\(\therefore 一共有\ 6\ 种可能，即\ ans=6\)

思路

我们这道题采用动态规划（DP）的方法。我们以每一个位置为一个阶段，并将阶段储存在一维数组 \(f\) 内，也就是说有 \(n\) 个阶段。

对于第 \(i\) 个阶段（\(0<i≤n\)），有两种可能： \[ \begin{array}{lr} 若\ i≤k:\\ 则: f_i=(i+1)\ mod\ 5000011\\ 若：i>k\\ 则:f_i=(f_{i-1}+f_{i-k-1})\ mod\ 5000011 \end{array} \] 也就是说我们的状态转移方程是这样的： \[ f_i=\left\{\begin{array}{lr} i≤k\ \ \ \ \ (i+1)\ mod\ 5000011\\ i>k\ \ \ \ \ (f_{i-1}+f_{i-k-1})\ mod\ 5000011 \end{array}\right. \] 那么我们的边界条件是什么呢？通过我们的分析，我们可以看出，边界条件就是 \(f_i=i+1\ \ (0<i≤k)\)

实现

实现的话很简单，只需要模拟就可以，注意一点：循环一定要从 \(0\) 开始，如果不是的话，那么等着 WA 吧

#include <iostream>

using namespace std;

int n, k, f[100009];

int main() {
    cin >> n >> k;
    for (int i = 0; i <= n; i++) {
        if (i <= k) {
            f[i] = (i + 1) % 5000011;
        } else {
            f[i] = (f[i - 1] + f[i - k - 1]) % 5000011;
        }
    }
    cout << f[n];
}

B, C, D, E, F 未完待续，欢迎催更