0%

CF EDU 84 题解 (Except D)

。。。

$\text{A}$

我们先把每个位置填个 $1$ ,然后再除掉 $2$,就变成了 $n$ 是否能变成若干个不同非负整数之和的题了,也就是判断一下 $n$ 和 $k(k-1) / 2$ 的大小关系,无解就过程中判一下减不掉或者除不掉。

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

void solve(int n, int k) {
if (n < k){
puts("NO");
return;
}
n -= k;
if (n % 2) {
puts("NO");
return;
}
n /= 2;
if (n >= 1ll * (k - 1) * k / 2) puts("YES");
else puts("NO");
}
int main() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
solve(n, k);
}
}

$\text{B}$

这个限制非常松,只需要先每个公主贪心匹配,然后匹配不满就在没有匹配的公主的列表里加一个没有匹配的骑士即可。

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

using namespace std;

int t, n;
void solve() {
cin >> n;
vector <int> mat(n + 1), unable;
for (int i = 1; i <= n; ++i) {
int t; cin >> t;
bool f = 0;
while (t--) {
int j; cin >> j;
if (!mat[j] && !f) {
mat[j] = 1;
f = 1;
}
}
if (!f) unable.push_back(i);
}
int pos = 0;
for (int i = 1; i <= n; ++i) if (!mat[i]) {
pos = i;
break;
}
if (!unable.size()) cout << "OPTIMAL\n";
else {
cout << "IMPROVE\n";
cout << unable[0] << " " << pos << '\n';
}
}
int main() {
ios::sync_with_stdio(0);
cin >> t;
while (t--) solve();
}

$\text{C}$

利用移动到边界就会被卡住的性质,先若干次UL将所有东西都挪到左上角,再环游世界即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

int n, m, k;
int main() {
cin >> n >> m >> k;

string s = "";
for (int i = 1; i <= m; ++i) s.push_back('L');
for (int i = 1; i <= n; ++i) s.push_back('U');
for (int i = 1; i <= m; ++i) {
if (i & 1)
for (int j = 1; j <= n-1; ++j) s.push_back('D');
else
for (int j = 1; j <= n-1; ++j) s.push_back('U');
if (i < m) s.push_back('R');
}
cout << s.size() << endl;
cout << s << endl;
}

$\text{D}$

数学功底太差,明天再说

$\text{E}$

考虑枚举位置,对于左右两边都有块的和只有一边有块的分类讨论,较为简单的组合计数。

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

const int mod = 998244353;
int n;
int qpow(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = 1ll * res * a % mod;
a = 1ll * a * a % mod;
b >>= 1;
}
return res;
}
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
if (i == n) printf("10 ");
else if (i == n - 1) printf("180 ");
else {
int ans1 = 1ll * (n - i - 1) * 10 % mod * 81 % mod * qpow(10, n - i - 2) % mod;
int ans2 = 1ll * 2 * 10 % mod * 9 % mod * qpow(10, n - i - 1) % mod;
printf("%d ", (ans1 + ans2) % mod);
}
}
return 0;
}

$\text{F}$

按位考虑,最后乘在一起,和 这题 差不多的思路。

具体来讲,我们先差分预处理出每个位置是否被钦定了为 $1$。接着,我们令 $dp_i = $ 前 $i$ 个位置,第 $i$ 个位置是 $0$,满足条件的方案数。

显然,如果 $a_i$ 被钦定为 $1$,则 $dp_i = 0$。

否则,一定是形如 $dp_i = \sum dp_j$ 的形式。

我们考虑一下,合法的 $j$ 应该从哪里转移?不难发现,如果要求 $and = 0$ 的区间在 $[j, i]$ 之间存在,那就不行,因为如果只有这两个点是 $0$ 的话中间那段肯定全 $1$,不满足题意。

所以我们令 $lmx_i$ 为在 $i$ 左边的区间的 $l$ 最大值。显然这个转移的 $j$ 要不小于这个位置。

又因为我们发现 $lmx_i$ 是一个前缀 $max$ 的形式,所以可以双指针维护范围来 $dp$。(因为每次范围只会向后推)

注意最后答案的求法:建一个虚点,强制他为 $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
#include <bits/stdc++.h>
using namespace std;
const int N = 500010;
const int mod = 998244353;
int n, k, m, l[N], r[N], x[N], dp[N], c[N], lmx[N];

