「TJOI 2019」所有题目【题解】

题目列表

  • D1T1. 甲苯先生的字符串
  • D1T2. 甲苯先生的滚榜
  • D1T3. 唱、跳、rap 和篮球
  • D2T1. 大中锋的游乐场
  • D2T2. 甲苯先生和大中锋的字符串
  • D2T3. 甲苯先生的线段树

简要题解

D1T1. 甲苯先生的字符串

题目大意:给出字符串 S1S_1S2S_2 的长度,S1S_1 中的相邻字母不能在 S2S_2 中相邻出现。

求满足要求的 S2S_2 的个数 ((字符集为小写字母))。保证 S1105,\lvert S_1 \rvert \leqslant 10^5, S21015\lvert S_2 \rvert \leqslant 10^{15}

思路分析:矩阵快速幂。

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;

typedef long long ll;
const int P = 1000000007;
ll n; int m, ans; char s[100010];
struct mat { int a[26][26]; } A, B;

mat operator * (const mat &A, const mat &B) {
mat C; memset(C.a, 0, sizeof(C.a));
for (int i = 0; i < 26; i++) {
for (int j = 0; j < 26; j++) {
for (int k = 0; k < 26; k++) {
C.a[i][k] = (C.a[i][k] + 1LL * A.a[i][j] * B.a[j][k]) % P;
}
}
}
return C;
}

int main() {
for (int i = 0; i < 26; i++) {
B.a[i][i]++;
for (int j = 0; j < 26; j++) {
A.a[i][j]++;
}
}
scanf("%lld %s", &n, s + 1), m = strlen(s + 1);
for (int i = 1; i < m; i++) {
A.a[s[i] - 'a'][s[i + 1] - 'a'] = 0;
}
for (n--; n; n >>= 1, A = A * A) {
if (n & 1) B = B * A;
}
for (int i = 0; i < 26; i++) {
for (int j = 0; j < 26; j++) {
(ans += B.a[i][j]) %= P;
}
}
printf("%d\n", ans);
return 0;
}

D1T2. 甲苯先生的滚榜

题目大意:在 ACM\text{ACM} 赛制的比赛中,如果通过题目数量不相等,则通过题目数量多的人排名更靠前;如果通过题目数量相等,则罚时更少的人排名更高。

mm 个人参赛,有 nnAC\text{AC},每次有人通过后输出排名在他的前面的人数。保证 m105,m \leqslant 10^5, n106n \leqslant 10^6,罚时总和不超过 1.5×1061.5 \times 10^6,数据随机。

思路分析:平衡树或者动态开点线段树。

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

typedef unsigned int ui;
typedef pair<int, pair<int, int> > P;
const int maxn = 1000010;
int T, m, n, a[100010], b[100010];
ui seed, lst = 7;
tree<P, null_type, greater<P>, rb_tree_tag,
tree_order_statistics_node_update> tr;
ui get() { return (seed = seed * 17 + lst) % m + 1; }

int main() {
scanf("%d", &T);
while (T--) {
scanf("%d %d %u", &m, &n, &seed), tr.clear();
for (int i = 1; i <= m; i++) {
tr.insert(P(a[i] = 0, make_pair(b[i] = 0, i)));
}
for (int i = 1; i <= n; i++) {
int p = get(), t = get();
tr.erase(P(a[p], make_pair(-b[p], p)));
tr.insert(P(++a[p], make_pair(-(b[p] += t), p)));
printf("%d\n", lst = tr.order_of_key(P(a[p], make_pair(-b[p], m))));
}
}
return 0;
}

D1T3. 唱、跳、rap 和篮球

题目大意:有 AA 个人喜欢唱、BB 个人喜欢跳、CC 个人喜欢 rap\text{rap}DD 个人喜欢篮球。要选出 nn 个人站队,使得不存在连续的 44 个人依次喜欢唱、跳、rap\text{rap} 和篮球。

求站队的方案数 mod\text{mod} 998244353998244353 的值。两个队伍是不同的,当且仅当至少有一个位置上的人的喜好不同。保证 n1000,n \leqslant 1000, A,B,C,D500A, B, C, D \leqslant 500

思路分析:考虑容斥,也就是强制选 kk 组 “连续的 44 个人""

强制选的部分可以直接 DP\text{DP},而其余位置的方案数为:

