自测9 A.字符串
没有继续观察性质。或者说应该反方向考虑？
考虑一个串一定是前面和前缀相同，后面和后缀相同
于是想到 \(boder\) ，那么从每个点向其 \(boder\) 连边，每次相当于查询两个点子树内相同点的数量
对应原串上相邻的两个子串（你重命名一下）
那么考虑 \(dfn\) 序的话就是二维数点。
把 \(boder\) 换成\(SAM\) 也行。
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
int read(){
int x = 0; char c = getchar();
while(!isdigit(c))c = getchar();
do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
return x;
}
const int maxn = 2e5 + 55;
int n, q, nxt[maxn]; char s[maxn];
vector<int>t1[maxn], t2[maxn];
struct BIT{
int t[maxn];
int lowbit(int x){return x & -x;}
void add(int x){while(x <= n){++t[x]; x += lowbit(x);}}
int query(int x){int ans = 0; while(x){ans += t[x]; x -= lowbit(x);} return ans;}
int query(int l, int r){return query(r) - query(l - 1);}
void clear(){for(int i = 1; i <= n; ++i)t[i] = 0;}
}T;
int dfn[maxn], dfnr[maxn], tim;
void dfs(int x){
dfn[x] = ++tim;
for(int v : t2[x])dfs(v);
dfnr[x] = tim;
}
int ans[maxn];
vector<pii>rem[maxn];
void solve(int x){
for(pii v : rem[x])ans[v.second] -= T.query(dfn[v.first], dfnr[v.first]);
if(x && x != n)T.add(dfn[x + 1]);
for(int v : t1[x])solve(v);
for(pii v : rem[x])ans[v.second] += T.query(dfn[v.first], dfnr[v.first]);
}
void solve(){
n = read(), q = read(); scanf("%s",s + 1);
nxt[1] = 0; t1[0].push_back(1);
for(int i = 2, j = 0; i <= n; ++i){
while(j && s[j + 1] != s[i])j = nxt[j];
if(s[j + 1] == s[i])++j;
nxt[i] = j; t1[nxt[i]].push_back(i);
}
nxt[n] = n + 1; t2[n + 1].push_back(n);
for(int i = n - 1, j = n + 1; i >= 1; --i){
while(j != n + 1 && s[j - 1] != s[i])j = nxt[j];
if(s[j - 1] == s[i])--j;
nxt[i] = j; t2[nxt[i]].push_back(i);
}
tim = -1; dfs(n + 1);
for(int i = 1; i <= q; ++i){
int x = read(), y = read();
if(x + y <= n)rem[x].push_back(pii(n - y + 1, i));
}
solve(0);
for(int i = 1; i <= q; ++i)printf("%d\n",ans[i]);
for(int i = 1; i <= q; ++i)ans[i] = 0;
for(int i = 0; i <= n + 1; ++i)t1[i].clear(), t2[i].clear();
for(int i = 0; i <= n + 1; ++i)rem[i].clear();
T.clear();
}
int main(){
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
int T = read(); for(int i = 1; i <= T; ++i)solve();
return 0;
}
自测9 B. 计树
问题在树上，所以肯定要树上 \(DP\)，考虑如何去计算答案
一种做法是考虑计算出每棵子树的答案，合并子树时也合并贡献
那么我们就需要知道子树内每个点在子树内的排名，于是可以这样设计\(DP\) 状态
\(f_{x, a, b}\) 表示在以 \(x\) 为根的子树内，节点 \(a\) 在子树内排名为 \(b\) 的方案数
令\(g_{x} = f_{x, x, 1}\) 表示 \(x\) 子树内的总方案数
使用 \(vector\) 记录子树内所有点
考虑计算新的答案，原先子树内的答案乘上另一棵子树的方案数，和分配排名的组合数（注意答案钦定了某两个点相邻，只要给他们分配一个排名）
对于两棵子树之间的贡献，枚举点和其排名，强制枚举到的点在新排名中相邻，前后用组合数计算
考虑转移 \(f_{x, a, b}\) 枚举 \(a, b\) 枚举另一棵子树有多少点排在 \(a\) 前面，进行转移。
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
int read(){
int x = 0; char c = getchar();
while(!isdigit(c))c = getchar();
do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
return x;
}
const int maxn = 205, mod = 1e9 + 7;
int n, rt, si[maxn], g[maxn], ans[maxn], tmp[maxn], f[maxn][maxn][maxn], c[maxn][maxn];
vector<int>e[maxn], ver[maxn];
void solve(int x, int fa){
si[x] = g[x] = 1;
for(int v : e[x])if(v != fa)solve(v, x);
for(int v : e[x])if(v != fa){
int sum = 1ll * g[x] * f[v][v][1] % mod * c[si[x] + si[v] - 2][si[v] - 1] % mod * abs(x - v) % mod;
for(int p : ver[x]){
for(int i = 1; i <= si[v]; ++i){
int tmp = 0;
for(int q : ver[v])tmp = (tmp + 1ll * abs(p - q) * f[v][q][i]) % mod;
if(tmp){
int val = 0;
for(int j = 1; j <= si[x]; ++j)if(f[x][p][j])
val = (val + 1ll * f[x][p][j] * c[i - 1 + j - 2][i - 1] % mod * c[si[x] + si[v] - i - j][si[x] - j]) % mod;
sum = (sum + 2ll * val * tmp) % mod;
}
}
}
for(int p : ver[x]){
for(int i = 2; i <= si[x]; ++i)if(f[x][p][i])
for(int j = 0; j <= si[v]; ++j)
tmp[i + j] = (tmp[i + j] + 1ll * f[x][p][i] * c[i - 2 + j][j] % mod * c[si[x] + si[v] - i - j][si[x] - i]) % mod;
for(int i = 1; i <= si[x] + si[v]; ++i)f[x][p][i] = 1ll * g[v] * tmp[i] % mod, tmp[i] = 0;
}
for(int p : ver[v]){
for(int i = 1; i <= si[v]; ++i)if(f[v][p][i])
for(int j = 1; j <= si[x]; ++j)
tmp[i + j] = (tmp[i + j] + 1ll * f[v][p][i] * c[i - 2 + j][i - 1] % mod * c[si[x] + si[v] - i - j][si[x] - j]) % mod;
for(int i = 1; i <= si[x] + si[v]; ++i)f[x][p][i] = 1ll * g[x] * tmp[i] % mod, tmp[i] = 0;
}
for(int p : ver[v])ver[x].push_back(p); ver[v].clear();
si[x] += si[v];
ans[x] = (1ll * ans[x] * g[v] % mod * c[si[x] - 2][si[v]] + 1ll * ans[v] * g[x] % mod * c[si[x] - 2][si[v] - 1] + sum) % mod;
g[x] = 1ll * g[x] * g[v] % mod * c[si[x] - 1][si[v]] % mod;
}
f[x][x][1] = g[x]; ver[x].push_back(x);
}
int main(){
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
for(int i = 0; i <= 200; ++i){
c[i][0] = 1;
for(int j = 1; j <= i; ++j)c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
}
n = read(), rt = read();
for(int i = 1; i < n; ++i){
int u = read(), v = read();
e[u].push_back(v); e[v].push_back(u);
}
solve(rt, 0);
printf("%d\n",ans[rt]);
return 0;
}
2023冲刺国赛模拟32 A. 树
考虑容斥进行计算，枚举 \(1\) 所在的连通块进行容斥， \(f_{s, i}\) 表示当前与 \(1\) 联通的集合为 \(s\)， 内部连了 \(i\) 条边的方案数。
用 \(cnt_s\) 表示 \(s\) 集合内的边的数量。
\[
f_{s, i} = \binom{cnt_s}{i} - \sum_{t\subset s \and 1 \in t}\sum_{j = 0}^{min(i, cnt_t)}\binom{cnt_{s \oplus t}}{i - j}f_{t, j}
\]
看成多项式
\[
F_{s} = (1 + x)^{cnt_s} - \sum_{t\subset s \and 1 \in t}(1 + x)^{cnt_{s \oplus t}}F_{t}
\]
设 \(y = 1 + x\)
那么转移是简单的，最后带入即可。
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
int read(){
int x = 0; char c = getchar();
while(!isdigit(c))c = getchar();
do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
return x;
}
const int mod = 1e9 + 7, maxn = 16;
int n, m, cz, mp[maxn][maxn], cnt[1 << 15];
int f[1 << 15][205], c[205][205], ans[205];
int main(){
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
n = read(), m = read();
for(int i = 1; i <= m; ++i){
int u = read(), v = read();
++cnt[(1 << u) | (1 << v)];
}
for(int i = 0; i <= m; ++i){
c[i][0] = 1;
for(int j = 1; j <= i; ++j)c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
}
for(int hl = 1, l = 2; l <= (1 << n); l <<= 1, hl <<= 1)
for(int i = 0; i < (1 << n); i += l)
for(int j = i; j < i + hl; ++j)
cnt[j + hl] += cnt[j];
for(int s = 1; s < (1 << n); s += 2){
f[s][cnt[s]] = 1;
for(int t = (s - 1) & s; t; t = (t - 1) & s)if(t & 1)
for(int j = 0; j <= cnt[t]; ++j)
(f[s][j + cnt[s ^ t]] -= f[t][j]) %= mod;
for(int i = 0; i <= cnt[s]; ++i)if(f[s][i] < 0)f[s][i] += mod;
}
int S = (1 << n) - 1;
for(int i = n - 1; i <= m; ++i)
for(int j = i; j <= m; ++j)
ans[i] = (ans[i] + 1ll * c[j][i] * f[S][j]) % mod;
for(int i = n - 1; i <= m; ++i)printf("%d ",ans[i]); printf("\n");
return 0;
}
2023冲刺国赛模拟32 B. 差
考虑设 \(c_i = a_{i + 1} - a{i}\)
那么 \(b_{i} = max(| c_{i} |,| c_{i + 1}|,|c_{i} +c_{i +1}|)\)
设 \(f_{i, x}\) 表示考虑完前 \(i\) 项， \(c_{i} = x\) 是否合法
转移时保留 \(0 \leq x \leq b_i\)
然后三种转移
\(x \to b_i - x\) 对应 \(max\) 取到第三项
\(b_i \to [0, b_i]\) 取到第一项
\(x \to b_i\) 取到第二项
发现需要维护一个区间和若干单点，支持删除前后缀，翻转，平移，区间只有一个可以直接维护，单点使用双端队列维护
记录每次删去的部分，构造方案时反过来倒推。
代码没写。
2023冲刺国赛自测10
暴力老哥的阶段性胜利
A. 硬币序列
\(f_{i, j, 0 / 1}\) 表示前 \(i\) 个位置，已经用了 \(j\) 个 \(0\) 最后一段是 \(0 / 1\) 的最短长度
二分答案可以做到 \(n^2log\)
既然已经二分答案了，那么记录最短长度看起来就比较多余？
变成枚举这次填的连续段长度，
然后变成\(f_{i, 1 / 0}\) 表示考虑前 \(i\) 个位置，最后一段是 \(1 / 0\) 填的 \(0\) 的个数的合法范围，大胆猜测是一个区间，于是变成维护最大最小值
可以使用单调队列进行优化。
构造方案考虑倒着扫，找到一个当前合法的段就填。
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
int read(){
int x = 0; char c = getchar();
while(!isdigit(c))c = getchar();
do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
return x;
}
const int maxn = 1e5 + 55, inf = 0x3f3f3f3f;
char s[maxn];
int T, type, n, a, b, sum[maxn];
void ckmi(int &x, int y){if(x > y)x = y;}
int f[maxn][2];
deque<int>q0, q1;
void trans(int len){
for(int i = 1; i <= n; ++i)f[i][0] = f[i][1] = inf;
q0.push_back(0); q1.push_back(0);
for(int i = 1; i <= n; ++i){
while(q0.size() && i - q0.front() > len)q0.pop_front();
while(q1.size() && i - q1.front() > len)q1.pop_front();
if(s[i] != '0' && q0.size())f[i][1] = f[q0.front()][0];
if(s[i] != '1' && q1.size())f[i][0] = f[q1.front()][1] + sum[i] - sum[q1.front()];
if(s[i] == '0')q0.clear(), f[i][1] = inf; if(s[i] == '1')q1.clear(), f[i][0] = inf;
if(f[i][0] != inf){
while(q0.size() && f[q0.back()][0] > f[i][0])q0.pop_back();
q0.push_back(i);
}
if(f[i][1] != inf){
while(q1.size() && f[q1.back()][1] - sum[q1.back()] > f[i][1] - sum[i])q1.pop_back();
q1.push_back(i);
}
}
q0.clear(); q1.clear();
}
void rev(){for(int i = 1; i <= n; ++i)if(s[i] != '?')s[i] = '0' + '1' - s[i];}
bool check(int len){
trans(len); if(f[n][0] > a && f[n][1] > a)return false;
rev(); trans(len); rev();
if(f[n][0] > b && f[n][1] > b)return false;
return true;
}
int mi[maxn][2], mx[maxn][2];
void print(int len){
trans(len);
for(int i = 1; i <= n; ++i)mi[i][0] = f[i][0], mi[i][1] = f[i][1];
rev(); trans(len); rev();
for(int i = 1; i <= n; ++i)mx[i][0] = sum[i] - f[i][1], mx[i][1] = sum[i] - f[i][0];
int r = n, v = 1, res = a;
if(mi[n][0] <= a && mx[n][0] >= a)v = 0;
while(r){
if(v){
for(int l = r - 1; l >= 0; --l)if(mi[l][0] <= res && mx[l][0] >= res){
for(int i = l + 1; i <= r; ++i)s[i] = '1';
r = l; break;
}
}else{
for(int l = r - 1; l >= 0; --l)if(mi[l][1] <= res - sum[r] + sum[l] && mx[l][1] >= res - sum[r] + sum[l]){
for(int i = l + 1; i <= r; ++i)s[i] = '0';
res = res - sum[r] + sum[l]; r = l; break;
}
}
v ^= 1;
}
for(int i = 1; i <= n; ++i)printf("%c",s[i]); printf("\n");
}
void solve(){
n = read(), a = read(), b = read();
scanf("%s",s + 1);
for(int i = 1; i <= n; ++i)sum[i] = sum[i - 1] + (s[i] == '?');
int len = 0, l = 0, c0 = 0;
for(int i = 1; i <= n; ++i)
if(s[i] == '?')len = 0;
else{
if(s[i] == s[i - 1])++len;
else len = 1;
l = max(l, len);
}
int r = max(c0, n - c0), ans = r;
while(l <= r){
int mid = (l + r) >> 1;
if(check(mid))r = mid - 1, ans = mid;
else l = mid + 1;
}
printf("%d\n",ans);
if(type)print(ans);
}
int main(){
freopen("coin.in","r",stdin);
freopen("coin.out","w",stdout);
T = read(), type = read();
for(int i = 1; i <= T; ++i)solve();
return 0;
}
B. 划分线段
线段的关系是一个树形结构，考虑进行树形 \(DP\)
\(f_{x, y, 0 / 1, 0 / 1}\) 表示考虑 \(x\) 子树，需要其祖先在里面选 \(y\) 个区间，左端/右端是否需要祖先选择的贡献
贡献预先统计好，
考虑到一棵树最多填 \(2size - 1\) 个区间，所以 \(y\) 只枚举到 \(size_x\) 树形背包是 \(n^2\) 的
一种好写的做法是，离散化值域，对线段按照长度排序，每次处理完一个线段在左端点位置记录线段编号
这样一个线段的儿子就是从左往右扫区间，扫到一个线段记为儿子，然后跳到右端点继续。
转移先把每个儿子左侧的段给儿子，然后背包拼接，最后把最右侧的段加上。
需要注意第一个儿子的值应该直接赋给当前点
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
int read(){
int x = 0; char c = getchar();
while(!isdigit(c))c = getchar();
do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
return x;
}
const int maxn = 5005;
int n, l[maxn], r[maxn], tmp[maxn + maxn], m, p[maxn], id[maxn + maxn];
bool cmp(const int &x, const int &y){return r[x] - l[x] < r[y] - l[y];}
int f[maxn][maxn][2][2], tl[maxn], si[maxn], g[maxn][2][2];
void ckmx(int &x, int y){if(y > x)x = y;}
void calc(int now){
int las = tmp[l[now]];
vector<int>rem;
for(int i = l[now]; i < r[now]; ++i)if(id[i]){
tl[id[i]] = tmp[l[id[i]]] - las; las = tmp[r[id[i]]];
rem.push_back(id[i]); i = r[id[i]];
}
si[now] = 1;
if(rem.empty())f[now][0][0][0] = tmp[r[now]] - tmp[l[now]];
else{
bool flag = true;
for(int v : rem){
for(int i = si[v] - 1; i >= 0; --i){
f[v][i][1][0] += tl[v];
f[v][i][1][1] += tl[v];
ckmx(f[v][i + 1][1][0], f[v][i][0][0] + tl[v]);
ckmx(f[v][i + 1][1][1], f[v][i][0][1] + tl[v]);
}
if(flag){
for(int j = 0; j <= si[v]; ++j)for(int a = 0; a <= 1; ++a)for(int b = 0; b <= 1; ++b)if(a + b <= j)f[now][j][a][b] = f[v][j][a][b];
si[now] += si[v]; flag = false;
}else{
for(int i = 0; i < si[now]; ++i)for(int p = 0; p <= 1; ++p)for(int q = 0; q <= 1; ++q)if(p + q <= i)
for(int j = 0; j <= si[v]; ++j)for(int a = 0; a <= 1; ++a)for(int b = 0; b <= 1; ++b)if(a + b <= j)
ckmx(g[i + j - (q && a)][p][b], f[now][i][p][q] + f[v][j][a][b]);
si[now] += si[v];
for(int i = 0; i < si[now]; ++i)for(int p = 0; p <= 1; ++p)for(int q = 0; q <= 1; ++q)f[now][i][p][q] = g[i][p][q], g[i][p][q] = 0;
}
}
int tr = tmp[r[now]] - las;
for(int i = si[now] - 1; i >= 0; --i)for(int p = 0; p <= 1; ++p)for(int q = 0; q <= 1; ++q)
if(q)f[now][i][p][q] += tr; else ckmx(f[now][i + 1][p][1], f[now][i][p][q] + tr);
for(int i = 0; i < si[now]; ++i)for(int p = 0; p <= 1; ++p)for(int q = 0; q <= 1; ++q){
ckmx(f[now][i][p][q], f[now][i + 1][p][q]);
if(!p)ckmx(f[now][i][p][q], f[now][i + 1][1][q]);
if(!q)ckmx(f[now][i][p][q], f[now][i + 1][p][1]);
if(p + q > i)f[now][i][p][q] = 0;
}
f[now][si[now]][0][0] = f[now][si[now]][1][0] = f[now][si[now]][0][1] = f[now][si[now]][1][1] = 0;
}
id[l[now]] = now;
}
int get_ans(){
int ans = 0;
for(int i = 1; i <= m; ++i)if(id[i]){ans += f[id[i]][0][0][0]; i = r[id[i]];}
return ans;
}
int main(){
freopen("segment.in","r",stdin);
freopen("segment.out","w",stdout);
n = read();
for(int i = 1; i <= n; ++i)l[i] = read(), r[i] = read();
if(n == 1){printf("%d\n",r[1] - l[1]); return 0;}
for(int i = 1; i <= n; ++i)tmp[++m] = l[i], tmp[++m] = r[i];
sort(tmp + 1, tmp + m + 1); m = unique(tmp + 1, tmp + m + 1) - tmp - 1;
for(int i = 1; i <= n; ++i)l[i] = lower_bound(tmp + 1, tmp + m + 1, l[i]) - tmp, r[i] = lower_bound(tmp + 1, tmp + m + 1, r[i]) - tmp;
for(int i = 1; i <= n; ++i)p[i] = i;
sort(p + 1, p + n + 1, cmp);
for(int i = 1; i <= n; ++i)calc(p[i]);
printf("%d\n",get_ans());
return 0;
}