堪堪能接受的一场。前两题一个半小时左右做完，后两题实在没什么思路，打完所有可能的暴力之后跑路了。
他们告诉我题目名称可以从上到下连起来读。
可以发现，假若同时有 $\newcommand{\bigO}{\operatorname{O}}a_i,a_{i+1}$ 和 $a_{i+1},a_{i+2}$ 都可合并，则取 $a_i, a_{i+2}$ 中任意一个合并之后，质因数集合总是变为原来的超集，另外一项仍可合并。
故而可以贪心合并所有合法的邻项，最终检查是否仅剩一项即可。注意到 $[1,700]$ 仅含 $125$ 个质因数，故可以用 std::bitset 保存每一项的质因子集合。复杂度 $O(\frac{128n}{\omega})$。赛时竟然还开了数组保存每个质因子的实际指数！ （更多…）
恕我语文不好，实在不晓得用何种词汇来描述看到下文的感受：
此比赛为正常的提高组难度，
甚至可以用来作为普及组模拟赛。
请选手 AK 后不要大声喧哗，以免影响他人 AK。
尤其是这套题的出题人是张隽铠的情况下。当然，OI 圈风气本就如此，我也不好过多评价。No comment.
T1 还算顺利，半小时左右搞定。T2 是大分类讨论，足够恶心人，但好在有相当可观的可以通过暴力与观察拿到的部分分。T3 猜测与线性基相关，但没有相应知识储备，暴力跑路。
T4 就……反正出题人开心就好。到现在都没人改出来。
依次往某个子序列中添加元素。则添加的元素必然成为新的最大值/最小值之一，否则违背题意。
于是枚举子序列首元素，将以其开头的严格上升子序列数与严格下降子序列数相乘即可。使用树状数组转移即可。复杂度 $\operatorname{O}(n \log n)$。 （更多…）
签到题看了半个小时；T2 没有考虑到只需要包含最优解即可，非要确定另一多余状态，只拿了部分分。
T3 只会考虑 “$x, y$ 的公共祖先中含有 $l$ 的概率”，不会高效计算“当二者的 $\operatorname{lca}$ 恰为 $l$ 时”的期望/概率与总长之和的乘积，仍然只有暴力分。
T4 无思路。
可以简单用归纳法证明，仅有所有管道中通行时间最大的会阻塞进度，是为两数据包到达终点的时间间隔。算出首个数据包到达的时间再将前者相加即可。
第一反应是类似笛卡尔树一样，在区间上依次合并区域最大值并计算贡献。$n \leq 300$ 似乎也在暗示这是一个区间 DP。
设 $f(l,r,\text{mx})$ 表示“考虑完成区间 $[l,r]$ 内所有贡献，且最大值恰好为 $\text{mx}$”的最大权值和。转移时从小到大枚举最大值 $\text{mx}=V_{i,j}$，枚举包含它的区间，尝试转移 $$f(l,r,\text{mx})\leftarrow f(l,i-1,\text{mx}’)-C_{i,j}+\text{mx}\cdot \operatorname{calc}(l,r,i)+f(i+1,r,\text{mx}”)$$，其中 $\operatorname{calc}(l,r,i)$ 计算 $\sum_{l’=l}^{i}\sum_{r’=i}^{r}Q_{l’,r’}$，可以由二维前缀和实现。稍加演算会发现，这样转移不会重复计算贡献。时间复杂度 $\operatorname{O}(\sum K_{i}N^2)$。 （更多…）
$T \leq 1000$ 组数据。给定 $n, a, b, c\in [0, 10^9], k_1,k_2\in [0, 10], k_1+k_2\leq 10$，求取
$$
\sum_{x=0}^{n}x^{k_1}\left\lfloor\frac{ax+b}{c}\right\rfloor^{k_2}
$$
当 $k_1=0,k_2=1$ 时，是为一般类欧几里得算法的模板。上述链接亦给出了 $k_1=0,k_2=2; k_1=1,k_2=1$ 时的解法。
当 $k_2=0$ 时，该式退化为 $\sum_{x=0}^{n}x^{k_1}$，即 $k_1$ 次的等幂求和。有一个模糊的结论：
设 $n$ 为正整数。则$k$ 次的等幂求和，$\sum_{x=0}^{n}x^k$，是一个关于 $n$ 的 $k+1$ 次多项式。
该结论来源于 zyw 学姐多项式专题所选题目 BZOJ 3453 – tyvj 1858 XLkxc。之所以说模糊，是因为该多项式的系数是已知的。不过我们仍然可以暴力计算 $k+2$ 个点以插值。
再观察 OI-Wiki 上对于 $k_1+k_2\leq 2$ 时的解法。在求取
$$h(n,a,b,c)=\sum_{x=0}^n\left\lfloor\frac{ax+b}{c}\right\rfloor^2$$时采取了如下转化：
$$\begin{aligned}
x^2&=2\times \frac{x(x+1)}{2}-x\\
&=2\left(\sum_{y=1}^{x}y\right)-x\end{aligned}
\quad\begin{aligned}
\Longrightarrow\sum_{x=0}^n\left\lfloor\frac{ax+b}{c}\right\rfloor^2=\sum_{x=0}^n2\left(\sum_{y=1}^{\left\lfloor\frac{ax+b}{c}\right\rfloor}y\right)-\left\lfloor\frac{ax+b}{c}\right\rfloor\\
\end{aligned}$$
这样一来，由于 $y$ 是一个线性算子，在 $ax+b\geq yc$ 时都有 $y$ 向总和贡献，于是我们可以应用类似于 $k_1=0,k_2=1$ 时的方法转化贡献。这个过程对 $k_2$ 作了降次。
那么，对于更高次项，有无办法采取同样的办法转化呢？是否可以设计一些转化，使得要求取的函数 $f(\cdots,k_1,k_2)$ 能够由 $f(\cdots,k_1-?,k_2-?)$ 推出呢？ （更多…）
策略和思维活跃度都极其糟糕的一个上午。
那么“在能力不足以保证完成更多正解”的情况下获取尽可能多的暴力分从而提高总分下限，又被重新提上议程。切记切记。
思维广度待进一步提升。
发现了是平面图，想到了数据结构与区间可达性，就是没把俩概念结合起来。
由题目保证的“两边不交”性质，可以发现，若不考虑无法从任何一个左侧点到达的右侧点，如有 $(A,y_1),(A,y_2),y_1<y_2$ 均可从 $(0,y_0)$ 达，则若有 $(A,y_3),y_3\in [y_1,y_2]$，则其必然亦可达。
缩点后拓扑排序求出每个连通块能到达的右侧点 $y$ 坐标区间即可。复杂度 $\operatorname(O)(n\log n+m)$。
联想到了 HDU “杭电杯”超级联赛（3) Spanning Tree Game 钦定最小生成树，按边权从小到大依次加边的动规方法。
可惜这是最小瓶颈生成树。
给定 $A+B$ 个本质相同的随机变量，在 $\{1,2,\cdots,6\}$ 内等概率取值。若两个随机变量 $a \in A, b \in B, a=b$，则二者相消为 $0$。求在所有可能的消除完成后，存在 $a \leq t, a \in A, t \in \{1,2,\cdots,6\}$ 的概率。对 $10^9+7$ 取模。
令 $c_i$ 表示随机结果中数值为 $i$ 的 $A$ 内变量数；$d_i$ 同理。原题意可以转化为求出 $1-P(\text{不存在小于等于}t\text{的}a)$。由概率的定义，我们可以用能造成后者局面的方案总数除以 $6^{A+B}$ 既是结果。换句话说，原命题的否命题应当满足 $\forall i \in \{1,2,\cdots,t\}, c_i \leq d_i$。
又因为这些随机变量本质相同，则由“可重集的排列数”得，若有确定的 $c_{1},c_2,\cdots,c_6, \sum_{i=1}^{6}c_i=A$，则掷出对应结果的方案数为
$$\dbinom{A}{c_1}\dbinom{A-c_1}{c_2}\cdots\dbinom{A-\sum_{i=1}^{5}c_i}{c_6}=\dfrac{\color{blue}A!}{\prod_{i=1}^{6}c_i!}$$ （更多…）
AtCoder Regular Contest 148 D – mod M Game
一个非常显然的 Bob 的必胜局面是：对于任意 $x\in \{0,1,\cdots,M-1\}$，在这 $2N$ 个数中的出现次数均为偶数。由此 Bob 可以选择与 Alice 上一轮选的相同的数而获胜。
那……其他局面就一定是 Alice 必胜么？
我们只依靠该结论交一份代码。不出意料，没有通过。不过它只错了两成的测点！看来大体方向是正确的。
CodeForces Round #502 Problem G – The Tree
这是lty数据结构专题里唯二自己做出来的题目中的一道。
如果不包含“将 $x$ 的子树全部染白”的操作，应当怎样处理？
题目所给操作可以这样转述：令 $x$ 为本次染色操作的节点。若 $x$ 为白色，则立刻染黑并退出；否则我们找到其子树中的，与 $x$ 相连的黑色连通块，则对于每个连通块底部节点，若其不是叶子节点，我们将其儿子染黑。
由于本题的树没有特殊性质，且将来加入回退操作，故而难以维护整个连通块以及其叶子节点。因此，我们可以从“在何种情况下，节点 $x$ 被染黑”的方向考虑。
显然，只有从在 $x$ 到根的路径上的节点开始的染色操作，才可能波及到 $x$。假如最终 $x$ 被染黑的一瞬，它被包含在了以 $\text{comprt}$ 为根的连通块中。令链 $\langle\text{comprt}, x\rangle$ 为 $\left\{x_1,x_2,\dots,x_n \right\},x_1=\text{comprt},x_n=x$，那么自然想到，一种一定合法的染色序列是 $\{y_1,y_2,\cdots,y_n\}$，其中有 $\forall k \in [1, n] \cap \mathbb{Z},y_k \in \{x_1,\cdots,x_k\}$，也即我们每一步都在该连通块内部，并将连通块的最大深度推进一层。
这种序列确实合法（它是充分条件），但这真的是 $x$ 被染黑的必要条件么？ （更多…）