BJ 萌熊集训

· · 个人记录

跑来萌熊最后垫底两个星期，准备省选冲击 F 队了。

可能顺便收录一些其他来源的杂题。

2.12

下午才跑来 BJ，一些训练题。

1A

考虑二分图染色，把情侣之间先连边，然后再连所有的 2i-1 和 2i 限制相邻三个不同色，注意到这张图不存在奇环，直接 dfs 染色即可。

1B

因为保证了约数个数不超过 7，所以每个数最多有两个质因子。考虑图论建模，将次数模 2 后的两个质因子连边（不够 2 个用 1 补），这张图上的一个环就会对应一个乘积为完全平方数的子集。

只需要找到图的最小环，直接枚举起点是 O(n^2) 的，但是注意到任意环上一定存在一个不超过 \sqrt V 的数，缩小下枚举范围是 O(n\sqrt V) 的。

1C

还没看，别急。

1D

倒着考虑问题，相当于求从 (a,b,c) 出发不走出长方体外走 d 步的路径数量。

注意到每一维是独立的，我们可以对每一维各算出走 i 步的合法路径数量然后再 NTT 卷起来，所以考虑一维的情况即可。

而一维的情况，设 f_i 表示走 i 步的合法路径数，我们可以先从 2f_{i-1} 转移过来，然后减去一些边界情况，这些边界情况形如一个反射容斥问题，复杂度形如 O(\frac{d^2}{n})。如果 n\le\sqrt d，我们可以改成跑一个暴力 dp，所以求一维可以做到 O(d\sqrt n)。

三维各求一遍然后 NTT 即可。

2B

考虑分治，并钦定 \max 在左/右区间，考虑计算另一端点的贡献，\min 和 \max 在同一侧是好算的，不在一侧的情况可以双指针+位运算维护贡献。

2.13

逆天模拟赛，20+100+0=120，rk3。

T1 T3 都是逆天不可做题，T2 做了个差不多的原通过了，咋差点登顶了/fad。

挂个 T2 我写的题解。

2.14

难绷的模拟赛，100+0+0=100，rk10。

只写了 T1 一道答辩题，T2 T3 都没开。

A

首先有个显然的建模是考虑让边选点，给每条边定向使得每个点入度最多为 1。注意到题目保证了一定有解，所以每个连通块一定形如树或者奇环数。

不妨单独考虑每一个连通块。对于树，可以把任意一个点提为根然后构造外向树，一共有 O(siz) 种定向方式。对于基环树，环上的边可以统一顺时针或者逆时针定向，挂出来的部分必须是外向的，只有 2 种定向方式。对于每种定向方式，可以得到它对应的两个人的价值和，把它看成一个二维平面上的点 (s_1,s_2)。因此可以将题目转化为：有若干个连通块，每个连通块内有若干个向量，在每个连通块内各挑一个向量，使得所有向量之和的 xy 最小。

对于最小化 xy 这种东西，一个经典套路是考虑凸壳相关的东西，对于一个点集来说 xy 最小的点一定会在下凸壳上，证明考虑这个过程相当于用反比例函数截点，而反比例函数图像是下凸的。

所以对每个连通块内的点求出对应的下凸壳，然后直接把所有凸壳用闵可夫斯基和合并起来即可，复杂度 O(n\log n)。

B

先考虑，给定一个由 {\tt 01?} 组成的串 s 该如何计算 f(s)\le r 的方案数。因为是和某个数字比大小的形式，所以考虑一些类似数位 dp 的状态设计，把当前 x 与 r 的 lcp 记在状态里，同时你发现操作不涉及进退位且更倾向于改低位，这么记唯一的问题就是不知道 lcp 后有没有 1，所以再把 lcp 后的 1 记到状态里即可。

也就是说，直接设 f_{i,j,k} 表示考虑了前 i 个操作，当前 x 与 r 的 lcp 长度为 j，x 在 lcp 以后的部分有 k 个 1 的方案数，直接转移可能需要一些复杂的预处理和讨论，一个方便的做法是把这个状态压到一个自动机里，可以显著减少讨论量和代码细节。

