24pht春2

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/137277940

pht春2

A

如果一个点把自己给叶子则同构

每个点进行操作后就会变成叶子

只要一个非叶给非叶就一定不同构，因为肯定会多一个叶子

所以可以大胆猜测操作次数就是非叶子节点个数 -1

听说他们打完结论假了。

好吧，他们是 $n=2$ 没有特判。

B

先猜一波，合法 $k$ 必然为一个连续区间。

上限显然是 $a_i>0$ 的个数。

下限先猜一波把所有负数丢前面，然后正数从小到大放

Finish！后面维护那个拿个动态开点线段树维护即可。

C

预处理两个东西 $a_i,b_i$ ，分别表示 $1\to i,i\to n$ 的最短路（最大值的最小）。

然后枚举一条边 $(u,v,w)$ ，然后取 $(w,a_u,b_v)$ 三个中两个较小值即可。

我的思路是没问题的。但是必须钦定 $w$ 是最大的那个。

然后直接dfs会T掉，其实本质就是个最小生成树而已，所以把原图变成最小生成树即可（感觉建出最小生成树后找 $1\to n$ 的路线就是答案）

D

转折排列就是上下上下上下的形式的排列。

对于 $p$ ，按数字顺序来走，形如左右左右。而构造字段序最小，正常思考方向是右左右左。

先把合法排列数量打出来：

1	1 2 4 10 32 122

直接丢oeis： https://oeis.org/A001250

如果钦定第一步的方向，也就是 $q_1<q_2$ 就是答案整体除2： https://oeis.org/A000111

然后有了这个东西感觉就可以类似泰勒展开的形式。

可以考虑一个形式， $f(L,R,0/1)$ 左边还有 $L$ 个，右边还有 $R$ 个，下一步方向往哪里。转移的地方是 $op\oplus 1$ 过来。然后分讨从 $L-1,R-1$ 哪里转移过来就行。

但是这样子似乎只能统计方案数，对于字典序统计做不了。而且这样子是 $O(n^2)$ 的，但是 $n$ 只有50。

求字典序，先枚举第一个元素能不能是1。如果是1，相当于钦定了 $q$ 中1所在的位置。

假设之前都满足，现在枚举一个元素 $x$ ，相当于已经有一些数钦定了。

等价于已经钦定了一些元素，在满足这一些的情况下的波浪排列数有多少个。如果排列数比所求要小，说明后面怎么填都不合法。那就可以把钦定的值调大，看一下行不行。若 $\ge k$ 则合法，递归。否则减去。

反正说了这些东西也是一些很显然的东西，关键是要怎么验证在某些东西已经填了的情况下求满足条件的转折序列。此时已经变成纯粹和 $q$ 有关的问题了。由于 $50$ ，状压肯定不行，区间DP似乎也不可行。

现在要求 $f$ 的一个DP。 $DP(i,j,0/1)$ 表示第 $i$ 个位置，前一个位置相对于后面是第几大，下一个是要上升还是下降。最后一个元素是第 $j$ 小的（剩下有 $j-1$ 个比他小）。

关于钦定的问题，可以发现已经填的数肯定是最小的。因为我们的 $p$ 是从小到大枚举的。那样子没钦定的数一定比钦定的数大。

E

可能要从线性代数的角度来思考？

首先有用的 $c$ 不会超过30个。

然后对于每个 $c$ 的取值最多只有30种，形式形如 XXXX011111 ，前面的 X 是一直顶着上界，然后某一位上界为1这位取0，后面就全1了。在这题中顶着下界取显然是没有意义的。感觉这个结论应该是没错的。

现在没有固定方向了，我感觉可以从两个方向入手：

扫描线 + 线段树
维护 XXXX 和 1111 的贡献，通过某些神秘的DP进行。

毕竟这东西总不能是流吧？

首先任意时刻的形式任然是 XXXXXX11111 。一个数的选法肯定是把1扩展一段，然后某位没有贡献（即为0），然后再把最前面的搞上去。

