杂项
CF1181E2 A Story of One Country (Hard)
启发式分裂
发现如果当前矩形中有一整行或一整列没有穿过城堡内部，就可以分为 \(2\) 部分
而且分开后相当于限制减少，每次贪心的能分就分，朴素实现复杂度为 \(O(n^2\log n)\)，可通过 easy version
考虑优化每次找分割点的过程
如果分割点靠近两侧，则扫了较长的一边不优，在二维平面上中途相遇
维护分别按上，下，左，右排序矩形的 set，然后同步找，直到某个方向上找到分割点
由于找的长度不会超过当前矩形边长的一半，复杂度分析同启发式合并，每次分割边长至少减半
struct rect // (a, b) (c, d)
{
int a, b, c, d;
}p[N];
struct cmp4
{
bool operator ()(const rect &x, const rect &y) {return x.a != y.a ? x.a < y.a : x.b < y.b;}
};
struct cmp3
{
bool operator ()(const rect &x, const rect &y) {return x.c != y.c ? x.c > y.c : x.d > y.d;}
};
struct cmp2
{
bool operator ()(const rect &x, const rect &y) {return x.d != y.d ? x.d > y.d : x.c > y.c;}
};
struct cmp1
{
bool operator ()(const rect &x, const rect &y) {return x.b != y.b ? x.b < y.b : x.a < y.a;}
};
int n;
int work(set<rect, cmp1> &nl, set<rect, cmp2> &nr, set<rect, cmp3> &nu, set<rect, cmp4> &nd, int num)
{
if(num == 1) return 1;
iter1 it1 = nl.begin(); iter2 it2 = nr.begin(); iter3 it3 = nu.begin(); iter4 it4 = nd.begin();
int maxr = nl.begin() -> d, minl = nr.begin() -> b, mind = nu.begin() -> a, maxu = nd.begin() -> c;
set<rect, cmp1> pl; set<rect, cmp2> pr; set<rect, cmp3> pu; set<rect, cmp4> pd;
for(int i = 2; i <= num; ++i)
{
maxr = max(maxr, it1 -> d), ++it1;
if(maxr <= it1 -> b)
{
for(iter1 it = nl.begin(); it != it1; ++it)
nr.erase(*it), nu.erase(*it), nd.erase(*it), pr.insert(*it), pu.insert(*it), pd.insert(*it);
pl.insert(nl.begin(), it1), nl.erase(nl.begin(), it1);
return work(nl, nr, nu, nd, num - i + 1) && work(pl, pr, pu, pd, i - 1);
}
minl = min(minl, it2 -> b), ++it2;
if(minl >= it2 -> d)
{
for(iter2 it = nr.begin(); it != it2; ++it)
nl.erase(*it), nu.erase(*it), nd.erase(*it), pl.insert(*it), pu.insert(*it), pd.insert(*it);
pr.insert(nr.begin(), it2), nr.erase(nr.begin(), it2);
return work(nl, nr, nu, nd, num - i + 1) && work(pl, pr, pu, pd, i - 1);
}
mind = min(mind, it3 -> a), ++it3;
if(mind >= it3 -> c)
{
for(iter3 it = nu.begin(); it != it3; ++it)
nl.erase(*it), nr.erase(*it), nd.erase(*it), pl.insert(*it), pr.insert(*it), pd.insert(*it);
pu.insert(nu.begin(), it3), nu.erase(nu.begin(), it3);
return work(nl, nr, nu, nd, num - i + 1) && work(pl, pr, pu, pd, i - 1);
}
maxu = max(maxu, it4 -> c), ++it4;
if(maxu <= it4 -> a)
{
for(iter4 it = nd.begin(); it != it4; ++it)
nl.erase(*it), nr.erase(*it), nu.erase(*it), pl.insert(*it), pr.insert(*it), pu.insert(*it);
pd.insert(nd.begin(), it4), nd.erase(nd.begin(), it4);
return work(nl, nr, nu, nd, num - i + 1) && work(pl, pr, pu, pd, i - 1);
}
}
return 0;
}
int main()
{
read(n);
set<rect, cmp1> lef; set<rect, cmp2> rit; set<rect, cmp3> up; set<rect, cmp4> down;
for(int i = 1; i <= n; ++i)
{
read(p[i].a, p[i].b, p[i].c, p[i].d);
lef.insert(p[i]), rit.insert(p[i]), up.insert(p[i]), down.insert(p[i]);
}
if(work(lef, rit, up, down, n)) puts("Yes");
else puts("No");
return 0;
}
CF925C Big Secret
大胆猜想，小心求证
建图之类的是行不通的，那这个问题其实没什么好的性质
有用的是若 \(x\operatorname{xor} y>x\)，则 \(y\) 二进制下最高那位在 \(x\) 中为 \(0\)
猜当前异或和从小到大找为 \(0\) 位，若还有最高位是此位的数就直接摆，这样就是对的！
证明其实比较复杂，主要证明这样不会把有解判为无解
考虑第 \(w\) 位，设最高位为 \(w\) 的数有 \(x\) 个，剩下数中第 \(w\) 位是 \(1\) 的数有 \(y\) 个，当前更高位的限制已经满足
最高位为 \(w\) 的数必须放在当前前缀异或和第 \(w\) 位为 \(0\) 的位置后面，即前缀中有偶数个 \(w\) 位为 \(1\) 的数
所以这 \(x\) 个数先在开头放一个，之后最多只能紧接着放在 \(y\) 个数的后面
剩下的位是不重要的，现在的摆放只跟单个数有关，摆放顺序不会影响解
若 \(x>y+1\)，则无解，否则每次插在前 \(x\) 个第二种数后面
这样 \(w\) 从大到小模拟已经可以做出来了，但还有更简洁的实现吗？
观察按顺序摆的序列，每次放时其实都符合上面的约束
上面已经说明了最高位相同的数的顺序不重要
因此直接摆不会漏掉有解情况
int main()
{
read(n);
for(ll i = 1; i <= n; ++i) read(a[i]), grp[(ll)floor(__lg(a[i]))].pb(a[i]);
for(ll i = 60; i >= 0; --i)
if(grp[i].size()) {mx = i; break;}
for(ll i = 1; i <= n; ++i)
{
ll flag = 0;
for(ll j = 0; j <= mx; ++j)
if(!((tot >> j) & 1) && grp[j].size())
{
flag = 1, tot ^= grp[j].back();
ans.pb(grp[j].back()), grp[j].pop_back();
break;
}
if(!flag) {puts("No"); return 0;}
}
puts("Yes");
for(ll i : ans) print(i), putchar(' ');
}
CF842E Nikita and game
注意结论：所有直径均交于一点，也就是树的中心，到一个点距离最远的点必然是直径的端点之一
考虑加入一个叶子，直径长度最多 \(+1\)
可以把端点划分为 \(2\) 个集合，移动树的中心
但我有个不太一样的解法：
注意到，某个点一旦不是直径的端点，它再无法成为直径端点
假设树的中心是根，那么只有叶子才可能是端点，如果某时刻它从端点变成了非端点，说明它不是叶子或它所在链比别的短，不是叶子肯定不是端点，链比别的短由于是加叶子所以也无法再变长
统计每个点对答案的贡献，即什么时候它是直径端点
可以算出每个时刻的直径长度和端点
根据上面的结论可以二分它最后为端点的时刻，判断当前直径的两个端点到它的距离是否等于直径长度
（这个点到这两个端点的路径必定不会经过后面加入的点）
用差分统计即可
void dfs(int x)
{
rmq[++cnt][0] = fa[x], dfn[x] = cnt, dep[x] = dep[fa[x]] + 1;
for(int y : edge[x]) dfs(y);
}
int getlca(int x, int y)
{
if(x == y) return x;
if(dfn[x] > dfn[y]) swap(x, y);
int v = __lg(dfn[y] - dfn[x]); x = rmq[dfn[x] + 1][v], y = rmq[dfn[y] - (1 << v) + 1][v];
return (dfn[x] < dfn[y]) ? x : y;
}
int dist(int x, int y) {return dep[x] + dep[y] - 2 * dep[getlca(x, y)];}
int merge(int val, int x)
{
int l = max(2, x), r = n;
while(l < r)
{
int mid = (l + r + 1) >> 1;
if(max(dist(x, d1[mid]), dist(x, d2[mid])) < sum[mid]) r = mid - 1;
else l = mid;
}
return l;
}
int main()
{
read(n), ++n;
for(int i = 2; i <= n; ++i) read(fa[i]), edge[fa[i]].pb(i);
dfs(1);
for(int j = 1; j <= 18; ++j)
for(int i = 1; i + (1 << j) - 1 <= n; ++i)
{
int ln = rmq[i][j - 1], rn = rmq[i + (1 << (j - 1))][j - 1];
rmq[i][j] = (dfn[ln] < dfn[rn]) ? ln : rn;
}
sum[2] = mx = 1, d1[2] = 1, d2[2] = 2;
for(int i = 3; i <= n; ++i)
{
d1[i] = d1[i - 1], d2[i] = d2[i - 1];
int dis1 = dist(d1[i], i), dis2 = dist(d2[i], i);
sum[i] = max({sum[i - 1], dis1, dis2});
if(dis1 >= mx || dis2 >= mx)
{
if(dis1 > mx)
mx = dis1, d2[i] = i;
else if(dis2 > mx)
mx = dis2, d1[i] = i;
}
else book[i] = 1;
}
for(int i = 1; i <= n; ++i)
{
if(book[i]) continue;
int p = merge(dis[i], i);
if(p >= i) ++ans[i], --ans[p + 1];
}
for(int i = 1; i <= n; ++i) ans[i] += ans[i - 1];
for(int i = 2; i <= n; ++i) print(ans[i]), putchar('\n');
return 0;
}
DP
CF461E Appleman and a Game
首先有显然的结论是 Appleman 每次一定会放当前能放的最长的子串
所以考虑找出 \(t\) 中没有的子串，长度越短越好，这样 Appleman 一次放的长度小
而且这样的串长度 \(\le 9\)，因为 \(4^9>n\)，已经不可能出现长度为 \(9\) 的所有串，长度更长没有意义
直接暴力枚举就好了
拼接需要首尾相接，即前一个串的末尾必须等于后一个串的开头才能有效的卡住 Appleman
我于是想着建图之后怎么找出所有的环，然后发现边界问题一大堆……
其实题目暗含了最小值最大，二分答案，判定 \(x\) 步内拼成的最短长度是否 \(\le n\)
设 \(f(x,i,j)\) 表示拼了 \(x\) 步，第一个拼的串开头为 \(i\)，最后一步拼的串末尾为 \(j\)
边界就是 \(f(1,i,j)\)，为开头为 \(i\)，末尾为 \(j\) 且不在 \(t\) 中出现过的长度最小的串长度 \(-1\)（因为 Appleman 不能放 \(j\)）
转移为 \(f(x+1,i,j)=\min\{f(x,i,k)+f(1,k,j)\}\)
可以用矩阵快速幂优化，由于转移矩阵均为 \(f(1)\)，也可以直接倍增
注意特判最后的边界：最后虽然 Appleman 拼哪个串长度都 \(>n\)，但如果不拼长度就 \(<n\)，即末尾有剩余，步数应 \(+1\)
const ll N = 100010, inf = 1e18;
ll n, m, ans, len[N];
vector<ll> edge[N];
string t, nw;
map<string, ll> str[10];
struct matrix
{
ll a[4][4];
matrix() {memset(a, 0x3f, sizeof(a));}
}f[2], pw[70];
matrix operator*(const matrix &x, const matrix &y)
{
matrix res;
for(ll i = 0; i < 4; ++i)
for(ll k = 0; k < 4; ++k)
if(x.a[i][k] < inf)
for(ll j = 0; j < 4; ++j) res.a[i][j] = min(res.a[i][j], x.a[i][k] + y.a[k][j]);
return res;
}
void dfs(ll x)
{
if(x > 9) return;
if(x > 2)
{
if(str[x - 1].find(nw) == str[x - 1].end())
f[1].a[nw[0] - 'A'][nw.back() - 'A'] = min(f[1].a[nw[0] - 'A'][nw.back() - 'A'], x - 2);
}
for(ll i = 1; i <= 4; ++i)
{
nw.pb('A' + i - 1);
dfs(x + 1);
nw.pop_back();
}
}
int main()
{
cin >> n >> t, m = t.length();
for(ll i = 1; i <= 9; ++i)
{
for(ll j = 0; j + i - 1 < m; ++j)
str[i][t.substr(j, i)] = 1;
}
dfs(1);
pw[0] = f[1], f[0].a[0][0] = f[0].a[1][1] = f[0].a[2][2] = f[0].a[3][3] = 0;
for(ll i = 1; i <= 60; ++i) pw[i] = pw[i - 1] * pw[i - 1];
for(ll i = 60; i >= 0; --i)
{
matrix nw = f[0] * pw[i]; ll tot = inf * 2;
for(ll j = 0; j < 4; ++j)
for(ll k = 0; k < 4; ++k) tot = min(tot, nw.a[j][k]);
if(tot <= n) ans += (1ll << i), f[0] = nw;
}
ll tot = inf * 2;
for(ll j = 0; j < 4; ++j)
for(ll k = 0; k < 4; ++k) tot = min(tot, f[0].a[j][k]);
printf("%lld", ans + ((tot < n) ? 1 : 0));
return 0;
}
CF494C Helping People
注意区间没有交，启发我们可以根据区间的包含关系建树
为方便增加 \([1,n]\) 的区间，它增加的概率为 \(0\)
而且最大值只能增加 \(O(q)\) 次，可以直接 DP 最大值增加 \(i\) 次的概率
但「恰好 \(x\) 次」还是不好处理，考虑容斥，设 \(f(x,i)\) 为 \(x\) 代表区间中最大值至多增加 \(i\) 的概率
预处理出每个区间内原来的最大值 \(mx\)，考虑合并子树 \(y\)
若 \(x\) 区间不 \(+1\)，它增加次数 \(\le mx_x+i-mx_y\)，否则 \(\le mx_x+i+1-mx_y\)
树形 DP，复杂度为 \(O(n\log n+q^2)\)
void dfs(int x)
{
siz[x] = 1;
for(int y : edge[x])
dfs(y), siz[x] += siz[y];
for(int i = 0; i <= q; ++i) tmp1[i] = tmp2[i] = 1;
tmp2[0] = 0;
for(int y : edge[x])
{
for(int i = q; i >= 0; --i)
{
if(mx[x] + i - mx[y] <= q) tmp1[i] = tmp1[i] * f[y][mx[x] + i - mx[y]];
if(i && mx[x] - mx[y] + i - 1 <= q) tmp2[i] = tmp2[i] * f[y][mx[x] - mx[y] + i - 1];
}
}
for(int i = q; i >= 0; --i)
f[x][i] = tmp1[i] * (1 - lin[x].pr) + tmp2[i] * lin[x].pr;
}
int main()
{
cin >> n >> q;
for(int i = 1; i <= n; ++i) cin >> a[i], rmq[i][0] = a[i];
for(int i = 1; i <= q; ++i) cin >> lin[i].l >> lin[i].r >> lin[i].pr;
sort(lin + 1, lin + q + 1);
for(int i = 1; i <= q; ++i) lin[i].id = i;
lin[0].l = 1, lin[0].r = n, lin[0].pr = 0, lin[0].id = 0;
for(int i = 1; i <= q; ++i) seg[lin[i].l].pb(lin[i]), del[lin[i].r + 1].pb(lin[i]);
for(int i = 1; i <= n; ++i)
{
for(segm j : del[i]) --top;
for(segm j : seg[i]) fa[j.id] = stk[top], edge[stk[top]].pb(j.id), stk[++top] = j.id;
}
for(int j = 1; j <= 17; ++j)
for(int i = 1; i + (1 << j) - 1 <= n; ++i) rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
for(int i = 0; i <= q; ++i)
{
int v = __lg(lin[i].r - lin[i].l + 1);
mx[i] = max(rmq[lin[i].l][v], rmq[lin[i].r - (1 << v) + 1][v]);
}
dfs(0), ans += f[0][0] * mx[0];
for(int i = 1; i <= q; ++i) ans += (f[0][i] - f[0][i - 1]) * (mx[0] + i);
printf("%.8f", ans);
return 0;
}
CF1168D Anagram Paths
DP 神题
先考虑什么时候无解
首先如果叶子到根的距离不相等一定无解
发现那些有两个儿子的节点比较重要，它下方两棵子树此时必须已经满足条件，因为它上方到根的路径相同了
一个字符 \(c\) 至少要出现的次数是到叶子的链中出现次数的最大值
所以设 \(f(x,c)\) 表示子树 \(x\) 内 \(c\) 在路径中出现次数的最大值
若在任意 \(x\) 处 \(\sum_{c}f(x,c)\ge len_x\)，则无解
而剩下的 \(?\) 可以随便选，为了使目标字符最多，就直接全部放目标字符
现在还要支持单点修改
修改某个点的值，会影响它到根节点处所有节点的 \(f\) 数组
可以用树剖维护动态 DP，能扩展至多叉树，但是这题为二叉树，有更特殊的性质
考虑真正产生合并的只有有两个儿子的节点，我们可以把单链缩成一个点，由于每个叶子深度相同，而且新树大小为 \(O(n)\) 且非叶子均有 \(2\) 个子节点，树高只有 \(O(\sqrt n)\)
因此可以直接暴力修改
void Dfs(int x)
{
if(!edge[x].size()) len[x] = 1;
for(int y : edge[x])
{
dep[y] = dep[x] + 1, Dfs(y);
len[x] = len[y] + 1;
}
maxdep = max(maxdep, dep[x]);
}
void dfs(int x, int las)
{
stk.pb(x);
if(book[x])
{
fa[x] = las, tree[las].pb(x);
for(int y : stk) fr[y] = x;
stk.clear(), las = x;
}
for(int y : edge[x]) dfs(y, las);
}
void calc(int x)
{
for(int y : tree[x])
{
calc(y);
for(int i = 0; i < 26; ++i) f[x][i] = max(f[x][i], f[y][i] + sum[y][i]);
}
int tot = 0;
for(int i = 0; i < 26; ++i) tot += f[x][i];
if(tot > len[x] - 1) ++num, ok[x] = 1;
}
void update(int x)
{
if(ok[x]) ok[x] = 0, --num;
for(int i = 0; i < 26; ++i) f[x][i] = 0;
for(int y : tree[x])
for(int i = 0; i < 26; ++i) f[x][i] = max(f[x][i], f[y][i] + sum[y][i]);
int tot = 0;
for(int i = 0; i < 26; ++i) tot += f[x][i];
if(tot > len[x] - 1) ok[x] = 1, ++num;
if(fa[x]) update(fa[x]);
}
void mian()
{
ios::sync_with_stdio(false), cin.tie(0);
cin >> n >> q;
for(int i = 2; i <= n; ++i) cin >> u >> ch[i], edge[u].pb(i);
for(int i = 1; i <= n; ++i)
if(edge[i].size() != 1 || i == 1) book[i] = 1;
Dfs(1);
for(int i = 2; i <= n; ++i)
if(!edge[i].size() && dep[i] != maxdep)
{
while(q--) puts("Fou");
return;
}
dfs(1, 0);
for(int i = 2; i <= n; ++i)
if(ch[i] != '?') ++sum[fr[i]][ch[i] - 'a'];
calc(1);
while(q--)
{
cin >> u >> op;
if(op != ch[u])
{
if(ch[u] != '?') --sum[fr[u]][ch[u] - 'a'];
if(op != '?') ++sum[fr[u]][op - 'a'];
ch[u] = op;
}
update(fa[fr[u]]), ans = res = 0;
if(num) {puts("Fou"); continue;}
for(int i = 0; i < 26; ++i) res += f[1][i] + sum[1][i];
for(int i = 1; i <= 26; ++i) ans += (len[1] - 1 - res + f[1][i - 1] + sum[1][i - 1]) * i;
printf("Shi %d\n", ans);
}
}
CF573D Bear and Cavalry
考虑若没有限制，根据排序不等式，一定是士兵和马按能力值从小到大排序后对应匹配最优
调整两个匹配 \(i,j\)，答案会减少
\(h_iw_i+h_jw_j-h_iw_j-h_jw_i=(h_i-h_j)(w_i-w_j)\)
把它放在二维平面上，横坐标为 \(h\)，纵坐标为 \(w\)，则减少的可以看作是 \((h_i,w_i),(h_j,w_j)\) 围成矩形的面积
限制相当于必须调整一些点
然后发现如果调整的 \(i,j\) 距离 \(>3\)，则可以分成调整更小的两个矩形，所以，很重要的结论是交换的距离不超过 \(3\)
设 \(f_i\) 表示 \(1\sim i\) 中减少的最小值
还有修改限制，考虑动态 DP，用矩阵维护 \(f_{i-2},f_{i-1},f_{i}\)
转移矩阵则是枚举与哪个交换，并产生相应贡献，交换两个位置的限制，只用修改这两个位置及其后 \(2\) 个的转移矩阵
线段树维护矩阵乘法，时间复杂度为 \(O(q\log n)\)
ll calc(ll x, ll xx, ll y, ll yy, ll z, ll zz) {return h[x].fi * w[xx].fi + h[y].fi * w[yy].fi + h[z].fi * w[zz].fi;}
struct segtree
{
matrix sum[N << 2];
ll lson(ll x) {return x << 1;}
ll rson(ll x) {return x << 1 | 1;}
void pushup(ll x) {sum[x] = sum[lson(x)] * sum[rson(x)];}
void modify(ll id, matrix val, ll l, ll r, ll p)
{
if(l == r) {sum[p] = val; return;}
ll mid = (l + r) >> 1;
if(mid >= id) modify(id, val, l, mid, lson(p));
else modify(id, val, mid + 1, r, rson(p));
pushup(p);
}
void upd(ll x)
{
matrix nw; nw.a[1][0] = nw.a[2][1] = 0;
if(match[x] != x) nw.a[2][2] = 0;
if(x > 1)
{
if(match[x - 1] != x - 1 && match[x] != x) nw.a[1][2] = 0;
else if(match[x] != x - 1 && match[x - 1] != x)
nw.a[1][2] = calc(x - 1, x - 1, x, x, 0, 0) - calc(x - 1, x, x, x - 1, 0, 0);
}
if(x > 2)
{
for(ll i = 1; i <= 3; ++i) p[i] = x - i + 1;
ll mn = inf;
for(ll i = 1; i <= 6; ++i)
{
ll flag = 1;
for(ll j = 1; j <= 3; ++j)
if(match[x - j + 1] == p[j]) {flag = 0; break;}
if(flag)
mn = min(mn, calc(x - 2, x - 2, x - 1, x - 1, x, x) - calc(x, p[1], x - 1, p[2], x - 2, p[3]));
next_permutation(p + 1, p + 4);
}
nw.a[0][2] = mn;
}
modify(x, nw, 1, n, 1);
}
}tree;
void mian()
{
read(n, q);
for(ll i = 1; i <= n; ++i) read(h[i].fi), h[i].se = i;
sort(h + 1, h + n + 1);
for(ll i = 1; i <= n; ++i) ordh[h[i].se] = i;
for(ll i = 1; i <= n; ++i) read(w[i].fi), w[i].se = i;
sort(w + 1, w + n + 1);
for(ll i = 1; i <= n; ++i) match[ordh[w[i].se]] = i, tot += w[i].fi * h[i].fi;
for(ll i = 1; i <= n; ++i) tree.upd(i);
init.a[0][2] = 0;
while(q--)
{
read(u, v);
swap(match[ordh[u]], match[ordh[v]]);
for(ll i = ordh[u]; i <= ordh[u] + 2 && i <= n; ++i) tree.upd(i);
for(ll i = ordh[v]; i <= ordh[v] + 2 && i <= n; ++i) tree.upd(i);
ans = init * tree.sum[1];
print(tot - ans.a[0][2]), putchar('\n');
}
}
DS
CF788E New task
发现两边的助手可以直接合并到中间相同段的两边，用树状数组算出方案数即可
考虑用线段树维护中间相同段
假设每种权值开一棵线段树，本来我的想法是动态统计每个位置上答案的增减
但是这样行不通，就算可以也非常复杂
其实正解很简单，考虑利用区间合并的性质，设这三个位置为 \(a,b,c\)，线段树上维护 \(a,b,c,ab,bc,abc\) 的数量，可以支持区间合并
这样单点修改也非常好处理
struct info {ll a, b, c, ab, bc, abc;}chg;
info operator +(const info &x, const info &y)
{
return (info){add(x.a, y.a), add(x.b, y.b), add(x.c, y.c), add(x.a * y.b % mod, add(x.ab, y.ab)), add(x.b * y.c % mod, add(x.bc, y.bc)), add(add(x.ab * y.c % mod, x.a * y.bc % mod), add(x.abc, y.abc))};
}
struct segtree
{
ll lson(ll x) {return x << 1;}
ll rson(ll x) {return x << 1 | 1;}
info node[N << 2];
void pushup(ll x)
{
node[x] = node[lson(x)] + node[rson(x)];
}
void build(ll l, ll r, ll p)
{
if(l == r)
{
node[p] = (info){num[0][id[l]], 1, num[1][id[l]], 0, 0, 0};
return;
}
ll mid = (l + r) >> 1;
build(l, mid, lson(p)), build(mid + 1, r, rson(p));
pushup(p);
}
void modify(ll id, info val, ll l, ll r, ll p)
{
if(l == r) {node[p] = val; return;}
ll mid = (l + r) >> 1;
if(mid >= id) modify(id, val, l, mid, lson(p));
else modify(id, val, mid + 1, r, rson(p));
pushup(p);
}
info query2(ll l, ll r, ll nl, ll nr, ll p)
{
if(l <= nl && nr <= r) return node[p];
ll mid = (nl + nr) >> 1;
if(mid >= l && mid < r)
return query2(l, r, nl, mid, lson(p)) + query2(l, r, mid + 1, nr, rson(p));
if(mid >= l) return query2(l, r, nl, mid, lson(p));
return query2(l, r, mid + 1, nr, rson(p));
}
}tree;
struct bit
{
ll sum[N];
void clear() {memset(sum, 0, sizeof(sum));}
void upd(ll x, ll val)
{
for(; x <= n; x += x & (-x)) sum[x] = add(sum[x], val);
}
ll query(ll x)
{
ll res = 0;
for(; x; x -= x & (-x)) res = add(res, sum[x]);
return res;
}
ll ask(ll l, ll r) {return (l > r) ? 0 : add(query(r), mod - query(l - 1));}
}bt, sec;
int main()
{
read(n);
for(ll i = 1; i <= n; ++i) read(a[i]), b[i] = 1, lsh[i] = a[i], id[i] = i;
sort(lsh + 1, lsh + n + 1), cnt = unique(lsh + 1, lsh + n + 1) - (lsh + 1);
for(ll i = 1; i <= n; ++i) a[i] = lower_bound(lsh + 1, lsh + cnt + 1, a[i]) - lsh;
sort(id + 1, id + n + 1, [](const ll x, const ll y) {return a[x] != a[y] ? a[x] < a[y] : x < y;});
memset(st, 0x3f, sizeof(st));
for(ll i = 1; i <= n; ++i) fid[id[i]] = i, ed[a[id[i]]] = max(ed[a[id[i]]], i), st[a[id[i]]] = min(st[a[id[i]]], i);
for(ll i = 1; i <= n; ++i)
{
num[0][i] = bt.ask(1, a[i]);
bt.upd(a[i], 1);
}
bt.clear();
for(ll i = n; i > 0; --i)
{
num[1][i] = bt.ask(1, a[i]);
bt.upd(a[i], 1);
}
for(ll i = 1; i <= n; ++i)
{
if(i == st[a[id[i]]]) qzh[i] = num[0][id[i]];
else qzh[i] = add(qzh[i - 1], num[0][id[i]]), is2[i] = qzh[i - 1], sec.upd(i, qzh[i - 1]);
}
for(ll i = 1; i <= n; ++i) init[i] = sec.ask(st[a[id[i]]], i - 1);
sec.clear();
for(ll i = 1; i <= n; ++i) sec.upd(i, num[0][id[i]]);
tree.build(1, n, 1);
read(q);
for(ll i = 1; i <= cnt; ++i)
if(st[i] <= ed[i]) ans = add(ans, tree.query2(st[i], ed[i], 1, n, 1).abc);
for(ll i = 1; i <= q; ++i)
{
read(op, pos);
if(op == 1 && b[pos])
{
b[pos] = 0, chg = (info){0, 0, 0, 0, 0, 0};
ll tmp = tree.query2(st[a[pos]], ed[a[pos]], 1, n, 1).abc; tree.modify(fid[pos], chg, 1, n, 1);
ans = add(ans, add(tree.query2(st[a[pos]], ed[a[pos]], 1, n, 1).abc, mod - tmp));
}
else if(op == 2 && !b[pos])
{
b[pos] = 1, chg = (info){num[0][pos], 1, num[1][pos], 0, 0, 0};
ll tmp = tree.query2(st[a[pos]], ed[a[pos]], 1, n, 1).abc; tree.modify(fid[pos], chg, 1, n, 1);
ans = add(ans, add(tree.query2(st[a[pos]], ed[a[pos]], 1, n, 1).abc, mod - tmp));
}
print(ans), putchar('\n');
}
return 0;
}
CF773E Blog Post Rating
先思考最优的摆放方式，一定是 \(a_i\) 单调不降，因为交换任意逆序对答案不劣
然后分析 \(F\) 的变化情况，它一定是先减少，到最小值后再增加与不变交替出现
分析最后的增加部分，想找到最后一个不变的位置，这样 \(F\) 的值可以直接计算
那么这个不变的位置一定是 \(\min_i\{a_i+k-i\}\) 取到的 \(i\)，也就是说，\(F\) 不会超过 \(\min_i\{a_i+k-i\}\)
现在还要找到最低点
发现 \(F\) 在 \(i\) 处值应该是 \(-i\)，当 \(-i\le a_i\) 时，无法继续减少，而对于之后的 \(j>i\)，\(-j<-i\le a_i\le a_j\)，更不可能继续减少
用权值线段树维护 \(a\) 和 \(\min\{a_i-i\}\)，在线段树上二分找到 \(-i\le a_i\) 的最后一个位置 \(p\)，对于插入 \(a_k\) 后，在 \(a_k\) 后的数排名增加 \(1\)，相当于区间减，查询 \(p\) 之后的后缀最小值
注意初始化细节，开始可以设为 \(i\) 处有 \(0\) 个数
struct segtree
{
int mx[N << 2], sum[N << 2], tag[N << 2], num[N << 2];
int lson(int x) {return x << 1;}
int rson(int x) {return x << 1 | 1;}
void pushup(int x)
{
num[x] = num[lson(x)] + num[rson(x)];
sum[x] = min(sum[lson(x)], sum[rson(x)]);
mx[x] = max(mx[lson(x)], mx[rson(x)]);
}
void upd(int x, int val) {mx[x] -= val, sum[x] += val, tag[x] += val;}
void pushdown(int x)
{
if(tag[x] == 0) return;
upd(lson(x), tag[x]), upd(rson(x), tag[x]), tag[x] = 0;
}
void build(int l, int r, int p)
{
if(l == r)
{
mx[p] = sum[p] = l; // 开始当作 a[]=l 的有 0 个
return;
}
int mid = (l + r) >> 1;
build(l, mid, lson(p)), build(mid + 1, r, rson(p));
pushup(p);
}
void modify(int id, int val, int rk, int l, int r, int p)
{
if(l == r) {++num[p]; return;}
pushdown(p);
int mid = (l + r) >> 1;
if(mid >= id) modify(id, val, rk, l, mid, lson(p));
else modify(id, val, rk, mid + 1, r, rson(p));
pushup(p);
}
void update(int l, int r, int val, int nl, int nr, int p)
{
if(l <= nl && nr <= r) return upd(p, val);
pushdown(p);
int mid = (nl + nr) >> 1;
if(mid >= l) update(l, r, val, nl, mid, lson(p));
if(mid < r) update(l, r, val, mid + 1, nr, rson(p));
pushup(p);
}
int find(int l, int r, int p)
{
if(l == r) return mx[p] >= 0 ? l : inf;
pushdown(p);
int mid = (l + r) >> 1;
if(mx[lson(p)] >= 0) return find(l, mid, lson(p));
return find(mid + 1, r, rson(p));
}
int querynum(int l, int r, int nl, int nr, int p)
{
if(l <= nl && nr <= r) return num[p];
pushdown(p);
int mid = (nl + nr) >> 1, res = 0;
if(mid >= l) res += querynum(l, r, nl, mid, lson(p));
if(mid < r) res += querynum(l, r, mid + 1, nr, rson(p));
return res;
}
int querysum(int l, int r, int nl, int nr, int p)
{
if(l <= nl && nr <= r) return sum[p];
pushdown(p);
int mid = (nl + nr) >> 1, res = inf;
if(mid >= l) res = min(res, querysum(l, r, nl, mid, lson(p)));
if(mid < r) res = min(res, querysum(l, r, mid + 1, nr, rson(p)));
return res;
}
}tree;
int main()
{
read(n);
for(int i = 1; i <= n; ++i) read(a[i]);
tree.build(-V, V, 1);
for(int i = 1; i <= n; ++i)
{
int rk = tree.querynum(-V, a[i], -V, V, 1);
tree.modify(a[i], a[i] - (rk + 1), rk + 1, -V, V, 1);
tree.update(a[i], V, -1, -V, V, 1);
int pos = tree.find(-V, V, 1); // 二分找到第一个 -i<=a[i] 的位置 pos，它作为最小值
print(tree.querysum(pos, V, -V, V, 1) + i), putchar('\n');
}
return 0;
}
CF643G Choosing Ads
发现 \(p\ge 20\%\)，区间内最多只有 \(5\) 个这样的数
设 \(k=\lfloor\frac{100}p\rfloor\)，则区间中只要保留 \(k\) 个数
考虑摩尔投票法，将 \(2\) 个拓展至多个，新加入数时，如果个数 \(<k\) 则直接加入它，否则个数全部减去最小值，把个数为 \(0\) 的去掉，只留下 \(k\) 个数
用线段树维护每个区间的合并结果，可以 \(O(k^2)\) 暴力合并，复杂度为 \(O(nk^2\log n)\)
struct segtree
{
vpii node[N << 2]; int tag[N << 2];
int lson(int x) {return x << 1;}
int rson(int x) {return x << 1 | 1;}
vpii pushup(vpii x, vpii y)
{
for(pii i : x)
{
int flag = 0;
for(pii &j : y)
if(j.fi == i.fi) {j.se += i.se, flag = 1; break;}
if(flag) continue;
if(y.size() < k) {y.pb(i); continue;}
vpii z; int mn = i.se;
for(pii j : y) mn = min(mn, j.se);
for(pii j : y)
if(j.se > mn) z.pb(mp(j.fi, j.se - mn));
if(i.se > mn) z.pb(mp(i.fi, i.se - mn));
y = z;
}
return y;
}
void pushdown(int l, int r, int p)
{
int mid = (l + r) >> 1;
if(!tag[p]) return;
tag[lson(p)] = tag[rson(p)] = tag[p];
node[lson(p)].clear(), node[lson(p)].pb(mp(tag[p], mid - l + 1));
node[rson(p)].clear(), node[rson(p)].pb(mp(tag[p], r - mid));
tag[p] = 0;
}
void build(int l, int r, int p)
{
if(l == r) {node[p].pb(mp(a[l], 1)); return;}
int mid = (l + r) >> 1;
build(l, mid, lson(p)), build(mid + 1, r, rson(p));
node[p] = pushup(node[lson(p)], node[rson(p)]);
}
void update(int l, int r, int val, int nl, int nr, int p)
{
if(l <= nl && nr <= r) {node[p].clear(); node[p].pb(mp(val, nr - nl + 1)), tag[p] = val; return;}
pushdown(nl, nr, p);
int mid = (nl + nr) >> 1;
if(mid >= l) update(l, r, val, nl, mid, lson(p));
if(mid < r) update(l, r, val, mid + 1, nr, rson(p));
node[p] = pushup(node[lson(p)], node[rson(p)]);
}
vpii query(int l, int r, int nl, int nr, int p)
{
if(l <= nl && nr <= r) return node[p];
pushdown(nl, nr, p);
int mid = (nl + nr) >> 1;
if(mid >= l && mid < r) return pushup(query(l, r, nl, mid, lson(p)), query(l, r, mid + 1, nr, rson(p)));
if(mid >= l) return query(l, r, nl, mid, lson(p));
return query(l, r, mid + 1, nr, rson(p));
}
}tree;
int main()
{
read(n, m, p), k = 100 / p;
for(int i = 1; i <= n; ++i) read(a[i]);
tree.build(1, n, 1);
for(int i = 1; i <= m; ++i)
{
read(op, nl, nr);
if(op == 1) read(v), tree.update(nl, nr, v, 1, n, 1);
else
{
vpii ans = tree.query(nl, nr, 1, n, 1);
print(ans.size()), putchar(' ');
for(pii j : ans) print(j.fi), putchar(' ');
putchar('\n');
}
}
return 0;
}
图论
CF464E The Classic Problem
考虑如何维护高精度数，需要支持加法以及比较大小
由于空间不够，需要用可持久化线段树，此时加法的进位均摊失效，必须快速找到连续 \(1\) 后面的 \(0\)，这个可以二分
区间赋值为 \(0\) 可以直接先建一棵全是 \(0\) 的线段树，直接把节点指向它
比较大小则类似于字符串哈希，直接用算出的答案作为哈希值，二分找到最长的公共后缀，然后比较下一位
struct segtree
{
ll hsh[M], ls[M], rs[M], idx;
void pushup(ll p) {hsh[p] = add(hsh[ls[p]], hsh[rs[p]]);}
ll build(ll l, ll r)
{
ll p = ++idx;
hsh[p] = 0;
if(l == r) return p;
ll mid = (l + r) >> 1;
ls[p] = build(l, mid), rs[p] = build(mid + 1, r);
return p;
}
ll buildful(ll l, ll r)
{
ll p = ++idx;
if(l == r) {hsh[p] = pw[l]; return p;}
ll mid = (l + r) >> 1;
ls[p] = buildful(l, mid), rs[p] = buildful(mid + 1, r);
pushup(p); return p;
}
ll find0(ll st, ll l, ll r, ll p)
{
if(l == r) return hsh[p] == 0 ? l : mod;
ll mid = (l + r) >> 1;
if(mid >= st)
{
if(hsh[p] != add(qzh[r], mod - qzh[l - 1]))
{
ll res = find0(st, l, mid, ls[p]);
if(res <= V) return res;
}
}
return find0(st, mid + 1, r, rs[p]);
}
ll update0(ll pre, ll nw, ll p, ll l, ll r, ll nl, ll nr)
{
if(l <= nl && nr <= r) return nw;
p = ++idx;
ls[p] = ls[pre], rs[p] = rs[pre], hsh[p] = hsh[pre];
ll mid = (nl + nr) >> 1;
if(mid >= l) ls[p] = update0(ls[pre], ls[nw], ls[p], l, r, nl, mid);
if(mid < r) rs[p] = update0(rs[pre], rs[nw], rs[p], l, r, mid + 1, nr);
pushup(p); return p;
}
ll update1(ll pre, ll p, ll id, ll l, ll r)
{
p = ++idx;
ls[p] = ls[pre], rs[p] = rs[pre], hsh[p] = hsh[pre];
if(l == r) {hsh[p] = pw[l]; return p;}
ll mid = (l + r) >> 1;
if(mid >= id) ls[p] = update1(ls[pre], ls[p], id, l, mid);
else rs[p] = update1(rs[pre], rs[p], id, mid + 1, r);
pushup(p); return p;
}
ll cmp(ll x, ll y, ll l, ll r) // x < y 1 x > y 0 x == y 2
{
if(l == r) return (hsh[x] > hsh[y] ? 0 : (hsh[x] < hsh[y] ? 1 : 2));
ll mid = (l + r) >> 1;
if(hsh[rs[x]] == hsh[rs[y]]) return cmp(ls[x], ls[y], l, mid);
return cmp(rs[x], rs[y], mid + 1, r);
}
}tree;
struct node
{
ll x, rt;
bool operator<(const node &x)const {return tree.cmp(rt, x.rt, 0, V) == 0;}
};
priority_queue<node> heap;
void dij()
{
rtful = tree.buildful(0, V);
for(ll i = 1; i <= n; ++i) root[i] = rtful;
root[S] = tree.build(0, V);
heap.push((node){S, root[S]});
while(!heap.empty())
{
int t = heap.top().x; heap.pop();
if(book[t]) continue;
book[t] = 1;
ll nrt = 0;
for(pll i : edge[t])
{
ll pos = tree.find0(i.se, 0, V, root[t]);
if(pos > i.se) nrt = tree.update0(root[t], root[S], nrt, i.se, pos - 1, 0, V);
else nrt = root[t];
nrt = tree.update1(nrt, nrt, pos, 0, V);
if(tree.cmp(nrt, root[i.fi], 0, V) == 1) root[i.fi] = nrt, las[i.fi] = t, heap.push((node){i.fi, nrt});
}
}
}
int main()
{
read(n, m);
for(ll i = 1; i <= m; ++i)
{
read(u, v, w);
edge[u].pb(mp(v, w)), edge[v].pb(mp(u, w));
}
read(S, T), pw[0] = qzh[0] = 1;
for(ll i = 1; i <= V; ++i) pw[i] = pw[i - 1] * 2ll % mod, qzh[i] = add(qzh[i - 1], pw[i]);
dij();
if(root[T] == rtful) {printf("-1"); return 0;}
for(ll x = T; x; x = las[x]) lin.pb(x);
reverse(lin.begin(), lin.end());
print(tree.hsh[root[T]]), putchar('\n'), print(lin.size()), putchar('\n');
for(ll i : lin) print(i), putchar(' ');
return 0;
}
CF1163F Indecisive Taxi Fee
删边最短路的科技
注意：只适用于正权图
先从 \(1,n\) 出发做两次 dij，记一条 \(1\to n\) 的最短路为 \(a_1,a_2,\dots,a_k\)
然后把点按到起点距离排序，预处理出 \(x\) 从 \(1\) 到 \(x\) 最短路最长经过的前缀 \(l_x\)，从 \(x\) 到 \(n\) 最长经过的后缀 \(r_x\)
去掉最短路上一条边后，经过的路径一定形如 \(a_1\to l_u\to u\to v\to r_v\to n\)
枚举边 \((u,v)\)，然后发现如果删去 \((l_u,r_v)\) 之间的边，这条边能对答案产生贡献
所以可以动态的用线段树更新最小值，离线下去差分 multiset 也可以
struct segtree
{
ll mn[N << 2], tag[N << 2];
ll lson(ll x) {return x << 1;}
ll rson(ll x) {return x << 1 | 1;}
void build(ll l, ll r, ll p)
{
mn[p] = tag[p] = inf;
if(l == r) return;
ll mid = (l + r) >> 1;
build(l, mid, lson(p)), build(mid + 1, r, rson(p));
}
void update(ll l, ll r, ll val, ll nl, ll nr, ll p)
{
mn[p] = min(mn[p], val);
if(l <= nl && nr <= r) {tag[p] = min(tag[p], val); return;}
ll mid = (nl + nr) >> 1;
if(mid >= l) update(l, r, val, nl, mid, lson(p));
if(mid < r) update(l, r, val, mid + 1, nr, rson(p));
}
ll query(ll id, ll l, ll r, ll p)
{
ll res = tag[p], mid = (l + r) >> 1;
if(l == r) return mn[p];
if(mid >= id) res = min(res, query(id, l, mid, lson(p)));
else res = min(res, query(id, mid + 1, r, rson(p)));
return res;
}
}tree;
void dij(ll st, ll id)
{
priority_queue<pll, vector<pll>, greater<pll> > heap;
memset(dis[id], 0x3f, sizeof(dis[id])), memset(book, 0, sizeof(book));
dis[id][st] = 0, heap.push(mp(dis[id][st], st));
while(!heap.empty())
{
ll t = heap.top().se; heap.pop();
if(book[t]) continue;
book[t] = 1;
for(ll i = head[t]; i; i = nxt[i])
if(dis[id][to[i]] > dis[id][t] + e[i])
{
dis[id][to[i]] = dis[id][t] + e[i];
if(!id) pre[to[i]] = i;
heap.push(mp(dis[id][to[i]], to[i]));
}
}
}
void trace()
{
for(int i = n; i; i = to[pre[i] ^ 1])
{
lin[++cnt] = i;
if(pre[i]) edg[++num] = pre[i], vis[pre[i]] = num;
}
reverse(lin + 1, lin + cnt + 1), reverse(edg + 1, edg + num + 1);
for(int i = 1; i <= cnt; ++i) fl[lin[i]] = i - 1, fr[lin[i]] = i;
}
int main()
{
read(n, m, q);
for(int i = 1; i <= m; ++i) read(u[i], v[i], w[i]), add(u[i], v[i], w[i]), add(v[i], u[i], w[i]);
dij(1, 0), memset(fr, 0x3f, sizeof(fr));
trace();
dij(n, 1);
for(ll i = 1; i <= n; ++i) pos[i] = i;
sort(pos + 1, pos + n + 1, [](const ll x, const ll y){return dis[0][x] < dis[0][y];});
for(ll i = 1; i <= n; ++i)
{
ll x = pos[i];
for(ll j = head[x]; j; j = nxt[j])
if(!vis[j] && !vis[j ^ 1] && dis[0][to[j]] == dis[0][x] + e[j]) fl[to[j]] = max(fl[to[j]], fl[x]);
}
sort(pos + 1, pos + n + 1, [](const ll x, const ll y){return dis[1][x] < dis[1][y];});
for(ll i = 1; i <= n; ++i)
{
ll x = pos[i];
for(ll j = head[x]; j; j = nxt[j])
if(!vis[j] && !vis[j ^ 1] && dis[1][to[j]] == dis[1][x] + e[j])
fr[to[j]] = min(fr[to[j]], fr[x]);
}
tree.build(1, num, 1);
for(ll i = 1; i <= n; ++i)
for(ll j = head[i]; j; j = nxt[j])
if(!vis[j] && !vis[j ^ 1] && fl[i] + 1 <= fr[to[j]] - 1 && fr[to[j]] <= cnt)
tree.update(fl[i] + 1, fr[to[j]] - 1, dis[0][i] + dis[1][to[j]] + e[j], 1, num, 1);
for(ll i = 1; i <= q; ++i)
{
read(road, vl);
if(!vis[road * 2] && !vis[road * 2 + 1])
ans = min({dis[0][n], dis[0][u[road]] + vl + dis[1][v[road]], dis[0][v[road]] + vl + dis[1][u[road]]});
else
{
if(vl < e[road * 2]) ans = dis[0][n] - (e[road * 2] - vl);
else
{
ll p = vis[road * 2] ? vis[road * 2] : vis[road * 2 + 1];
ans = min(dis[0][n] + (vl - e[road * 2]), tree.query(num + 1 - p, 1, num, 1));
}
}
print(ans), putchar('\n');
}
return 0;
}
CF103E Buying Sets
神奇的网络流
任意子集并的大小 \(\ge k\) 是个特殊的限制，选取时要求元素个数和集合个数相等也比较难以处理
把价值取反，求最大价值
分析一下，用最小割建模，但割掉源点连向集合的边表示不选集合，割掉元素连向汇点的边表示选元素
源点连向集合的边流量为 \(lim-a_i\)，元素连向汇点的边流量为 \(lim\)
假设左边选 \(x\) 条边，则剩下 \(n-x\) 个集合一定连向 \(\ge n-x\) 个元素，因此割掉的边数 \(\ge n\)
而边权全部 \(+lim\)，多割掉边不优，所以只会割掉 \(n\) 条边
不选集合个数 \(+\) 元素个数 \(= n\)，不选集合个数 \(+\) 选的集合个数 \(=n\)
所以 元素个数 \(=\) 选的集合个数
int main()
{
read(n), S = n * 2 + 1, T = n * 2 + 2;
for(ll i = 1; i <= n; ++i)
{
read(num[i]);
for(ll j = 1; j <= num[i]; ++j) read(u), add(i, u + n, inf), add(u + n, i, 0);
}
for(ll i = 1; i <= n; ++i) read(a[i]), sum += a[i], add(S, i, lim - a[i]), add(i, S, 0);
for(ll i = 1; i <= n; ++i) add(i + n, T, lim), add(T, i + n, 0);
while(bfs() == 1) ans += dinic(S, inf);
printf("%lld", min(0ll, sum + (ans - lim * n)));
return 0;
}
CF1779E Anya's Simultaneous Exhibition
好题
首先把胜负关系抽象成有向图，\(A\) 能赢 \(B\) 则连 \(A\to B\) 的边
连出来是一张竞赛图
假设我们已经知道了这张图，怎么判定谁能获胜？
如果有人不能被它和它能打败的任何一个人打败，那么这个人肯定赢不了
所以如果将图按强连通分量缩点，这个点所在强连通分量的拓扑序最小
问题变为怎么找这些点
我们可以花 \(n-1\) 次询问问出每个点的入度，出度，按出度从大到小排序
这些点的出度肯定最多，一定是这个序列的前缀
去掉之间连的边，它们向其它点连的都是出边
那么如果第一个 \(m\) 使 \((\sum_{i=1}^m out_i)-\frac{m(m-1)}2=m(n-m)\)，则前 \(m\) 个点为要找的
简要证明：如果真实的强连通分量大小为 \(x\)，若 \(x<m\)，则到 \(x\) 时等式必然满足，若 \(x>m\)，则 \(m+1\sim x\) 没有连向前 \(m\) 个点的边，它们不可能在一个强连通分量中
int ask(int x, bitset<N> bit)
{
cout << "? " << x << " ";
for(int i = 1; i <= n; ++i) cout << bit[i];
cout << endl; int res = 0; cin >> res; return res;
}
int cmp(const int &x, const int &y) {return out[x] > out[y];}
int main()
{
cin >> n; m = out[n] = n * (n - 1) / 2;
for(int i = 1; i < n; ++i)
{
s.set(), s[i] = 0;
out[i] = ask(i, s), out[n] -= out[i];
}
for(int i = 1; i <= n; ++i) id[i] = fa[i] = i, in[i] = n - 1 - out[i];
sort(id + 1, id + n + 1, cmp);
for(int i = 1; i <= n; ++i)
{
sum += out[id[i]];
if(sum - i * (i - 1) / 2 == i * (n - i))
{
for(int j = 1; j <= i; ++j) ans[id[j]] = 1;
break;
}
}
cout << "! ";
for(int i = 1; i <= n; ++i) cout << ans[i];
cout << endl;
return 0;
}
数学
[ARC136C] Circular Addition
智慧题，考虑把 \(A\) 不断 \(-1\) 变成 \(0\)
发现一次操作相当于对环上的差分序列 \(+1,-1\) 同时对最大值最多 \(-1\)
设 \(M=\max_{i=0}^{n-1}\{A_i-A_{(i+1)\bmod n}\}\)，\(D=\max_{i=0}^{n-1}\{A_i\}\)
则答案的下界是 \(\max\{M,D\}\)
CF1815E Bosco and Particle
先从简单情况入手，如果只有一块挡板，它的上下都是必然反弹的墙
我们发现粒子的运动有循环节，长度为 \(O(|S|)\)
所以粒子在两边运动次数的比例可以模拟求出来
如果有多块挡板，则可以看作粒子飞下去后又回来，中间经过的过程不重要，看作是它又反弹回来
这样每两块挡板之间飞行次数的比例可以算出来
现在就是要求满足比例的最小正整数
直接算肯定会爆炸，设第一块板子上下经过次数为 \(a_1:b_1\)，第二块板子上下经过次数为 \(a_2:b_2\)，初始空隙经过 \(x\) 次，则 \(x\) 必须是 \(a_1\) 的倍数
而且 \(x:\star =a_1:b_1\) 且 \(\star=ka_2,k\in N^*\)，所以 \(\star\) 为 \(\frac {a_1a_2} {b_1}\) 的倍数
依次类推，把每个 \(a,b\) 分解质因数，然后求每个质数出现的最大次数，即可求出 \(x\)，然后递推出所有值
注意特判如果有块板子全是 \(1\)，则它相当于边界，不可通过
void init()
{
mn[1] = pw[0] = 1;
for(ll i = 2; i <= V; ++i)
{
if(!st[i]) prime[++cnt] = mn[i] = i;
for(ll j = 1; j <= cnt && i * prime[j] <= V; ++j)
{
st[i * prime[j]] = 1, mn[i * prime[j]] = prime[j];
if(i % prime[j] == 0) break;
}
}
for(ll i = 1; i <= V; ++i) pw[i] = pw[i - 1] * P % mod;
}
void upd(int x)
{
ll m = s.length(); hsh[0] = 0;
for(ll i = 1; i <= m; ++i) hsh[i] = (hsh[i - 1] * P % mod + s[i - 1]) % mod;
for(ll i = 1; i <= m; ++i) // 找最小循环节 i
{
if(m % i) continue;
ll hah = gethsh(1, i), flag = 1;
for(ll j = i + 1; j <= m; j += i)
if(gethsh(j, j + i - 1) != hah) {flag = 0; break;}
if(flag) {m = i; break;}
}
if(m == 1 && s[0] == '1') {tot = x - 1; return;} // 全是 1,下面的没用了
for(ll i = 0, cur = 0, flag = 0; ; i = (i + 1) % m) // 好像循环节最长也是 O(V) 量级 ?
{
if(i == 0 && cur == 0) ++flag;
if(flag == 2) break;
if(!cur)
{
if(s[i] == '0') ++a[x], ++b[x], cur = 1;
else a[x] += 2, cur = 0;
}
else
{
if(s[i] == '0') ++a[x], ++b[x], cur = 0;
else b[x] += 2, cur = 1;
}
}
}
void add(ll x, ll val)
{
while(mn[x] > 1) // 分解质因数，统计质因数的最高次数
{
ll nw = mn[x], num = 0;
while(x % nw == 0) x /= nw, ++num;
sum[nw] += num * val, mx[nw] = max(mx[nw], sum[nw]);
}
}
int main()
{
init();
cin >> n, tot = n;
for(int i = 1; i <= n; ++i)
{
cin >> s;
if(i <= tot) upd(i);
}
if(!tot)
{
printf("2");
return 0;
}
for(ll i = 1; i <= tot; ++i) add(a[i], 1), add(b[i], -1);
f[1] = 1;
for(ll i = 2; i <= V; ++i) f[1] = f[1] * qmi(i, mx[i]) % mod;
for(ll i = 2; i <= tot + 1; ++i) f[i] = f[i - 1] * b[i - 1] % mod * qmi(a[i - 1], mod - 2) % mod;
for(ll i = 1; i <= tot + 1; ++i) ans = (ans + f[i]) % mod;
printf("%lld", ans);
return 0;
}
[ARC139E] Wazir
小清新多项式题
首先得构造出答案的上界：
- 若 \(m,n\) 为偶数，则可以交错着摆，有 \(2\) 种方案
- 若 \(m,n\) 有一个为偶数，则把它调整为行，列必然是交错着摆且其中有一段空了 \(2\) 个，这个 \(2\) 个的空隙相邻行坐标相差 \(1\)（此时第一行和最后一行也算相邻），答案为 \(n\times\frac {m-1}2\)
- 若 \(m,n\) 均为奇数，其实也可以像上面这样构造，但是必须满足 \(n\ge m\)，否则转不回去
现在抽象出比较好计数的结构，发现空隙很有规律
有序列 \(a_1,a_2,\dots,a_{n+1}\)，则 \(\forall i\in[1,n],|a_{i+1}-a_i|=1\pmod m\) 且 \(a_{n+1}=a_1\)
-
如果 \(n\le 10^5\)，则可以直接枚举 \(n\) 个差分是 \(+1\) 还是 \(-1\)，要求和 \(\bmod m=0\)，组合数统计
-
否则考虑优化，写出生成函数，则方案数相当于 \((x+x^{-1})^n\pmod{x^m-1}\) 的 \(0\) 次项系数，注意这里的取模实际上就是乘完后把指数对 \(m\) 取模，跟上面的组合意义一样
int main()
{
cin >> n >> m;
if(n % 2 == 0 && m % 2 == 0)
{
printf("2");
return 0;
}
if(m % 2 == 0 || (n % 2 && m % 2 && n < m)) swap(n, m);
if(n <= 100000)
{
fact[0] = invf[0] = 1;
for(ll i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i % mod;
invf[n] = qmi(fact[n], mod - 2);
for(ll i = n - 1; i > 0; --i) invf[i] = invf[i + 1] * (i + 1) % mod;
for(ll i = 0; i <= n; ++i)
if((n - i - i) % m == 0) ans = add(ans, c(n, i));
printf("%lld", ans * m % mod); return 0;
}
poly a(m), res(m); a[1] = a[m - 1] = res[0] = 1;
while(n)
{
if(n & 1) mul(res, a);
n >>= 1, mul(a, a);
}
printf("%lld", res[0] * m % mod);
return 0;
}
贪心
AT_dp_x Tower
交换排序贪心
考虑 \(i,j\) 交换位置，之前必须满足 \(x\le s_i,x+w_i\le s_j\)，之后必须满足 \(x\le s_j,x+w_j\le s_i\)
移项，得 \(x\le s_j-w_i,x\le s_i-w_j\)
所以若 \(s_j-w_i>s_i-w_j\)，则限制更容易被满足 ，\(i\) 放在前面更优
排好序后做背包即可
struct box
{
ll w, s, v;
}a[N];
int main()
{
read(n);
for(ll i = 1; i <= n; ++i) read(a[i].w, a[i].s, a[i].v);
sort(a + 1, a + n + 1, [&](const box x, const box y){return x.s - y.w < y.s - x.w;});
for(ll i = 1; i <= n; ++i)
for(ll j = a[i].w + a[i].s; j >= a[i].w; --j)
f[j] = max(f[j], f[j - a[i].w] + a[i].v);
for(ll i = 1; i <= 20000; ++i) ans = max(ans, f[i]);
printf("%lld", ans);
return 0;
}
[ARC121D] 1 or 2
如果每次只能选两个，从小到大排序后，最大和最小，次大和次小等依次配对最优
可能只选一个，神奇的转化是看作与 \(0\) 配对
枚举一共有多少个 \(0\) 然后贪心匹配，复杂度为 \(O(n^2)\)
void work()
{
int i, j;
for(i = 0, j = p.size() - 1; i < j; ++i, --j) mn = min(mn, p[i] + p[j]), mx = max(mx, p[i] + p[j]);
if(i == j) mn = min(mn, p[i]), mx = max(mx, p[j]);
ans = min(ans, mx - mn);
}
int main()
{
read(n);
for(int i = 1; i <= n; ++i) read(a[i]);
sort(a + 1, a + n + 1);
for(int i = 1; i <= n; ++i) p.pb(a[i]);
mx = -inf, mn = inf, work();
for(int i = 1; i <= n; ++i)
{
p.insert(lower_bound(p.begin(), p.end(), 0), 0);
mx = -inf, mn = inf, work();
}
printf("%d", ans);
return 0;
}
CF1592F2 Alice and Recoloring 2
选取子矩形不好维护，考虑转化为单点修改
定义二维差分数组，每个位置的实际值为后缀矩形的异或和
操作 \(1\) 为单点修改，操作 \(4\) 为修改 \(4\) 个点，且形如 \((x,y),(n,y),(x,m),(n,m)\)
发现操作 \(2,3\) 都是无用的，可以通过 \(2\) 次操作 \(1\) 得到
假设先只用操作 \(1\)，然后利用操作 \(4\) 使代价减少
先考虑 easy version
操作 \(4\) 为花费 \(3\) 改 \(4\) 个点，如果能操作操作肯定更优，但 \((n,m)\) 被翻转，之后最多有 \(3\) 个有效翻转的位置，与操作 \(1\) 等价
因此操作 \(4\) 最多只进行 \(1\) 次，判断即可
现在由于花费变为 \(2\)，把 \((n,m)\) 翻转后可能剩下的还是能继续翻转
但是这要求剩下 \(3\) 个点都是有效翻转，代价才能相比原来只用操作 \(1\) 减少
会翻转 \((n,y),(x,m)\)，每一行，每一列均只能出现 \(1\) 次，想选出最多的 \((x,y)\)
转换为二分图匹配，可以用网络流，复杂度为 \(O(n^2\sqrt n)\)
int main()
{
ios::sync_with_stdio(false), cin.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; ++i) cin >> (s[i] + 1);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j) a[i][j] = (s[i][j] == 'B') ? 1 : 0;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j) b[i][j] = a[i][j + 1] ^ a[i][j];
for(int j = 1; j <= m; ++j)
for(int i = 1; i <= n; ++i) a[i][j] = b[i][j] ^ b[i + 1][j];
S = n + m + 1, T = n + m + 2;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
{
if(i < n && j < m && a[i][j] && a[i][m] && a[n][j])
add(i, j + n, 1), add(j + n, i, 0);
if(a[i][j]) ++ans;
}
for(int i = 1; i <= n; ++i) add(S, i, 1), add(i, S, 0);
for(int i = n + 1; i <= n + m; ++i) add(i, T, 1), add(T, i, 0);
while(bfs() == 1) sum += dinic(S, inf);
if(sum & 1) ans += a[n][m] ? -1 : 1;
printf("%d", ans - (sum * 3) + sum * 2);
return 0;
}
CF1693C Keshi in Search of AmShZ
假设现在 Keshi 在点 \(x\)，如果我们已经知道 Keshi 走到 \(y\) 最少还需要的天数 \(f_y\)，我们贪心的想让他走到最少的
我们会封住一些边，但考虑最坏情况，Keshi 一定走到了剩下的最大的点
所以把 \(y\) 按 \(f_y\) 从小到大排序，封住比 \(f_y\) 大的点，然后找出最小的封路代价 \(+f_y\)
考虑最短路的过程，每次从堆顶取出的一定是当前 \(f\) 最小的，相当于已经从小到大排了序，统计指向它的点 \(x\) 还有多少点的 \(f\) 比它大，\(f_x\) 就能被更新
直接倒着跑最短路，定义 \(dis\) 为 \(f\)
void dij()
{
memset(dis, 0x3f, sizeof(dis));
priority_queue<pii, vector<pii>, greater<pii> > heap;
dis[n] = 0, heap.push(mp(0, n));
while(!heap.empty())
{
int t = heap.top().se; heap.pop();
if(vis[t]) continue;
vis[t] = 1;
for(pii x : edge[t])
{
out[x.fi] -= x.se;
if(dis[x.fi] > dis[t] + out[x.fi] + 1)
{
dis[x.fi] = dis[t] + out[x.fi] + 1;
heap.push(mp(dis[x.fi], x.fi));
}
}
}
}
int main()
{
read(n, m);
for(int i = 1; i <= m; ++i) read(u, v), ++out[u], ++book[v][u];
for(int i = 1; i <= n; ++i)
for(iter it = book[i].begin(); it != book[i].end(); ++it) edge[i].pb(mp(it -> fi, it -> se));
memset(f, 0x3f, sizeof(f)), f[n] = 0;
dij();
printf("%d", dis[1]);
return 0;
}
P8341 [AHOI2022] 回忆
题意为在树上选出最少条数的路径，使每组 \((s,t)\) 的两个点在某条路径中被同时经过
分析一下，以 \(1\) 为根，由于 \(s\) 为 \(t\) 的祖先，我们肯定优先从 \(t\) 开始把它们所在的链选上，再考虑能否合并两条链为一条路径，减少路径数
按深度从大到小考虑
合并时能合并则合并，因为已经合并的可以直接拆散引上来，但是未合并的到后面就不一定能合并
路径有 \(3\) 种状态：已经合并，已到 \(s\) 但未合并，未到 \(s\) 且未合并
对于没有到 \(s\) 的路径，如果 \(x,y\) 均有这样的路径则保留 \(s\) 深度更小的，在深度更大的 \(s\) 处打上标记表示到了 \(s\) 会多出来一条已到 \(s\) 但未合并的路径
对于已到 \(s\) 但未合并的路径，在 \(x\) 处肯定是能合并则合并，假设从 \(y\) 传上来一些路径，且 \(y\) 中未合并的路径更多，考虑把 \(x\) 中已匹配的路径拆散去匹配 \(y\) 中剩下的，讨论 \(x\) 处的路径够不够全部合并
最后答案为已合并的路径数 \(+\) 剩余的路径
注意到达 \(t\) 时，要讨论新建未到 \(s\) 路径的情况
- 如果子树内有这样的路径，直接把那条延长
- 否则考虑从子树内传一条路径上来，这样不劣于新建路径，因为有多余未合并路径可以直接记为未到 \(s\)，拆散匹配的话能多出一条已到 \(s\) 但未合并路径，增加的路径条数均为 \(1\)，但灵活性更强
实现上新建路径的操作全部在 \(s\) 处体现，每个点最多只有 \(1\) 条未到 \(s\) 路径，记录它的 \(s\) 即可
int chkmin(int x, int y) {return dep[x] < dep[y] ? x : y;}
void Dfs(int x, int fa)
{
for(int y : edge[x])
{
if(y == fa) continue;
Dfs(y, x);
if(up[y] == x) up[y] = 0, ++path[y]; // 注意特判 s 深度最小的路径也到了 s，去掉
path[y] += tag[x], tag[x] = 0; // tag[x] 条路径到 s，它们成为 y 中待匹配的路径
if(up[y] && up[x]) ++tag[dep[up[x]] > dep[up[y]] ? up[x] : up[y]];
up[x] = chkmin(up[x], up[y]); // 合并未达到 s 的路径
if(path[y] < path[x]) swap(path[y], path[x]), swap(match[y], match[x]); // y 剩余路径更多
if(match[x] * 2 + path[x] >= path[y]) // y 中多余路径全部能与 x 中路径合并
match[x] += (path[x] + path[y]) / 2 + match[y], path[x] = (path[x] + path[y]) % 2;
else // 有剩余
path[y] -= match[x] * 2, match[x] = match[x] * 2 + path[x] + match[y], path[x] = path[y] - path[x];
} // 用 path[y] 中转，避免修改 path 前 match 被更新
if(goal[x]) // 有路径起点
{
if(!up[x]) // 子树内没有未到 s 路径，传上去一条原来的去完成目标，若没有则隐式新开一条
{
if(path[x]) --path[x];
else if(match[x]) --match[x], ++path[x];
}
up[x] = chkmin(up[x], goal[x]); // 否则直接把那条延长
}
}
int main()
{
read(t);
while(t--)
{
clear();
read(n, m);
for(int i = 1; i < n; ++i) read(u, v), edge[u].pb(v), edge[v].pb(u);
dfs(1, 0), dep[0] = inf;
for(int i = 1; i <= m; ++i) read(u, v), goal[v] = chkmin(goal[v], u);
Dfs(1, 0);
print(match[1] + path[1]), putchar('\n');
}
return 0;
}
字符串
我不明白为什么 NOIP 前集训给了 SAM，PAM 题……
甚至还有多项式 FFT，难绷
CF1037H Security
考虑把区间限制转化，将询问离线按右端点从小到大排序，这样只用要求左端点尽量靠右，即右端点尽量靠右
建出 SAM 后，将 \(T\) 匹配，最优答案一定是 \(T\) 的一段前缀 \(+\) 比 \(T\) 后面一个字符大的最小字符
枚举 \(T\) 匹配的长度 \(len\) 和下一个字符 \(c\)，此时在 SAM 上会到一个节点 \(x\)
根据 \(endpos\) 集合的定义，\(x\) 在 \(parent\ tree\) 上的子树内的节点的 \(endpos\) 都是它的子集
这样想在子树内找最靠右的节点，每次要动态加入一个节点
将树序列化，用线段树维护，每次在 \([dfn_x,mxdfn_x]\) 之间找最大值，判断是否合法，若合法则更新答案
struct qry
{
string t;
int l, r, id;
}lsh;s
vector<qry> ask[N];
struct segtree
{
int mx[N << 2];
int lson(int x) {return x << 1;}
int rson(int x) {return x << 1 | 1;}
void pushup(int p) {mx[p] = max(mx[lson(p)], mx[rson(p)]);}
void update(int id, int val, int l, int r, int p)
{
if(l == r) return void(mx[p] = val);
int mid = (l + r) >> 1;
if(mid >= id) update(id, val, l, mid, lson(p));
else update(id, val, mid + 1, r, rson(p));
pushup(p);
}
int query(int l, int r, int nl, int nr, int p)
{
if(l <= nl && nr <= r) return mx[p];
int mid = (nl + nr) >> 1, res = 0;
if(mid >= l) res = max(res, query(l, r, nl, mid, lson(p)));
if(mid < r) res = max(res, query(l, r, mid + 1, nr, rson(p)));
return res;
}
}tree;
struct SAM
{
int len[N], siz[N], fa[N], ch[N][27], idx = 1, las = 1, root = 1;
vector<int> edge[N];
int insert(int c)
{
int p = las, np = las = ++idx;
len[np] = len[p] + 1;
for(; p && !ch[p][c]; p = fa[p]) ch[p][c] = np;
if(!p) fa[np] = root;
else
{
int q = ch[p][c];
if(len[q] == len[p] + 1) fa[np] = q;
else
{
int nq = ++idx;
memcpy(ch[nq], ch[q], sizeof(ch[q])), len[nq] = len[p] + 1;
fa[nq] = fa[q], fa[q] = fa[np] = nq;
for(; p && ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
}
}
return las;
}
void dfs(int x)
{
dfn[x] = ++cnt;
for(int y : edge[x]) dfs(y);
mxdfn[x] = cnt;
}
void find(string str, int l, int r, int id)
{
int m = str.length(), u = root, lstlen = 0;
for(int i = 0; i <= m; ++i)
{
if(l + i > r) return;
int lim = 0;
if(i < m) lim = str[i] - 'a' + 1;
for(int j = lim; j < 26; ++j)
if(ch[u][j])
{
if(tree.query(dfn[ch[u][j]], mxdfn[ch[u][j]], 1, idx, 1) < l + i) continue;
if(!ans[id].empty()) ans[id].pop_back();
for(int k = lstlen; k < i; ++k) ans[id] += str[k];
ans[id] += ('a' + j), lstlen = i;
break;
}
if(i >= m) return;
if(!ch[u][str[i] - 'a']) return;
u = ch[u][str[i] - 'a'];
}
}
}sam;
int main()
{
cin >> s >> q, n = s.length();
for(int i = 1; i <= q; ++i) cin >> lsh.l >> lsh.r >> lsh.t, lsh.id = i, ask[lsh.r].pb(lsh);
for(int i = 1; i <= n; ++i) fr[i] = sam.insert(s[i - 1] - 'a');
for(int i = 2; i <= sam.idx; ++i) sam.edge[sam.fa[i]].pb(i);
sam.dfs(sam.root);
for(int i = 1; i <= n; ++i)
{
tree.update(dfn[fr[i]], i, 1, sam.idx, 1);
for(qry x : ask[i]) sam.find(x.t, x.l, i, x.id);
}
for(int i = 1; i <= q; ++i) cout << (ans[i].empty() ? "-1" : ans[i]), cout << "\n";
return 0;
}
CF1073G Yet Another LCP Problem
求后缀的最长公共前缀，想到对反串建 SAM
然后是在两个集合中选，且集合的总大小有限，根据 SAM 的性质，这两个串的开头代表节点在 parent tree 上的 lca 的 len 就是答案
自然想到建虚树，然后直接在节点处统计答案
注意清空
struct SAM
{
int len[N], fa[N], ch[N][27], idx = 1, las = 1, root = 1;
int insert(int c)
{
int p = las, np = las = ++idx;
len[np] = len[p] + 1;
for(; p && !ch[p][c]; p = fa[p]) ch[p][c] = np;
if(!p) fa[np] = root;
else
{
int q = ch[p][c];
if(len[q] == len[p] + 1) fa[np] = q;
else
{
int nq = ++idx;
memcpy(ch[nq], ch[q], sizeof(ch[q])), len[nq] = len[p] + 1;
fa[nq] = fa[q], fa[q] = fa[np] = nq;
for(; p && ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
}
}
return las;
}
void dfs(int x)
{
dfn[x] = ++cnt, rmq[0][cnt] = fa[x];
for(int y : edge[x]) dfs(y);
}
}sam;
int getlca(int x, int y)
{
if(x == y) return x;
if(dfn[x] > dfn[y]) swap(x, y);
int l = dfn[x] + 1, r = dfn[y], v = lg[r - l + 1];
return dfn[rmq[v][l]] < dfn[rmq[v][r - (1 << v) + 1]] ? rmq[v][l] : rmq[v][r - (1 << v) + 1];
}
void clear()
{
for(int i : del) tree[i].clear(), siz[0][i] = siz[1][i] = 0;
pnt.clear(), del.clear();
}
void add(int u, int v) {tree[u].pb(v);}
int cmp(const int &x, const int &y) {return dfn[x] < dfn[y];}
void build(vector<int> p)
{
p.pb(sam.root), sort(p.begin(), p.end(), cmp);
vector<int> lsh; lsh.clear();
for(int i = 1; i < p.size(); ++i) lsh.pb(getlca(p[i - 1], p[i]));
for(int i : p) lsh.pb(i);
sort(lsh.begin(), lsh.end(), cmp), del.pb(lsh[0]);
for(int i = 1; i < lsh.size(); ++i)
{
if(del.back() == lsh[i]) continue;
int lca = getlca(del.back(), lsh[i]);
add(lca, lsh[i]), del.pb(lca), del.pb(lsh[i]);
}
}
void Dfs(int x)
{
ans += 1ll * sam.len[x] * siz[0][x] * siz[1][x];
for(int y : tree[x])
{
Dfs(y);
ans += 1ll * sam.len[x] * (siz[0][x] * siz[1][y] + siz[1][x] * siz[0][y]);
siz[0][x] += siz[0][y], siz[1][x] += siz[1][y];
}
}
int main()
{
read(n, m), reads(s);
for(int i = n; i > 0; --i) fr[i] = sam.insert(s[i] - 'a');
for(int i = 2; i <= sam.idx; ++i) edge[sam.fa[i]].pb(i);
sam.dfs(sam.root);
for(int j = 1; j <= 18; ++j)
for(int i = 1; i + (1 << j) - 1 <= sam.idx; ++i)
{
int ln = rmq[j - 1][i], rn = rmq[j - 1][i + (1 << (j - 1))];
rmq[j][i] = dfn[ln] < dfn[rn] ? ln : rn;
}
lg[0] = -1;
for(int i = 1; i <= sam.idx; ++i) lg[i] = lg[i >> 1] + 1;
for(int i = 1; i <= m; ++i)
{
read(p, q);
for(int j = 1, u = 0; j <= p; ++j)
{
read(u), ++siz[0][fr[u]];
if(in[fr[u]] < i) pnt.pb(fr[u]), in[fr[u]] = i;
}
for(int j = 1, u = 0; j <= q; ++j)
{
read(u), ++siz[1][fr[u]];
if(in[fr[u]] < i) pnt.pb(fr[u]), in[fr[u]] = i;
}
ans = 0, build(pnt);
Dfs(sam.root);
clear(), print(ans), putchar('\n');
}
return 0;
}
P4199 万径人踪灭
先容斥转化为统计对称的字符串个数，最后再用 Manacher 统计回文串个数并减去
枚举对称中心 \(i\)，则对于 \(x+y=2i\) 的字符 \(s_x,s_y\) 应相同
转化为统计不同的数量，答案形如 \(\sum_{x+y=2i}[s_x=a][s_y=b]\)
这不就是和卷积的形式吗！设多项式 \(f=\sum_{i=1}^{n}[s_i=a]x^i,g=\sum_{i=1}^n [s_i=b]x^i\)，答案就是 \(f*g\)
由于最后每项系数不超过 \(n\) 且模数不好，用 FFT 优化
复杂度为 \(O(n\log n)\)
struct comp {double real, imag;};
comp operator + (const comp &x, const comp &y) {return (comp){x.real + y.real, x.imag + y.imag};}
comp operator - (const comp &x, const comp &y) {return (comp){x.real - y.real, x.imag - y.imag};}
comp operator * (const comp &x, const comp &y) {return (comp){x.real * y.real - x.imag * y.imag, x.real * y.imag + x.imag * y.real};}
typedef vector<comp> poly;
ll a[N], rev[N], pw[N], lim, n, p[N], tot[N], mx, id, ans, flaga, flagb;
poly fa, fb;
char s[N], t[N];
void fft(poly &f, ll n, ll typ)
{
for(ll i = 0; i < n; ++i) rev[i] = 0;
for(ll i = 0; i < n; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (n >> 1) : 0);
for(ll i = 0; i < n; ++i)
if(i < rev[i]) swap(f[i], f[rev[i]]);
for(ll step = 2; step <= n; step <<= 1)
{
ll gap = step >> 1;
comp w = (comp){cos(2.0 * pi / step), typ * sin(2.0 * pi / step)};
for(ll i = 0; i < n; i += step)
{
comp cur = (comp){1.0, 0};
for(ll j = i; j < i + gap; ++j, cur = cur * w)
{
comp p = f[j], q = f[j + gap] * cur;
f[j] = p + q, f[j + gap] = p - q;
}
}
}
}
void mul(poly f, poly g)
{
for(lim = 1; lim <= n * 2; lim <<= 1);
f.resize(lim), g.resize(lim);
fft(f, lim, 1), fft(g, lim, 1);
for(ll i = 0; i < lim; ++i) f[i] = f[i] * g[i];
fft(f, lim, -1);
for(ll i = 0; i < lim; ++i) tot[i] = (ll)(f[i].real / lim + 0.5);
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0);
cin >> (s + 1), n = strlen(s + 1);
fa.resize(n + 1), fb.resize(n + 1);
for(int i = 1; i <= n; ++i)
if(s[i] == 'a') flaga = 1, fa[i] = (comp){1, 0};
else flagb = 1, fb[i] = (comp){1, 0};
flaga && flagb ? mul(fa, fb) : void();
t[0] = '$', t[n * 2 + 2] = '~', t[n * 2 + 1] = '#';
for(int i = 1; i <= n; ++i) t[i * 2 - 1] = '#', t[i * 2] = s[i];
for(int i = 1; i <= n * 2; ++i)
{
p[i] = mx > i ? min(p[id * 2 - i], mx - i) : 1;
while(p[i] < i && i + p[i] <= n * 2 + 1 && t[i - p[i]] == t[i + p[i]]) ++p[i];
if(i + p[i] - 1 > mx) mx = i + p[i] - 1, id = i;
ans = (ans + mod - p[i] / 2) % mod;
}
pw[0] = 1;
for(int i = 1; i <= n * 2; ++i) pw[i] = pw[i - 1] * 2ll % mod;
for(ll i = 1; i <= n * 2; ++i)
if(i & 1) ans = (ans + pw[min(i / 2, n - i / 2) - tot[i]] - 1) % mod;
else ans = (ans + (pw[min(i / 2 - 1, n - i / 2) - tot[i]] - 1) * 2ll % mod) % mod;
printf("%lld", (ans + n) % mod);
return 0;
}
CF1400F x-prime Substrings
找性质题，发现 \(x\) 非常小，符合要求的串不含 \(1\)，长度不超过 \(10\)
直接暴搜出哪些串不能出现，建出字典树，发现节点数大概只有 \(5000\)
然后就是经典问题：原串中不能出现某些串，求原串最多保留的字符数
那就在 AC 自动机上 DP，设 \(f(i,j)\) 表示已经考虑到第 \(i\) 个位置，匹配到自动机上的节点 \(j\) 的答案
先在 fail 树上找出哪些点不能到，然后枚举选/不选这个字符转移
struct ACAM
{
int son[M][12], cnt[M], fail[M], idx = 1, root = 1;
void insert(string str)
{
int u = root, len = str.length();
for(int i = 0; i < len; ++i)
{
if(!son[u][str[i] - '0']) son[u][str[i] - '0'] = ++idx;
u = son[u][str[i] - '0'];
}
cnt[u] = 1;
}
void getfail()
{
for(int i = 1; i <= 9; ++i)
if(son[root][i]) fail[son[root][i]] = root, q[++tt] = son[root][i];
else son[root][i] = root;
while(hh <= tt)
{
int u = q[hh++];
for(int i = 1; i <= 9; ++i)
if(son[u][i]) fail[son[u][i]] = son[fail[u]][i], q[++tt] = son[u][i];
else son[u][i] = son[fail[u]][i];
}
for(int i = 1; i <= tt; ++i) cnt[q[i]] += cnt[fail[q[i]]];
}
}ac;
void dfs(int x)
{
if(ss[x - 1] == k)
{
ac.insert(t);
return;
}
if(x > k || ss[x - 1] > k) return;
for(int i = 1; i <= 9; ++i)
{
int flag = 1;
for(int j = 0; j < x; ++j)
if(ss[x - 1] - ss[j] + i < k && k % (ss[x - 1] - ss[j] + i) == 0) {flag = 0; break;}
if(flag)
{
ss[x] = ss[x - 1] + i, t.pb(i + '0');
dfs(x + 1);
t.pop_back();
}
}
}
void chkmax(int &a, int b) {a = b > a ? b : a;}
int main()
{
cin >> s >> k, n = s.length();
dfs(1);
ac.getfail();
for(int j = 2; j <= ac.idx; ++j) f[1][j] = -N;
for(int i = 0; i < n; ++i, cur ^= 1)
{
for(int j = 1; j <= ac.idx; ++j) f[cur][j] = f[cur ^ 1][j];
for(int j = 1; j <= ac.idx; ++j)
{
if(!ac.cnt[ac.son[j][s[i] - '0']])
chkmax(f[cur][ac.son[j][s[i] - '0']], f[cur ^ 1][j] + 1);
}
}
for(int j = 1; j <= ac.idx; ++j) ans = max(ans, f[cur ^ 1][j]);
printf("%d", n - ans);
return 0;
}
CF955D Scissors
首先特判整个 \(t\) 直接出现，可以在 \(2k\) 的长度内被剪下的情况
然后考虑拼接，枚举 \(t\) 的起点，一定是匹配尽量长的前缀，此时后缀的起点有一个范围，想在这个范围内找匹配后缀的最长长度，如果两个长度加起来 \(\ge m\) 即可
二分哈希预处理出后缀匹配的最长长度，用 ST 表维护区间最大值
复杂度为 \(O(n\log n)\)，有 \(O(n)\) KMP 做法，但我不会
int merge(int x)
{
int l = 0, r = min({m, k, x});
while(l < r)
{
int mid = (l + r + 1) >> 1;
if(gethshs(x - mid + 1, x) == gethsht(m - mid + 1, m)) l = mid;
else r = mid - 1;
}
return l;
}
int merge2(int x)
{
int l = 0, r = min({m, k, n - x + 1});
while(l < r)
{
int mid = (l + r + 1) >> 1;
if(gethshs(x, x + mid - 1) == gethsht(1, mid)) l = mid;
else r = mid - 1;
}
return l;
}
struct info {int mx, pos;};
info rmq[20][N];
struct stable
{
info chkmax(info x, info y) {return x.mx > y.mx ? x : y;}
void init()
{
lg[0] = -1;
for(int i = 1; i <= n; ++i) rmq[0][i] = (info){lcp[i], i}, lg[i] = lg[i >> 1] + 1;
for(int j = 1; j <= 18; ++j)
for(int i = 1; i + (1 << j) - 1 <= n; ++i)
rmq[j][i] = chkmax(rmq[j - 1][i], rmq[j - 1][i + (1 << (j - 1))]);
}
info query(int l, int r)
{
if(l > r) return (info){0, 0};
if(l == r) return rmq[0][l];
int v = lg[r - l + 1];
return chkmax(rmq[v][l], rmq[v][r - (1 << v) + 1]);
}
}st;
int main()
{
read(n), read(m), read(k), reads(s), reads(t);
pw[0] = 1;
for(int i = 1; i <= n; ++i) pw[i] = pw[i - 1] * P;
for(int i = 1; i <= n; ++i) hshs[i] = hshs[i - 1] * P + s[i];
for(int i = 1; i <= m; ++i) hsht[i] = hsht[i - 1] * P + t[i];
for(int i = 1; i <= n; ++i)
{
lcp[i] = merge(i);
if(lcp[i] >= m)
{
for(int nl = 1, nr = nl + k; nl <= i - m + 1 && nr + k - 1 <= n; ++nl, ++nr)
if(i <= nr + k - 1)
{
printf("Yes\n%d %d", nl, nr);
return 0;
}
}
}
st.init();
for(int i = 1; i <= n; ++i)
{
int nw = merge2(i), ln = i + nw - 1;
if(ln < k || m - nw > k) continue;
if(nw >= m)
{
for(int nl = 1, nr = nl + k; nr + k - 1 <= n; ++nl, ++nr)
if(nl <= i && i + nw - 1 <= nr + k - 1)
{
printf("Yes\n%d %d", nl, nr);
return 0;
}
}
info rn = st.query(ln + m - nw, n - k + m - nw);
if(rn.pos && rn.mx >= m - nw)
{
printf("Yes\n%d %d", ln - k + 1, rn.pos - (m - nw) + 1);
return 0;
}
}
puts("No");
return 0;
}
CF1530E Minimax
什么大分类讨论破题……
不太想说，反正特判只有一个字符，无法变化和一个字符只出现一次，答案为 \(0\)，剩下的均可构造至答案为 \(1\)
讨论字典序最小的字母是否能在开头连着放 \(2\) 个，如果可以，后面它一定要与其它的交错
所以出现次数太多的话，开头只能放一个，填上次大后连着摆，注意若没有第三大的则必须把次大填完
int main()
{
cin >> t;
while(t--)
{
cin >> (s + 1), n = strlen(s + 1);
mn = 26, lin.clear();
for(int i = 0; i < 26; ++i) num[i] = 0;
for(int i = 1; i <= n; ++i) ++num[s[i] - 'a'];
for(int i = 0; i < 26; ++i)
if(num[i]) lin.pb(i);
for(int i = 0; i < 26; ++i)
if(num[i] == 1) {mn = i; break;}
if(lin.size() == 1)
{
cout << (s + 1) << "\n";
continue;
}
if(mn < 26)
{
ans[1] = mn + 'a', --num[mn]; int cnt = 1;
for(int i = 0; i < lin.size(); ++i)
for(int j = 1; j <= num[lin[i]]; ++j) ans[++cnt] = lin[i] + 'a';
}
else
{
ans[1] = lin[0] + 'a', --num[lin[0]];
if(num[lin[0]] <= n / 2)
{
for(int i = 2; i <= n; ++i)
if(i % 2 == 0 && num[lin[0]]) ans[i] = lin[0] + 'a', --num[lin[0]];
else
{
for(int j = 1; j < lin.size(); ++j)
if(num[lin[j]]) {--num[lin[j]], ans[i] = lin[j] + 'a'; break;}
}
}
else
{
if(lin.size() == 2)
{
for(int i = 2; i <= num[lin[1]] + 1; ++i) ans[i] = lin[1] + 'a';
for(int i = num[lin[1]] + 2; i <= n; ++i) ans[i] = ans[1];
}
else
{
ans[2] = lin[1] + 'a';
for(int i = 3; i <= num[lin[0]] + 2; ++i) ans[i] = lin[0] + 'a';
int cnt = num[lin[0]] + 2;
ans[++cnt] = lin[2] + 'a', --num[lin[2]], --num[lin[1]];
for(int i = 1; i < lin.size(); ++i)
for(int j = 1; j <= num[lin[i]]; ++j) ans[++cnt] = lin[i] + 'a';
}
}
}
for(int i = 1; i <= n; ++i) cout << ans[i];
cout << "\n";
}
return 0;
}
CF103409H Popcount Words
好题
发现 \(\operatorname{popcount}\) 有非常好的倍增性，这已经在不止一题中见到过了
设 \(w^T(l,r)\) 为 \(w(l,r)\) 中 \(01\) 反转后的串，为开区间 \([l,r)\)
则 \(w(0,2^k)=w(0,2^{k-1})+w(2^{k-1},2^k)=w(0,2^{k-1})+w^T(0,2^{k-1})\)
把每段询问区间拆成 \(O(\log V)\) 段形如 \(w(l,l+2^k)\)，这样就能写成 \(w/w^T(0,2^k)\)
多串匹配，把询问串建 AC 自动机，在 AC 自动机上倍增预处理出 \(f(i,j,0/1)\) 表示从 \(i\) 节点出发，匹配 \(w/w^T(0,2^j)\) 后到达的节点
然后就可以在自动机上用 \(f\) 数组快速求出匹配位置，打标记 \(g(i,j,0/1)\)，表示从 \(i\) 出发的 \(w/w^T(0,2^j)\) 的个数
同理反着倍增下传标记，求出 \(g(i,0,0/1)\)，这样它的子节点 \(son(i,x)\) 就被经过了 \(g(i,0,x)\) 次
最后统计答案即可
struct ACAM
{
int son[M][2], idx = 1, root = 1, fail[M], que[M], hh = 1, tt, f[2][32][M];
ll g[2][32][M], cnt[M];
int insert(string str)
{
int u = root, len = str.length();
for(int i = 0; i < len; ++i)
{
if(!son[u][str[i] - '0']) son[u][str[i] - '0'] = ++idx;
u = son[u][str[i] - '0'];
}
return u;
}
void getfail()
{
for(int i = 0; i < 2; ++i)
if(son[root][i]) que[++tt] = son[root][i], fail[son[root][i]] = root;
else son[root][i] = root;
while(hh <= tt)
{
int u = que[hh++];
for(int i = 0; i < 2; ++i)
if(son[u][i]) que[++tt] = son[u][i], fail[son[u][i]] = son[fail[u]][i];
else son[u][i] = son[fail[u]][i];
}
}
void jump()
{
for(int i = 1; i <= idx; ++i) f[0][0][i] = son[i][0], f[1][0][i] = son[i][1];
for(int j = 1; j <= 29; ++j)
for(int i = 1; i <= idx; ++i)
f[0][j][i] = f[1][j - 1][f[0][j - 1][i]], f[1][j][i] = f[0][j - 1][f[1][j - 1][i]];
}
void calc()
{
for(int j = 29; j > 0; --j)
for(int i = 1; i <= idx; ++i)
{
g[0][j - 1][i] += g[0][j][i], g[1][j - 1][f[0][j - 1][i]] += g[0][j][i];
g[1][j - 1][i] += g[1][j][i], g[0][j - 1][f[1][j - 1][i]] += g[1][j][i];
}
for(int i = 1; i <= idx; ++i) cnt[son[i][0]] += g[0][0][i], cnt[son[i][1]] += g[1][0][i];
for(int i = tt; i > 0; --i) cnt[fail[que[i]]] += cnt[que[i]];
}
}ac;
int main()
{
cin >> n >> q;
for(int i = 1; i <= n; ++i) cin >> l[i] >> r[i];
for(int i = 1; i <= q; ++i) cin >> s[i], fr[i] = ac.insert(s[i]);
ac.getfail(), ac.jump();
auto lowbit = [](int x) -> int {return x & (-x);};
int nw = ac.root;
for(int i = 1; i <= n; ++i)
{
int nl = l[i], nr = r[i] + 1;
while(nl < nr)
{
int num = popcnt(nl) & 1, lb = lowbit(nl), v = 0;
if(nl + lb <= nr) v = __lg(lb);
else lb = lowbit(nr - nl), v = __lg(lb);
++ac.g[num][v][nw], nw = ac.f[num][v][nw], nl += lb;
}
}
ac.calc();
for(int i = 1; i <= q; ++i) print(ac.cnt[fr[i]]), putchar('\n');
return 0;
}