对于钦定某个某位为 \tt 0 的方案数，考虑把转移过程倒过来，得到 g_{i,j,k} 表示后缀的 dp 值，统计第 i 个位置的答案时，只需要把 f_{i-1,j,k} 转移一步 \tt 0，然后和 g_{i+1,j',k'} 乘起来累加即可得到答案，容易做到 O(nk^2)。

C

数论不看。

2.15

我训练题全都不会咋办。

1A

对于一个数 x 假设它的质因数分解为 \prod p_i^{e_i}，则它对答案的贡献显然是 \prod(ke_i+1)，然后 x 从 1 到 n 求和，直接维护这个多项式的系数即可，次数最高八次。

1B

比较复杂的 dp，别急。

1C

考虑比较简单的情况，比如 S=2 怎么做。给每一行的两个数之间连边，问题转化为给边定向使得每个点的入度和出度差不超过 1。注意到这个很像欧拉回路，建一个虚点和所有度数为奇数的点连边跑欧拉回路，就能构造出一组合法的解。

尝试扩展这个做法，S=2^k 所以考虑分治。你发现一件很深刻的事情就是，上面的欧拉回路相当于是可以把所有颜色划分到左右两部分，使得每种颜色左右的数量差不超过 1，所以每层你都跑个欧拉回路分治下去就做完了。

至于这个做法的正确性，相当于是考虑线段树每层只有两种长度不同的区间且差只有 1，这个的证明直接归纳即可。

P6881

我的题解

省选计划 R14T2

考虑到三元环等价于三个矩形都无交，考虑补集转化，用总三元组减去不合法的，不合法的分为一对或两对之间有交，以及三个之间都有交两种，前者是好算的，考虑后者。

比较难直接统计，考虑从下往上扫描线，在三个矩形里上边界最低的矩形处统计答案，这样扫描到一个矩形的上边界时就得到了在 x 轴方向上与其有交的矩形集合。这样问题可以变为序列上的问题，动态插入删除区间，并查询有多少对有交的区间都与给定的区间有交。

假设待查询的区间是 [l,r]，那么我们先算出与 [l,r] 有交的区间 c，这个相当于拿总区间个数减去左端点 >r 的区间个数再减去右端点 <r 的区间个数，这样合法的区间对数就是 \dbinom{c}{2} 减去都与 [l,r] 有交但彼此之间没交的区间对数，后者可以通过线段树上维护一个区间内右端点的个数、左端点的个数、右端点小于左端点的对数完成，时间复杂度 O(n\log n)。

省选计划 R14T3

考虑 ARC150D/ARC165E 的经典技巧，将题目转化为随机一个排列操作，这样就白送了 O(n^4)。

怎么做到 O(n^3) 我还没想好，别急。

2.16

PR #15 T1

显然转化为计算 \sum_{i=1}^nP([f(i)=f(i\bmod n+1)])，问题变成快速求 f(x)=f(y) 的概率。

最小表示法应当是和循环节强相关的东西，注意到如果确定了一个长度为 n 的字符串循环节为 d（限制是 d\mid n），那么最小表示法的起始下标会在 [1,d] 内均匀随机，即概率都是 \frac{1}{d}。

考虑上个莫反分别求出每种循环节的字符串数量，注意到我们只需要分别对 a_x 和 a_y 的约数求所以一次是根号的，则每种下标的答案可以划分为 O(\sqrt V) 段相同的数，双指针统计即可，容易做到 O(n\sqrt V)。

PR #15 T2

我的题解

省选计划 R15T3

数据范围和子任务提醒了你直接数据分治。对于 n 比较大的情况，集合大小的最小值不大，把它提到开头枚举它选了哪个数即可。对于 n 比较小的情况，每次尝试合并开头和结尾两个集合，一共只会进行 n 次合并。

