NOTE
题库补题链接：码蹄集

A - 侠累擅权韩#

关键词：签到

Code#

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
int main()
5
{
6
    string s;
7
    cin >> s;
8

9
    reverse(s.begin(), s.end());
10

11
    cout << s << endl;
12
    return 0;
13
}

B - 仲子受辱恨#

关键词：签到

Code#

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
const int N = 1010;
5
string s[N];
6
int res[N];
7

8
int main()
9
{
10
    int n, m;
11
    cin >> n >> m;
12

13
    for (int i = 0; i < n; i++)
14
        cin >> s[i];
15

16
    while (m--)
17
    {
18
        string t;
19
        cin >> t;
20

21
        for (int i = 0; i < n; i++)
22
        {
23
            // cout << s[i].find(t) << endl;
24
            if (s[i].find(t) == 0)
25
                res[i]++;
26
        }
27
    }
28

29
    for (int i = 0; i < n; i++)
30
        cout << res[i] << " ";
31
    return 0;
32
}

C - 重金求死士#

关键词：暴力

Code#

1
#include <bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
const int N = 1010;
5

6
ll n, m, t1, t2;
7
ll g[N][N];
8
ll res;
9

10
ll quer(int lx, int ly, int rx, int ry)
11
{
12
    ll res = 0;
13
    for (int i = lx; i <= rx; i++)
14
    {
15
        for (int j = ly; j <= ry; j++)
16
            res ^= g[i][j];
17
    }
18
    return res;
19
}
20

21
int main()
22
{
23
    cin >> n >> m >> t1 >> t2;
24
    for (int i = 1; i <= n; i++)
25
        for (int j = 1; j <= m; j++)
26
            cin >> g[i][j];
27

28
    for (int lx = 1, ly = 1;;)
29
    {
30
        if (ly > m)
31
        {
32
            lx += t1, ly = 1;
33
            continue;
34
        }
35

36
        if (lx > n)
37
            break;
38

39
        int rx = lx + t1 - 1, ry = ly + t2 - 1;
40

41
        res += quer(lx, ly, rx, ry);
42
        ly += t2;
43
    }
44
    cout << res << endl;
45

46
    return 0;
47
}

D - 屠肆会聂政#

关键词：贪心

思路#

赛时要是想到就能金牌了，唉唉。不知道自己练了这么半天有什么用。——2026.5.25 23:55

由于传统上升子序列的模板时间复杂度太大，所以考虑贪心做。

为了找出一个长度至少为 3 的递增子序列，我们在遍历查询区间 [l, r] 时，只需要维护两个变量：

min1：目前遇到的最小元素。
min2：目前遇到的、排在 min1 后面且大于 min1 的最小元素。

初始化两个变量为无穷大，在遍历过程中如果当前元素 <= min1，就更新 min1，否则如果 <= min2 就更新 min2，否则（比 min2 还大，我们就找到了一个大于 min1 且大于 min2 的元素，这就意味着一定存在一个长度至少为 $3$ 的上升序列。

时间复杂度 $O(n)$ 。

Code#

1
#include <bits/stdc++.h>
2
using namespace std;
3
const int N = 1e4 + 10;
4

5
int a[N], n, q;
6

7
bool query(int l, int r)
8
{
9
    int min1 = 2e9, min2 = 2e9;
10
    for (int i = l; i <= r; i++)
11
    {
12
        if (a[i] <= min1)
13
            min1 = a[i];
14
        else if (a[i] <= min2)
15
            min2 = a[i];
16
        else
17
            return true;
18
    }
19
    return false;
20
}
21

22
int main()
23
{
24
    cin >> n >> q;
25
    for (int i = 1; i <= n; i++)
26
        cin >> a[i];
27
    while (q--)
28
    {
29
        int l, r;
30
        cin >> l >> r;
31
        cout << (query(l, r) ? "Yes" : "No") << endl;
32
    }
33
    return 0;
34
}

E - 母终诺赴义#

关键词：线性DP

思路#

题目给了一个 $2 \times n$ 的网格（只有 0 和 1 两行，列是从 1 到 $n$ ）。假设我们有两个黑色的落脚点，分别在 $(r_1, c_1)$ 和 $(r_2, c_2)$ 。它们之间的曼哈顿距离是 $|r_1 - r_2| + |c_1 - c_2|$ 。

题目要求这个距离必须 $\ge d$ 。我们分两种情况讨论：

