「BJOI 2019」部分题目【题解】

题目列表

  • D1T1. 奥术神杖
  • D1T2. 堪破神机
  • D1T3. 送别
  • D2T1. 排兵布阵
  • D2T2. 光线
  • D2T3. 删数

简要题解

D1T1. 奥术神杖

题目大意:给出一个长度为 nn 的残缺的模板串,以及 mm 个带权的文本串。

要求确定每个残缺位 (09(0 \sim 9 的数字)),使得所有出现的文本串的权值 ((同一个文本串出现多次要重复计算)) 的几何平均值 (v1v2vkk)\big( \sqrt[k]{v_1 v_2 \cdots v_k} \big) 最大,并输出任意一种方案。

ss 为文本串的总长度。保证 n,m,s1501n, m, s \leqslant 1501,权值 v109v \leqslant 10^9

思路分析:取 log\log 后转算数平均,即 0101 分数规划。二分,AC 自动机上 DP。

时间复杂度为 Θ(nsΣloglogvϵ)\Theta \left(ns \lvert \Sigma \rvert \log \large \frac{\log v}{\epsilon} \right),其实严格上并不存在完全正确的程序。

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1510, A = 10;
const double EPS = 1e-3;
int n, m, tot = 1, tr[maxn][A], fail[maxn], pos[maxn];
char s[maxn], t[maxn];
double l, r = 21, v[maxn], sum[maxn], f[maxn][maxn];
vector<int> G[maxn];
pair<int, int> ans[maxn][maxn];

void build_AC() {
queue<int> q; fail[1] = 1;
for (int i = 0; i < A; i++) {
if (tr[1][i]) {
fail[tr[1][i]] = 1, q.push(tr[1][i]);
} else {
tr[1][i] = 1;
}
}
while (!q.empty()) {
int p = q.front(); q.pop();
for (int i = 0; i < A; i++) {
if (tr[p][i]) {
fail[tr[p][i]] = tr[fail[p]][i], q.push(tr[p][i]);
} else {
tr[p][i] = tr[fail[p]][i];
}
}
}
for (int i = 2; i <= tot; i++) {
G[fail[i]].push_back(i);
}
}

void dfs(int v) {
for (int i = 0; i < G[v].size(); i++) {
sum[G[v][i]] += sum[v], dfs(G[v][i]);
}
}

double chk(double x) {
memset(sum, 0, sizeof(sum));
for (int i = 1; i <= m; i++) {
sum[pos[i]] = v[i] - x;
}
memset(f, -0x3f, sizeof(f));
dfs(1), f[0][1] = 0;
for (int i = 0; i < n; i++) {
for (int j = 1; j <= tot; j++) {
if (s[i + 1] == '.') {
for (int c = 0; c < A; c++) {
f[i + 1][tr[j][c]] = max(f[i + 1][tr[j][c]], f[i][j]);
}
} else {
int c = s[i + 1] - '0';
f[i + 1][tr[j][c]] = max(f[i + 1][tr[j][c]], f[i][j]);
}
}
for (int j = 1; j <= tot; j++) {
f[i + 1][j] += sum[j];
}
}
return *max_element(f[n], f[n] + tot + 1);
}

void print() {
memset(sum, 0, sizeof(sum));
for (int i = 1; i <= m; i++) {
sum[pos[i]] = v[i] - l;
}
memset(f, -0x3f, sizeof(f));
dfs(1), f[0][1] = 0;
for (int i = 0; i < n; i++) {
for (int j = 1; j <= tot; j++) {
if (s[i + 1] == '.') {
for (int c = 0; c < A; c++) {
if (f[i][j] > f[i + 1][tr[j][c]]) {
f[i + 1][tr[j][c]] = f[i][j];
ans[i + 1][tr[j][c]] = make_pair(j, c);
}
}
} else {
int c = s[i + 1] - '0';
if (f[i][j] > f[i + 1][tr[j][c]]) {
f[i + 1][tr[j][c]] = f[i][j];
ans[i + 1][tr[j][c]] = make_pair(j, c);
}
}
}
for (int j = 1; j <= tot; j++) {
f[i + 1][j] += sum[j];
}
}
int p = max_element(f[n], f[n] + tot + 1) - f[n];
for (int i = n; i; i--) {
t[i] = ans[i][p].second + '0', p = ans[i][p].first;
}
}

int main() {
scanf("%d %d %s", &n, &m, s + 1);
for (int i = 1, x; i <= m; i++) {
scanf("%s %d", t + 1, &x), v[i] = log(x);
int p = 1, len = strlen(t + 1);
for (int j = 1; j <= len; j++) {
int c = t[j] - '0';
if (tr[p][c]) p = tr[p][c];
else p = tr[p][c] = ++tot;
}
pos[i] = p;
}
build_AC();
while (r - l > EPS) {
double mid = (l + r) / 2;
chk(mid) > 0 ? l = mid : r = mid;
}
print(), printf("%s\n", t + 1);
return 0;
}

D2T1. 排兵布阵

题目大意:有 nn 座城堡,玩家有 mm 名士兵。每次由两名玩家对战。如果一名玩家在第 ii 座城堡的士兵数严格大于对手士兵数的两倍,那么他就获得 ii 分。

小 C 将和其他 ss 名玩家两两对战,且派遣士兵的方案必须相同。给出其他 ss 名玩家即将使用的策略,求小 C 总分的最大值。保证 s,n100,s,n \leqslant 100, m2×104m \leqslant 2 \times 10^4

思路分析:暴力。时间复杂度为 Θ(nms)\Theta(nms)

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

int s, n, m, a[110][110], f[110][20010];
void chk(int &x, int y) { if (x < y) x = y; }

