T1

正解是单调队列，时间复杂度 $\Theta(n)$。

我们先把数组复制 $3$ 遍。等等，为什么不是两遍呢？

因为最大值有变化，某首歌是否满足条件的数据在变化，所以可能出现第一次可以播放，但第二次不行的情况。平时我们是复制两遍，所以这里要多复制一遍。

然后从第一首歌开始，一次遍历被复制了三遍的数组，维护一个单调递减的队列。当然，里面存的是数组下标，下标当然不是单调递减的，但是代表的喜爱值是递减的。

我们以样例举例：

3 2 5 3

1
2
3
i =   1  2  3  4  5  6  7  8  9  10 11 12
a =   3  2  5  3  3  2  5  3  3  2  5  3
ans = 0  0  0  0  0  0  0  0  0  0  0  0

每次遍历到一个数，依次进行如下操作：

第一步：判断队首元素是否符合标准，当前遍历到的元素 $i$ 是否满足要求，即是否有 $ai<\dfrac{a{q.\text{front()}}}{2}$。如果是，那么计算队首元素的答案（从它开始最多可以放多少首歌，即为当前遍历到的歌曲编号减去队首元素的编号）并把队首元素弹出。

注意队首可能不止一个元素不满足要求，需要连续弹出。

比如我们遍历到了 $6$ 号，然后单调队列现在长这样：

front {3, 4, 5} back 也就是 front {5, 3, 3} back

本来没什么问题，但是注意到 $2<\frac{5}{2}$，所以如果播放了 $3$ 号歌曲，就不能播放 $6$ 号歌曲了。那么，从 $3$ 号歌曲开始播放最多能播放 $6-3=3$ 首歌，也就是 $3,4,5$ 这三首。

1
2
3
4
5
                     v i遍历到这儿了
i =   1  2  3  4  5  6  7  8  9  10 11 12
a =   3  2  5  3  3  2  5  3  3  2  5  3
ans = 0  0  3  0  0  0  0  0  0  0  0  0
            ^答案被更新

第二步：把遍历到的元素放进单调队列。当然，为了保持单调，也许需要弹出队尾的一些元素。

其实这也是为什么不能用队列长度来更新答案的原因。有些数可能会被弹掉，此时直接用队列长度判断答案可能会遗漏。

遍历完数组之后就可以输出答案了，但是有个问题：

比如样例遍历完之后 ans 数组长这样：

0 0 3 0 0 0 3 0 0 0 3 0

那 $1,2,4$ 号怎么办呢？

其实这个很简单，你想一下，就以 $2$ 号歌曲举例，你先听一首到 $3$ 号歌曲，然后再按照 $3$ 号的答案计算不就行了吗？所以这里我们再倒序遍历一遍数组，如果某个下标的答案没被更新，就把答案更新为 在它后面的最近的一个本来就有答案的值 + 当前遍历到的下标和那个数的下标之差。

给出代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <cstdio>
#include <deque>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)

const int maxn = (int)3e5 + 5;

int n, N, a[maxn], ans[maxn];
std::deque<int> q;

inline void file() {
    freopen("playlist.in", "r", stdin);
    freopen("playlist.out", "w", stdout);
    return;
}

int main() {
    file();
    scanf("%d", &n);
    rep(i, 1, n) {
        scanf("%d", &a[i]);
        a[i + n] = a[i + (n << 1)] = a[i];
    }
    N = 3 * n;
    rep(i, 1, N) {
        while(!q.empty()/*防止 RE*/ && (a[i] << 1) < a[q.front()]) {
            ans[q.front()] = i - q.front();
            q.pop_front();
        }
        while(!q.empty() && a[q.back()] < a[i])
            q.pop_back();
        q.push_back(i);
    }
    int tot = 0, lst = N + 1;
    dep(i, N, 1) {
        if(ans[i]) {
            tot = 0;
            lst = i;
        } else
            ans[i] = ans[lst] + tot;
        ++tot;
    }
    rep(i, 1, n)
        printf("%d ", (ans[i] < n << 1) ? ans[i] : -1);
    return 0;
}

T2

二分很明显，关键是 $\text{check}$ 函数怎么写。

这里我们用 dp：$dp_{i,j}$ 代表用了 $i$ 次红色，$j$ 次绿色最多能覆盖到的神坛的编号（注意这个编号及以前的所有神坛都需要被覆盖）。

但是有一个问题：$r,g$ 的范围是 $10^9$，这样难道不会炸掉吗？

这里需要注意一下，因为 $n\le 2000$，所以只要 $r+g\ge 2000$，答案就一定是 $1$，直接输出即可。

那么我们就人为地把 $r,g$ 的范围降到了 $2000$。然后就可以开始愉快的 $\Theta(n^2)$ 啦！（口胡）

