Educational Codeforces Round 97 简要题解
缺省源
#include <queue>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MP make_pair
#define ll long long
#define fi first
#define se second
using namespace std;
template <typename T>
void read(T &x) {
x = 0; bool f = 0;
char c = getchar();
for (;!isdigit(c);c=getchar()) if (c=='-') f=1;
for (;isdigit(c);c=getchar()) x=x*10+(c^48);
if (f) x=-x;
}
template<typename F>
inline void write(F x, char ed = '
') {
static short st[30];short tp=0;
if(x<0) putchar('-'),x=-x;
do st[++tp]=x%10,x/=10; while(x);
while(tp) putchar('0'|st[tp--]);
putchar(ed);
}
template <typename T>
inline void Mx(T &x, T y) { x < y && (x = y); }
template <typename T>
inline void Mn(T &x, T y) { x > y && (x = y); }
A. Marketing Scheme
直接判断 (l imes 2 ge r) 即可。
B. Reverse Binary Strings
这题让好多人想了一会（我也，考虑对序列异或差分，最终序列要求全部事 1，每次 reverse 可以发现只有两端的值变，所以每次可以同时消掉两个 0
C. Chef Monocarp
简单 dp 即可
D. Minimal Height Tree
模拟 bfs 即可，找到最长的连续段当作一串儿子挂在一个节点上。
const int N = 200050;
int dep[N], a[N], T, n;
int main() {
for (read(T); T; T--) {
read(n);
memset(dep, 0, n * 4 + 200);
queue<int> q; q.push(1);
for (int i = 1;i <= n; i++) read(a[i]);
for (int i = 2;i <= n; i++) {
int t = q.front();
dep[i] = dep[t] + 1, q.push(i);
if (a[i] >= a[i+1]) q.pop();
}
write(dep[n]);
}
return 0;
}
E. Make It Increasing
先考虑序列的合法情况，显然严格上升序列可以通过 (a[i] = a[i] - i) 变成非严格上升序列，所以我们先正着反着扫两遍，得出是否有解和哪些位置必须要改变，剩下的位置做最长上升子序列即可。
const int N = 500050;
int st[N], a[N], vis[N], n, k, tp;
void insert(int x) {
if (!tp) return st[++tp] = x, void();
int l = 1, r = tp;
while (l <= r) {
int mid = (l + r) >> 1;
if (st[mid] <= x) l = mid + 1;
else r = mid - 1;
}
if (l > tp) st[++tp] = x;
else st[l] = x;
}
int main() {
read(n), read(k);
for (int i = 1;i <= n; i++) read(a[i]), a[i] -= i;
for (int i = 1, x;i <= k; i++) read(x), vis[x] = 1;
int lim = -1e9;
for (int i = 1;i <= n; i++) {
if (vis[i] == 1) {
if (a[i] < lim) return write(-1), 0;
Mx(lim, a[i]);
}
if (a[i] < lim) vis[i] = -1;
}
lim = 1e9;
for (int i = n;i >= 1; i--) {
if (vis[i] == 1) {
if (a[i] > lim) return write(-1), 0;
Mn(lim, a[i]);
}
if (a[i] > lim) vis[i] = -1;
}
memset(st, 0x3f, sizeof(st));
st[tp = 0] = 0;
for (int i = 1;i <= n; i++) {
if (vis[i]) continue;
insert(a[i]);
}
write(n - k - tp);
return 0;
}
F. Emotional Fishermen
考后自己补出来的。
假设我们已经获得了最终的序列，把前缀最大值看成隔板，首先两个前缀最大值 (a_i, a_{i+1}) 要满足 (2a_ile a_{i+1})，考虑其他元素 x，发现在第一个大于等于 (2x) 前缀最大值之后就可以随便填了。因此我们一个一个放前缀最大值，每放一个最大值，发现有一些元素可以随便放了，用排列算一下即可。
dp 的过程发现还可以前缀和优化，吊打标算了
const int N = 5005;
const int P = 998244353;
ll fac[N], inv[N], pre[N], dp[N], a[N], n;
ll A(int n, int m) { return fac[n] * inv[n-m] % P; }
int cnt[N];
ll fpw(ll x, ll mi) {
ll res = 1;
for (; mi; mi >>= 1, x = x * x % P)
if (mi & 1) res = res * x % P;
return res;
}
int main() {
read(n);
for (int i = 1;i <= n; i++) read(a[i]);
fac[0] = 1;
for (int i = 1;i <= n; i++)
fac[i] = fac[i-1] * i % P;
inv[n] = fpw(fac[n], P - 2);
for (int i = n - 1; i >= 1; i--)
inv[i] = inv[i+1] * (i + 1) % P;
inv[0] = dp[0] = 1, sort(a + 1, a + n + 1);
int j = 0;
if (a[n-1] * 2 > a[n]) return write(0), 0;
for (int i = 1;i <= n; i++) {
while (j < n && a[j+1] * 2 <= a[i]) j++;
dp[i] = (A(n - 1, j) + pre[j] * inv[n - 1 - j]) % P;
pre[i] = (pre[i-1] + dp[i] * fac[n - j - 2]) % P;
}
write(dp[n]);
return 0;
}
G. Death DBMS
套路模板题，链剖 + AC 自动姬，考场上竟然码出来了，我也是码农
jly 有更好写的 (Theta(nsqrt n)) 算法，考虑暴力跳 fail，每次跳 fail 当前串长度都会减少 1，由于空节点的的值事 -1，我们直接跳过去，由于长度不同的串最多有 (sqrt n) 个，所以复杂度正确。
const int N = 600050;
int ch[N][26], en[N], f[N], id[N], ed[N], cnt = 1;
char s[N];
inline void insert(char *s, int k) {
int p = 1, len = strlen(s + 1);
for (int i = 1;i <= len; i++) {
int c = s[i] - 'a';
if (!ch[p][c]) ch[p][c] = ++cnt;
p = ch[p][c];
}
en[k] = p, ed[p] = k;
}
int dep[N], siz[N], son[N], Top[N], dfn[N], num;
int h[N], ne[N<<1], to[N<<1], tot;
inline void add(int x, int y) { ne[++tot] = h[x], to[h[x] = tot] = y; }
void dfs(int x) {
dep[x] = dep[f[x]] + (siz[x] = 1);
for (int i = h[x], y; i; i = ne[i]) {
dfs(y = to[i]), siz[x] += siz[y];
if (siz[son[x]] < siz[y]) son[x] = y;
}
}
void dfs2(int x, int topf) {
Top[x] = topf, dfn[x] = ++num, id[num] = x;
if (son[x]) dfs2(son[x], topf);
for (int i = h[x], y; i; i = ne[i])
if ((y = to[i]) != son[x]) dfs2(y, y);
}
void build(void) {
queue<int> q;
for (int i = 0;i < 26; i++)
if (ch[1][i]) q.push(ch[1][i]), f[ch[1][i]] = 1;
else ch[1][i] = 1;
while (q.size()) {
int x = q.front(); q.pop();
if (x != 1) add(f[x], x);
for (int i = 0;i < 26; i++) {
if (!ch[x][i]) ch[x][i] = ch[f[x]][i];
else q.push(ch[x][i]), f[ch[x][i]] = ch[f[x]][i];
}
}
}
#define ls p << 1
#define rs ls | 1
int mx[N<<2];
void build(int p, int l, int r) {
mx[p] = -1;
if (l == r) return mx[p] = ed[id[l]] ? 0 : -1, void();
int mid = (l + r) >> 1;
build(ls, l, mid), build(rs, mid + 1, r);
mx[p] = max(mx[ls], mx[rs]);
}
void change(int p, int l, int r, int x, int c) {
if (l == r) return mx[p] = c, void();
int mid = (l + r) >> 1;
if (x <= mid) change(ls, l, mid, x, c);
else change(rs, mid + 1, r, x, c);
mx[p] = max(mx[ls], mx[rs]);
}
void query(int p, int l, int r, int L, int R, int &ans) {
if (L <= l && r <= R) return Mx(ans, mx[p]);
int mid = (l + r) >> 1;
if (L <= mid) query(ls, l, mid, L, R, ans);
if (R > mid) query(rs, mid + 1, r, L, R, ans);
}
void query(int x, int &ans) {
while (x) {
query(1, 1, num, dfn[Top[x]], dfn[x], ans);
x = f[Top[x]];
}
}
struct Heap {
priority_queue<int> A, B;
void update(void) { while (B.size() && A.top() == B.top()) A.pop(), B.pop(); }
int Top(void) { update(); return A.top(); }
void del(int x) { B.push(x); }
void push(int x) { A.push(x); }
}q[300005];
int pre[N], n, m;
int main() {
read(n), read(m);
for (int i = 1;i <= n; i++)
scanf ("%s", s + 1), insert(s, i), q[en[i]].push(0);
build(), dfs(1), dfs2(1, 1), build(1, 1, num);
for (int i = 1, x, y;i <= m; i++) {
int op; read(op);
if (op == 1) {
read(x), read(y);
q[en[x]].push(y), q[en[x]].del(pre[x]), pre[x] = y;
change(1, 1, num, dfn[en[x]], q[en[x]].Top());
}
else {
scanf ("%s", s + 1);
int len = strlen(s + 1), nw = 1, ans = -1;
for (int i = 1;i <= len; i++) {
nw = ch[nw][s[i] - 'a'];
query(nw, ans);
}
write(ans);
}
}
return 0;
}