考试总结

估：100 + 100 + 100 + 40

实：100 + 100 + 100 + 40 rk1

被高一的 max 打爆。

括号序列问题

求括号串中所有子串的合法子串个数之和。\(\quad |s| \le 3 \times 10 ^ 5\)

考虑拆贡献，拆到每个合法子串，对于 \([l, r]\) 合法的贡献显然是 \(l \times (n - r + 1)\)，枚举 \(r\) 维护 \(l\) 的和是简单的。

#include 
using namespace std;
#define int ll
#define ll long long
#define usd unsigned
#define el putchar('\n')
#define lowbit(x) (x & (-x))
#define AC return 
#define AK return 0
#define YS cout << "YES"
#define NO cout << "NO"
#define Ys cout << "Yes"
#define No cout << "No"
#define ys cout << "yes"
#define no cout << "no"
#define ls(i) ch[i][0]
#define rs(i) ch[i][1]
#define debug(num) cerr << #num << ' ' << num << '\n'
#define void inline void
#define il inline
#define Mod(x) (((x) % mod + mod) % mod)
#define pii pair 
#define pll pair 
il char gc() { char c; while((c = getchar()) <= ' ') ; return c; }
il int rd() {char c; int x, f = 1;while(!isdigit(c = getchar())) if(c == '-') f *= -1;x = c ^ 48;while(isdigit(c = getchar())) x = (x << 3) + (x << 1) + (c ^ 48);return x * f;
}
void ACehomoxue();
signed main() {srand(time(0));freopen("string.in", "r", stdin);freopen("string.out", "w", stdout);int t = 1;// t = rd();while(t--) ACehomoxue();AK;
}
const int mod = 998244353, maxn = + 18;int n, ans = 0;
map  sum;
string s;void ACehomoxue() {cin >> s;n = s.length();for(int i = 1, v = 0; i <= n; i++) {if(s[i - 1] == '(') sum[v++] += i;if(s[i - 1] == ')') sum[v--] = 0;if(s[i - 1] == ')') ans = (ans + sum[v] * (n - i + 1)) % mod;}cout << ans;el;
}

涂色

使。

一块 \(1 \times n\) 的木板，每次操作 \((l, r, c)\) 代表可以将 \([l, r]\) 区间涂成 \(c\) 颜色。操作有先后顺序，后涂的颜色覆盖先涂的颜色。给定序列 \(s\) 代表目标颜色，请你用尽量少的操作数量达到目标，并输出方案。\(\quad n \le 700\)

设 \(dp_{l, r}\) 表示把 \([l, r]\) 染完了的最小代价，\(f_{l, r, c}\) 表示填一次 \((l, r, c)\) 后能把 \([l, r]\) 涂完的最小代价（\((l, r, c)\) 这一次不算）。对于 \(dp\) 的转移，枚举区间中转点有：

对于 \(f\) 的转移，同样的枚举中转点：

这一步由于有 \(s_k = c\) 的限制可以做到均摊 \(O(n ^ 3)\)。考虑从 \(f\) 转移到 \(dp\)，枚举 \(c\)，有：

其中 \(x\) 表示最大的满足 \(\forall k \in [i, x) \land s_k = c\) 的位置，\(y\) 表示最小的位置并满足 \(\forall k \in (k, r] \land s_k = c\)，预处理可以做到 \(O(n ^ 2 \times 26)\)。最小次数就是 \(dp_{1, n}\)，方案的话计一个来源即可。做完了，注意卡常。

