JOISC 2022

JOISC2022

Day1T2 京都观光

在 zr 的时候花子讲过这个题，当时就觉得非常的震撼！！现在来看还是觉得这个题好牛啊。

假设我们现在只有两条路走：第一条是 ↓ →，第二条是 → ↓。贡献分别为：\(B_1\times n+A_n\times m\) 以及 \(A_1\times m+B_m\times n\)。移项后两侧分别为 \((A_n-A_1)\times m\) 和 \((B_m-B_1)\times n\)。也就是 \(\frac{A_n-A_1}{n}\) 以及 \(\frac{B_m-B_1}{m}\) 的大小比较。这个看一眼就像是在比斜率啊。

然后因为对于整个路径中的每一个局部都是可以去做这个微调的尝试的，所以把 \(A/B\) 凸壳求出来后按照闵和去走就行了。

这我哪会啊唉。。

Day1T3 错误拼写

先研究 \(T_{A_i}\le T_{B_i}\) 的充要条件：令 \(L=\min\{A_i,B_i\},R=\max\{A_i,B_i\}\)。则限制形如：要么 \(s[L\sim R]\) 全部相等，要么第一次出现不等的位置，填的是小于号 or 大于号。

倒序，扫描线，维护 dp：设扫描到位置 \(i\)。令 \(f(x,j)\) 表示已经确定了 \(S[i...n]\)，\(S_i=x\) 且第一处不为 \(i\) 的字符位于 \(S_{j+1}\) 处，且 \(S_i\lt S_{j+1}\) 的方案数；令 \(g(x,j)\) 表示 \(S_i\gt S_{j+1}\) 的方案数。特别地，我们认为 \(S_{n+1}=\infty\)，因此 \(i=n\) 的时候有初始化 \(f(x,n)=1,g(x,n)=0(x\in \Sigma)\)。

转移的时候从时刻 \(i+1\) 的 \(f/g\) 转移到时刻 \(i\) 的 \(f/g\)，只需要分类讨论 \(S_i\) 和 \(S_{i+1}\) 的相等关系

1. \(S_i\neq S_{i+1}\)。进一步讨论 \(S_i\lt S_{i+1}\) 或者 \(S_i\gt S_{i+1}\)。以前者为例，那么不能存在一个 \(L=i\) 的限制，且要求第一个填的是大于号。

2. \(S_i=S_{i+1}\)，那假设继承 \(f(x,j)\)，就要求不存在一个 \(L=i,R\gt j\) 的限制，且要求第一个填的是大于号。继承 \(g(x,j)\) 同理。

观察上述 dp 数组的转移过程，发现需要维护这样一个数据结构：前端插入，前端推平成 \(0\)，求前缀和。使用栈就足够了。

时间复杂度 \(O(n\Sigma)\)。

Day2T1 复制粘贴 3

考虑最后一次进行剪切操作后，此时输入栏为空。我们能做的只有：输入字符/末尾粘贴一个字符串 \(T\)。因此易得结论，\(T\) 一定是 \(S\) 的一个子串。

设计 dp：设 \(f(l,r)\) 表示我们想要打出 \(S[l...r]\) 这个串的最少代价。同样地，枚举最后一次进行剪切操作后的串 \([x,y]\in [l,r]\)，则花费为：\((C-(y-x+1)A)\times occ + B + A\times (r-l+1)\)。其中 \(occ\) 是 \(S[x,y]\) 在 \(S[l,r]\) 中的不重叠出现次数。

容易观察到：事实上如果 \(l/r\) 这个字符是自己打出来的，我们就可以直接转移到 \(f(l+1,r)/f(l,r-1)\)。如果 \(l\) 这个字符是复制得到的，那么就有 \(x=l\)。考虑按照 \(l\) 的顺序降序计算区间 dp 值：第一类转移可以留到最后做。对于第二类转移，不妨直接枚举 \(y\) 的值，然后再去枚举 \(occ\)，注意到这个 \(occ\) 的上界总和是有调和级数去保证的！所以对于一个固定的左端点 \(l\)，第二类转移只有 \(O(n\ln n)\) 种。

最后的问题是怎么快速地找到这些位置，即对于每个 \(S\) 中的子串 \([l,r]\)，我们希望求出下一个 \(\gt r\) 的出现位置。

首先 \(O(n^2)\) 地预处理两两后缀的 LCP，接下来枚举 \(l\) 计算所有的 \(g(l,r)\)。刻画一个位置 \(p\) 合法的充要条件：

• \(p\gt r\)。

• \(lcp(l,p)\ge r-l+1\)

