练习选讲（2023.9）
9 月
9.1
P5546 [POI2000] 公共串：二分，哈希，SA（紫）
二分长度 \(len\)，用一个 unordered_map 存储对于每一个字符串，当前长度的哈希值是否出现过。最后再枚举第一个字符串中出现的长度为 \(len\) 子串即可。
时间复杂度 \(O(n\log m)\)，其中 \(m\) 为字符串长度。
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <unordered_map>
using namespace std;
typedef unsigned long long ull;
const ull P = 19260817;
int n, minlen = 2000; ull p[2010], h[10][2010];
char s[10][2010];
bool check(int len) {
unordered_map<ull, bool> nums[10];
for (int i = 2; i <= n; ++i) {
for (int j = len; j <= strlen(s[i]+1); ++j) {
ull num = h[i][j] - h[i][j-len] * p[len];
nums[i][num] = 1;
}
}
for (int i = len; i <= strlen(s[1]+1); ++i) {
ull num = h[1][i] - h[1][i-len] * p[len];
bool check = 1;
for (int j = 2; j <= n; ++j) check &= nums[j][num];
if (check) return 1;
}
return 0;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> s[i]+1;
if (n == 1) return printf("%d\n", strlen(s[1]+1)), 0;
p[0] = 1;
for (int i = 1; i <= 2000; ++i) p[i] = p[i-1] * P;
for (int i = 1; i <= n; ++i) {
minlen = min(minlen, (int)strlen(s[i]+1));
for (int j = 1; j <= strlen(s[i]+1); ++j)
h[i][j] = h[i][j-1] * P + (s[i][j]-'a');
}
int l = -1, r = minlen+1;
while (l+1 != r) {
int mid = l + r >> 1;
if (check(mid)) l = mid;
else r = mid;
}
printf("%d\n", l);
return 0;
}
P8818 [CSP-S 2022] 策略游戏：st 表（绿）
显然我们应该考虑后手的情况：
1 后手无负数
1.1 先手有正数：此时先手会取区间内最大值，后手只能取区间内最小值。
1.2 先手无正数：此时先手只能取区间内最大值，后手会取区间内最大值。
2 后手无正数
2.1 先手有负数：此时先手会取区间内最小值（负负得正，相乘后变为最大值），后手会取区间内最大值。
2.2 先手无负数：此时先手只能取区间内最小值，后手会取区间内最小值。
3 后手既有正数又有负数
3.1 先手有 \(0\)：此时先手只能选 \(0\)，否则后手一定有策略使得结果为负。
3.2 先手无正数：此时先手只能取区间内最大值，后手会取区间内最大值。
3.3 先手无负数：此时先手只能取区间内最小值，后手会取区间内最小值。
3.4 先手既有正数又有负数：先手可以在 3.2 和 3.3 两种情况中取最大值，即 \(\max(\text{先手区间内最大负数}\times \text{后手区间内最大值},\text{先手区间内最小正数}\times\text{后手区间内最小值})\)。
观察上面这 \(8\) 种情况，我们可以发现，我们需要维护：
- 区间内最大/小值；
- 区间内最大非正数，区间内最小非负数。
用 \(4\) 个 st 表维护即可。时间复杂度 \(O(n\log n+q)\)。
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = 1e5+10, INF = 2e9;
int n, m, q;
int st[3][5][N][20];
// 1: 区间内最大值, 2: 区间内最小值, 3: 区间内最大非正数, 4: 区间内最小非负数
int query(int p, int op, int l, int r) {
int k = log2(r-l+1);
if (op & 1) return max(st[p][op][l][k], st[p][op][r-(1<<k)+1][k]);
else return min(st[p][op][l][k], st[p][op][r-(1<<k)+1][k]);
}
int main() {
scanf("%d%d%d", &n, &m, &q);
for (int i = 1; i <= n; ++i) {
int x; scanf("%d", &x);
st[1][1][i][0] = x, st[1][2][i][0] = x;
st[1][3][i][0] = (x > 0) ? -INF : x, st[1][4][i][0] = (x < 0) ? INF : x;
}
for (int i = 1; i <= m; ++i) {
int x; scanf("%d", &x);
st[2][1][i][0] = x, st[2][2][i][0] = x;
st[2][3][i][0] = (x > 0) ? -INF : x, st[2][4][i][0] = (x < 0) ? INF : x;
}
for (int i = 1; (1<<i) <= n; ++i) {
for (int j = 1; j+(1<<i)-1 <= n; ++j)
st[1][1][j][i] = max(st[1][1][j][i-1], st[1][1][j+(1<<i-1)][i-1]),
st[1][2][j][i] = min(st[1][2][j][i-1], st[1][2][j+(1<<i-1)][i-1]),
st[1][3][j][i] = max(st[1][3][j][i-1], st[1][3][j+(1<<i-1)][i-1]),
st[1][4][j][i] = min(st[1][4][j][i-1], st[1][4][j+(1<<i-1)][i-1]);
}
for (int i = 1; (1<<i) <= m; ++i) {
for (int j = 1; j+(1<<i)-1 <= m; ++j)
st[2][1][j][i] = max(st[2][1][j][i-1], st[2][1][j+(1<<i-1)][i-1]),
st[2][2][j][i] = min(st[2][2][j][i-1], st[2][2][j+(1<<i-1)][i-1]),
st[2][3][j][i] = max(st[2][3][j][i-1], st[2][3][j+(1<<i-1)][i-1]),
st[2][4][j][i] = min(st[2][4][j][i-1], st[2][4][j+(1<<i-1)][i-1]);
}
int l1, r1, l2, r2;
while (q -- ) {
scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
int maxa = query(1, 1, l1, r1), mina = query(1, 2, l1, r1), maxb = query(2, 1, l2, r2), minb = query(2, 2, l2, r2);
if (minb >= 0) {
if (maxa > 0) printf("%lld\n", (ll)maxa*minb);
else printf("%lld\n", (ll)maxa*maxb);
} else if (maxb <= 0) {
if (mina < 0) printf("%lld\n", (ll)mina*maxb);
else printf("%lld\n", (ll)mina*minb);
} else {
int maxxa = query(1, 3, l1, r1), minna = query(1, 4, l1, r1);
if (maxxa == 0) puts("0");
else if (maxa < 0) printf("%lld\n", (ll)maxa*maxb);
else if (mina > 0) printf("%lld\n", (ll)mina*minb);
else printf("%lld\n", max((ll)maxxa*maxb, (ll)minna*minb));
}
}
return 0;
}
补之前的 ABC 317：
ABC317A. Potions：枚举（红）
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n, h, x, a[110];
int main() {
scanf("%d%d%d", &n, &h, &x);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
if (h+a[i] >= x) printf("%d\n", i), exit(0);
}
}
ABC317B. MissingNo：枚举（红）
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n, minl = 1001, nums[1100];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
int x; scanf("%d", &x);
minl = min(minl, x), nums[x] ++;
}
for (int i = minl; i <= minl+n; ++i) {
if (!nums[i])
printf("%d\n", i), exit(0);
}
}
ABC317C. Remembering the Days：枚举，dfs（橙）
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n, m, ans, a[15], g[15][15];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
g[u][v] = g[v][u] = w;
}
for (int i = 1; i <= n; ++i) a[i] = i;
while (true) {
int tot = 0;
for (int i = 1; i < n; ++i) {
if (g[a[i]][a[i+1]]) tot += g[a[i]][a[i+1]];
else break;
}
ans = max(ans, tot);
if (!next_permutation(a+1, a+n+1)) break;
}
printf("%d\n", ans);
return 0;
}
ABC317D. President：dp（黄）
令 \(f_{i,j}\) 表示前 \(i\) 个选取中共获得 \(j\) 张票的最小花费。初始时若 \(x_1>y_1\) 则 \(f_{1,z_1}=0\)；否则 \(f_{1,z_1}=y_1-\left\lfloor\dfrac{x_1+y_1}{2}\right\rfloor\)。
同样的，当 \(x_i>y_i\) 时，状态转移方程为：
\[f_{i,j}=f_{i-1,j-z_i}
\]
否则，
\[f_{i,j}=\min\{f_{i-1,j},f_{i-1,j-z_i}+y_i-\left\lfloor\dfrac{x_i+y_i}{2}\right\rfloor\}
\]
答案为 \(\displaystyle\min_{\lceil tot/2\rceil\le j\le tot} f_{n,j}\)。
时间复杂度 \(O(n\sum(x_i+y_i))\)。
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define int long long
const int N = 110, M = 1e5+10;
int n, ans, tot, x[N], y[N], z[N], f[N][M];
signed main() {
scanf("%lld", &n);
for (int i = 1; i <= n; ++i) scanf("%lld%lld%lld", &x[i], &y[i], &z[i]), tot += z[i];
for (int i = 1; i <= tot; ++i) f[1][i] = 1e18;
f[1][z[1]] = (x[1] > y[1]) ? 0 : y[1]-(x[1]+y[1])/2;
for (int i = 2; i <= n; ++i) {
for (int j = 0; j <= tot; ++j) {
f[i][j] = (int)1e18;
if (x[i] > y[i] && j >= z[i]) f[i][j] = min(f[i][j], f[i-1][j-z[i]]);
if (x[i] < y[i]) f[i][j] = min(f[i-1][j], (j>=z[i])?(y[i]-(x[i]+y[i])/2+f[i-1][j-z[i]]):(int)1e18);
}
}
ans = 1e18;
for (int i = (tot+1)/2; i <= tot; ++i) ans = min(ans, f[n][i]);
printf("%lld\n", ans);
return 0;
}
ABC317E. Avoid Eye Contact：bfs（黄）
实际上直接暴力处理出地图就好了，但我赛时脑抽了写了个奇丑的二分……
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
typedef pair<int, int> pii;
int n, m, dist[2010][2010]; pii S, T;
vector<pii> row[2010], col[2010];
char c[2010][2010];
bool check(int x, int y) {
if (!(x && y && (x <= n) && (y <= m) && (c[x][y] == '.' || c[x][y] == 'G'))) return 0;
int l = upper_bound(row[x].begin(), row[x].end(), make_pair(y, 0)) - row[x].begin() - 1;
int r = upper_bound(row[x].begin(), row[x].end(), make_pair(y, 0)) - row[x].begin();
int u = upper_bound(col[y].begin(), col[y].end(), make_pair(x, 0)) - col[y].begin() - 1;
int d = upper_bound(col[y].begin(), col[y].end(), make_pair(x, 0)) - col[y].begin();
return ((l == -1 || row[x][l].second > -1) && (r == row[x].size() || row[x][r].second < 1) &&
(u == -1 || col[y][u].second < 1) && (d == col[y].size() || col[y][d].second > -1));
}
void bfs() {
queue<pii> q; q.push(S), dist[S.first][S.second] = 0;
while (q.size()) {
auto t = q.front(); q.pop();
int x = t.first, y = t.second;
for (int i = 0; i < 4; ++i) {
int x_ = x+dx[i], y_ = y+dy[i];
if (dist[x_][y_] > dist[x][y]+1 && check(x_, y_)) dist[x_][y_] = dist[x][y]+1, q.push({x_, y_});
}
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> c[i]+1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j)
dist[i][j] = 1e9;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (c[i][j] == '.') continue;
else if (c[i][j] == '#') row[i].push_back({j, 0}), col[j].push_back({i, 0});
else if (c[i][j] == 'S') S = {i, j};
else if (c[i][j] == 'G') T = {i, j};
else if (c[i][j] == '>') row[i].push_back({j, -1}), col[j].push_back({i, 0});
else if (c[i][j] == '<') row[i].push_back({j, 1}), col[j].push_back({i, 0});
else if (c[i][j] == '^') col[j].push_back({i, -1}), row[i].push_back({j, 0});
else if (c[i][j] == 'v') col[j].push_back({i, 1}), row[i].push_back({j, 0});
}
}
bfs();
if (dist[T.first][T.second] == 1e9) puts("-1");
else printf("%d\n", dist[T.first][T.second]);
return 0;
}
ABC317F. Nim：数位 dp（蓝）
注意到 \(X,Y,Z\) 都很小但 \(N\) 很大，考虑数位 dp。令 \(f_{u,a,b,c,l_1,l_2,l_3,z_1,z_2,z_3}\) 表示计算到 \(N\) 的二进制第 \(u\) 位，当前选的数模 \(X,Y,Z\) 的余数分别是 \(a,b,c\)，且三个数是否到当前位上界，是否为 \(0\) 的方案数，记忆化搜索实现。
时间复杂度 \(O(2^6X^3\log N)\)。
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int P = 998244353;
long long n;
int x, y, z, r[65], f[65][15][15][15][2][2][2][2][2][2];
int dfs(int u, int a, int b, int c, bool l1, bool l2, bool l3, bool z1, bool z2, bool z3) {
if (u < 0) return ((!a) && (!b) && (!c) && (!z1) && (!z2) && (!z3));
if (f[u][a][b][c][l1][l2][l3][z1][z2][z3] != -1) return f[u][a][b][c][l1][l2][l3][z1][z2][z3];
int res = 0;
for (int i = 0; i <= (l1 ? r[u] : 1); ++i) {
for (int j = 0; j <= (l2 ? r[u] : 1); ++j) {
for (int k = 0; k <= (l3 ? r[u] : 1); ++k) {
if (i ^ j ^ k) continue;
res += dfs(u-1, (a+(1ll<<u)*i)%x, (b+(1ll<<u)*j)%y, (c+(1ll<<u)*k)%z, (l1&&(i==r[u])), (l2&&(j==r[u])), (l3&&(k==r[u])), (z1&&(!i)), (z2&&(!j)), (z3&&(!k)));
res %= P;
}
}
}
return f[u][a][b][c][l1][l2][l3][z1][z2][z3] = res;
}
int main() {
memset(f, -1, sizeof f);
scanf("%lld%d%d%d", &n, &x, &y, &z);
for (int i = 62; i >= 0; --i) r[i] = ((n >> i) & 1);
printf("%d\n", dfs(62, 0, 0, 0, 1, 1, 1, 1, 1, 1));
return 0;
}
9.2
ABC317G. Rearranging：二分图，最大流（紫）
将这个问题转化为一个图论问题，若 \(a_{i,j}=x\)，我们就从表示第 \(i\) 行的点向表示数 \(x\) 的点之间连一条边。显然最后会形成一个二分图，若该二分图恰好有 \(m\) 个完美匹配则存在答案。
Hall 定理：二分图有完美匹配的充要条件是，对于左部点集的任意一个子集 \(S\)，它的邻居集合（可重集）\(N(S)\) 均满足 \(|S|\le |N(S)|\)。
实际上，Hall 定理可以推广到有 \(m\) 个完美匹配的形式，此时需要满足 \(m|S|\le |N(S)|\)。
我们先给出做法：不断寻找完美匹配，找到后把该完美匹配内的所有边删除，重复 \(m\) 次。若有一次找不到完美匹配则无解。那么，若原图满足上述条件，删除一组完美匹配后仍然满足上述条件；否则无解。
通过 Dinic 算法求解二分图的完美匹配，时间复杂度 \(O(n^{1.5}m^2)\)。
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 410, M = 50010, INF = 2e9;
int n, m, S, T, a[N][N], ans[N][N];
int idx = 1, cnt, e[M], ne[M], h[N], c[M];
int d[N], cur[N];
void add(int u, int v, int w) {
e[++ idx] = v, ne[idx] = h[u], c[idx] = w, h[u] = idx;
}
bool bfs() {
memset(d, 0, sizeof d);
queue<int> q; q.push(S), d[S] = 1, cur[S] = h[S];
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = h[u]; i != -1; i = ne[i]) {
int v = e[i];
if (!d[v] && c[i] > 0) {
d[v] = d[u]+1, q.push(v), cur[v] = h[v];
if (v == T) return 1;
}
}
}
return 0;
}
int dinic(int u, int mf) {
if (u == T) return mf;
int sum = 0;
for (int i = cur[u]; i != -1; i = ne[i]) {
cur[u] = i;
int v = e[i];
if (d[v] == d[u]+1 && c[i] > 0) {
int f = dinic(v, min(mf, c[i]));
c[i] -= f, c[i^1] += f, sum += f, mf -= f;
if (!mf) break;
}
}
if (!sum) d[u] = 0;
return sum;
}
int MaxFlow() {
int flow = 0;
while (bfs()) flow += dinic(S, INF);
return flow;
}
int main() {
S = 0, T = 400;
memset(h, -1, sizeof h);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
scanf("%d", &a[i][j]);
add(i, a[i][j]+n, 1), add(a[i][j]+n, i, 0);
}
}
cnt = idx;
for (int i = 1; i <= n; ++i) add(S, i, 1), add(i, S, 0), add(i+n, T, 1), add(T, i+n, 0);
for (int j = 1; j <= m; ++j) {
if (MaxFlow() != n) return puts("No"), 0;
for (int i = 3; i <= cnt; i += 2) {
if (!c[i]) continue;
int u = e[i], v = e[i^1];
ans[u][j] = v-n;
c[i] = c[i^1] = 0;
}
for (int i = cnt+2; i <= idx; i += 2) {
if (!c[i]) continue;
c[i^1] = 1, c[i] = 0;
}
}
puts("Yes");
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j)
printf("%d ", ans[i][j]);
puts("");
}
return 0;
}
CF540E. Infinite Inversions：树状数组（紫）
（双倍经验：P2448 无尽的生命）
答案可以分为两种情况：
- 两个调换过位置的数构成的逆序对：
这种情况直接用树状数组维护即可。
- 一个调换过位置的数和一个没有调换过位置的数构成的逆序对：
令 \(x\) 表示调换过位置的数，其调换后位置为 \(y\)，\(x\) 和 \(y\) 之间还有 \(k\) 个调换过位置的数，那么其对答案的贡献为 \(|x-y-k|\)。
显然，两个没有调换过位置的数不可能构成逆序对。
时间复杂度 \(O(n\log n)\)。
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
const int N = 2e5+10;
int n, a[N], c[N]; long long ans; pii oper[N];
vector<int> pos;
int find(int x) {
return lower_bound(pos.begin(), pos.end(), x) - pos.begin() + 1;
}
int lowbit(int x) {
return x & -x;
}
void add(int x, int k) {
for (int i = x; i < N; i += lowbit(i)) c[i] += k;
}
int query(int x) {
int sum = 0;
for (int i = x; i > 0; i -= lowbit(i)) sum += c[i];
return sum;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
int x, y; scanf("%d%d", &x, &y);
oper[i] = {x, y}; pos.push_back(x), pos.push_back(y);
}
sort(pos.begin(), pos.end());
pos.erase(unique(pos.begin(), pos.end()), pos.end());
for (int i = 1; i <= pos.size(); ++i) a[i] = pos[i-1];
for (int i = 1; i <= n; ++i) swap(a[find(oper[i].first)], a[find(oper[i].second)]);
for (int i = 1; i <= pos.size(); ++i) {
int x = query(find(a[i]));
ans += (find(a[i])-1 - x) + abs(a[i]-pos[i-1]-(find(a[i])-find(pos[i-1])));
add(find(a[i]), 1);
}
printf("%lld\n", ans);
return 0;
}
P5854 【模板】笛卡尔树：单调栈，笛卡尔树（蓝）
笛卡尔树是一种特殊的二叉搜索树，其一个节点上有两个信息 \((x_i,y_i)\)，如果只考虑 \(x_i\)，它是一棵二叉搜索树；如果只考虑 \(y_i\)，它是一个小根堆。
在保证 \(x_i\) 递增的情况下，我们可以在 \(O(n)\) 的时间复杂度内构建笛卡尔树。
每次插入一个新节点时，为了确保二叉搜索树的性质得到满足，我们需要将新节点插入到尽可能靠右的位置。也就是说，我们需要维护从根节点一直到右儿子形成的链。设当前要插入的点为 \(u\)，则我们需要从下往上在这条链上找到第一个点 \(v\) 满足 \(y_v<y_u\)，那么将 \(v\) 的右儿子设置为 \(u\)（若不存在这样的 \(v\)，则将 \(u\) 设为根节点），若 \(v\) 已经有右子树了，则将 \(v\) 原来的右儿子设为 \(u\) 的左儿子。
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e7+10;
int n, top, p[N], L[N], R[N], stk[N]; ll ans1, ans2;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<23],*p1=buf,*p2=buf;
template <typename T>
void read(T &x) {
x = 0;
register int flag = 1;
static char c = getchar();
while (!isdigit(c)) {
if (c == '-') flag = -1;
c = getchar();
}
while (isdigit(c)) {
x = x * 10 + c - '0';
c = getchar();
}
x *= flag;
}
void build() {
for (int i = 1; i <= n; ++i) {
while (top && p[stk[top]] > p[i]) top --;
if (!top) L[i] = stk[top+1];
else L[i] = R[stk[top]], R[stk[top]] = i;
stk[++ top] = i;
}
}
int main() {
read(n);
for (int i = 1; i <= n; ++i) read(p[i]);
build();
for (int i = 1; i <= n; ++i) ans1 ^= 1ll * i * (L[i]+1), ans2 ^= 1ll * i * (R[i]+1);
printf("%lld %lld\n", ans1, ans2);
return 0;
}
9.3
P3538 [POI2012] OKR-A Horrible Poem：字符串哈希，线性筛（蓝）
本题需要用到循环节的几个关键性质：
-
若 \(s[l\cdots r-len]=s[l+len\cdots r]\)，则 \(len\) 为 \(s[l\cdots r]\) 的循环节长度。
-
循环节 \(\times\) 循环次数 \(=\) 总长度，即总长度的质因子可分为循环节和循环次数。
-
最小循环节的倍数也是循环节。
知道这些之后，我们可以将区间长度 \(len\) 分解质因数，即不断将 \(len\) 除以其最小质因子，并判断能否成为循环节。
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
const int N = 5e5+10;
const ull P = 998244353;
int n, m; char s[N];
ull h[N], power[N];
int cnt, prime[N], p[N]; bool st[N];
// p[i]表示i的最小质因子
void Euler() {
st[0] = st[1] = 1;
for (int i = 2; i <= n; ++i) {
if (!st[i]) prime[++ cnt] = i, p[i] = i;
for (int j = 1; j <= cnt && prime[j]*i <= n; ++j) {
st[i*prime[j]] = 1, p[i*prime[j]] = prime[j];
if (i % prime[j] == 0) break;
}
}
}
ull get_hash(int l, int r) {
return h[r] - h[l-1] * power[r-l+1];
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> s+1 >> m;
Euler();
power[0] = 1; for (int i = 1; i <= n; ++i) power[i] = power[i-1] * P;
for (int i = 1; i <= n; ++i) h[i] = h[i-1] * P + (s[i]-'a');
int l, r, ans, len;
while (m -- ) {
cin >> l >> r;
ans = len = r-l+1;
while (len > 1) {
int newlen = ans / p[len];
if (get_hash(l, r-newlen) == get_hash(l+newlen, r)) ans /= p[len];
len /= p[len];
}
cout << ans << '\n';
}
return 0;
}
P1377 [TJOI2011] 树的序：笛卡尔树（蓝）
这题与板子题的区别在于，权值符合二叉搜索树的性质，编号符合小根堆的性质（因为始终先插入父亲，再插入儿子）。那么只需要在读入时调换一下位置就好。
如何求出字典序最小的插入顺序？由于权值是二叉搜索树，所以先序遍历输出答案即可。
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n, p[N], L[N], R[N];
int top, stk[N];
void build() {
for (int i = 1; i <= n; ++i) {
while (top && p[stk[top]] > p[i]) top --;
if (!top) L[i] = stk[top+1];
else L[i] = R[stk[top]], R[stk[top]] = i;
stk[++ top] = i;
}
}
void dfs(int u) {
if (!u) return ;
printf("%d ", u), dfs(L[u]), dfs(R[u]);
}
int main() {
scanf("%d", &n);
for (int i = 1, x; i <= n; ++i) scanf("%d", &x), p[x] = i;
build(), dfs(stk[1]);
return 0;
}
P8773 [蓝桥杯 2022 省 A] 选数异或：st 表（绿）
对于每一个 \(a_i\)，我们求出一个最大的 \(last_i=j\)，使得 \(a_j\oplus a_i=x\) 且 \(j\le i\)。我们用 st 表维护区间内最大的 \(last_i\)，显然，若 \(l\le \displaystyle\max_{l\le i\le r}last_i\le r\)，则区间内存在两个数异或结果为 \(x\)；否则不存在。
时间复杂度 \(O(n\log n)\)。
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1e5+10, M = 1 << 21;
int n, m, x, a[N], L[N], last[M], st[N][20];
int query(int l, int r) {
int k = log2(r-l+1);
return max(st[l][k], st[r-(1<<k)+1][k]);
}
int main() {
scanf("%d%d%d", &n, &m, &x);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (int i = 1; i <= n; ++i) last[a[i]] = i, st[i][0] = L[i] = last[x^a[i]];
for (int j = 1; (1<<j) <= n; ++j) {
for (int i = 1; i+(1<<j)-1 <= n; ++i)
st[i][j] = max(st[i][j-1], st[i+(1<<j-1)][j-1]);
}
int l, r;
while (m -- ) {
scanf("%d%d", &l, &r);
int pos = query(l, r);
if (l <= pos && pos <= r) puts("yes");
else puts("no");
}
return 0;
}
CF618F. Double Knapsack：构造（紫）
可以猜测，一定有解且为两个连续子段。
令 \(suma_i\) 表示 \(a\) 的前缀和，\(sumb_i\) 表示 \(b\) 的前缀和。不妨设 \(suma_n\le sumb_n\)。
对于每一个 \(i\)，我们求出一个最大的 \(c_i=j\) 使得 \(suma_i\ge sumb_j\)。那么有 \(suma_i<sumb_{c_i+1}\)，即 \(suma_i<sumb_{c_i}+b_{c_i+1}\)。移项得 \(suma_i-sumb_{c_i}<b_{c_i+1}\)。由于 \(1\le b_{c_i+1}\le n\)，所以 \(0\le suma_i-sumb_{c_i}<n\)，有 \(n\) 种可能。而 \(0\le i\le n\)，有 \(n+1\) 种可能。那么至少有两个 \(suma_i-sumb_{c_i}\) 是相等的。
假设 \(suma_{i1}-sumb_{c_{i1}}=suma_{i2}-sumb_{c_{i2}}\)，且 \(i1<i2\)，那么 \(suma_{i2}-suma_{i1}=sumb_{c_{i2}}-sumb_{c_{i1}}\)。即 \([i1+1,i2]\) 和 \([c_{i1}+1,c_{i2}]\) 就是符合条件的两个子段。
由于 \(c_i\) 都是单调不降的，用指针计算即可。
时间复杂度 \(O(n)\)。
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 1e6+10;
bool check = 1;
int n, a[N], b[N], c[N], num[N]; ll sa[N], sb[N];
int main() {
scanf("%d", &n); memset(num, -1, sizeof num);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), sa[i] = (ll)sa[i-1]+a[i];
for (int i = 1; i <= n; ++i) scanf("%d", &b[i]), sb[i] = (ll)sb[i-1]+b[i];
if (sa[n] > sb[n]) for (int i = 1; i <= n; ++i) swap(sa[i], sb[i]), check = 0;
int now = 0;
for (int i = 0; i <= n; ++i) {
while (now < n && sa[i] >= sb[now+1]) now ++;
c[i] = now;
if (num[sa[i]-sb[c[i]]] == -1) num[sa[i]-sb[c[i]]] = i;
else {
int last = num[sa[i]-sb[c[i]]];
if (check) {
printf("%d\n", i-last);
for (int j = last+1; j <= i; ++j) printf("%d ", j); puts("");
printf("%d\n", c[i]-c[last]);
for (int j = c[last]+1; j <= c[i]; ++j) printf("%d ", j); puts("");
} else {
printf("%d\n", c[i]-c[last]);
for (int j = c[last]+1; j <= c[i]; ++j) printf("%d ", j); puts("");
printf("%d\n", i-last);
for (int j = last+1; j <= i; ++j) printf("%d ", j); puts("");
}
return 0;
}
}
}
P4398 [JSOI2008] Blue Mary的战役地图：哈希（蓝）
哈希乱搞一下就过了。时间复杂度 \(O(n^4)\)。
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef unsigned long long ull;
const int N = 55;
const ull P1 = 19260817, P2 = 19491001; // 行和列选取不同的进制
int n, a[2][N][N]; ull h[2][N][N], power[N];
ull get_hash(int x, int y, int k, int op) {
ull res = 0;
for (int i = x; i <= x+k-1; ++i) res = res*P2 + h[op][i][y+k-1]-h[op][i][y-1]*power[k];
}
int main() {
scanf("%d", &n);
for (int k = 0; k <= 1; ++k) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j)
scanf("%d", &a[k][i][j]);
}
}
power[0] = 1;
for (int i = 1; i <= n; ++i) power[i] = power[i-1]*P1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j)
h[0][i][j] = h[0][i][j-1]*P1+a[0][i][j], h[1][i][j] = h[1][i][j-1]*P2+a[1][i][j];
}
for (int k = n; k >= 1; --k) {
unordered_map<ull, int> nums;
for (int i = 1; i <= n-k+1; ++i) {
for (int j = 1; j <= n-k+1; ++j)
nums[get_hash(i, j, k, 0)] = 1;
}
for (int i = 1; i <= n-k+1; ++i) {
for (int j = 1; j <= n-k+1; ++j)
if (nums[get_hash(i, j, k, 1)])
return printf("%d\n", k), 0;
}
}
return puts("0"), 0;
}
CF1092F. Tree with Maximum Cost：换根 dp（绿）
板子题。
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 2e5+10;
int n, a[N], dist[N]; ll sum, ans, siz[N], f[N];
vector<int> e[N];
void dfs(int u, int fa) {
siz[u] = a[u], f[1] += (ll)dist[u]*a[u];
for (auto v : e[u]) {
if (v == fa) continue;
dist[v] = dist[u]+1, dfs(v, u), siz[u] += siz[v];
}
}
void dp(int u, int fa) {
ans = max(ans, f[u]);
for (auto v : e[u]) {
if (v == fa) continue;
f[v] = f[u] - siz[v] + (sum-siz[v]), dp(v, u);
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), sum += a[i];
for (int i = 1; i < n; ++i) {
int u, v; scanf("%d%d", &u, &v);
e[u].push_back(v), e[v].push_back(u);
}
dfs(1, 1), dp(1, 1);
printf("%lld\n", ans);
return 0;
}