#include 
using namespace std;
#define int short
#define ll long long
#define usd unsigned
#define el putchar('\n')
#define lowbit(x) (x & (-x))
#define AC return 
#define AK return 0
#define YS cout << "YES"
#define NO cout << "NO"
#define Ys cout << "Yes"
#define No cout << "No"
#define ys cout << "yes"
#define no cout << "no"
#define ls(i) ch[i][0]
#define rs(i) ch[i][1]
#define debug(num) cerr << #num << ' ' << num << '\n'
#define void inline void
#define il inline
#define Mod(x) (((x) % mod + mod) % mod)
#define pii pair 
#define pll pair 
il char gc() { char c; while((c = getchar()) <= ' ') ; return c; }
il int rd() {char c; int x, f = 1;while(!isdigit(c = getchar())) if(c == '-') f *= -1;x = c ^ 48;while(isdigit(c = getchar())) x = (x << 3) + (x << 1) + (c ^ 48);return x * f;
}
void ACehomoxue();
signed main() {srand(time(0));freopen("paint.in", "r", stdin);freopen("paint.out", "w", stdout);int t = 1;// t = rd();while(t--) ACehomoxue();AK;
}
const int maxn = 705;int n, a[maxn], pre[maxn][26], suf[maxn][26], dp[maxn][maxn], f[maxn][maxn][26], pos[26];
int has[maxn][maxn];
struct node {int l, r, c;node(int L, int R, int C) { l = L, r = R, c = C; }
} ;
vector  ldp[maxn][maxn], lf[maxn][maxn][26];void dfs(node x) {int l = x.l, r = x.r, c = x.c;if(c == -1) {if(has[l][r]) cout << l << ' ' << r << ' ' << char(has[l][r] - 1 + 'A'), el;for(node to : ldp[l][r]) {dfs(to);}} else {for(node to : lf[l][r][c]) {dfs(to);}}
}void ACehomoxue() {n = rd();for(int i = 1; i <= n; i++) a[i] = gc() - 'A';for(int i = 1; i <= n; i++) {for(int c = 0; c < 26; c++) {pre[i][c] = i, suf[i][c] = i;while(pre[i][c] <= n && a[pre[i][c]] == c) pre[i][c]++;while(suf[i][c] >= 1 && a[suf[i][c]] == c) suf[i][c]--;}}memset(f, 0x3f, sizeof(f));memset(dp, 0x3f, sizeof(dp));for(int len = 1, kk; len <= n; len++) {for(int l = 1, r = len; r <= n; l++, r++) {kk = 0;for(int k = l; k < r; k++) (dp[l][k] + dp[k + 1][r] < dp[l][r]) ? (dp[l][r] = dp[l][k] + dp[k + 1][r], kk = k) : 0;if(kk) {has[l][r] = 0;ldp[l][r].clear();ldp[l][r].push_back(node(l, kk, -1));ldp[l][r].push_back(node(kk + 1, r, -1));}for(int k = l; k < r; k++) (f[l][k][a[k]] + f[k + 1][r][a[k]] < f[l][r][a[k]]) ? (f[l][r][a[k]] = f[l][k][a[k]] + f[k + 1][r][a[k]], pos[a[k]] = k) : 0;for(int c = 0; c < 26; c++) {if(pos[c]) {lf[l][r][c].clear();lf[l][r][c].push_back(node(l, pos[c], c));lf[l][r][c].push_back(node(pos[c] + 1, r, c));pos[c] = 0;}if(pre[l][c] > r) { ldp[l][r].clear(); dp[l][r] = 1, has[l][r] = c + 1; }int x = pre[l][c], y = suf[r][c];if(dp[x][y] < f[l][r][c]) {f[l][r][c] = dp[x][y];lf[l][r][c].clear();lf[l][r][c].push_back(node(x, y, -1));}if(f[l][r][c] + 1 < dp[l][r]) {ldp[l][r].clear();has[l][r] = c + 1;ldp[l][r].push_back(node(l, r, c));dp[l][r] = f[l][r][c] + 1;}}}}cout << dp[1][n], el;dfs(node(1, n, -1));
}

交换