对 n 设置阈值 B，记 S 为集合大小和，复杂度为 O(\max(BS,\frac{S^2}{B}))，取 B=\sqrt S 即可平衡到 O(S\sqrt S)。

2.17

模拟赛，暴力摆了写了 100+0+0=100，但是忘记交代码了，唐，这下喜提 rk inf 了。

A

考虑有根树的做法，设 a_u 表示 u 的删除时间，转化为在树上填数使得 a_u\le a_{fa_u}，但是数字必须从 1 开始都出现过。先忽略这个限制直接 dp，然后套一个二项式反演即可得到有根树的答案，容易做到 O(n^2)。

对于无根树的情况，考虑最后一次操作一定会删除一个连通块，直接使用点减边容斥即可，本题的数据范围允许暴力换根，所以可以写 O(n^3)。

B

令 d 为原题中的 2d，n 为数轴长度。原题可以转化为，数轴上有一些点，对于在 x_i 的点你可以选择把它移动到 x-d。同时修改代价的计算方式，放置一个线段需要 a 的代价，每扩展一个单位加 b 的代价。

考虑对 d 进行数据分治。对于 d\le 16 的部分，考虑直接顺序扫描数轴，发现只需要关心最近 d 个位置有没有被线段覆盖，直接状压 dp 即可。对于 d>16 的情况，注意到每个点移动前后的位置模 d 不变，因为 d 比较大所以模 d 意义下每个等价类的位置很少，可以提前预处理出每个等价类的每种覆盖状态是否合法，然后再用一个 dp 合并即可，当然需要预先枚举 \bmod\ d=0 的状态处理和 \bmod\ d=d-1 的状态的合并。

时间复杂度懒得算。

C

考虑链的情况，显然可以顺着链 dp。设 f_{i,0/1} 表示考虑了链上的前 i 个点，i 所在的连通块和 0 号点有没有在一个连通块的最优价值，转移非常容易，答案即为 f_{n,0}。这个转移显然可以写成 (\min,+) 矩阵，所以使用线段树维护 ddp 即可做到 O(n\log n)，同时带一个 2^3 的矩阵常数。

对于一般的情况，首先因为图上的边权不会改变所以显然可以只保留 MST 上的边，因此其实是树上问题。我们称一个点是黑点如果它没有保留和 0 号点的连边，若保留则称它为白点，问题变成，可以将树上一些点染白并断掉一些边，要求断边后每个连通块恰好有一个白点。同样考虑设 f_{u,0/1} 表示 u 子树内 u 所在的连通块有没有白点的答案，转移同样可以写成矩阵，此时套用树上 ddp 可以做到 O(n\log^2n)（其实上个 LCT 就 O(n\log n) 了，但我并不会）。

事实上有更厉害的做法。首先两棵树如果它们的 Kruskal 重构树结构相同那这两棵树是等价的，感性理解显然，大概就是加入每条边时连通性完全一样。所以可以考虑直接给图求出来一棵 Kruskal 重构树，然后按照中序遍历把它拍成链，这样就转化成了链上的问题，直接套用链的做法即可，所以还是 O(n\log n)。

CF1495F

称普通边为连接 i 和 i+1 的边，特殊边为连接 i 与最小的 j 使得 p_j>p_i 的边，显然可以将问题转化为多次询问两个位置之间的最短路。

考虑离线下来对左端点进行扫描线，维护每个位置的最短路。当 l 左移时，首先可以先算上普通边的贡献，每个位置的最短路先加上 a_l。考虑特殊边，一个很好的性质就是这个 j 是用单调栈找到的，所以所有特殊边要么包含要么不交，如果 i\to j 这条特殊边更优 j 更靠后的位置一定也可以走这条边，所以贡献形式都是简单的区间加，树状数组维护即可，O(n\log n)。

2.18

天哪我这一天干啥了来着，是不是摆得太厉害了。

2.19

模拟赛，20+100+0=120，rk13。

完全不会这个傻逼 T1，我是不是奶龙。

A