考虑前 $i$ 位，比如是 011101001001010_______ ，策略就是把一个1变成0，然后后面全都是1。但这个时候后面的下划线是没有贡献的。

因此把一个数后面改全1只存在在一个数里面，其他数使用原数，那样子答案是不变的。因为两个数同时搞一段1，肯定会有一段覆盖另一段。

如果统计 $[L,R]$ 区间所有数直接二进制加不进位的值， $a_1a_2a_3a_4\dots$ ，最优策略必然是选一个 $a_i>1$ ，令 $a_i-1$ ，然后把后面所有 $j>i$ 的 $a_j$ 都变成1。然后把所有大于1的变成1就行了。

~~我感觉我的结论很对。~~哦，不对，假了。这个做法只能用在没下界的情况。

贪心结论，对于每一个询问，最多有一个元素不是取最大值，其他都取最大值。这个性质我已经推出来了。

然后对于每个 $i$ ，在区间 $[L,R]$ 之下，记 $a_i$ 表示有多少个数最大值这一位为1， $b_i$ 表示有多少个数可以把这一位变成0后后面全部为1。

然后从大到下枚举，如果 $a_i\ge 1$ 则令这一位为1。如果出现一位 $a_i>1$ 且 $b_i>0$ 则后面可以全部为1。

F

数数题。

首先两个队列只要是单调不降的就必然可行。

什么时候不可以，如果出现 $a>b>c$ 是必然不行。思考此条件是不是充要的。充分性是显然的，我想想必要性怎么证。

考虑 $a>b$ ，则 $b$ 必然要和 $a$ 在另一个队列里面。这个关系是满足传递闭包的。

我目前想不出反例，就先假设是充要的。那这样的序列是长成什么样子的？

【这里中间有1000字内容太奇怪所以数据屏蔽】

首先，对于初始那 $k$ 个数，有些数之间可以不放，虽然这可以在插板的时候稍微调整一下。但是对于最前面的那些后面没插数的数是会贡献到新dp的第二维里面的，这就出现问题了。

一个做法是我再枚举多一维，那样子复杂度就变成4次方的了。观察到题目有 $\sum a_i\le 500$ ，这有没有可能会产生某些均摊呢？

现在的转移大概是：

$dp(i,k)\to dp(i+1,j+t+1)\times \binom{(a_i-j-1)+(t-1)-1}{t-1},t\le k\le \sum a,j\le a_i$

任意三个数之间最多发生1次碰撞，所以总复杂度是 $O(n^3)$ 的应该是没错的。

等价于问有多少个序列 $b$ ，满足第 $i$ 个元素恰好出现 $a_i$ 次，且 $b$ 可以拆分成两个非递减序列。

假如给我一个 $b$ ，怎么拆。直接贪心即可。假设贪心分别为 $(x,y)$ ，则塞入比它小的里面最大的那个。是为了让其中一个尽量小。事实上我们也是这样子。

现在来考虑枚举所有 $b$ ，从左到右添加元素。如何刻画当前用了哪些元素，状压DP不太可行，但我们可以用两个队列末尾的元素来刻画当前的状态。

可以设计这么一个DP。 $DP(i,x,y)$ 现在枚举到第 $i$ 个，较小队列为 $x$ ，较大为 $y$ 。

枚举下一个数。可能变成 $DP(i+1,x',y),DP(i+1,x,y')$ 这两个。但现在有个问题，不知道 $x,y$ 之前用多少个元素。而且复杂度是四次方的。

我们并不需要这样子，可以更简单一点。

$DP(y,cnt)$ ，现在不关心是哪个元素。只关心较大的元素是谁， $cnt$ 表示还有多少个比 $y$ 小的元素没有塞进去。现在枚举下一个元素，如果比 $y$ 小，则放入下一个队列，转移到 $DP(y,cnt-1)$ 。

