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)。