YAIU 非官方营业日志（1、2、3）

P6383 『MdOI R2』Resurrection

题面：

$n$ $T$ $1$ $n-1$ 。
$T$ $u$ $u$ $n$ $u$ 的节点。
$n$ $G$ ：
$1 \sim n-1$ $p$ $n-1$ $i$ $T$ $p_i$ $(a,b)$ $u$ $v$ $T$ $a,b$ $G$ $u$ $v$ 号点之间连一条边。
$T$ $G$ $G_1$ $G_2$ $u$ $v$ $G_1$ $(u,v)$ $G_2$ 中存在。
$998244353$ $n\le 3000$ 。

题解：

$(u,v)$ $u=fa_v$ $v$ 为其端点之一；这条边，只能向其祖先连过去。

考虑链的情况，玩一下，发现图应该长如下这样：

也就是不能相交。证明的话，如果有相交的，显然无解；如果没有相交的，我们直接递归构造。搬到树上也一样的，我们只要数这种连边方式的数量。

dp $dp_{u,S}$ $u$ $S$ $S$ 需要存下向上所有的连边方案，这是行不通的。

$f_{u,i}$ $i$ $u$ 子树内的方案数。那么就很可做了，得到状态转移方程：

f_{u,i}=\sum_{j=1}^{i}\prod_{v\in son_u}f_{v,i-j+2}

AC Submision Click Here!

CF1592F2 Alice and Recoloring 2

题面：

$n\times m$ 的 01 矩阵和四种操作：
$(1,1)$ $1$ 。
$(n,m)$ $2$ 。
$(1,m)$ $3$ 。
$(n,1)$ $4$ 。
$0$ $n\le 300$ 。

题解：

$(n,m)$ 为原点），那么一操作就是一次单点翻转，二操作就是一次四点翻转。

$del_{u,v}=1$ $del_{u,m}=1$ $del_{n,v}=1$ $(u,v)$ $u$ $v$ 。直接跑二分图最大匹配即可。

$(n,m)$ $O(n^3)$ ，AC Submision Click Here!

P5332 [JSOI2019]精准预测

题面：

$n$ $1,2,……,n$ $T$ $1,2,……,T$ ）的生死情况，每条预测都是如下两种形式之一：
$0$ $t$ $x$ $y$ $t$ $x$ $t+1$ $y$ $x$ $t$ 时刻是生存状态时，该预测也被认为是正确的）；
$1$ $t$ $x$ $y$ $t$ $x$ $t$ $y$ $x$ $t$ 时刻是死亡状态时，该预测也被认为是正确的）。
$T+1$ $n\le 50000$ $\le 10^5$ 。

题解：

2-SAT $u\rightarrow v$ $\bar v\rightarrow\bar u$ 连上，因为这个事调了我好久啊啊啊啊啊）。

$u$ $v$ $u\not\rightarrow\bar u$ $v\not\rightarrow\bar v$ $u\not\rightarrow\bar v$ bitset $O(\frac {nm}w)$ 。

$T+1$ 时刻。这样就能卡过去了：AC Submision Click Here!

CF932F Escape Through Leaf

题面：

$n$ $1$ $n$ $i$ $a_i,b_i$ 。
$x$ $y$ $a_x\times b_y$ 。跳跃多次走过一条路径的总费用为每次跳跃的费用之和。请分别计算出每个节点到达树的每个叶子节点的费用中的最小值。
$1$ ，根节点也不算做叶子节点。另外，不能从一个节点跳到它自己.
$2\leq n\leq 10^5$ $-10^5\leq a_i\leq 10^5$ $-10^5\leq b_i\leq 10^5$ 。

题解：

$a=x$ $u$ $x$ $O(n\log n)$ $O(n\log n)$ 的了。AC Submision Click Here!

P5334 [JSOI2019]节日庆典

题面：

对于字符串，定义
$T_i=T[i……|T|]::T[1……i-1](1 \leq i \leq |T|)$
$::$ $f(T)$ $i$ $1 \leq i \leq |T|$ $T_i=min(T_1,T_2,……,T_{|T|})$ （字典序意义下）。
$S$ $S[1……i]$ $1 \leq i \leq |S|$ $f(S[1……i])$ 。

