总结
一堆知识点忘了导致什么都写不了
- T1 不会写欧拉回路，改罚。
- T2 卡到 0/1 分数规划的部分，赛时推二分做法没搞出来。
- T3 暴力。为什么不考虑退火？
- T4 暴力和部分分都是特别好想的，由于前面花的时间过长没来得及写。
很多 板子/trick 都要复习一遍。
题解
card
考虑每一个串 \(S\) 的内部，1 之间的间隔必须恰为 \(m\)。将前后缀 1 的位置处理出来。建立点 \(0\sim m-1\)，在 \((b-j)\) 和 \((b-j+\lvert S\rvert)\) 之间连有向边，一个从 0 考试到 0 结束的欧拉回路就是一个合法拼接顺序，问题转化为找最小字典序欧拉回路。
时间复杂度为 \(\mathcal O(\sum\left\lvert S_i\right\rvert+m)\)。
market
最坏情况相当于 \(w_0=r_0,\forall i>0,w_i=l_i\)，那么问题转化为找到一个集合 \(S\) 让期望最大。
式子为
\[\frac{\sum\limits_{i\in S}w_iv_i}{w_0+\sum\limits_{i\in S}w_i} \]考虑二分，判断期望是否不小于 \(p\)，化简有
\[\sum_{i\in S}w_i\left(w_i-p\right)\geq w_0p \]可以二分计算单次询问的答案。
多次询问在值域线段树上二分即可。时间复杂度为 \(\mathcal O(m\log V)\)。
dating
先考虑一维问题。发现取中位数是最优的，因为 \(x,y\) 两个维度互相独立，所以分别取中位数计算即可。
根据上面的启发，可以猜想目的地一定由某个 \(x_i,y_j\) 组成。因此目的地的范围缩小到 \(\mathcal O(n^2)\)，枚举目的地，可以做到 \(\mathcal O(n^3)\) 或 \(\mathcal O(n^3\log n)\)。
令目的地坐标为 \((a,b)\)。固定 \(b\) 的值，从小到大扫描 \(a\) 的值，随着 \(a\) 的变化，点 \(x_i,y_i\) 到 \((a,b)\) 的距离只会在 \(a\geq x_i\) 时切换一次表达式，即 \(\lvert y_i-b\rvert+\lvert x_i-a\rvert\)。将 \(x_i<a\) 的 \(i\) 放进集合 \(L\)，其余放进集合 \(R\)，那么 \(L,R\) 固定的时候只需分别找最小的 \(k_1,k_2\) 个元素，使得 \(k_1+k_2=k\) 且总和最小，动态维护 \(L,R\)。
具体地，用堆维护 \(L,R\) 集合并保留当前方案最优的 \(k_1,k_2\)，把 \(a\) 转移的过程中，若有 \(c\) 个点 \(L\to R\)，那么 \(k_1,k_2\) 的改变量是 \(\mathcal O(c)\) 的。时间复杂度为 \(\mathcal O(n^2\log n)\)。
string
考虑 \(P\) 的出现情况，令插入后 \(S=L+B+R\)。
- \(\lvert B\rvert>\lvert P\rvert\)。
-
\(P\) 完全包含于 \(L/B/R\)，可以直接 \(kmp\) 预处理。
-
\(P\) 跨过 \(L,B\) 分界线，那么要找的 \(x\) 满足 \(B\) 的长度为 \(x\) 的前缀等于 \(P\) 的长度为 \(x\) 的后缀。
建立 \(P\) 的 fail 树。把所有 \(\lvert P\rvert -x\) 打上标记，那么在 \(i\) 后插入 \(B\) 的匹配数量就是 fail 树上 \(A[:i]\) 匹配到的最长前缀结点的祖先的标记数量和。\(B,R\) 分界线翻转字符串再做一次即可。
- \(\lvert B\rvert\leq\lvert P\rvert\)
-
多了一种跨过两个分界线的情况。
找出所有 \(B\) 在 \(P\) 中匹配位置 \([x+1,x+\lvert B\rvert]\)，然后转化为统计有多少位置的 \(i\) 满足
\[A[i-x+1,i]=p[:x]\and A[i+1,i+\lvert P\rvert-\lvert B\rvert]=p[x+\lvert B\rvert+1:] \]求出 \(A[:i]\) 匹配的最长前缀长度 \(u\) 和 \(A[i+1:]\) 匹配反串的最长长度 \(v\)，那么就是求有多少个 \(x\) 满足 \(x\) 在正串 fail 树上是 \(u\) 的祖先且 \(\lvert P\rvert-\lvert B\rvert-x\) 在反串 fail 树上是 \(v\) 的祖先。
于是转化成为一个二维数点，时间复杂度为 \(\mathcal O(n\log n)\)。