A Shuffle Hashing

给定一个串 $s$，随机打乱顺序后，询问是否可能是 $t$ 的子串。

暴力枚举 $t$ 的每个子串。

B A and B

智商没对上 T^T。

给定两个整数 $a,b$，第 $i$ 轮选一个数加 $i$，最小多少轮两数相同。

相当于将 $1,2,\dots,n$ 分配到两个数组中，一个和为 $s$ 另一个和为 $t$，且 $s+t=n(n+1)/2,s-t=|a-b|$。

C Berry Jam

D Segment Tree

给定 $n$ 条线段，两条线段之间连边当且仅当相交不包含，端点为 $1$ 到 $2n$ 的排列。

扫描线，枚举所有与给线段相交不包含的部分，并查集合并，如果出现环则停止。最多暴力合并 $n$ 次。

最后检查一下并查集完全联通。

E Tests for problem D

给定一张图，生成一下 D 题的线段。

递归地进行构造，对于子树 $u$，他的左端点为 $l_u$，右端点位置是 $r_u+deg_u+1$（$l_u,r_u$ 为递归参数）。

对于他的所有儿子结点，都与 $u$ 线段相交，并且兄弟结点依次包含，左端点会从右边 $r_u+deg_u$ 一直放到 $r_u+1$。

考虑右端点的限制，因为需要包含前面的兄弟的子树内结点，因此右端点需要往右偏移一段，即上一个兄弟的子树大小的两倍减一（减一由于根节点的左端点在 $u$ 的内部，$u$ 外部的点数为两倍减一）。

初始时，$l_1=r_1=1$。

F Cards

随机变量 $X$ 服从 $B(n,p)$，求 $E(X^k)$。

根据斯特林数展开

$$
E[X^k]=\sum_{i=0}^k S(k,i) E[X(X-1)\dots (X-i+1)]
$$

伯努利分布的 $i$ 次下降幂

$$
E[X(X-1)\dots (X-i+1)]=A(n,i)p^i
$$

带入得到答案。

参考资料：Factorial_moment 和 What is the kth factorial moment of the binomial distribution?。

考虑直接推式子，实际上等价于上面下降幂的推导过程
$$
E(X^k)=\sum_{i=0}^n {n \choose i} \frac{1}{m}^i(1-\frac{1}{m})^{n-i} i^k \
=\sum_{j=0}^{k} S(k,j) \sum_{i=0}^n {n \choose i} \frac{1}{m}^i(1-\frac{1}{m})^{n-i} A(i,j)
$$

题意

有一排长度为 $n$ 空白序列，有 $q$ 个时刻，每个时刻会将序列中的某一个位置填上数字 $h_i$，或者询问序列 $[l,r]$ 区间中与 $h$ 差的绝对值的最小值。

其中 $1 \le n \le 5 \cdot 10^5, 1 \le q \le 10^6$。

分析

有一个显然的做法，转化为四维偏序问题，时间复杂度 $O(q\log^3q)$，显然 T 飞了。

将询问离线，从左到右枚举右端点 $r$，如果位置 $r$ 曾经出现，则将 $r$ 插入数据结构，枚举这个点结束的询问进行回答。

令位置 $i$ 的出现时间为 $appear(i)$，对于询问 $(t,l,r,h)$，其中 $l,r,h$ 为输入，$t$ 为时间戳，我们需要在数据结构中查询权值小于等于 $h$ 的最大位置 $pos$，满足 $pos \ge l$ 且 $appear(pos) < t$，或者权值大于等于 $h$ 的最小位置，满足同样的条件。

为此，我们维护一棵权值线段树。

记权值线段树上的结点 $u$ 对应区间 $[l,r]$，在 $u$ 上维护出权值在 $[l,r]$ 范围内的所有位置。

查询时，如果 $[l,r]$ 包含于询问的值域区间，则检查当前区间内是否存在一个位置满足上述条件，如果满足则继续往下递归，直到叶子，否则剪枝。显然，如果一个区间不含合法点，会直接被剪枝，因此实际经过的结点仍然只有 $\log n$ 个。