如果比他大，可能转移到 $DP(y',cnt+\delta)$ 。取决于这个元素和 $y$ 之前相差了多少个元素。

相同的情况枚举有多少个数即可，也就是钦定这个 $y$ 是最后一个 $y$ 。但这样子还要乘个组合数什么的，非常复杂。

$DP(i,j)$ 表示有 $i$ 个元素大于等于 $y$ ， $j$ 个严格小于，没有放入。

main函数调用 $DP(n,0)$ 。

首先从 $i$ 可以推最后一个数是什么。此时要么插最小的数，要么插大于等于他中在编号上小的（我们令其有编号）

G

我印象中曾经遇到过一道变成括号序列那样子的题目。那道题有个优美的结论，把所有端点拿出来，则任意一段子区间都是一个完美的括号匹配。

考虑推广到这题成不成立， ~~每个子区间都必选~~ 。直接假掉了， 00000111110000 这样子就直接假掉了。

或者说0，1个数相同本质就是钦定某个区间的和。考虑对原序列作前缀和，约束等价于 $S_R-S_{L-1}=\frac{R-L+1}2$ ，信息虽然看起来还好，但是后面那里感觉就是更难利用性质。

现在要么是这个方向堵死了，要么后面是什么根本不重要，任意常数 $C$ 都可以做。

我先从第二个方向进行思考。先用并查集并在一起。然后还有一些大于小于关系，比如 $0\le s_i-s_{i-1}\le 1$ 、这个形式很像2-sat，但又明显不是。

$d_i$ 表示前缀 $i$ 的1的个数。然后 $d_i\ge d_{i-1},d_i\le d_{i-1}+1$ 还有什么和 $L,R$ 相关的形式。

我们现在求字典序，所以是求最短路。

$d_{i-1}\le d_i$
$d_i\le d_{i-1}+1$
$d_{L-1}\le d_R-\dfrac {len}2$
$d_R\le d_{L-1}+\dfrac{len}2$

因为一定有解，所以不存在负环。

但同时有正权和负权，要SPFA，但会被卡。

现在改动使其只有正权。

$d_i$ 不直接表示0的个数，表示0比1多多少个，则边是这样子的：

$d_{L-1}=d_R$
$d_i\ge d_{i-1}-1$
$d_i\le d_{i-1}+1$

写成小于等于的形式：

$d_{i-1}\le d_i+1$

思考会不会有 $d_{i-1}=d_i$ 的情况。

由于有第一个限制，好像不会有。

现在要求最大值，然后跑最短路。然后变01bfs了？

最大值，要跑最短路，是因为比如 $Y\le X+d$ ，可以写成 $X\ge Y - d$ ，希望沿着这条边来跑（现在用 $X$ 去更新 $Y$ ）。

构造只需要把 $d$ 求出来即可。

H

考虑一个位置 $i-1$ 答案是0， $i$ 是1，那么 $i$ 的 $k$ 只能是 $k=\frac {i-1}2$ 。否则可以尝试继承上一个的 $k$ ，如果可以就是1，如果不行尝试自己的新1。

问题就在于试 $k$ 的这个过程。设旧的 $k$ 为 $k'$ ，则要试的有 $[k',\frac{i-1}2]$ 。因为任何一个都有机会成为合法 $k$ 。

对于这一步感觉应该不是直接做，而是要找找性质。

某个 $k$ 的检测似乎只能从 $2k+1$ 开始，能不能预处理或者继承？

给数组 $a$ ，对于某个前缀，如果存在某一个 $k$ ，满足划分成一堆长为 $k$ 的序列，对应位置上的地方的数形成一个等差数列。然后求合法前缀个数。

反过来思考，对于每一个长度为 $k$ 的block，都一定有到某个位置 $L$ 为止之前，它可以是好的。

然后考虑一段一段来判断。用哈希。两段时始终是好的。

对于最后一段内部可以二分定位。往前两段长度 $k$ 就行。

其实也可以不二分，枚举下一个 $k'$ 某个时刻是不可以的，也就是可以 two-pointer。

相当于对于当前末尾，所以枚举下一个 $k'$ 只需要从这个位置开始即可。那样子总枚举数是 $O(n)$ 的。当然前面那一部分有个调和所以数 $O(n\ln n)$ 。