给定一个长度为 (n) 的目标排列 (p)，从初始排列 ([1,2,\dots,n]) 出发，依次进行 (n-1) 次交换，第 (i) 次交换的位置由排列 (a_i) 决定，即交换 (s_{a_i}) 与 (s_{a_i+1})。求有多少个长度为 (n-1) 的排列 (a)，能够使最终得到的排列恰好为 (p)，答案对 (10^9+7) 取模。 \(\quad n \le 3000\)

首先判断无解，我们考虑暴力构造出构造序列，方法类似冒泡，但是由于每个 \(i < n\) 只能在 \(a\) 中出现一次，所以每个 \((i, i + 1)\) 只能交换一次，那么我们只要在暴力构造的时候一个 \((i, i + 1)\) 了超过一次那么就是无解。考虑计数，对于我们构造出来的 \(a\)，考虑一直交换 \(a\) 的相邻两项来构造出所有方案。注意到当相邻两项的差如果大于 \(1\) 那么交换之后对答案一定没有影响，但是如果相邻的两项差只有 \(1\) 交换之后弄出来的就一定不是 \(p\) 了，相当于对于每一个 \(i\) 和 \(i + 1\) 的相对位置不能变，那么显然可以认为限制就是每个 \(i\) 和 \(i + 1\) 的相对位置。考虑对这个限制进行 dp，设 \(dp_{i, j}\) 表示第 \(i\) 个数排在前 \(i\) 个数中第 \(j\) 个的方案数，初始状态显然为 \(dp_{1, 1} = 1\)，答案显然为 \(\sum_i dp_{n - 1, i}\)。考虑转移，枚举 \(i - 1\) 的位置 \(k\)，若 \(i\) 应在 \(i - 1\) 的前面，应有：

若 \(i\) 应该在后面，则为：

前缀和优化即可 \(O(n ^ 2)\)。做完了。

#include 
using namespace std;
#define int ll
#define ll long long
#define usd unsigned
#define el putchar('\n')
#define lowbit(x) (x & (-x))
#define AC return 
#define AK return 0
#define YS cout << "YES"
#define NO cout << "NO"
#define Ys cout << "Yes"
#define No cout << "No"
#define ys cout << "yes"
#define no cout << "no"
#define ls(i) ch[i][0]
#define rs(i) ch[i][1]
#define debug(num) cerr << #num << ' ' << num << '\n'
#define void inline void
#define il inline
#define Mod(x) (((x) % mod + mod) % mod)
#define pii pair 
#define pll pair 
il char gc() { char c; while((c = getchar()) <= ' ') ; return c; }
il int rd() {char c; int x, f = 1;while(!isdigit(c = getchar())) if(c == '-') f *= -1;x = c ^ 48;while(isdigit(c = getchar())) x = (x << 3) + (x << 1) + (c ^ 48);return x * f;
}
void ACehomoxue();
signed main() {srand(time(0));freopen("swap.in", "r", stdin);freopen("swap.out", "w", stdout);int t = 1;// t = rd();while(t--) ACehomoxue();AK;
}
const int mod = 1e9 + 7, maxn = 3000 + 18;int n, p[maxn], pos[maxn], a[maxn], tmp[maxn], dp[maxn], sum[maxn], ans = 0;
bool vis[maxn];
vector  vec[maxn];
il int get(int l, int r) { return l ? (sum[r] - sum[l - 1] + mod) % mod : sum[r]; }void ACehomoxue() {n = rd();if(n == 1) { cout << 1; el; AC; }for(int i = 1; i <= n; i++) p[i] = rd(), pos[p[i]] = i, tmp[i] = i;int t = 0;for(int i = 1; i <= n; i++) {for(int j = i - 1; j >= pos[i]; j--) {if(vis[j]) { cout << 0; el; AC; }vis[j] = true;swap(tmp[j], tmp[j + 1]);a[++t] = j;}}for(int i = 1; i < n; i++) if((i < n && !vis[i]) || (p[i] != tmp[i])) { cout << 0; el; AC; }reverse(a + 1, a + t + 1);pos[n] = 0;for(int i = 1; i <= t; i++) pos[a[i]] = i;dp[1] = 1;for(int i = 2; i < n; i++) {sum[0] = 0;for(int j = 1; j <= i; j++) sum[j] = (sum[j - 1] + dp[j]) % mod, dp[j] = 0;for(int j = 1; j <= i; j++) {if(pos[i] > pos[i - 1]) dp[j] = get(1, j - 1);else dp[j] = get(j, i);}}for(int i = 1; i < n; i++) ans = (ans + dp[i]) % mod;cout << ans;el;
}