首先我们要想一下这个状态转移方程。假设我们这一次要用红色，那么我们要依托 $dp_{i-1,j}$ 的值，假设它为 $k$。我们已经覆盖到了第 $k$ 个神坛，所以，我们可以忽略第 $k$ 个和第 $k+1$ 个之间的那些空的坐标，直接把第 $k+1$ 个神坛作为左端点。

那右端点可以覆盖到哪里呢？这个需要预处理一下。我们设 $R_i$ 代表用红色的线段（长度为 $L$，就是我们需要 $\text{check}$ 的那个数），把第 $i$ 个神坛作为左端点，右端点能够覆盖的最大神坛编号，这个数是固定的。

至于怎么预处理，因为 $n$ 很小，$\Theta(n)$ 和 $\Theta(n^2)$ 都可以用。$\Theta(n)$ 就是用两个指针，先全都指着 $1$，然后一点一点往右走，保证两个指针之间的区间长度不超过 $L$ 但是最长，这样计算答案就可以了。

绿色同理，只不过是把 $L$ 换成 $2\times L$，$R$ 换成 $G$。

状态转移方程：

当然，如果你直接这么写的话会愉快的 WA 掉。

注意初始化：$dp$ 极小值，$dp_{0,0}=0$，且枚举需要从 $0$ 开始（注意有 $0$ 的时候需要特殊判断）。

然后还是 WA……

注意状态转移方程，这个方程可能会访问到 $R/G_{n+1}$，所以我们还需要一句：$G_{n+1}←n,R_{n+1}←n$。

然后就没了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <cstdio>
#include <cstring>
#include <algorithm>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)

const int maxn = 2005;

int n, r, g, a[maxn];
int R[maxn], G[maxn], dp[maxn][maxn];

inline void file() {
    freopen("light.in", "r", stdin);
    freopen("light.out", "w", stdout);
    return;
}

inline bool check(int L) {
    memset(dp, -0x3f, sizeof(dp));
    dp[0][0] = 0;
    int p = 1, q = 1;
    while(p <= n) {
        while(q <= n && a[q] - a[p] + 1 <= L)
            ++q;
        R[p] = q - 1;
        ++p;
    }
    p = 1, q = 1;
    while(p <= n) {
        while(q <= n && a[q] - a[p] + 1 <= L << 1)
            ++q;
        G[p] = q - 1;
        ++p;
    }
    G[n + 1] = R[n + 1] = n;
    rep(i, 0, r) {
        rep(j, 0, g) {
            if(!i && !j)
                continue;
            else if(!i)
                dp[i][j] = G[dp[i][j - 1] + 1];
            else if(!j)
                dp[i][j] = R[dp[i - 1][j] + 1];
            else
                dp[i][j] = std::max(R[dp[i - 1][j] + 1], G[dp[i][j - 1] + 1]);
        }
    }
    return dp[r][g] >= n;
}

int f(int l, int r) {
    if(l == r)
        return l;
    int mid = (l + r) >> 1;
    if(check(mid))
        return f(l, mid);
    return f(mid + 1, r);
}

int main() {
    file();
    scanf("%d %d %d", &n, &r, &g);
    if(r + g >= n) {
        printf("1");
        return 0;
    }
    rep(i, 1, n)
        scanf("%d", &a[i]);
    std::stable_sort(a + 1, a + n + 1);
    printf("%d", f(1, 1000000000));
    return 0;
}

T3

思维题诶！全场 AC 人数最少的一道题。

首先看数据范围，$1\le n\le 10^9$，肯定不能用 $n$ 来枚举 （毕竟 mjl 测评不开 O2）。

那我们再思考一下，发现 $1\le m\le 10^5$，可以用 $m$ 来枚举。所以我们可以求一下：以每一个公共牌作为顺牌中第一张公共牌的方案数。

这样想有一个好处：不用去重。因为只要第一张公共牌不一样，那么两种方案肯定不同；而求一种情况时也不会重复计算。

那么怎么算呢？我们可以求出此时这个顺牌区间左端点能够覆盖到的最小和最大值，然后再减一下不就行了吗。

那这个最值怎么算呢？假设现在需要求的牌编号为 $i$。

先说最小值吧：

首先我们把给出的公共牌排序、去重。众所周知，数组去了重之后不一定和原来数组一样长，所以，我们现在用 $m$ 代表顺牌区间的长度，$k$ 代表去重后公共牌的个数，切勿混淆。

第一点，因为 $i$ 是顺牌序列中的第一张公共牌，所以，顺牌的开头必须比第 $i-1$ 张公共牌的数值更大，即 $a_{i-1}+1$。

第二点，因为要形成连续 $m$ 张顺牌，而个人牌只有 $s$ 张，所以这个连续的序列里必须包含至少 $\bf{m-s}$ 张公共牌。 而 $i$ 是第一张，所以还要往后继续找至少 $m-s-1$ 张公共牌，而在规定条件下，找得越少，顺牌的开始位置就越靠前，这也是我们要找的最小值。从第 $i$ 张牌开始，往后找 $m-s-1$ 张牌是第 $i+m-s-1$ 张，再往前找开头，往前再找 $m$ 个就可以了。