我们需要找到最小的 \(p\)。如果倒序枚举 \(r\)，可以看出候选的 \(p\) 一直在增多，不会变小。道理很简单，两个限制都在变宽。所以可以 \(O(n^2)\) 预处理之。总复杂度 \(O(n^2\ln n)\)。

UPD：最近做梦熊模拟赛的时候刚好有一道基于本题改编的题目。也没有什么花样，就是 \(n\le 2\times 10^6\)，然后想让你求出 \(S\) 的每个前缀的不重叠覆盖位置。这个时候我们求 LCP 先用 Z 来搞一手。接下来还是经典倒序枚举前缀长度这就错完了。正确姿势是顺序枚举前缀长度。这样我们干的事情是 ban 掉而不是加入一些位置。但是好处是我们不断在做的是在序列上 lower bound，结合删除的话是可以和 dsu 适配的，如果和加入结合那就不行。所以这就拿下 \(2\times 10^6\) 了。

Day2T3 团队竞技

这个题其实还是很趣味的。做法很简单：考虑 \(x/y/z\) 最大的三个人。比如说如果 \(x\) 最大的那个人，他的 \(y/z\) 也是最大的。那这个人不可能出现在答案里，删去。否则 \(x/y/z\) 已经是一组合法解，并且很容易看出来是最大的。那就得到了一个特别简洁的 \(O(n\log n)\) 做法！

给我的感觉有点像 这个题

Day3T3 蚂蚁与方糖

我觉得是这场比赛里最值得做的一个题。

这种问题都有直觉转成匹配/费用流问题。别的题都好说，这个题的难点就是想到转了之后好像还不太好做。令 \(N(S)\) 是 \(S\) 集合的左部点能吃到的右部点数量。则我们根据 Hall 定理就要求 \(|S|-N(S)\) 的最大值。

在一些比较常见的题目里，\(S\) 在最优解里通常会是一个区间来方便维护：但这个题显然就不成立了。他给出了另一种思路：尝试把贡献拆成每个位置独立的，然后去做 ddp。这其实比“最优解是一个区间”还要更加的泛化。

把贡献拆成每个位置独立，它的难点在哪里？两个左部点对应到的右部点可能是有重合的。但是这个题的连边又很独特：位置 \(p\) 的左部点连向 \([p-L,p+L]\) 的右部点。所以随着左部点在数轴上的向右移动，这个覆盖区间也是不断地向右移动的。

那我们直接令 \(p_i\) 是左部点 \(i\) 减去所有 \([i-L,i+L]\) 范围内的右部点的值。然后对于一个 \(S\) 来说，先把 \(\sum_{i\in S}p_i\) 全部加上。再对于那些 \((i-1)\) 和 \(i\) 都在 \(S\) 中的情况，去掉它们在右端点那部分的交即可。这样的话贡献就相对地拆成了每个位置独立的情况了。

归纳一下就是每个位置有两个贡献 \(p/q\)。并且满足 \(p\ge q\)。一个 \(S\) 的 \(f(S)=|S|-N(S)\) 计算规则如下：如果 \(i\in S\)，那么如果 \(i-1\in S\) 贡献是 \(q\)，否则是 \(p\)。我们还是想求 \(f(S)\) 的最大值。

并且有更良好的性质：对于一个应该填 \(q\) 的位置，让他填 \(p\) 也没有关系。所以整个问题变成了：每个位置能选 \(0/p/q\)，唯一限制是，如果选了 \(p\)，前面一个位置必须是 \(0\)。（除非 \(p\) 位于开头）。

这就很好用一个线性 dp 解决了，并且看上去很有 ddp 的前途。

研究修改：加入一个左部点的时候相当于只修改一处的 \((p,q)\)（不妨开始每个位置都存在且认为 \(x=0\)，这样就不用处理插入的问题了）。加入右部点就比较麻烦，虽然 \(q\) 还是只被修改一处。但是 \(p\) 的话会修改到一个 \([x-L,x+L]\) 这样的范围内所有左部点的 \(p\) 值！谁家的 ddp 能做区间修改啊 woc。

再往下做一步就需要惊人观察力了：注意到这个区间 \(len = 2L\)，那其实根据原问题的意义：我们在选左部点的时候，如果出现了 \(q[000]p\) 这种情况，它们两个的距离一定 \(\gt 2L\)，否则你替换成 \(q[qqq]q\) 不会让 \(f(S)\) 更小（打中括号的意思是可能有任意多个，也可能零个）。

基于这个想法可以看出，区间加的时候，很大概率这个区间 ddp 里维护的信息里，只会也必须出现一次选 \(p\) 的位置。如果我们能保证这一点，那所谓的区间修改，就是在对 dp 值进行区间加罢了。。

