id0

[WTF2019E]. e

题意：

$n$ $S$ 形如 X--X-X-X--X-X，其中 X- $f(n,S)$ $n$ $S$ $|\mathrm{endpos}|$ $\lim_{n\rightarrow+\infty}{\frac{f(n,S)}n}$ 。
$p+\frac qe +\frac{r}{e^2}$ $p,q,r$ $998244353$ $|S|\le 1000$ 。

题解：

$S=X$ $n$ $[0,1]$ $x_{1\sim n}$ $x_i$ $i$ $i-1$ $i+1$ $i$ 处放一个人。

$x$ $i$ $x_i$ $x_i$ 右侧的极长下降字串的长度为偶数。而左侧为偶数的概率和右侧为偶数的概率彼此独立，我们不妨单独计算左侧为偶数的概率，容斥一下：

\begin{equation}\begin{aligned} f(x_i)&=1-P(x_{i-1}<x_i)+P(x_{i-2}<x_{i-1}<x_{i})-P(x_{i-3}<x_{i-2}<x_{i-1}<x_{i})+\cdots\\ &=1-x_i+\frac{x_i^2}{2!}-\frac{x_i^3}{3!}+\cdots\\ &=e^{-x_i} \end{aligned}\end{equation}

$\lim_{n\rightarrow+\infty}{\frac{f(n,X)}n}=\int_{0}^1e^{-2x}dx=\frac 12-\frac 1{2e^2}$ 。

$dp_i$ $dp_i$ $x_i$ $\mathrm{const\ } x_i$ 结尾的概率是多少。不难发现只需要用一个 bool 记录下左边的奇偶性，一个 boolbool $dp$ $P(x)+\frac{Q(x)}e+k\cdot e^{-x}$ $O(|S|^2)$ 。

[AGC056 E] Cheese

题意：

$n$ $[0,n)$ $\forall i\in[0,n)$ $i+0.5$ $n-1$ $\frac{A_i}{\sum A_i}$ $i$ $x$ $\frac 12$ $n\le 40$ 。

题解：

直接做的话会发现，绕不开一个对状态 / 出现顺序之类的东西的枚举。然后陷入困境……这是做这类描述一个随机过程的题的常见经历。类似上一题，我们重新刻画这个随机的过程，使得这个过程可以拆分或者可以更好地描述。（下面的内容参考了 OneInDark）。

把每只奶酪的活动过程分解为多个判定：