a=0Akb=0Bkc=0Ckd=0Dk[a+b+c+d=n4k](n4k)!(a!)(b!)(c!)(d!)\sum_{a = 0}^{A - k} \sum_{b = 0}^{B - k} \sum_{c = 0}^{C - k} \sum_{d = 0}^{D - k} [a + b + c + d = n - 4k] \frac{(n - 4k)!}{(a!) (b!) (c!) (d!)}

直接暴力或者用 NTT\text{NTT} 优化。时间复杂度为 O(n3)O(n^3)O(n2logn)O(n^2 \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
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
using namespace std;

const int maxn = 4010, P = 998244353;
int n, a, b, c, d, ans, lim, l, r[maxn], f[maxn][maxn];
int fact[maxn], A[maxn], B[maxn], C[maxn], D[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;
}

void ntt(int *c, int type) {
for (int i = 0; i < lim; i++) {
if (i < r[i]) swap(c[i], c[r[i]]);
}
for (int i = 1; i < lim; i <<= 1) {
int x = qp(3, type == 1 ? (P - 1) / (i << 1) : P - 1 - (P - 1) / (i << 1));
for (int j = 0; j < lim; j += i << 1) {
for (int k = 0, y = 1; k < i; k++, y = 1LL * y * x % P) {
int p = c[j + k], q = 1LL * y * c[i + j + k] % P;
c[j + k] = (p + q) % P, c[i + j + k] = (p - q + P) % P;
}
}
}
if (type == -1) {
for (int i = 0, t = qp(lim, P - 2); i < lim; i++) {
c[i] = 1LL * c[i] * t % P;
}
}
}

int main() {
scanf("%d %d %d %d %d", &n, &a, &b, &c, &d);
int mn = min(min(a, b), min(c, d));
int mx = max(max(a, b), max(c, d));
for (int i = f[0][0] = 1; i <= n; i++) {
for (int j = 0; j <= mn; j++) {
f[i][j] = f[i - 1][j];
if (i >= 4 && j) (f[i][j] += f[i - 4][j - 1]) %= P;
}
}
for (int i = fact[0] = 1; i <= max(n, mx); i++) {
fact[i] = 1LL * i * fact[i - 1] % P;
}
for (lim = 1; lim <= a + b + c + d; lim <<= 1) l++;
for (int i = 0; i < lim; i++) {
r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
}
for (int i = 0; i <= mn && i * 4 <= n; i++) {
memset(A, 0, sizeof(A)), memset(B, 0, sizeof(B));
memset(C, 0, sizeof(C)), memset(D, 0, sizeof(D));
for (int j = 0; j <= mx - i; j++) {
if (j <= a - i) A[j] = qp(fact[j], P - 2);
if (j <= b - i) B[j] = qp(fact[j], P - 2);
if (j <= c - i) C[j] = qp(fact[j], P - 2);
if (j <= d - i) D[j] = qp(fact[j], P - 2);
}
ntt(A, 1), ntt(B, 1), ntt(C, 1), ntt(D, 1);
for (int j = 0; j < lim; j++) {
A[j] = 1LL * A[j] * B[j] % P * C[j] % P * D[j] % P;
}
ntt(A, -1); long long t = i & 1 ? P - 1 : 1;
ans = (ans + t * f[n][i] % P * fact[n - 4 * i] % P * A[n - 4 * i]) % P;
}
printf("%d\n", ans);
return 0;
}

D2T1. 大中锋的游乐场

题目大意:给定一张 nn 个点、mm 条边的无向图,以及起点和终点。

初始时权值为 00,每个点可能会让权值 ±1\pm 1,任意时刻权值的绝对值都必须 k\leqslant k。求最短路的长度,如果无法到达输出 1-1。保证 n104,n \leqslant 10^4, m105,m \leqslant 10^5, k10k \leqslant 10

思路分析:最短路。

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

typedef pair<int, int> P;
typedef pair<int, P> Q;
const int maxn = 10010;
int T, n, m, K, s, t, f[maxn][21], w[maxn];
struct edge { int v, w; };
vector<edge> G[maxn];
priority_queue<Q, vector<Q>, greater<Q> > q;

int main() {
scanf("%d", &T);
while (T--) {
scanf("%d %d %d", &n, &m, &K);
memset(f, 0x3f, sizeof(f));
for (int i = 1; i <= n; i++) {
scanf("%d", &w[i]), G[i].clear();
if (w[i] == 2) w[i] = -1;
}
for (int i = 1, u, v, w; i <= m; i++) {
scanf("%d %d %d", &u, &v, &w);
G[u].push_back((edge){v, w});
G[v].push_back((edge){u, w});
}
scanf("%d %d", &s, &t);
if (abs(w[s]) > K) { printf("-1\n"); continue; }
q.push(make_pair(f[s][K + w[s]] = 0, P(s, K + w[s])));
while (!q.empty()) {
Q t = q.top(); q.pop();
if (t.x != f[t.y.x][t.y.y]) continue;
int v = t.y.x, k = t.y.y;
for (int i = 0, u; i < G[v].size(); i++) {
int nk = k + w[u = G[v][i].v];
if (abs(nk - K) <= K && f[u][nk] > t.x + G[v][i].w) {
q.push(Q(f[u][nk] = t.x + G[v][i].w, P(u, nk)));
}
}
}
int ans = INT_MAX;
for (int i = 0; i <= K + K; i++) {
ans = min(ans, f[t][i]);
}
printf("%d\n", ans > 1e9 ? -1 : ans);
}
return 0;
}

D2T2. 甲苯先生和大中锋的字符串

题目大意:给定一个长度为 nn 的字符串,求在恰好出现了 kk 次的子串中,按照字串的长度分类,数量最多的那一类的长度 ((如有多个输出最长长度))。保证数据组数 100,\leqslant 100, n105,n \leqslant 10^5, n3×106\sum n \leqslant 3 \times 10^6

思路分析:恰好出现了 rl+1r - l + 1 次的子串的长度 tt 显然满足:

{l<ir, theight[i]t>height[l]t>height[r+1]\begin{cases} \forall l < i \leqslant r,\ t \leqslant \text{height}[i] \\ t > \text{height}[l] \\ t > \text{height}[r + 1] \end{cases}

每个 rr 都会对一段区间的 tt 有贡献,差分即可。时间复杂度为 O((nlogn))O \big( \sum (n \log n) \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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 100010;
int T, n, K, SZ, h, t, q[maxn], s[maxn];
int rk[maxn], sa[maxn], sc[maxn], ht[maxn], buc[26];
char S[maxn];

void radix_sort() {
for (int i = 1; i <= SZ; i++) buc[i] = 0;
for (int i = 1; i <= n; i++) buc[rk[i]]++;
for (int i = 1; i <= SZ; i++) buc[i] += buc[i - 1];
for (int i = n; i; i--) sa[buc[rk[sc[i]]]--] = sc[i];
}

void calc_sa() {
for (int i = 1; i <= n; i++) rk[i] = S[i] - 'a' + 1, sc[i] = i;
SZ = 26, radix_sort();
for (int k = 1; k <= n; k <<= 1) {
int cnt = 0;
for (int i = n - k + 1; i <= n; i++) sc[++cnt] = i;
for (int i = 1; i <= n; i++) if (sa[i] > k) sc[++cnt] = sa[i] - k;
radix_sort(), swap(rk, sc), rk[sa[1]] = cnt = 1;
for (int i = 2; i <= n; i++) {
rk[sa[i]] = (sc[sa[i]] == sc[sa[i - 1]] &&
sc[sa[i] + k] == sc[sa[i - 1] + k] ? cnt : ++cnt);
}
SZ = cnt; if (cnt == n) break;
}
for (int i = 1, j = 0; i <= n; i++) {
if (rk[i] == 1) { j = ht[rk[i]] = 0; continue; }
j = max(0, j - 1);
while (S[sa[rk[i] - 1] + j] == S[i + j]) j++;
ht[rk[i]] = j;
}
}

int main() {
scanf("%d", &T);
while (T--) {
scanf("%s %d", S + 1, &K);
n = strlen(S + 1), calc_sa();
fill(s + 1, s + n + 1, t = ht[n + 1] = 0);
for (int i = h = 1; i <= n; i++) {
while (h <= t && ht[q[t]] >= ht[i]) t--;
q[++t] = i;
while (h <= t && q[h] <= i - K + 1) h++;
if (i < K) continue;
int tmp = ht[q[h]];
if (h > t) tmp = n - rk[i] + 1;
if (max(ht[i - K + 1], ht[i + 1]) >= tmp) continue;
s[max(ht[i - K + 1], ht[i + 1]) + 1]++, s[tmp + 1]--;
}
int ans = 0;
for (int i = 1; i <= n; i++) {
s[i] += s[i - 1];
if (s[i] >= s[ans]) ans = i;
}
printf("%d\n", s[ans] ? ans : -1);
}
return 0;
}

D2T3. 甲苯先生的线段树 ()(\star)

题目大意:有一棵深度为 dd 的满二叉树。根节点编号为 11;对于一个编号为 xx 的结点,左孩子编号为 2x2x,右孩子编号为 2x+12x + 1

再给定两个结点 a,ba, b,有两种类型 ((cc 表示)) 的问题:

  • c=1c = 1:求 a,ba, b 之间的简单路径的编号和。
  • c=2c = 2:求还有多少条简单路径的编号和等于 c=1c = 1 时的答案。

保证数据组数 10,\leqslant 10, d50d \leqslant 50

思路分析c=1c = 1 可以暴力做,不妨记答案为 nn。对于 c=2c = 2,考虑枚举路径深度最小的点 xx 以及两边向下延伸的长度 l,rl, r ((可能为 0)0)。确定了 n,l,rn, l, r 后,实际上 xx 也唯一确定了,所以可以将问题规约至 x=1x = 1 的情况。

考虑 x=1x = 1 的情况。首先可以得到 nn 的下界 ((两条链全往左延伸))

nmin=1+2++2l+3+6++32r1=2l+1+32r4\begin{aligned} n_{\min} &= 1 + 2 + \cdots + 2^l + 3 + 6 + \cdots + 3 \cdot 2^{r - 1} \\ &= 2^{l + 1} + 3 \cdot 2^{r} - 4 \end{aligned}

每当在深度为 ii 处选择进入右子树,就会对 nn 产生 j=0i2j=2i+11\sum_{j = 0}^i 2^j = 2^{i + 1} - 1 的贡献。所以这个问题转化为:

要确定两个长度分别为 l1l - 1r1r - 10101 串,第 ii((下标从 00 开始)) 的权值为 2i+112^{i + 1} - 1,求方案数。

可以数位 DP\text{DP},或者直接记忆化搜索也可以 ((复杂度是正确的))

考虑 x1x \neq 1 的情况。同理可得 nn 的下界和 xx 的值:

(Let k=2l+1+2r+13, b=2r1)nmin=kx+bx=nbk\begin{aligned} & (\text{Let } k = 2^{l + 1} + 2^{r + 1} - 3,\ b = 2^r - 1) \\ & n_{\min} = kx + b \Rightarrow x = \Big \lfloor \frac{n - b}{k} \Big \rfloor \end{aligned}

于是规约为 n=(nb) mod k,n' = (n - b) \text{ mod } k, x=1x = 1 的子问题。

时间复杂度为 O(d5)O(d^5),常数非常小。

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

typedef long long ll;
int T, d, c;
ll n, A, B, ans;
unordered_map<ll, ll> mp[55][55];

ll dfs(int x, int y, ll z) {
if (z < 0 || z > (2LL << x) + (2LL << y) - x - y - 4) return 0;
if (x < y) swap(x, y);
if (!x && !y) return !z;
if (mp[x][y].count(z)) return mp[x][y][z];
return mp[x][y][z] = dfs(x - 1, y, z) + dfs(x - 1, y, z - (1LL << x) + 1);
}

int dep(ll x) {
int cnt = 0;
while (x) cnt++, x >>= 1;
return cnt;
}

int main() {
scanf("%d", &T);
while (T--) {
scanf("%d %lld %lld %d", &d, &A, &B, &c);
for (n = ans = 0; A ^ B; n += A, A >>= 1) {
if (A < B) swap(A, B);
}
n += A;
if (c == 1) { printf("%lld\n", n); continue; }
for (int l = 0; l <= d; l++) {
ll k = (2LL << l) - 1;
if (k <= n && dep(n / k) + l <= d) ans += dfs(l, 0, n % k);
}
for (int l = 1; l <= d; l++) {
for (int r = 1; r <= d; r++) {
ll k = (2LL << l) + (2LL << r) - 3, b = (1LL << r) - 1;
if (k + b > n || dep((n - b) / k) + max(l, r) > d) continue;
ans += dfs(l - 1, r - 1, (n - b) % k);
}
}
printf("%lld\n", ans - 1);
}
return 0;
}