int solve(int b) {
for (int i = 1; i <= n; ++i) lmx[i] = 0, c[i] = 0, dp[i] = 0;
for (int i = 1; i <= m; ++i) {
if (x[i] >> b & 1) ++c[l[i]], --c[r[i] + 1];
else lmx[r[i]] = max(lmx[r[i]], l[i]);
}
for (int i = 1; i <= n + 1; ++i) lmx[i] = max(lmx[i], lmx[i - 1]), c[i] += c[i - 1];
int sdp = 1, j = 0;
dp[0] = 1;
for (int i = 1; i <= n + 1; ++i) {
if (c[i] > 0) { dp[i] = 0; continue; }
while (j < lmx[i - 1]) sdp = (sdp - dp[j++] + mod) % mod;
dp[i] = sdp;
sdp = (sdp + dp[i]) % mod;
}
return dp[n + 1];
}
int main() {
scanf ("%d%d%d", &n, &k, &m);
for (int i = 1; i <= m; ++i)
scanf ("%d%d%d", &l[i], &r[i], &x[i]);

int ans = 1;
for (int i = 0; i < k; ++i)
ans = 1ll * ans * solve(i) % mod;
cout << ans << '\n';
return 0;
}

$\text{G}$

考虑在 $\texttt{AC}$ 自动机上 $dp$。所以需要先把所有 $t$ 串塞到自动机里,然后构建好 $fail$ 树。

我们发现,这种题一般都是让你填问号(BJOI2019 奥术神杖),然后最大化某个匹配的值。而且又发现有一个要求是不能填重复的字符,那很自然联想到状压。

容易想到朴素 $dp$:令 $f_{i, j, k} = $ 前 $i$ 个字符,目前使用过的字符集合为 $j$,当前状态为 $k$ 的最优解。但是你发现光状态总数就有 $400000 \times 1000\times 16384$ 个。光荣gg。

小朋友你是否有很多问号

我们来考虑一下决策。不难发现,如果模拟这个状态方程转移,那么我们每当遇到一个不能被改的位置的时候都会直接强制 $dp$ 数组长什么样子。又因为题目说了 $S$ 中的问号个数不超过 $14$ 个,也就等同于需要我们进行 $dp$ 的位置也只有 $14$ 个。两个问号中间的部分只需要模拟一下 $\texttt{AC}$ 自动机的匹配算一下匹配贡献,直接加上即可。

现在 $dp$ 就看起来变成 $1000\times 16384\times 14$ 的空间复杂度了。尽管还是不能过,但是看起来变得可行了。

我们再来看,有效的状态有一个规律,即 $bitcnt(k) = i-1$。那也就是说如果我们记录了 $k$ 就可以随之而来得到 $i$,所以我们可以直接把 $i$ 这一维删去。

现在就变成了 $1000w$ 量级了,看起来很合理,所以我们考虑一下转移复杂度。

转移复杂度的话…我们来看看我们枚举了什么。

1
2
3
4
5
6
7
8
9
10
11
for (int i = 0; i + 1 < v.size(); ++i) { // 14
for (int root = 0; root <= tot; ++root) { // 1000
for (int p = v[i] + 1; p <= v[i + 1] - 1; ++p) dosth
for (int state = 0; state < (1 << 14); ++state) { // 16384
if (__builtin_popcount(state) != i) continue;
int L = 0, R = 13;
if (i + 1 == v.size() - 1) L = 14, R = 14; // force the last '?'
for (int d = L; d <= R; ++d) if (!(state >> d & 1)) doth // 14
}
}
}

看起来是 $14\times 1000\times 16384\times 14$,像是gg,其实并不然。注意到我们在 $state$ 那里做了一个 $bitcnt$ 的剪枝,大范围地避免了无用决策的更新,所以跑的非常快。

