面基之路

idea from he_____he, data,solution from hehezhou

算法一

首先需要注意到最重要的结论：题意等价于所有人走到同一位置所需最短时间。证明只需要让所有网友在面基成功之后跟随 hehe 蚤行动即可。

对于子任务 $1$，不难发现最终汇合点一定在某个点上或某条边正中。如果汇合点在边的非中点位置，移动到端点或中点，一定有一种更优。

只需要求出会合到每一个位置的答案即可。时间复杂度 $O(k(n\log n+m))$，期望得分 $30$。

算法二

对于子任务 $2$，不难发现 $T$ 就是最远点距离除以二。

首先会合时间不可能更早，因为 $1$ 和最远点的距离达到了 $2T$。而只需要让所有人移动到 $1$ 和最远点的带权中心就是一组合法方案。

算法三

首先汇合点在点上的情况是简单的，考虑汇合点在边上的情况。

定义边的左右侧是它的两个端点，枚举每个人是从哪一侧进入这条边的，每侧只需要考虑最晚进入的人即可，答案不难计算。

时间复杂度 $O(m{2}^k+kn\log n)$，期望得分 $85$。

算法四

由于每侧只需考虑最晚进入的人，对于每条边，一定存在一种最优方案，将所有人按照到达左侧时间排序后，一个前缀从左侧进入而剩余的后缀从右侧进入。

时间复杂度 $O(kn\log n+mk\log k)$，期望得分 $100$。

bonus

如果 hehe 蚤的速度是 $a$ 而网友们的速度是 $b$，这个问题又该怎么解决呢？

这个问题会在数日后被加入 uoj 题库。

机器人表演

idea, data from djq_cpp, solution from hehezhou