\operatorname{check}(cheese_i,mouse_i)= \left\{ \begin{aligned} &\mathrm{probability}\frac 12 \rightarrow Eat\ it!\\ &\mathrm{probability}\frac 12 \rightarrow \operatorname{check}(cheese_i,mouse_{i+1}) \end{aligned} \right.

$\operatorname{check}(x,y_1)$ $\operatorname{check}(x,y_2)$ $\operatorname{check}(x_1,y)$ $\operatorname{check}(x_2,y)$ $cheese$ 。

$i$ $dp[][][]$ $dp[i-1][][]$ $i$ $O(N\cdot N^4)$ 。

[CF1685E] The Ultimate LIS Problem

题意：

$2n+1$ $q$ $k$ $k$ $LIS$ $n$ $k=-1$ $n\le 10^5$ 。

题解：

乍看很不科学，但是一个思路是：试一试一些的构造，对于这个构造下合法的就直接输出，否则以其不合法条件为新增的前提条件，继续做一道弱化版的本题，知道条件足够强为止。

$n+1$ $0$ $n+1$ $1$ $-1$ $LIS$ $\ge n+1$ $n+1$ $n+1$ $1$ 的结论，就矛盾了。

$LIS$ $n+1$ $n+1$ $n+1$ $n+1$ $n+1$ $n+1$ $n+1$ $1,2,\cdots,n+1$ $n+1,n+2,\cdots,2n+1$ $O(n\log n)$ 。

[CF1458F] Range Diameter Sum

题意：

$n$ $1$ $\sum_{l< r}\max_{l\le u<v\le r}{\operatorname{dis}(u,v)}$ $n\le 10^5$ 。

题解：

$(O,r)$ $O$ $r$ 为半径的一个树上圆覆盖。为了避免圆心出现在边中点的情况，令每条边的中间都加一个虚点。

$\max_{u,v\in S}\operatorname{dis}(u,v)$ $S$ $c(S)$ $S$ $T\subseteq c(S)\Rightarrow c(T)\subseteq c(S)$ 。所以可以以任意一个顺序进行最小覆盖圆的合并从而求出直径。不难定义最小覆盖圆的加法：

\odot (O_1,r_1)+\odot(O_2,r_2)= \left\{ \begin{aligned} &(O_2,r_2) &(O_1O_2+r_1\le r_2)\\ &(O_1,r_1) &(O_1O_2+r_2\le r_1)\\ &\left(\operatorname{go}\left(O_1,O_2,\frac 12(O_1O_2-r_1+ r_2)\right),\frac 12(O_1O_2-r_1+ r_2)\right)&(\mathrm{else}) \end{aligned} \right.

$\operatorname{go}(u,v,w)$ $u$ $v$ $w$ 步到达的点。

$\mathrm{const}\ L\in{l,mid}$ $r$ $3$ $\odot[L,mid]$ $\operatorname{go}$ $\odot[L,mid]$ $S$ $u$ $O(n\log^2{n})$ $O(n\log^3{n})$ 的“不咋平衡二叉树”并拿下最优解。注：一直以来没有注意的一个细节：pushup 之前一定要 pushdown。

[CF1672G] Cross Xor

题意：

$n\times m$ 01 $(i,j)$ 和与它同行或同列的所有格子一起取反。
01? $n\times m$ 矩阵，问有多少种将 ? 替换为 0 或 1 的方案使得此矩阵可以通过上述操作消成全 0 的矩阵。

题解：

$n$ $m$ $y$ $x_{i,j}$ $(i,j)$ $y$ $x$ $n\times m$ $y$ $S$ $S$ $x$ $0$ $0$ $0$ $n\times m$ ，我们只要找到一个包含其一个基的子集即可。不难发现如下形状的方程组即可满足要求：

0001000\\ 0001000\\ 1110111\\ 0001000\\ 0001000\\ 0001000\\ 0001000

$X$ $n+m$ ? $n+m-$ $0$ $\log_2$ 每个变量均恰好存在于两个方程中，那么这两个方程一定同时处于子集中或者子集外 $0$ $2$ $O(nm)$ 。

[CF1684H] Hard Cut

题意：

01 $2$ $\sum n\le 10^6$ 。

题解：

$1$ $1$ $2$ 的幂，贪心判断是否有解，直到有解为止。不知道为什么评 3400 且 djq 等一众神仙居然没过此题（）。

[CF1687F] Koishi's Unconscious Permutation

题意：

$s=\sum \limits_{i=1}^{n-1}[p_i+1=p_{i+1}]$ $[x]=1$ $x$ 成立。
$\forall k \in [0,n-1]$ $n$ $k=\sum \limits_{i=1}^{n-1} [p_i<p_{i+1}]$ 。

题解：

$s$ $n-s$ $\sum_{i=1}^{n-s-1}[p_i<p_{i+1}]=k-s$ $\sum_{i=1}^{n-s-1}[p_i+1=p_i]=0$ $\pmatrix{s+n-1\\ n-1}$ $n\leftarrow n-s,k\leftarrow k-s$ 。

$\mathrm{Ans}=\sum_{i=0}^{n-1}\pmatrix{n-1\\i}\cdot(-1)^i\cdot\left<\begin{matrix}n-i\\ k-i\end{matrix}\right>$ $\left<\begin{matrix}n\\ k\end{matrix}\right>=(k+1)\cdot \left<\begin{matrix}n-1\\ k\end{matrix}\right>+(n-k)\cdot \left<\begin{matrix}n-1\\ k-1\end{matrix}\right>$ $O(n^2)$ 的做法，然后就是 EI 的事情了，我们凡人就不应该插手。