这两个条件必须同时满足，所以在计算最小值时取这两个的最大值，即：

最大值要简单一些，因为要包含这张牌，所以最多到 $a_i$；而且因为顺牌的个数是 $m$ 张，所以要保证这么多牌，开头不能超过 $n-m+1$。取这两者的最小值即可。

这里需要注意一点，有时最小值可能反而比最大值大，此时是无解的，不要加上一个负数。

代码倒是挺简洁。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <cstdio>
#include <algorithm>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)

const int maxn = (int)1e5 + 5;

int n, m, s, ans, a[maxn];

inline int max(int x, int y) { return x > y ? x : y; }
inline int min(int x, int y) { return x < y ? x : y; }

inline void file() {
    freopen("straight.in", "r", stdin);
    freopen("straight.out", "w", stdout);
}

int main() {
    file();
    scanf("%d %d %d", &n, &m, &s);
    rep(i, 1, m)
        scanf("%d", &a[i]);
    std::stable_sort(a + 1, a + m + 1);
    int k = std::unique(a + 1, a + m + 1) - a - 1;
    rep(i, 1, k - m + s + 1) {
        int Min = max(a[i - 1] + 1, a[i + m - s - 1] - m + 1);
        int Max = min(a[i], n - m + 1);
        ans += max(0, Max - Min + 1);
    }
    printf("%d", ans);
    return 0;
}

T4

先纠正一个错误：DNA 是两条，这玩意儿应该是 RNA 但是又要换一个字母……

这题的突破口是 $|e|$ 和字母种类都很小，字母只有四种。

我们先写一个函数 $\text{f(ch)}$，可以把不同的字母转换为不同的下标（$eg.\ A\to 0,T\to 1,G\to 2,C\to 3$），这样可以使代码更加方便。

然后看一下这个序列，如果要从某一个字母开始周期修改，假设周期的长度是 $len$，某个字符在周期（也就是 $e$）中的位置是 $i$，我们会发现一件有趣的事，如图：

红色的地方即为这个字符会修改到的地方，可以发现这个分部是有规律的，它所有能够修改到的字符的下标 $\bmod\ len$ 的结果是一样的。

所以我们可以令 $BIT_{i,ch,j,k}$ 来代表字符为 $ch$，周期长度为 $j$ 且在周期中的位置为 $k$（周期遍历从 $1$ 开始），所有满足这些条件的字符在 $1\sim i$ 这个范围中的个数。

然后就是板子了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <cstdio>
#include <cstring>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)

const int maxn = (int)1e5 + 5;

int n, m, len;
char s[maxn], e[15];
int BIT[maxn][4][11][11];

inline int lowbit(int x) { return x & -x; }
inline int min(int x, int y) { return x < y ? x : y; }

inline int f(char c) {
    if(c == 'A')
        return 0;
    else if(c == 'T')
        return 1;
    else if(c == 'G')
        return 2;
    return 3;
}

inline void update(int x, int k, char c, int p, int id) {
    int l = f(c);
    while(x <= n) {
        BIT[x][l][p][id] += k;
        x += lowbit(x);
    }
    return;
}

inline int query(int x, char c, int p, int id) {
    int sum = 0, l = f(c);
    while(x) {
        sum += BIT[x][l][p][id];
        x -= lowbit(x);
    }
    return sum;
}

inline void file() {
    freopen("virus.in", "r", stdin);
    freopen("virus.out", "w", stdout);
}

int main() {
    file();
    scanf("%s", s + 1);
    n = strlen(s + 1);
    rep(i, 1, n)
        rep(j, 1, 10)
            update(i, 1, s[i], j, i % j);
    scanf("%d", &m);
    int op, x, l, r;
    char c;
    rep(i, 1, m) {
        scanf("%d", &op);
        if(op == 1) {
            scanf("%d %c", &x, &c);
            rep(j, 1, 10) {
                update(x, 1, c, j, x % j);
                update(x, -1, s[x], j, x % j);
            }
            s[x] = c;
        } else {
            scanf("%d %d %s", &l, &r, e + 1);
            len = strlen(e + 1);
            int ans = 0;
            // 这里注意一下应该是 (l + j - 1) % len 而不是 j，因为我们定义的周期遍历是从 1 而非从 l 开始 
            rep(j, 1, min(len, r - l + 1))
                ans += query(r, e[j], len, (l + j - 1) % len) - query(l - 1, e[j], len, (l + j - 1) % len);
            printf("%d\n", ans);
        }
    }
    return 0;
}

总结

这次考试爆炸了，$0+10+0+0$ 差点就保龄了……

T1 我打了一个线段树，结果没有调出来，T2 写了二分+贪心就没管了，T3 和 T4 都没有写出一个像样的代码……

只能说明思维和码力都太弱了 qwq。

以及，一定不要拘泥于才学过的知识点（话说我 T3 刚开始也打的线段树来着 qwq）。