我们再来看看怎么 $dp$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for (int i = 0; i + 1 < v.size(); ++i) {
for (int root = 0; root <= tot; ++root) {
int jroot = root;
ll sum = 0;
for (int p = v[i] + 1; p <= v[i + 1] - 1; ++p) jroot = go[jroot][s[p] - 'a'], sum += up[jroot]; // 加上问号间的贡献
for (int state = 0; state < (1 << 14); ++state) {
if (__builtin_popcount(state) != i) continue;
int L = 0, R = 13;
if (i + 1 == v.size() - 1) L = 14, R = 14; // force the last '?'
for (int d = L; d <= R; ++d) if (!(state >> d & 1)) { // 枚举未出现过的字符
int nroot = go[jroot][d];
dp[nroot][state | (1 << d)] = max(dp[nroot][state | (1 << d)], dp[root][state] + sum + up[nroot]); // 更新答案
}
}
}
}

看起来很易懂,但是还是有两个实现细节:

$1. $ 注意我们输出的是什么?一看好像看不出来… 那我们就在最后多加一个问号,强制它填 m(也就是没出现过的字符),这样它就能起到一个汇总答案的作用。

$2.$ 一定要注意, $root$ 和 $state$ 的枚举顺序不能反。为什么呢?因为你要注意,你是在 $root$ 的里面计算的问号间的贡献,这一步的复杂度高达 $400000$。如果你先套 $state$ 再套 $root$,那就直接 gg 了。

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 <bits/stdc++.h>
#pragma GCC optimize("Ofast","-funroll-loops","-fdelete-null-pointer-checks")
#pragma GCC target("ssse3","sse3","sse2","sse","avx2","avx")
using namespace std;
typedef long long ll;
const int M = 1010, N = 400010, ST = (1 << 15) + 5;
int k, n;
int fail[M], tot, go[M][15];
ll up[M];
char t[M], s[N];
ll dp[M][ST], cnt, gg[M];
void insert(char* t, int val) {
int u = 0;
for (int i = 1; t[i]; ++i) {
if (!go[u][t[i] - 'a']) go[u][t[i] - 'a'] = ++tot;
u = go[u][t[i] - 'a'];
}
up[u] += val;
}
void get_fail() {
queue <int> q;
for (int i = 0; i < 15; ++i)
if (go[0][i]) q.push(go[0][i]);
while (!q.empty()) {
int u = q.front();
q.pop();
up[u] += up[fail[u]];
for (int i = 0; i < 15; ++i) {
if (go[u][i]) fail[go[u][i]] = go[fail[u]][i], q.push(go[u][i]);
else go[u][i] = go[fail[u]][i];
}
}
}
int main() {
double cl = clock();
scanf ("%d", &k);
for (int i = 1; i <= k; ++i) {
scanf ("%s", t + 1);
int c; scanf ("%d", &c);
insert(t, c);
}
get_fail();
scanf ("%s", s + 1);
n = strlen(s + 1);
vector <int> v; s[0] = '?'; s[n + 1] = '?';
for (int i = 0; i <= n + 1; ++i) if (s[i] == '?') v.push_back(i);

for (int i = 0; i < v.size(); ++i) {
for (int state = 0; state < (1 << 15); ++state) {
if (__builtin_popcount(state) != i) continue;
for (int root = 0; root <= tot; ++root) dp[root][state] = 0xcfcfcfcfcfcfcfcfll;
}
}
dp[0][0] = 0;
for (int i = 0; i + 1 < v.size(); ++i) {
for (int root = 0; root <= tot; ++root) {
int jroot = root;
ll sum = 0;
for (int p = v[i] + 1; p <= v[i + 1] - 1; ++p) jroot = go[jroot][s[p] - 'a'], sum += up[jroot];
for (int state = 0; state < (1 << 14); ++state) {
if (__builtin_popcount(state) != i) continue;
int L = 0, R = 13;
if (i + 1 == v.size() - 1) L = 14, R = 14; // force the last '?'
for (int d = L; d <= R; ++d) if (!(state >> d & 1)) {
int nroot = go[jroot][d];
dp[nroot][state | (1 << d)] = max(dp[nroot][state | (1 << d)], dp[root][state] + sum + up[nroot]);
}
}
}
}
ll ans = 0xcfcfcfcfcfcfcfcfll;
for (int state = 0; state < (1 << 15); ++state) {
if (__builtin_popcount(state) != v.size() - 1) continue;
for (int root = 0; root <= tot; ++root) ans = max(ans, dp[root][state]);
}
cout << ans << endl;
return 0;
}