匹配子串

给定一个仅包含 (、) 和 ? 的字符串，其中每个 ? 可以独立替换成 ( 或 )。每次询问区间 ([L,R])，求其中有多少个子串能通过替换 ? 变成合法括号序列，每个子串只计一次。 \(\quad |s|, q \le 5 \times 10 ^ 5\)

考虑一个区间合法的冲要条件，首先显然长度应为偶数。对于每一个前缀，我们把 ? 也当作 (，那么任意前缀 ( 个数应不小于 ) 个数；对于每一个后缀，我们把每个 ? 当成 )，那么任意后缀 ) 次数不应少于 (。首先必要性显然，手玩一下可以发现这样子一定存在一个配分 ) 和 ( 给 ? 的方法使得合法，即让原来的 ( 和原来的 ) 匹配，然后再让剩下的 ( 和 ?、? 和 ) 匹配，最后对于的 ? 互相匹配。我们设 \(f_{i}\) 表示最长的 \([i, f_i]\) 能满足第一个限制，\(g_i\) 表示最长的 \([g_i, i]\) 能满足第二个性质，那么对于同奇偶的 \([l, r]\)，存在 \(r \le f_i \land g_r \ge l\) 即可合法。求出 \(f\) 和 \(g\) 可以使用单调栈。

现在考虑计算答案。我们考虑扫描线，枚举 \(r\)，设 \(c_i\) 表示以 \(c_i\) 为开头且结尾 \(\le r\) 的区间数，那么区间 \([l, r]\) 的答案显然为 \(\sum_{i \in [l, r]} c_i\)。考虑 \(t_i = 0/1\) 表示是否存在 \(f_i \ge r\)，动态维护 \(t\)。我们计算右端点为 \(r\) 的区间的贡献，对于区间 \([g_r, r]\) 内所有与 \(i\) 奇偶性不同的 \(i\)，一定有 \([i, r]\) 区间长度为偶，那么直接 \(c_i \gets c_i + t_i\) 即可。计算答案直接求和即可，用线段树维护即可做到 \(O((n + q) \log n)\)。做完了。

#include 
using namespace std;
#define int ll
#define ll long long
#define usd unsigned
#define el putchar('\n')
#define lowbit(x) (x & (-x))
#define AC return 
#define AK return 0
#define YS cout << "YES"
#define NO cout << "NO"
#define Ys cout << "Yes"
#define No cout << "No"
#define ys cout << "yes"
#define no cout << "no"
#define ls(i) ch[i][0]
#define rs(i) ch[i][1]
#define debug(num) cerr << #num << ' ' << num << '\n'
#define void inline void
#define il inline
#define Mod(x) (((x) % mod + mod) % mod)
#define pii pair 
#define pll pair 
il char gc() { char c; while((c = getchar()) <= ' ') ; return c; }
il int rd() {char c; int x, f = 1;while(!isdigit(c = getchar())) if(c == '-') f *= -1;x = c ^ 48;while(isdigit(c = getchar())) x = (x << 3) + (x << 1) + (c ^ 48);return x * f;
}
void ACehomoxue();
signed main() {srand(time(0));freopen("brackets.in", "r", stdin);freopen("brackets.out", "w", stdout);int t = 1;// t = rd();while(t--) ACehomoxue();AK;
}
const int mod = 998244353, maxn = 5 * 1e5 + 18;string s;
int n, q, ans[maxn], v[maxn], f[maxn], g[maxn];
vector  ask[maxn];
vector  stk, del[maxn];class xds {struct tree {int l, r, c0, c1, s0, s1, t0, t1;} t[maxn << 2];void mdf(int i, int x0, int x1) {t[i].s0 += t[i].c0 * x0, t[i].t0 += x0;t[i].s1 += t[i].c1 * x1, t[i].t1 += x1;}void push_up(int i) {t[i].c0 = t[i << 1].c0 + t[i << 1 | 1].c0;t[i].c1 = t[i << 1].c1 + t[i << 1 | 1].c1;t[i].s0 = t[i << 1].s0 + t[i << 1 | 1].s0;t[i].s1 = t[i << 1].s1 + t[i << 1 | 1].s1;}void push_down(int i) {mdf(i << 1, t[i].t0, t[i].t1);mdf(i << 1 | 1, t[i].t0, t[i].t1);t[i].t0 = t[i].t1 = 0;}
public:void build(int i, int l, int r) {t[i].l = l, t[i].r = r;if(l == r) AC;int mid = l + r >> 1;build(i << 1, l, mid);build(i << 1 | 1, mid + 1, r);}void updata(int i, int l, int r, int x0, int x1) {if(l > r) AC;if(t[i].l >= l && t[i].r <= r) {mdf(i, x0, x1);AC;}push_down(i);int mid = t[i].l + t[i].r >> 1;if(l <= mid) updata(i << 1, l, r, x0, x1);if(r > mid) updata(i << 1 | 1, l, r, x0, x1);push_up(i);}void modify(int i, int p, int x0, int x1) {if(t[i].l == t[i].r) { t[i].c0 = x0, t[i].c1 = x1; AC; }push_down(i);int mid = t[i].l + t[i].r >> 1;if(p <= mid) modify(i << 1, p, x0, x1);else modify(i << 1 | 1, p, x0, x1);push_up(i);}il int query(int i, int l, int r, int k0, int k1) {if(l > r) AK;if(t[i].l >= l && t[i].r <= r) return t[i].s0 * k0 + t[i].s1 * k1;push_down(i);int mid = t[i].l + t[i].r >> 1, res = 0;if(l <= mid) res += query(i << 1, l, r, k0, k1);if(r > mid) res += query(i << 1 | 1, l, r, k0, k1);return res;}
} ds;void ACehomoxue() {cin >> s;q = rd();for(int i = 1, l, r; i <= q; i++) {l = rd(), r = rd();ask[r].push_back({l, i});}n = s.length();for(int i = 1; i <= n; i++) v[i] = v[i - 1] + (s[i - 1] == ')' ? -1 : 1);v[n + 1] = -1e6;stk.push_back(n + 1);for(int i = n; i + 1; i--) {while(v[stk.back()] >= v[i]) stk.pop_back();f[i + 1] = stk.back() - 1;stk.push_back(i);}v[0] = -1e6, v[n + 1] = 0;for(int i = n; i; i--) v[i] = v[i + 1] + (s[i - 1] == '(' ? -1 : 1);stk.clear(), stk.push_back(0);for(int i = 1; i <= n + 1; i++) {while(v[stk.back()] >= v[i]) stk.pop_back();g[i - 1] = stk.back() + 1;stk.push_back(i);}ds.build(1, 1, n);for(int r = 1; r <= n; r++) {del[f[r] + 1].push_back(r);if(r & 1) ds.modify(1, r, 0, 1);else ds.modify(1, r, 1, 0);for(int i : del[r]) ds.modify(1, i, 0, 0);if(r & 1) ds.updata(1, g[r], r, 1, 0);else ds.updata(1, g[r], r, 0, 1);for(pii tmp : ask[r]) {int l = tmp.first, i = tmp.second;ans[i] = ds.query(1, l, r, 1, 1);}}for(int i = 1; i <= q; i++, el) cout << ans[i];
}