题解：

感觉是一个比较典型的字符串的推导过程。

$1\sim i$ $S$ $T[S_{j+1},i]$ $T[S_{j},i]$ Border $|S_{j+1}|\cdot 2 > |S_j|$ ，大概会长下面这个样子：

$B$ $A$ 的一个 Border，也是候选集和中的一个元素；容易发现，ABX 一定不会比 AABX 和 BXABX $O(\log{n})$ 级别的了。

维护候选集合直接从左到右暴力地做就好了；那么如何从候选集合中找到答案呢？这就需要快速比较字典序了。由于循环位移比较字典序中需要比的串对中，至少得有一个是前缀，所以可以用 exKMPlcp $O(1)$ 比较字典序啦！AC Submision Click Here!

P5597 [XR-4]复读

题意：

小 X 捡到了一台复读机，这台复读机可以向机器人发号施令。机器人将站在一棵完全二叉树的根上，完全二叉树是无限延伸的。你将向复读机录入一串指令，这串指令单个字符可以是：
L：命令机器人向当前节点的左子走；
R：命令机器人向当前节点的右子走；
U：命令机器人向当前节点的父亲走（若没有，则命令非法）。
录入指令后，复读机将会把指令无限复读下去。比如命令为 LR，那么机器人会遵从 LRLRLRLR... 一直走下去。
$n$ 个节点的连通块，保证这个连通块包含根节点。连通块上的每个节点都埋有宝藏，机器人到达过的地方如果有宝藏，则会将其开采。如果一个地方没有宝藏，机器人也可以到那里去。机器人也可以反复经过一个地方。
显然，这个连通块本身也是一棵二叉树。
现在，有人告诉了小 X 埋有宝藏的这棵二叉树的前序遍历，小 X 需要寻找到一条尽量短的指令，使得机器人能够挖掘出所有宝藏。

题解：

枚举一个周期的位移矢量，然后会把原树分成很多段，求个并即可。没什么好解释的，就是码就好了。AC Submision Click Here!

P3293 [SCOI2016]美味

题面：

$n$ $1,2,...,n$ $i$ $a_i$ $m$ $i$ $b_i$ $x_i$ $i$ $j$ $b_i\,\,xor\,\, (a_j+x_i)$ $xor$ 表示异或运算。
$i$ $l_i$ $r_i$ 道中选择。请你帮助他们找出最美味的菜。

题解：

$O(\log^2n)$ 。AC Submision Click Here!

P4898 [IOI2018] seats 排座位

题面：

$HW$ $H$ $W$ $0$ $H-1$ $0$ $W-1$ $r$ $c$ $(r,c)$ $HW$ $0$ $HW-1$ $i(0 \leq i \leq HW - 1)$ $(R_i,C_i)$ 。座位表中参赛者和座位是一一对应的。
$S$ 长方形的 $r_1, r_2, c_1$ $c_2$ 满足下列条件：
$0 \leq r_1 \leq r_2 \leq H - 1$ 。
$0 \leq c_1 \leq c_2 \leq W - 1$ 。
$S$ $r_1 \leq r \leq r_2$ $c_1 \leq c \leq c_2$ $(r, c)$ 的集合。
$k(1 \leq k \leq HW)$ $0$ $k-1$ ，那么该集合是美妙的。一个座位表的美妙度定义为这个表中美妙的长方形座位集合的个数。
$Q$ $0$ $Q-1$ $j(0 \leq j \leq Q - 1)$ $A_j$ $B_j$ 的座位。你立即接受每个请求并更新座位表。每次更新后，你的目标是计算当前座位表的美妙度。

题解：

在 Chen_03 的循循善诱下做出了这道题。

$ps_i$ $i$ $1\sim i$ 能构成美妙集合当且仅当：

\sum_{j=1}^i 1-[a_{ps_i-1}<i]=1

$\sum_{j=1}^i 1-[a_{ps_i-1}<i]$ $a_{ps_i-1}$ 的贡献，那么它对应着一个区间加。统计最小值个数即可。

二维情况怎么办？如下：

$A$ $B$ $B$ $5$ $A$ $4$ $1$ ，直接维护一个编号上的线段树即可。