本题改编自 CPIdeas (https://codeforces.com/blog/entry/104374) 生成的题面：

You are given a string S consisting of 0 and 1. You can do the following operation on S any number of times: Choose a non empty substring T of S, and append 0 to the beginning and 1 to the end of T. The resulting string will be S again. How many different strings will S be after the operations? Find the count
modulo 998244353.

算法一

我会状压！

接下来令左括号对应 0，右括号对应 1，合法括号前缀是满足任意前缀 0 不少于 1 的串，合法括号串是 01 个数相等的合法括号前缀，$A$ 和 $B$ 可以合并出 $C$ 等价于 $C$ 可以被划分为两个子序列分别等于 $A$ 和 $B$。

首先我们考虑给定一个串 $T$，判断其是否可以通过合并串 $S$ 和某个括号串得到。这可以在 $O(|S||T|)$ 的时间内完成，具体的，设 $f_{i,j}(i\ge j)$ 表示是否存在一个合法括号前缀使得它和 $S[1:j]$ 可以合并出 $T[1:i]$。考虑转移，有以下两种转移：

1. $f_{i,j}\to f_{i+1,j+1}(S_{i+1}=T_{j+1})$

2. $f_{i,j}\to f_{i+1,j}(a_{i+1}\ge b_j)$

其中若 $T_i$ 是左括号，$a_i=a_{i-1}+1$，否则 $a_i=a_{i-1}-1$，$b$ 是定义在 $S$ 上的类似序列。第一种转移显然正确，第二种转移是因为：所有合并方案中，合法括号前缀的两种数量都是固定的。

如果 $f_{|T|,|S|}=\text{true}$ 且 $a_{|T|}=b_{|S|}$，则串 $T$ 可以通过合并串 $S$ 和某个括号串得到。

对应这个 dp，我们可以列出求解原题的状压 dp。$d{p}_{i,j,V}$ 表示已经填好了 $T$ 的前 $i$ 位，$f_{i,k}$ 等于 $V$ 的第 $k$ 位，$a_i=j$，转移按照上述转移式对应转移即可。

时间复杂度 $O(2^{n}n(n+t{)}^2)$，可以通过子任务 $1,2,4$，期望得分 $45$。

如果省略无用状态，可以额外通过子任务 $3$，期望得分 $60$。

算法二

我是打表大师！我打表转移找到规律了！

规律就是：对于固定的 $S,i,j$，非零 $d{p}_{i,j,V}$ 两个后继状态的 $V$ 的最高位只和当前 $V$ 的最高位有关。

可以只记录 $V$ 的最高位，状态数减少为 $O(n(n+t{)}^2)$。

时间复杂度 $O(n^2(n+t{)}^2)$，进一步得到转移规律可以做到 $O(n(n+t{)}^2)$，期望得分 $75\sim 100$。

算法三

我喜欢严谨做题！我要证明这个结论！

先注意到几个重要性质：

1. 两个合法括号前缀合成的串一定是合法括号前缀。考虑定义不难得出。

2. 若 $f_{i,j}=1$，则有 $a_i\ge b_j$。考虑转移或考虑 dp 意义均不难得出。

考虑当前已经匹配了前 $i$ 位，$a_i$ 确定，并且可以匹配的 $S$ 的最长前缀是 $k$，考虑在算上第 $i+1$ 位 $x$ 以后，可以匹配的 $S$ 最长前缀：

1. $S_{k+1}=x$：显然新的最长前缀是 $k+1$。

2. 否则若 $x=0$（即左括号） 或 $a_i>b_k$：那么 $a_{i+1}\ge b_k$，新的最长前缀是 $k$。

3. 否则有 $x=1$（即右括号）且 $a_i=b_k$，这种情况较为复杂。先给出结论：新的最长前缀 $k^{\prime }=\underset{t<k,b_t<b_k}{max}t$。第一步证明这个前缀是合法的：不难发现 $S[k^{\prime }+1,k]$ 是一个合法括号前缀，否则就存在更大的位置满足 $b_t<b_k$。首先证明 $f_{i,k^{\prime }}=\text{true}$，只需要将 $f_{i,k}$ 对应的合法方案中，$S[k^{\prime }+1,k]$ 对应的子序列划为合法括号前缀部分，由性质 $1$ 我们就得到了 $f_{i,k^{\prime }}$ 对应的一组方案，因此 $f_{i,k^{\prime }}=\text{true}$ 且可以转移到 $f_{i+1,k^{\prime }}$。然后我们证明不存在更长的前缀 $x$ 可以匹配 $T$ 的前 $i+1$ 个位置，否则 $b_x\ge b_k>a_i-1=a_{i+1}$，与性质 $2$ 矛盾。

至此我们证明了这个结论。

期望得分 $100$ 分。

稳健型选手

idea,data,solution from xyr2005

谢罪！谢罪！谢罪！谢罪！谢罪！

算法一

我会暴力！状压当前剩下哪些数，复杂度 $O(n{2}^n+q)$，可以通过子任务一获得 $10$ 分。

算法二

我会观察性质！先考虑单组询问。

首先，如果 $n$ 是奇数，那 QAQ 蚤会在最后一次取最后一个数，转化成前 $n-1$ 个数的问题，容易发现这是最优的。所以我们可以假设 $2\mid n$。

考虑 QAQ 蚤取的数的集合要满足什么条件。令序列 $b_i=0/1$ 表示这个位置最终 QAQ 蚤 取不取。

那 QAQ 蚤可以贪心每次取 $b_i=1$ 的最靠前的那个，那么可以发现 一个 $b$ 合法当且仅当 $\sum b_i=\frac{n}{2}$ 且 $\mathrm{\forall }i\in [1,n],\sum _{j=1}^i{b}_j\le \lceil \frac{i}{2}\rceil$

我们可以 $d{p}_{i,j}$ 表示考虑了前 $i$ 个元素，总共取了 $j$ 个，和最大是多少，转移时保证 $j\le \lceil \frac{i}{2}\rceil$ 即可。

复杂度 $O(n^{2}q)$ ，可以通过子任务一二获得 $20$ 分。

算法三

考虑优化算法二。

可以使用反悔贪心，从前往后扫，维护 QAQ 蚤取了哪些数。

每次加进来两个数 $x,y$，首先假设 $x,y$ 都取了，这时候取了的数的总数是 $\frac{i}{2}+1$，再删掉一个最小的已经取了的数。

用堆维护上述过程，复杂度 $O(nq\log n)$ ，可以通过子任务一二三获得 $40$ 分。

算法四

我们发现，前 $2i$ 个取了 $\le i$ 个 $\iff$ 后 $2i$ 个取了 $\ge i$ 个。

于是算法三也可以倒着来做，从后往前扫，维护 QAQ 蚤没取哪些数。

每次加进来两个数 $x,y$，首先假设 $x,y$ 都没取，这时候取了的数的总数是 $\frac{i}{2}-1$，再取一个最大的没取的数。

于是我们现在可以在 $O(\log n)$ 复杂度内，向前加两个数，向后加两个数，使用不删除莫队维护。

复杂度 $O(n\sqrt{q}\log n)$，可以通过子任务一二三四获得 $70$ 分。

使用压位trie/veb 维护，复杂度 $O(n\sqrt{q}{\log }_{w}n)/O(n\sqrt{q}\log \log n)$，期望得分 $70$ 分，实际得分 $100$ 分。

算法五

继续优化算法四。

使用分治，用主席树对 $[l,mid]$ 的每个后缀维护取了哪些数，对 $[mid+1,r]$ 的每个前缀维护没取哪些数。

然后考虑合并 $[x,mid]$ 和 $[mid+1,y]$，那会发生的变化是，$[x,mid]$ 中一些取了的数现在不取了，$[mid+1,y]$ 中一些没取的数现在取了。假设 $[x,mid]$ 中发生变化的数的集合是 $S$，$[mid+1,y]$ 中发生变化的数的集合是 $T$，那么 $|S|=|T|$ ， $maxS<minT$，$S$ 是一段前缀，$T$ 是一段后缀。于是我们二分 $k$ ，找到最大的 $k$ 满足左边第 $k$ 小 $<$ 右边第 $k$ 大，然后就知道了 $S,T$，于是做完了。

复杂度 $O((n+q){\log }^{2}n)$，可以通过子任务一二三四五获得 $100$ 分。