一个更强的结论，如果一个前缀 $l$ 对于 $k$ 合法，必然有 $S[1:l-2k]+S[k + 1 : l - k]=2S[2k + 1 : l]$

然后现在直接双指针就非常简单了！

哈希真得太神奇了！

I

英文题目，差评。

给定 $n,m$ 的有向图，每条边有 $[0,1]$ （概率）的边权。然后1号学生知道某个信息，他会直接传播出去。

按dfs顺序遍历每条边，每条边都可以走，一个点visit过就不visit了。每个点在第一次visit的时候会更新所有其他点（即如果 aware[u]=1, 则由边权的概率 aware[v]=1）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
1: Let aware[1..n] be a new array initialized as F alse
2: Let visited[1..n] be a new array initialized as F alse
3: procedure DFS(u)
4: 	if visited[u] then
5: 		return
6: 	end if
7: 		visited[u] ← True
8: 		for (u, v, w) ∈ edges starting from u do
9: 		// Enumerate edges in the order of input /
10: 		if aware[u] and not aware[v] then
11: 			with probability w, aware[v] ← T rue
12: 		end if
13: 		DFS(v)
14:	 end for
15: end procedure
16: procedure SPREAD
17: 	aware[1] ← T rue .// The first student knows the information at the beginning
18: 	DFS(1)
19: end procedure
求每个点被激活的概率。

Visit顺序构成一棵生成树。

一个朴素的思路是先把第一次的概率求出来，然后再求出第二次的概率。

第一次的概率就是沿着生成树的边走边权全部乘起来。

第二次的概率就是在第一次的基础上在剩余情况中遍历每条边乘概率。但似乎要按照dfs序倒序来做。

不知道对不对，感觉很抽象。

第一轮会生成dfs生成树。注意，这是有向图的dfs生成树。

有四类边：

树边
横叉边
返祖边
超越边（祖先只向某个后代）

树边有传递能力。横叉边有激活能力，返祖边没有用。

单独考虑某个节点 $v$ ，考虑所有指向 $v$ 的边。一条是树边，还会有一些横叉和超越。只考虑 $v$ 被激活的可能性。

这三条边对 $v$ 的意义来说是一样的。考虑三个关键节点，分别长了一个东西（打标记的叶子），然后其他只有树边。等价于从根出发摸到打标机叶子的概率。

如果单测可以树形DP。求出某个点走不到打标机叶子的概率。现在有了 $O(n^2)$ 的做法了。

但事实上可以更简单一点。虚树。

我们把所有和 $v$ 有关的点拿出来建虚树，然后跑树形DP即可。

隐藏的最深的虚树。

J

好神秘啊。

假设数的数量很少，我们就可以直接建一个深度为 $\log$ 的二叉树，分别代表除 $k$ 次之后的奇偶，然后初始在根节点每人轮流往一个方向走，谁不能走谁输。

题目已经保证区间不交了。

一个暴力做法就是倒插建Trie树，每次可以往左或往右，不能走就输。

考虑一个区间长成二进制 $[110000,1111111]$ ，那前5次操作是无意义的。而一个区间，一定可以被拆成 $\log$ 个类似这样子的区间。

比如 $[2,12]$ ，就可以拆分 $[12,12][8,11][4,7][2,3]$ 4个区间，也就是尽量往前找若干个1又不超过，其形式一定为 $[X,X+2^k-1]$ ，这样子一定不交的。

拆完之后，把 $X$ 这个数倒插到第 $k$ 棵Trie树。

现在维护 $60$ 棵Trie树，因为前 $k$ 次操作都不会影响。

假设已经维护好所有Trie树。

Alice在1树上走。Bob也是走左边或右边，但是在2棵树上走。然后Alice在3棵树上走。直到在任何一棵Tire树上找不到下一个节点。

实现上可以先在第0棵树上走，然后如果走不了了就跳到第1棵树上，然后就继续走，继续跳。

这个过程和AC自动机建Fail树的过程一样的。然后可以从第59棵树往前建Fail指针。

然后能走就走原树边，不行就走Fail边，做树形dp即可。

做得最久的一题，因为好多神秘错误调了3.5h