2025.1 TY集训冬令营 (补发)

· · 个人记录

P9823

解法：

定义f_i表示长度为i的好排列个数

考虑其中最小的数放在哪里，假设最小的数放在了第x个位置，那么肯定有x\in[1,k]，进而发现[1,x-1]的位置是可以任意选数任意排列的，方案数为C_{i-1}^{x-1}(x-1)!，而从x开始的后面k个位置放数肯定可以满足条件，所以方案数就相当于长度为i-x的好排列，即f_{i-x}，所以

f_i=\sum_{x=1}^{min(i,k)}C_{i-1}^{x-1}(x-1)!f_{i-x}

化简得

f_i=(i-1)!\sum_{x=1}^{min(i,k)}\frac{f_{i-x}}{(i-x)!}

发现后面的\sum是\frac{f_{k}}{k}的和的形式，维护其前缀和即可优化到O(n)

CF1659E

发现答案只有0,1,2三种情况，即(00)_2,(01)_2,(10)_2，因为(10)_2\& \dots \to (01)_2一定不可能

【ans=0】 \Rightarrow 【存在\mathrm{mex}=0，即S中都不是0】 \Rightarrow 【存在一位k使得路径中所有边权的第k位都是1】

【ans=1】 \Rightarrow 【存在\mathrm{mex}=1，即S中存在0并且不存在1】 \Rightarrow 【先走到一个点p使得u\to p的所有边权存在一位k(k>0)满足第k位都是1，以保证前面不会出现1，然后p走到第0位为0的一条边，以保证后面不会出现1，然后由于ans不是0所以这个第k位到后面必定会变成0，保证了后面出现0】

【ans=2】 \Rightarrow 【\mathrm{otherwise}】

可以在每一位上开一个并查集，询问连通性即可。

T232043

考虑转化树上问题为序列问题，用bfs序来转化，发现此时一个点的子树内与这个点距离相同的点的bfs序是连在一起的，所以直接放在线段树上做即可。

QOJ 8672

首先将询问离线下来，按右端点升序排序后从前往后处理，然后将同一右端点的一并处理。

假设当前扫描到了第i个操作区间，用线段树每个位置j维护[j,i]操作区间对应的答案，可以发现这个答案是单调递减的，而对于当前的操作区间[l_i,r_i]，由于有单调性，所以可以使用线段树上二分，找到线段树上数在[l_i,r_i]内的区间[L,R]，那么对于j\in[L,R]，在[j,i-1]操作后变成的数经过了第i个区间要加1，所以让线段树上的[L,R]区间统一加一即可。

正确维护后，找到询问右端点为i的区间，根据这棵线段树的定义，直接询问这个区间左端点位置在线段树中的值即可。

P2824

直接排序是困难的，考虑如何转化

可以使用二分答案，二分第q个位置的数x，对于原序列的每个数a_i，如果a_i>x则将其记录为1，否则记录为0，这样就转化为对01序列排序，排序后查询第q个位置的值，如果是0那么a_q\le x，否则a_q>x。对01序列排序可以使用线段树简单维护。