事实上设 \(f(x,0/1/2,0/1)\) 表示：\(x\) 代表的区间内，第一个位置选择 \(0/p/q\)，最后一个位置选择 \(0/(p or q)\) 能得到的最大值。并且我们加上一条限制：强制至少有一个位置不是 \(0\)（仅用来限定 \(f(x,0,0)\)）。加上这样一个限定后，可以证明。如果 \(x\) 的区间长度不超过 \(2L\)。那么对于一个固定的 \(f(x,a,b)\)。要么它代表的状态里恰好出现一次 \(p\)要么一次都不出现。于是区间修改也变得容易。时间复杂度 \(O(n+q\log n)\)。事实上也存在很多别的 dp 方式，都是类似的。

Day4T1 一流团子师傅

对上眼了这个题。

先考虑 \(m=2\)：考虑试除法：每次尝试删去一个元素，若删去后一串都组不出来他就必须保留，否则删去。

\(m\gt 2\) 的情况直接分治即可，暴力删去元素，若删去后无法组出 \(mid\) 串就必须保留，否则删去，即可。

询问次数 \(nm\log m\)，刚好。

Day4T2 鱼2

著名题啊！竟然现在才做到！这个题也很厉害。

令 \(a_0=a_{n+1}=\infty\)。不考虑 \([L,R]\) 的限制。一个位置出发不断拓展，最后一定会得到一个 \([s,t]\) 使得 \(\sum_{i=s}^{t}a_i \lt \min\{a_{s-1},a_{t+1}\}\)。称从 \(i\) 出发得到的这样的一个 \([s,t]\) 为 \(f(i)\)。

这个题最厉害的点就是信息竟然是可合并的，所以可以用线段树玩。。。甚至还能把修改换成区间 cover。。。怎么一个归并法？

假设两个区间 \([L,mid],(mid,R]\)。现在考虑左边的一个位置 \(p\)，假设只考虑 \([L,mid]\) 时 \(f(p)\) 的右端点不是 \(mid\)，那么它本来只考虑 \([L,mid]\)，现在算上 \((mid,R]\) 它还是吃不完。

右侧同理，可能吃完的位置必须满足 \(f(p)\) 的左端点是 \(mid+1\)。

我们并不记录区间内每个位置的 \(f(p)\)，而是转而记录每个 \([s,t]\) 作为多少个 \(f(p)\) 出现过。并且根据上面的分析我们已经知道了 \(s=L/t=R\) 必须有至少一者成立。事实上容易证明：\(s=L/t=R\) 的区间只有 \(O(\log V)\) 个。以 \(s=L\) 为例，\([L,p]\) 出现的话就意味着 \(a_{p+1}\gt \sum_{i=L}^{p}a_i\)，则拓展到 \(p+1\) 的时候区间和就至少翻倍了。

所以我们一个区间真的只需要记录 \(O(\log V)\) 个前缀和后缀信息（区间以及它的出现次数）就够了！唯一剩下的问题就是归并。归并的话其实对 \([L,mid]\) 的每个后缀信息，以及 \((mid,R]\) 的每个前缀信息暴力算新的结果就行了。这个题跑的确实挺快的，毕竟每个节点不可能都卡满 \(O(\log V)\) 的。

Day4T3 复兴计划

有一个很妙的 \(O(m\log q\log n)\) 做法，这个做法可以把 \(n\) 开到很大！

先离线询问并排序（其实不离线也照样做）。首先对于一条边而言，它存在于 MST 的时刻一定是一个区间，这个区间一定包含 \(w_i\)（当然也可能 \(x=w_i\) 它也不在 MST）。如果能求出这个区间，则最后计算答案就是容易的。

求这个区间可以考虑类似分治的结构！如果 \(w_i\lt mid\)，那当且仅当它存在于 \(mid+1\) 时刻的生成树上，他才可能在 \((mid,R]\) 这部分的 MST 里出现。同理如果 \(w_i\gt mid\)，那当且仅当它存在于 \(mid\) 时刻的生成树上，他才可能在 \([L,mid]\) 这部分的 MST 里出现。如果这条边同时在 \(L/R\) 的 MST 里出现，则它一定在 \(L\sim R\) 内都出现。如果一条边已经确定了在 \(L\sim R\) 内都出现，则在 dsu 上直接 merge 对应的两个点，并且这条边不再下传。

根据上述的事实，每条边递归的过程都像是在一个线段树上定位一个区间。那很显然一条边最多递归 \(O(\log q)\) 次。

由于使用了可撤销 dsu，所以复杂度即为 \(O(m\log q\log n)\)。