如果在同一行 ( $r_1 = r_2$ )：距离为 $|c_1 - c_2|$ 。这就要求两列的跨度 $\ge d$ 。
如果在不同行 ( $r_1 \neq r_2$ )：距离变成 $1 + |c_1 - c_2|$ 。这就要求两列的跨度 $\ge d - 1$ 。

题目要求任意两格黑色记号之间的曼哈顿距离都不小于 $d$ ，实际上有一个更强的性质：当 $d \ge 2$ 时，只要相邻的两个黑格子满足这个性质，所有的黑格子就都可以满足。

推导：假设有三个黑格子从左到右按列排开，列号是 $c_1 < c_2 < c_3$ 。如果 $c_2$ 和 $c_1$ 满足条件，说明 $c_2 - c_1 \ge d - 1$ 。如果 $c_3$ 和 $c_2$ 满足条件，说明 $c_3 - c_2 \ge d - 1$ 。那么 $c_3$ 和 $c_1$ 的跨度就是 $c_3 - c_1 \ge 2d - 2$ 。只要 $d \ge 2$ ，必有 $2d - 2 \ge d$ ，这说明首尾格子的距离直接就是合法的。

这意味着我们只需要关心每一步操作的“上一个黑格子”在哪里，考虑线性DP。

状态表示：定义 $f[i]$ 表示以第 $i$ 列的第 0 行作为最后一个黑格子，且合法的染色方案数。由于网格只有两行，是完全对称的，因此以第 $i$ 列第 1 行结尾的方案数也是 $f[i]$ 。

考虑对于第 $i$ 列第 0 行的这颗新棋子，它的上一步可以从哪里转移过来：

上一步在同行（第 0 行）： 列数 $j$ 必须满足 $i - j \ge d \implies j \le i - d$ 。
上一步在不同行（第 1 行）： 列数 $j$ 必须满足 $i - j \ge d - 1 \implies j \le i - d + 1$ 。
没有上一步： 这颗棋子是第一个黑点（1 种情况）。

状态转移方程： $f[i] = 1 + \sum_{j=1}^{i-d} f[j] + \sum_{j=1}^{i-d+1} f[j]$ ，这里使用了 $f[j]$ 替代第 $1$ 行的方案数，因为他们对称相等。

对于方程中的两个求和式子，可以通过维护前缀和来 $O(1)$ 计算。

最终答案为第 $0$ 行的所有结尾方案 + 第 $1$ 行的所有结尾方案，再加上一种“一个格子都不涂”的方案。

注意特判 $d = 1$ 的情况，只要是两个不一样的格子，曼哈顿距离肯定 $\ge 1$ ，因此一共 $2n$ 个格子，答案为 $2^{2n}=4^n$ 。

Code#

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
// clang-format off
5
#define endl '\n'
6
#define all(x) (x).begin(), (x).end()
7
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
8
// clang-format on
9

10
using ll = long long;
11
using ull = unsigned long long;
12
using pii = pair<int, int>;
13
using pdd = pair<double, double>;
14
using pll = pair<long long, long long>;
15
using i128 = __int128;
16

17
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
18
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
19
const int inf = 0x3f3f3f3f;
20
const int N = 0;
21
const ll mod = 1e9 + 7;
22

23
ll qmi(ll a, ll k)
24
{
25
    ll res = 1;
26
    while (k)
27
    {
28
        if (k & 1)
29
            res = (res * a) % mod;
30
        a = (a * a) % mod;
31
        k >>= 1;
32
    }
33
    return res;
34
}
35

36
void solve()
37
{
38
    int n, d;
39
    cin >> n >> d;
40

41
    if (d == 1)
42
    {
43
        cout << qmi(4, (ll) n) << endl;
44
        return;
45
    }
46

47
    vector<ll> dp(n + 1, 0), sum(n + 1, 0);
48

49
    for (int i = 1; i <= n; i++)
50
    {
51
        ll dp0 = (i - d >= 0) ? sum[i - d] : 0;
52
        ll dp1 = (i - d + 1 >= 0) ? sum[i - d + 1] : 0;
53

54
        dp[i] = (1 + dp0 + dp1) % mod;
55

56
        sum[i] = (sum[i - 1] + dp[i]) % mod;
57
    }
58

59
    ll res = (2 * sum[n] + 1) % mod;
60
    cout << res << endl;
61
}
62

63
int main()
64
{
65
    fastio();
66

67
    int T = 1;
68
    // cin >> T;
69

70
    while (T--)
71
        solve();
72

73
    return 0;
74
}