打得还行，希望能晋级P。
T1. Find and Replace
有一个字符串 $S$，初始为单个字符 a。有 $n$ 次操作，每次给定字符 $c$ 和字符串 $s$，将 $S$ 中所有 $c$ 替换为 $s$。操作结束后给定 $l,r$，询问 $S_{l\dots r}$。
$\sum \lvert s \rvert \le 2\cdot 10^5,r-l+1\le 2\cdot 10^5$
Tag: 搜索
设 $f_{i,j}$ 表示字符 $i$ 经过操作 $j,j+1\dots n$ 后会变为多少个字符。则可以根据 $f$ 的值 DFS（类似线段树查询，一层层拆分区间，$f$ 的值即为区间大小）。
这样会遇到一个问题：如果存在大量 $\lvert s \rvert =1$，即一个字符变为一个字符，那么 DFS 中操作次数可能达到 $O(n^2)$ 次。对此，可以预处理出字符 $i$ 在操作 $j$ 后第一个 $\lvert s \rvert >1$ 的操作 $nxt_{i,j}$，以及在操作 $nxt_{i,j}$ 时字符 $i$ 变成了字符 $to_{i,j}$。这样可以快速跳转至下一个增加 $S$ 长度的操作。
由于每次有效操作都会将 $S$ 长度至少+1，而 $r-l+1\le 2\cdot 10^5$，所以需要处理的操作也不会超过这个数。
Code
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
| char c[N];
string s[N];
ll dp[26][N], nxt[26][N], to[26][N];
ll L, R, n;
void dfs(ll x, ll d, ll p, ll l, ll r) {
if (d == n) {
cout << char('a' + x);
return;
}
rep(i, s[d].size()) {
int y = s[d][i] - 'a';
ll w = dp[y][d + 1];
if (p <= r && p + w - 1 >= l)dfs(to[y][d + 1], nxt[y][d + 1], p, max(p, l), min(p + w - 1, r));
p += w;
if (p > r)break;
}
}
void solve() {
cin >> L >> R >> n;
rep(i, n)cin >> c[i] >> s[i];
rep(i, 26)dp[i][n] = 1, nxt[i][n] = n, to[i][n] = i;
for (int j = n - 1;j >= 0;--j) rep(i, 26) {
if (c[j] - 'a' != i) {
dp[i][j] = dp[i][j + 1];
nxt[i][j] = nxt[i][j + 1];
to[i][j] = to[i][j + 1];
}
else if (s[j].size() == 1) {
dp[i][j] = dp[s[j][0] - 'a'][j + 1];
nxt[i][j] = nxt[s[j][0] - 'a'][j + 1];
to[i][j] = to[s[j][0] - 'a'][j + 1];
}
else {
dp[i][j] = 0, nxt[i][j] = j, to[i][j] = i;
rep(k, s[j].size()) {
dp[i][j] += dp[s[j][k] - 'a'][j + 1];
dp[i][j] = min(dp[i][j], (ll)MAXN * MAXN);
}
}
}
dfs(0, 0, 1, L, R);
}
|
T2. Lights Off
Tag: 数学
有两个二进制数 $a,b$，每次操作，先将 $b$ 的一位取反，然后将 $a$ 异或上 $b$，最后将 $b$ 在二进制下循环右移一位。问至少几次操作让 $a=0$。
多测，数据组数 $\le 2\cdot 10^5$，所有测试点中 $a,b$ 在二进制下位数相同且 $\le 20$。
考虑将一位反转会对结果造成什么影响，发现一定是异或上连续的一串1，而由于每次操作内只能反转一次，所以每种长度的一串1有且仅有一个。于是可以预处理一个背包 $f_{i,j}$ 表示长度为 $1\dots i$ 的串异或起来能否得到 $j$。询问时枚举答案即可。
不太清楚是怎么证明答案 $\le n$ 的。
Code
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
| int T_ = 1, case_;
int n;
bool dp[21][1 << 21];
int shift(int x) {
int y = x % 2;
return y * (1 << (n - 1)) + x / 2;
}
string s, t;
int a, b;
void solve() {
cin >> s >> t;
a = b = 0;
rep(i, n)a = a * 2 + s[i] - '0', b = b * 2 + t[i] - '0';
int now = 0;
rep(i, n + 1) {
if (dp[i][(a ^ now)]) {
cout << i << endl;
return;
}
now = shift(now) ^ b;
}
}
int main() {
cin >> T_ >> n;
dp[0][0] = 1;
int p[21];
init(p, 0);
rep(i, n) {
rep(j, n)p[j] = shift(p[j]) ^ (1 << j);
rep(msk, (1 << n)) {
if (!dp[i][msk])continue;
rep(j, n)dp[i + 1][(msk ^ p[j])] = 1;
}
}
for (case_ = 1; case_ <= T_; case_++)solve();
return 0;
}
|
T3. Moo Rute
一条长度为 $n+1$ 的链，节点标号为 $0 \dots n$。从 0 开始走，每步向左或向右一个节点。已知每条边的经过次数 $a_i$，求在掉头次数最少的前提下，有多少种方案。
$n \le 10^5,a_i \le 10^6$
只写了个 $n=2$ 的部分分，组合数随便搞搞。
正解不知道怎么做。
UPD 2023/3/24：晋级了
先只考虑 $n=2$ 时的情况：
- 若 $a_1>a_2$，答案为 $\dbinom{a_1/2}{a_2/2}$
- 若 $a_1 \le a_2$，答案为 $\dbinom{a_2/2-1}{a_1/2-1}$
稍加思考可以知道，$n$ 更大的情况其实就相当于若干个 $n=2$ 连起来，相乘即可。
Code
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
| ll n, a[100005], ans = 1;
ll f[1000006];
ll qpow(ll x, ll y) {
ll p = 1;
while (y) {
if (y & 1)p = p * x % mod;
x = x * x % mod;
y >>= 1;
}
return p;
}
ll C(ll x, ll y) {
return f[x] * qpow(f[y], mod - 2) % mod * qpow(f[x - y], mod - 2) % mod;
}
ll Solve(int a, int b) {
if (a > b)return C(a / 2, b / 2);
else return C(b / 2 - 1, a / 2 - 1);
}
void solve() {
cin >> n;
rep(i, n)cin >> a[i];
f[0] = 1;
repp(i, 1000000)f[i] = f[i - 1] * i % mod;
rep(i, n - 1)ans = ans * Solve(a[i], a[i + 1]) % mod;
cout << ans;
}
|