面基之路
idea from he_____he, data,solution from hehezhou
算法一
首先需要注意到最重要的结论：题意等价于所有人走到同一位置所需最短时间。证明只需要让所有网友在面基成功之后跟随 hehe 蚤行动即可。
对于子任务 $1$，不难发现最终汇合点一定在某个点上或某条边正中。如果汇合点在边的非中点位置，移动到端点或中点，一定有一种更优。
只需要求出会合到每一个位置的答案即可。时间复杂度 $O(k(n\log n+m))$，期望得分 $30$。
算法二
对于子任务 $2$，不难发现 $T$ 就是最远点距离除以二。
首先会合时间不可能更早，因为 $1$ 和最远点的距离达到了 $2T$。而只需要让所有人移动到 $1$ 和最远点的带权中心就是一组合法方案。
算法三
首先汇合点在点上的情况是简单的，考虑汇合点在边上的情况。
定义边的左右侧是它的两个端点，枚举每个人是从哪一侧进入这条边的，每侧只需要考虑最晚进入的人即可，答案不难计算。
时间复杂度 $O(m2^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\geq j)$ 表示是否存在一个合法括号前缀使得它和 $S[1:j]$ 可以合并出 $T[1:i]$。考虑转移，有以下两种转移：
$f_{i,j}\to f_{i+1,j+1} (S_{i+1}=T_{j+1})$
$f_{i,j}\to f_{i+1,j} (a_{i+1}\geq 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。$dp_{i,j,V}$ 表示已经填好了 $T$ 的前 $i$ 位，$f_{i,k}$ 等于 $V$ 的第 $k$ 位，$a_i=j$，转移按照上述转移式对应转移即可。
时间复杂度 $O(2^nn(n+t)^2)$，可以通过子任务 $1,2,4$，期望得分 $45$。
如果省略无用状态，可以额外通过子任务 $3$，期望得分 $60$。
算法二
我是打表大师！我打表转移找到规律了！
规律就是：对于固定的 $S,i,j$，非零 $dp_{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$。
算法三
我喜欢严谨做题！我要证明这个结论！
先注意到几个重要性质：
两个合法括号前缀合成的串一定是合法括号前缀。考虑定义不难得出。
若 $f_{i,j}=1$，则有 $a_i\geq b_j$。考虑转移或考虑 dp 意义均不难得出。
考虑当前已经匹配了前 $i$ 位，$a_i$ 确定，并且可以匹配的 $S$ 的最长前缀是 $k$，考虑在算上第 $i+1$ 位 $x$ 以后，可以匹配的 $S$ 最长前缀：
$S_{k+1}=x$：显然新的最长前缀是 $k+1$。
否则若 $x=0$（即左括号） 或 $a_i\gt b_k$：那么 $a_{i+1}\geq b_k$，新的最长前缀是 $k$。
否则有 $x=1$（即右括号）且 $a_i=b_k$，这种情况较为复杂。先给出结论：新的最长前缀 $k'=\max_{t\lt k,b_{t}\lt b_k} t$。第一步证明这个前缀是合法的：不难发现 $S[k'+1,k]$ 是一个合法括号前缀，否则就存在更大的位置满足 $b_{t}\lt b_k$。首先证明 $f_{i,k'}=\text{true}$，只需要将 $f_{i,k}$ 对应的合法方案中，$S[k'+1,k]$ 对应的子序列划为合法括号前缀部分，由性质 $1$ 我们就得到了 $f_{i,k'}$ 对应的一组方案，因此 $f_{i,k'}=\text{true}$ 且可以转移到 $f_{i+1,k'}$。然后我们证明不存在更长的前缀 $x$ 可以匹配 $T$ 的前 $i+1$ 个位置，否则 $b_x\geq b_k\gt a_i-1=a_{i+1}$，与性质 $2$ 矛盾。
至此我们证明了这个结论。
期望得分 $100$ 分。
稳健型选手
idea,data,solution from xyr2005
谢罪！谢罪！谢罪！谢罪！谢罪！
算法一
我会暴力！状压当前剩下哪些数，复杂度 $O(n2^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 n2$ 且 $\forall i\in[1,n],\sum_{j=1}^ib_j\le \lceil\frac i2\rceil$
我们可以 $dp_{i,j}$ 表示考虑了前 $i$ 个元素，总共取了 $j$ 个，和最大是多少，转移时保证 $j\le \lceil\frac i2\rceil$ 即可。
复杂度 $O(n^2q)$ ，可以通过子任务一二获得 $20$ 分。
算法三
考虑优化算法二。
可以使用反悔贪心，从前往后扫，维护 QAQ 蚤取了哪些数。
每次加进来两个数 $x,y$，首先假设 $x,y$ 都取了，这时候取了的数的总数是 $\frac{i}2+1$，再删掉一个最小的已经取了的数。
用堆维护上述过程，复杂度 $O(nq\log n)$ ，可以通过子任务一二三获得 $40$ 分。
算法四
我们发现，前 $2i$ 个取了 $\le i$ 个 $\Leftrightarrow$ 后 $2i$ 个取了 $\ge i$ 个。
于是算法三也可以倒着来做，从后往前扫，维护 QAQ 蚤没取哪些数。
每次加进来两个数 $x,y$，首先假设 $x,y$ 都没取，这时候取了的数的总数是 $\frac i2-1$，再取一个最大的没取的数。
于是我们现在可以在 $O(\log n)$ 复杂度内，向前加两个数，向后加两个数，使用不删除莫队维护。
复杂度 $O(n\sqrt q\log n)$，可以通过子任务一二三四获得 $70$ 分。
使用压位trie/veb 维护，复杂度 $O(n\sqrt q\log_wn)/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|$ ， $\max S< \min T$，$S$ 是一段前缀，$T$ 是一段后缀。于是我们二分 $k$ ，找到最大的 $k$ 满足左边第 $k$ 小 $<$ 右边第 $k$ 大，然后就知道了 $S,T$，于是做完了。
复杂度 $O((n+q)\log^2n)$，可以通过子任务一二三四五获得 $100$ 分。
鄂公网安备 42010202000505 号