int main() {
scanf("%d %d %d", &s, &n, &m);
for (int i = 1; i <= s; i++) {
for (int j = 1; j <= n; j++) {
scanf("%d", &a[j][i]), a[j][i] = 2 * a[j][i] + 1;
}
}
for (int i = 1; i <= n; i++) {
sort(a[i], a[i] + s + 1);
for (int j = 0; j <= s; j++) {
for (int k = 0; k + a[i][j] <= m; k++) {
chk(f[i][k + a[i][j]], f[i - 1][k] + i * j);
}
}
}
printf("%d\n", *max_element(f[n], f[n] + m + 1));
return 0;
}

D2T2. 光线

题目大意:每个玻璃有两个参数 ai,bia_i, b_i。打在该玻璃上的 xx 单位光中有 xai%x \cdot a_i \% 的光会穿过它,有 xbi%x \cdot b_i\% 的光会反射回去 ((另外的光就被吸收了))

现在 nn 层玻璃叠在一起,有 11 单位的光打在第 11 层玻璃上。求有多少单位的光能穿过所有 nn 层玻璃,答案对 109+710^9 + 7 取模。保证 n5×105n \leqslant 5 \times 10^5

思路分析:设 fif_i 表示正向打到第 ii 层玻璃的光,gig_i 表示反向,则:

fi=fi1ai1%+gi1bi1%gi=fi+1bi+1%+gi+1ai+1%\begin{aligned} f_i &= f_{i - 1} \cdot a_{i - 1}\% + g_{i - 1} \cdot b_{i - 1}\% \\ g_i &= f_{i + 1} \cdot b_{i + 1}\% + g_{i + 1} \cdot a_{i + 1}\% \end{aligned}

手动高消,将 fif_i 表示为 pi+qigip_i + q_i \cdot g_i 的形式。时间复杂度为 Θ(nlogP)\Theta(n \log P)

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

const int maxn = 500010, P = 1000000007;
int n, a[maxn], b[maxn], p[maxn], q[maxn];

int qp(int x, int y) {
int z = 1;
for (; y; y >>= 1, x = 1LL * x * x % P) {
if (y & 1) z = 1LL * z * x % P;
}
return z;
}

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d %d", &a[i], &b[i]);
a[i] = 1LL * a[i] * qp(100, P - 2) % P;
b[i] = 1LL * b[i] * qp(100, P - 2) % P;
}
p[1] = 1;
for (int i = 2; i <= n + 1; i++) {
int t = (1LL * a[i - 1] * q[i - 1] + b[i - 1]) % P;
p[i] = 1LL * a[i - 1] * p[i - 1] % P;
q[i] = 1LL * t * a[i] % P;
t = qp(P + 1 - 1LL * b[i] * t % P, P - 2);
p[i] = 1LL * p[i] * t % P, q[i] = 1LL * q[i] * t % P;
}
printf("%d\n", p[n + 1]);
return 0;
}

D2T3. 删数

题目大意:如果一个序列能在若干次删数操作后变为空,则称这个序列可以删空。定义一次删数操作为:记当前序列长度为 kk,则序列数列中所有等于 kk 的数。

有一个长度为 nn 的序列 aa。有 mm 次修改操作,每次修改操作为单点修改或数列整体加减一。每次修改后回答:对于当前的序列 aa,至少还需要修改几个数才可删空?

保证 n,m1.5×105,n, m \leqslant 1.5 \times 10^5, 1ain1 \leqslant a_i \leqslant n

思路分析:点 ii 在数轴上覆盖 [icnt(i)+1,i][i - \text{cnt}(i) + 1, i][1,n][1, n] 中未被覆盖的点即为答案。线段树维护即可,注意不能把大于 nnaia_i 算进答案。时间复杂度为 O(nlogn)O(n \log 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
#include <bits/stdc++.h>
#define mid (l + r >> 1)
#define ls (k << 1)
#define rs (k << 1 | 1)
using namespace std;

const int maxn = 150010;
int n, m, tag, a[maxn], cnt[450010];
struct node { int s, tag; } t[maxn * 20];

void maintain(int k, int l, int r) {
t[k].s = t[k].tag ? r - l + 1 : t[ls].s + t[rs].s;
}

void add(int k, int l, int r, int ql, int qr, int v) {
if (l >= ql && r <= qr) { t[k].tag += v, maintain(k, l, r); return; }
if (mid >= ql) add(ls, l, mid, ql, qr, v);
if (mid < qr) add(rs, mid + 1, r, ql, qr, v);
maintain(k, l, r);
}

int sum(int k, int l, int r, int ql, int qr) {
if (t[k].tag) return min(r, qr) - max(l, ql) + 1;
if (l >= ql && r <= qr) return t[k].s;
int s = 0;
if (mid >= ql) s += sum(ls, l, mid, ql, qr);
if (mid < qr) s += sum(rs, mid + 1, r, ql, qr);
return s;
}

void modify(int x, int v) {
add(1, 1, n + m + m, x - cnt[x] + 1, x, v);
}

void ins(int x, int v) {
if (x > tag && x <= tag + n) modify(x, -1);
cnt[x] += v;
if (x > tag && x <= tag + n) modify(x, 1);
}

int main() {
scanf("%d %d", &n, &m), tag = m;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]), ins(a[i] += m, 1);
}
for (int i = 1, p, x; i <= m; i++) {
scanf("%d %d", &p, &x);
if (!p) {
if (x > 0) {
modify(tag + n, -1), modify(tag, 1), tag--;
} else {
tag++, modify(tag, -1), modify(tag + n, 1);
}
} else {
ins(a[p], -1), ins(a[p] = x + tag, 1);
}
printf("%d\n", n - sum(1, 1, n + m + m, tag + 1, tag + n));
}
return 0;
}

参考文献