注意到 w 的最高位只会变低，我们设 cnt 为全局中最高位小于 w 的数的个数，显然答案的下界为 cnt，很难不注意到（我场上他妈没看出来这个？？？）上界其实就是 cnt+1，你只能选一个最高位和自己相同的去异或，所以只需要判断答案能不能到上界即可。

考虑先离线，枚举每一种最高位分开做。我们要判断一个和 w 最高位的 a_i 选了之后答案能不能取到上界，其实就是会有一些异或不等式的限制，在 Trie 上打若干标记维护一下即可，时间复杂度两个 \log 或者三个 \log，具体细节别急。

B

显然若全局 sum<0 则答案为 0，然后先转化下题意，令序列 c_i=a_i-b_i，那么相当于是可以对 c 进行重排，设一个重排的价值为最小的 i 使得：

对所有重排方案的权值和计数。

尝试处理 i 最小这个限制，很难不注意到第二条限制的 \le sum 其实是假的，假设存在一个 j 使得 \sum_{k=j}^{i-1}c_k\ge0，直接将 i 移动到 j 的位置显然也符合条件，所以第二条限制可以直接改成 <0。

然后对着 dp 即可，预处理一个后缀和 <0 的和前缀和 \ge 0 的拼起来即可，时间复杂度 O(n2^n)。

C

搬这题是不是属于脑子有点问题。

P10175

首先枚举 |S| 跑树背包容易得到一个 O(n^3) 的做法，这个比较容易，但是只有 24 分。

考察这个奇怪的 \bmod\ U^V 到底是在干啥，你注意到一个连通块的价值是一个乘积式，如果这个乘积是一个关于 U 的多项式那么次数 \ge V 的项就都会没有贡献，维护多项式前 V 项即可。考虑将 |S| 用带余除法拆成 pU+q 的形式，那么一个连通块的贡献就会变成 \prod_{u\in S}(pU+q+a_u)，这样就利用了上面的性质。

因为 V 很小所以你可以直接维护这个多项式的系数，把先枚举 |S| 改成先枚举 q，设 f_{u,x,y} 表示考虑 u 子树内 u 所在的连通块大小为 x 时 U^y 的系数和，直接转移即可做到 O(n^2UV^2)。

2.20

模拟赛，开摆了。

A

考虑先拆位，计算 \sum_{(u,v)}(\sum_{i=0}^{24}2^ia_{i})^2，其中 a_{x,i} 表示路径点权异或和的第 i 位。

注意到平方还是难处理的，所以再把平方拆开，变成 \sum_{u,v}\sum_{i=0}^{24}\sum_{j=0}^{24}2^{i+j}a_ia_j。再交换下求和号，直接枚举下 i,j，然后统计有多少路径的点权异或和第 i 位和第 j 位都是 1 即可，这步容易用一个 O(n) 的 dp 统计，所以最后的复杂度是 O(n\log^2V) 的。

B

注意到这个问题的形式和保序回归中指数为 1 的形式是非常相似的，懒得喷。那就只能考虑下整体二分了，设 \text{Solve}(l,r,Q) 表示 Q 中的位置答案值域在 [l,r] 时的问题，尝试求出 Q 中答案 \le mid 和 >mid 的位置分别有哪些，然后继续递归成子问题即可。

考虑如何解决填 mid 还是 mid+1 的问题，一般情况这里是跑最大权闭合子图，但是本题的偏序关系是一个网格图，所以一定会存在一条轮廓线，满足这条轮廓线左上方 >mid，右下方 \le mid。尝试直接对着轮廓线 dp，按照行或者列扫描，则转移形如前后缀 +1 和整体取前/后缀 \min（这里取决于扫描方向）。这个过程可以通过 set 维护差分的方式来优化，以后缀 \min 为例，set 中如果有 j 个 i 表示 f_{i}-f_{i-1}=j，这样后缀加就是插入一个 i，前缀加就是插入一个 0 然后找到第一个 \ge i 的位置删除。

最后的复杂度是 O(n\log^2n)。