见到了 p_b_p_b 神仙!

CF848E Days of Floral Colours

是某个奇怪的组合数学 / 生成函数题. 总共四种连线方案, 如图

从上到下从左到右依次编号 $1$ 到 $4$. 显然情况 $2$ 和 $4$ 把区间分成了多段, 并且情况 $4$ 会使两侧的点跨段 (姑且称之为段).

先考虑线段上的问题. 设 $f_{0/1/2}[n]$ 分别表示有 $0/1/2$ 侧端点跨段长为 $n$ 的区间 (也就是不一定是一整段) 的贡献. 定义段不包括左侧而包括右侧的边界点, 显然长为 $x$ 的段贡献为 $(x-1)^2$. 定义 $g[n]$ 表示只有 $1$ 和 $3$ 两种情况组合出来长为 $n$ 的段的方案数. 则有

$$ f_0[n]=g[n-1](n-1)^2+\sum_{i=1}^{n-1}f_0[n-i]g[i-1](i-1)^2+\sum_{i=2}^{n-2}f_1[n-i]g[i-2](i-1)^2\\ f_1[n]=g[n-2](n-1)^2+\sum_{i=2}^{n-1}f_0[n-i]g[i-2](i-1)^2+\sum_{i=3}^{n-2}f_1[n-i]g[i-3](i-1)^2\\ f_2[n]=g[n-3](n-1)^2+\sum_{i=2}^{n-2}f_1[n-i]g[i-2](i-1)^2+\sum_{i=3}^{n-3}f_2[n-i]g[i-3](i-1)^2\\ g[n]=g[n-4]+g[n-2] $$

然后窝不会 BM 就直接拿了兔爷的线性递推式

$$ \{0,4,8,-1,16,-10,4,-12,-48,26,-44,15,-16,-4,-4,-1\} $$

或者像 jiangly 爷一样

$$ \frac{24x^3+4x^4+144x^5-4x^6+348x^7-128x^8+240x^9+28x^{10}+188x^{11}-68x^{12}+16x^{13}+4x^{15}}{1-4x^2-8x^3+x^4-16x^5+10x^6-4x^7+12x^8+48x^9-26x^{10}+44x^{11}-15x^{12}+16x^{13}+4x^{14}+4x^{15}+x^{16}} $$

LOJ3014 [JOI 2019 Final]独特的城市

长链剖分, 显然贡献只会在点到直径端点的连线上. 用次重 (长?) 儿子去去掉重儿子上深度小于它的点, 再用重儿子去掉其它深度不够的点. 用栈维护一下即可.

光说很难理解, 直接看代码.

void sqfa(int u,int v) {
    while (top&&dep[u]-dep[stk[top]]<=mxd[msi[u]]) pop();
    push(u); if (mxi[u]) sqfa(mxi[u],u);
    while (top&&dep[u]-dep[stk[top]]<=mxd[mxi[u]]) pop();
    pri[u]=max(pri[u],ans);
    for (auto i:edg[u]) if (i!=mxi[u]&&i!=v) {
        if (stk[top]!=u) push(u); sqfa(i,u);
    }
    if (stk[top]==u) pop();
}

mxi[]和msi[]是重儿子和次重儿子,mxd[]是子树最大深度,push()和pop()是对栈的操作. 记得更新完每个儿子之后重新把当前点压进栈. 从直径两个端点各做一次即可.

LOJ3123 [CTSC2019]重复

KMP 自动机... 不是很理解, 只是照着题解复读了一遍.

总之建出来边之后跑一个 DP 和暴力匹配就好了.

LOJ2336 [JOI 2017 Final]绳

显然一开始就染好不会更劣. 要折成长度为 $2$ 的绳子, 首先显然不超过 $2$ 种颜色, 然后除两侧外每一个相同颜色的连续段段长必须是偶数, 证明省略.

然后只需要枚举一下每种颜色, 然后考虑左端的奇偶性, 从剩下的颜色中找出来最多的作为另一种即可. 复杂度和代码实现有关, 应该要用个vector<>存一下每种颜色的出现位置才好写.

for (int i=1;i<=m;++i) {
    s=e[i].size(); for (auto j:e[i]) remove(c[j]);
    for (auto j:e[i]) if (c[j^1]!=i) remove(c[j^1]); q=n-s-r;
    for (auto j:e[i]) if (c[j^1]!=i) insert(c[j^1]);
    for (auto j:e[i]) if (c[((j-1)^1)+1]!=i) remove(c[((j-1)^1)+1]);
    printf("%d\n",min(q,n-s-r));
    for (auto j:e[i]) if (c[((j-1)^1)+1]!=i) insert(c[((j-1)^1)+1]);
    for (auto j:e[i]) insert(c[j]);
}

insert()和remove()就是统计 / 不统计该点.

LOJ3037 [JOISC 2019 Day3]开关游戏

可以转化为先区间覆盖再区间取反.

首先考虑只有取反, 需要的次数为 $1$ 的极长连续段的个数. 那么区间覆盖的要求就是最小化 $1$ 连续段的个数.

考虑 DP, 设 $f_{0/1/2}[n]$ 表示前 $n$ 个位置, 当前没有覆盖 / 覆盖 $0$/ 覆盖 $1$ 的最小代价(加上取反), 转移方程为

f[i][0]=min(f[i-1][0]+(s[i-1]^t[i-1]^s[i]^t[i]),min(f[i-1][1]+(48^t[i-1]^s[i]^t[i])+1,f[i-1][2]+(49^t[i-1]^s[i]^t[i])+1));
f[i][1]=min(f[i-1][0]+(s[i-1]^t[i-1]^48^t[i])+1,min(f[i-1][1]+(48^t[i-1]^48^t[i]),f[i-1][2]+(49^t[i-1]^48^t[i])+2));
f[i][2]=min(f[i-1][0]+(s[i-1]^t[i-1]^49^t[i])+1,min(f[i-1][1]+(48^t[i-1]^49^t[i])+2,f[i-1][2]+(49^t[i-1]^49^t[i])));

LOJ2554 [CTSC2018]青蕈领主

蕈(xun), 对丈育极不友好.

考虑每一个极长连续段 (显然连续段不会相交), 认为其包含的连续段为它的儿子, 总共有 $s$ 个. 把这个连续段的儿子缩成点, 组成一个新排列. 这个新排列的 $L$ 显然是 $\{1,1,\ldots,1,s-1\}$ 的, 也就是内部不包含更小的连续段. 设这样的长为 $\operatorname{len}$ 的新排列有 $f[\operatorname{len}]$ 种排列方式, 那答案就是 $\prod_if[s_i]$.

接下来试着求出 $f$. 称一个排列是合法的, 当其 $L=\{1,1,\ldots,l,\operatorname{len}-1\}$. 假设现在有一个 $1\sim n-1$ 的排列, 插入 $n+1$, 分情况考虑:

• 如果原排列合法: 那只要 $n$ 不与 $n-1$ 相邻即可, 贡献 $f[n-1](n-1)$;
• 如果原排列不合法: 插入 $n$ 最多打破一个不合法区间, 且该区间不能包含 $n-1$, 所以枚举该区间长度, 贡献 $\sum_{i=2}^{n-2}f[i]f[n-i](n-i-1)=\sum_{i=2}^{n-2}f[i]f[n-i](i-1)$.

综合起来有

$$ f[n]=f[n-1](n-1)+\sum_{i=2}^{n-2}f[i]f[n-i](i-1) $$

求 $s$ 可以单调栈, 最后注意判不合法即可.

World Tour Finals 2019 C

不会, 咕了.