20231112题解

好了我打脸了,这才是最后一篇。

真的要 AFO 了。

18 号之后可能还会出一下 NOIP 游记,然后退役。

plugin

为什么会有占用一个插座贡献 0 个插座的插线板啊。

贪心性质非常显然,肯定要从限制最小的手机开始考虑,并且层数较低的插线板应该尽可能的大。

但是直接贪心好像不太行:你不知道那些限制小的手机有几个要抛弃。

所以二分一下手机数量,剩下的贪心判断能否满足就好。

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 4e5 + 5;
int n, m;
int a[maxn], b[maxn];

int main() {
auto read = [&](auto &r) -> void {
r = 0; int ch = getchar(), f = 0;
while (!isdigit(ch)) { if (ch == 45) f ^= 1; ch = getchar(); }
while (isdigit(ch)) { (r *= 10) += ch - 48; ch = getchar(); }
if (f) r = -r;
};
// freopen("plugin.in", "r", stdin), freopen("plugin.out", "w", stdout);
read(m); read(n);
for (int i = 1; i <= m; i++) read(b[i]);
for (int i = 1; i <= n; i++) read(a[i]);
sort(a + 1, a + n + 1);
sort(b + 1, b + n + 1, [&](int a, int b) -> bool { return a > b; });
int l = 1, r = n, mid;
while (l < r) {
mid = (l + r) >> 1;
if ([&](int x) -> bool {
int dep = 0, cnt = 1, j = 0;
for (int i = x; i <= n; i++) {
while (dep < a[i]) {
int tcnt = 0;
while (j < m && cnt && b[j + 1]) cnt--, tcnt += b[++j];
cnt += tcnt;
dep++;
}
if (cnt) cnt--;
else return false;
}
return true;
}(mid)) r = mid;
else l = mid + 1;
}
printf("%d\n", n - l + 1);
return 0;
}

string

哈希妙题。

判断有多少个不同的字符串只要哈希就可以了。但是哈希值怎么支持区间推平呢?

如果原字符串是 \(s\) 的话,我们常见的哈希其实是 \(h=\sum_{i=1}^{len}{131^{n - i}s_i}\) 之类的。容易发现,在固定位置上的哈希系数是固定的。

所以可以用线段树,维护两个值:一个是区间哈希系数总和,一个是区间哈希总和。推平的时候用系数乘上推平值即可。

进一步思考发现,这种做法的关键是抛弃了原来的哈希可以快速获得子串哈希的性质。既然如此,我们可以有更好的哈希系数:随即产生一个 \(a\) 序列,让 \(h=\sum_{i=1}^{len}{a_is_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
#include <bits/stdc++.h>
using namespace std;

template <class T>
void read(T &r) {
r = 0; int ch = getchar(), f = 0;
while (!isdigit(ch)) {if (ch == 45) f ^= 1; ch = getchar(); }
while (isdigit(ch)) (r *= 10) += ch - 48, ch = getchar();
if (f) r = -r;
}

const int maxn = 5e5 + 5;
int n, len, m;
mt19937_64 rd(time(NULL));
unsigned long long h[maxn];
int tmp[maxn];

struct node; typedef node* pos;
struct node { unsigned long long val, hval; int l, r, tag; pos ls, rs; node() { ls = rs = this; }};
node buf[maxn << 1], *buf_pos = buf;
pos root[maxn];
pos new_node(int l, int r) { pos p = ++buf_pos; p -> ls = p -> rs = buf; p -> l = l, p -> r = r; return p; }
void push_up(pos p) { p -> val = p -> ls -> val + p -> rs -> val; p -> hval = p -> ls -> hval + p -> rs -> hval; }
void update_one(pos p, int x) { p -> tag = x; p -> val = p -> hval * x; }
void push_down(pos p) { if (p -> tag) update_one(p -> ls, p -> tag), update_one(p -> rs, p -> tag), p -> tag = 0; }
void build(pos p) {
if (p -> l == p -> r) p -> hval = h[p -> l], p -> val = tmp[p -> l] * h[p -> l];
else {
int mid = (p -> l + p -> r) >> 1;
p -> ls = new_node(p -> l, mid), build(p -> ls);
p -> rs = new_node(mid + 1, p -> r), build(p -> rs);
push_up(p);
}
}
void update(pos p, int l, int r, int x) {
if (l <= p -> l && p -> r <= r) return update_one(p, x);
push_down(p);
if (l <= p -> ls -> r) update(p -> ls, l, r, x);
if (p -> rs -> l <= r) update(p -> rs, l, r, x);
push_up(p);
}

map<unsigned long long, int> mp;

int main() {
freopen("string.in", "r", stdin), freopen("string.out", "w", stdout);
read(n); read(len); read(m);
for (int i = 1; i <= len; i++) h[i] = rd();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= len; j++) {
tmp[j] = getchar();
while (!isalpha(tmp[j])) tmp[j] = getchar();
}
root[i] = new_node(1, len);
build(root[i]);
mp[root[i] -> val]++;
}
while (m--) {
int id, l, r, x;
read(id); read(l); read(r); x = getchar(); while (!isalpha(x)) x = getchar();
if (!(--mp[root[id] -> val])) mp.erase(root[id] -> val);
update(root[id], l, r, x);
mp[root[id] -> val]++;
printf("%lu\n", mp.size());
}
return 0;
}