但是，上述做法时间仍然难以接受，因为每个结点内需要使用一个数据结构进行维护，时间复杂度为 $O((n+q)\log^2n)$。

继续对其进行优化，我们注意到一个事实，在一个线段树结点内，如果 $i < j$ 且 $appear(i)>appear(j)$，那么 $i$ 一定不如 $j$ 优，因为 $j$ 更靠近右端点，出现时间也更加早。

因为我们可以直接线段树结点上，维护一个关于出现时间递增的单调栈，因为最多只有 $n\log n$ 个结点，因此插入的时间复杂度是 $O(n \log n)$。查询时，在该单调栈上二分一个位置 $pos$，使得 $pos \ge l$ 且 $appear(pos) < t$。

最终，时间复杂度为 $O(n\log q + q \log^2q)$。

问题

给定一个字符串 $s(1\le |s| \le 10^5)$ ，求最小的 $k$ ，使得存在 $s_1,s_2,\dots,s_k$ ，满足 $s_i(1\le i \le k)$ 均为回文串，且 $s_1,s_2, \dots ,s_k$ 依次连接后得到的字符串等于 $s$ 。

Div. 1 (久违的题解)。

A Feeding Chicken

给定一块 $r \times c$ 的空地，每个格子上可能放着一份猫粮，一共 $k$ 只猫，你现在需要为每只猫分配一个四联通块，使得每只猫得到的猫粮个数极差最小。

显然，可以尽量构造出一种平均的方案，即极差 $\le 1$。一个比较容易的方案是按照蛇形棋的顺序分配。

B Send Boxes to Alice

给定一个序列 $a$，每个位置有 $a_i$ 份猫粮，每次操作可以把一份猫粮从 $i$ 位置移动到 $i+1$ 或 $i-1$，你现在要最小化操作次数，使得整个序列的 $\gcd > 1$。

枚举总猫粮数的因子 $p$，计算使得最终 $\gcd$ 为 $p$ 的倍数时的最小操作次数。枚举每个前缀，计算在模 $p$ 意义下的前缀和 $sum$，代表前面这些位置还未被分配的个数，如果这些个数很少，可以把这些东西统一向后移动一格，否则个数很多时，可以把后面的东西移动到前边，即 $\min(sum,p-sum)$。

C Point Ordering

交互题，猜一个 $n$ 个点凸多边形的顺序，隐藏多边形的点编号不是按照顺时针或逆时针顺序，而是乱序，你现在需要用最多 $3n$ 次询问猜出这个顺序。

你有两种询问，第一种询问一个三角形的面积，第二种询问三个点 $i,j,k$ 的 $\vec{ij} \times \vec{ik}$ 的正负号。

第一步，用 $n$ 次询问找出多边形的一条边。随便选一对点，然后枚举其他点向某一边扩展。

第二步，求出这条边和其他所有点的三角形面积，找到面积最大的三角形的对应顶点。

第三步，确定其他点在上一步这个最大顶点的哪一侧。同一侧高度单调，面积也单调。

D Tree Queries

给定一棵无根树，有两种操作。

1. 输入 $v,d$，从 $n$ 个点中等概率选择点 $r$，然后将所有满足到 $r$ 的路径经过点 $v$ 的点 $u$，权值加上 $d$。

2. 询问 $v$ 的点权期望。

简单推一下修改的贡献，点 $u$ 的期望加 $d$，考虑其每个邻居（包括父亲）的子树大小 $siz$，这个子树内的点权加上 $(n-siz)/n$。

然后一个显然的做法呼之欲出，按度数大小分块，小度数线段树维护，大度数暴力打标记，时间复杂度 $O(n\sqrt{n \log n})$。

修改的瓶颈在于不能枚举一个点的所有度数。考虑树剖，只修改重儿子对应子树，和询问点的子树外的所有点。询问时，只需要计算根到询问点路径上所有轻边带来的贡献，显然只有 $\log n$ 条轻边，时间复杂度 $O(n\log n)$。