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

时间复杂度为 O(nsΣloglogvϵ)O \Big (ns \lvert \Sigma \rvert \log {\small \dfrac{\log v}{\epsilon}} \Big),其实严格上并不存在完全正确的程序。

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;
}

D1T2. 勘破神机

题目大意:设用 1×21 \times 2 填满 2×n2 \times n 的方案数为 fnf_n,填满 3×n3 \times n 的方案数为 gng_n

给定 k,mk, m (m{2,3})(m \in \{ 2, 3 \}),求出 ansm\text{ans}_m998 244 353998\ 244\ 353 的值,其中:

ans2=1rl+1n=lr(fnk)ans3=1rl+1n=lr(gnk)\begin{aligned} \text{ans}_2 &= \frac{1}{r - l + 1} \sum_{n = l}^r \binom{f_n}{k} \\ \text{ans}_3 &= \frac{1}{r - l + 1} \sum_{n = l}^r \binom{g_n}{k} \end{aligned}

保证 1lr1018,1 \leqslant l \leqslant r \leqslant 10^{18}, 1k5011 \leqslant k \leqslant 501

思路分析:求出通项公式,扩域计算。时间复杂度为 O(k2logr)O(k^2 \log r)

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

typedef long long ll;
const ll P = 998244353;
ll m, l, r, k, C[510][510], S[510][510];

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

void init(ll K = 505) {
for (ll i = 0; i < K; i++) {
for (ll j = C[i][0] = 1; j <= i; j++) {
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % P;
}
}
for (int i = S[0][0] = 1; i < K; i++) {
for (int j = 1; j <= i; j++) {
S[i][j] = (S[i - 1][j - 1] - (i - 1) * S[i - 1][j]) % P;
}
}
}

struct Z { // a + b sqrt(m)
ll a, b;
Z(ll x = 0, ll y = 0) : a(x % P), b(y % P) {}
Z conj() { return Z(a, -b); }
Z operator + (Z y) { return Z(a + y.a, b + y.b); }
Z operator - (Z y) { return Z(a - y.a, b - y.b); }
Z operator * (Z y) { return Z(a * y.a + m * b * y.b, a * y.b + b * y.a); }
Z operator / (Z y) { return *this * y.conj() * qp(y.a * y.a - m * y.b * y.b, P - 2); }
} A, B, x, y;
Z Zpow(Z x, ll y) {
Z z = 1;
for (; y; y >>= 1, x = x * x) {
if (y & 1) z = z * x;
}
return z;
}

Z solve() {
r++; Z ans = 0;
for (ll i = 0; i <= k; i++) {
for (ll j = 0; j <= i; j++) {
Z z = Zpow(x, j) * Zpow(y, i - j);
Z t = Zpow(A, j) * Zpow(B, i - j) * (S[k][i] * C[i][j] % P);
if (!(z - 1).a && !z.b) ans = ans + t * ((r - l) % P);
else ans = ans + t * (Zpow(z, r) - Zpow(z, l)) / (z - 1);
}
}
return ans;
}

int main() {
scanf("%*d %lld %lld %lld %lld", &m, &l, &r, &k);
init(); ll len = r - l + 1;
if (m == 2) {
l++, r++, m = 5;
A = Z(0, 1) / 5, x = Z(1, 1) / 2;
} else {
l = (l + 1) >> 1, r >>= 1;
if (l > r) printf("0\n"), exit(0);
A = Z(3, 1) / 6, x = Z(2, 1);
}
B = A.conj(), y = x.conj(); ll tmp = 1;
for (ll i = 1; i <= k; i++) tmp = tmp * i % P;
Z ans = solve() * qp(tmp, P - 2) * qp(len, P - 2);
printf("%lld\n", (ans.a % P + P) % P);
return 0;
}

D2T1. 排兵布阵

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

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

思路分析:暴力。时间复杂度为 O(nms)O(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 的形式。时间复杂度为 O(nlogP)O(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;
}

参考文献