qlx

你突然 对我说 七里香的 名字很美 我此刻却只想吻你倔强的嘴

类似于最长公共子序列,定义 \(f_{i,j}\) 表示以 \(s_i\) 结尾的 \(s\) 的子串匹配到 \(t_j\) 为止所需要的最短长度。为了方便转移,可以把最短长度改成最大左端点,即 \(f_{i,j}\) 是使得 \(s_l \sim s_i\) 包含子序列 \(t_1 \sim t_j\) 的最大 \(l\)

这样转移就很简单:

  • \(s_i = t_j\)\(f_{i,j} \leftarrow f_{i-1,j-1}\)
  • \(s_i \ne t_j\)\(f_{i,j} \leftarrow f_{i-1,j}\)

优化就更显然了:能实现第一个转移的 \(j\) 只有一个,所以记录每一个 \(t_j\) 值对应的 \(j\) 是多少。剩下的部分继承前一个 \(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
#include <bits/stdc++.h>
using namespace std;

template <class T>
void read(T &r) {
r = 0; int ch = getchar(), f = 0;
while (!isdigit(ch)) {if (ch == 45) f ^= 1; ch = getchar(); }
while (isdigit(ch)) (r *= 10) += ch - 48, ch = getchar();
if (f) r = -r;
}

const int maxn = 1e6 + 5, maxm = 1e6 + 5;
int dp[maxm], n, m, _;
pair<int, int> ans;
int s[maxn], t[maxm], in_t[maxm];

int main() {
freopen("qlx.in", "r", stdin), freopen("qlx.out", "w", stdout);
read(_);
while (_--) {
read(n); read(m);
for (int i = 1; i <= n; i++) read(s[i]);
memset(in_t, 0, sizeof in_t);
for (int i = 1; i <= m; i++) read(t[i]), in_t[t[i]] = i;
ans = make_pair(0x3f3f3f3f, -1); memset(dp, 0xcf, sizeof dp);
for (int i = 1; i <= n; i++) {
int j = (s[i] <= 1e6) ? in_t[s[i]] : 0;
if (j) {
if (j == 1) dp[j] = max(dp[j], i);
else dp[j] = max(dp[j], dp[j - 1]);
}
ans = min(ans, make_pair(i - dp[m] + 1, i));
}
if (ans.first > n) printf("-1\n");
else printf("%d %d\n", ans.second - ans.first + 1, ans.second);
}
return 0;
}