本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-26 14:46:53

• 24.05.11 枚举 $1$ 到 $n$ 中每个数所有在 $n$ 以内的倍数，复杂度为 $O(n\ln n)$
• 24.05.26 枚举子集：

for(int T=S;T;T=(T-1)&S)

总时间复杂度 $O(3^n)$.

• 24.05.30 括号序列类问题

转化成对应前缀和的一段折线考虑。（/bx @Iceturky）

• 24.06.01 无逆元时要从总乘积中除掉一项

维护前后缀乘积（/bx @Iceturky）

• 24.06.17 $!!f$ int 强转 bool

• 24.06.20 序列问题有后效性，倒序处理 $f_i$ 为 $i$ 到 $n$ 的答案并乘上系数（/bx @Aimtpyim）

• 24.07.17 序列问题可以转成前缀和，之后区间操作可能转化为两点操作

• 24.07.29 两种不同的暴力拼起来可能就是根号分治，参数 $B$ 一定要让各部分复杂度相近，需要考虑到常数因素（SDSC Day5T2）

• 24.10.17 线性求逆元

求出 $inv_i\times i \equiv 1\pmod p$，考虑计算 $p=ri+t,t<i$，则 $ri\equiv -t,i\equiv-\frac tr,inv_i\equiv -\frac rt\pmod p$，所以 $inv_i=(p-\lfloor\frac pi\rfloor)inv_{p\bmod i}\bmod p$。

• 25.02.06 字典序最优问题

使用可持久化值域线段树维护哈希值，从而快速求出最长公共前后缀，进行比较和更新。

• 25.02.17 点边容斥

当树上每个连通块作为根计算答案时，可用每个点为根计算一遍并累加，再减去以所有边连接的两个点合成大点作为个根的答案，这样每个连通块的贡献只有 $1$。

• 25.04.29 整点凸包

当凸包的横纵坐标均为 $[0,n]$ 内的整数时，凸包的点数为 $O(n^{\frac23})$。

• 25.05.01 竞赛图相关

竞赛图强连通缩点后的 DAG 呈链状, 前面的所有点向后面的所有点连边；

竞赛图存在哈密顿回路和哈密顿路径。

• 25.05.04 矩阵快速幂

多次询问时可预处理转移矩阵的 $2^k$ 次方，每次询问做 $\log n$ 次向量乘矩阵，复杂度为 $O(k^3\log n+qk^2\log n)$。

• 25.09.26 排列字典序

若要最小化排列 $p$ 的字典序，可考虑其逆排列 $q$（$p_{q_i}=i,q_{p_i}=i$），并求出倒序字典序最大的 $q$，再还原回 $p$ 即为答案。

证明考虑首先最小化 $p_1$，也就是 $q$ 中 $1$ 的位置，以此类推。则 $q$ 从后往前考虑，只能填 $1$ 时再填 $1$，以此类推。

• 25.11.03 线段树二分

实在困难，记一下。代码选自 P11210。

int getp(int u,int l,int r,int L)
{
	if(r<L) return n+1;
	if(l>=L)
	{
		if(wy[u]<L) return n+1;
		if(l==r) return l;
	}
	int rl=getp(Lc,L);
	return rl==n+1?getp(Rc,L):rl;
}

• 25.11.14 线性基求后继（异或上 $x$）

int nxt(int lim,int x)
{
	int y=x,s=0; ini();
	vector <int> tv;
	for(int i=0;i<=30;i++) if(a[i]) tv.pb(a[i]),s++;
	for(int i=s-1;i>=0;i--) if((y^tv[i])>y) y^=tv[i];
	if(y<lim) return inf;
	for(int i=s-1;i>=0;i--) if((y^tv[i])>=lim) y^=tv[i];
    return y;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-29 09:03:41

加训是 不畏苦暗！

题目（Update:6.03）

1. HB-24.09-，23.12，24.07，24.07.25
2. 24.07-SDSC-Rest，24.10-XM-Rest，25.02-.25.02--MX
3. VP ZR-10,MX-13,MX-25 + CF,AT
4. NFLS 专题 + 24.02-MX（补题 + 21-23 未看）
5. 二轮省集 + 三轮省集
6. 转
7. 首页 +收藏栏做题计划（早期残留 + 24.02-MX + WC2025）

计划（Update:8.18）

1. 25.07-SDSC 补题解
2. 对着有用的板子学点科技
3. 核桃前期的课
4. ZR.MX 前期模拟赛 VP
5. 补做题计划

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-04 19:50:37

记录

ABCD 15min 切掉了，E 题思考了较长时间，中途还换过思路，60min 切掉了，F 题一直在想数据结构，没有想出正解。

VP 后补了 F，G 紫 H 黑决定不补了。

题解

A - Jogging

基本判断 + 数学题，略过不表。

B - Perfect String

开桶 + 记录是否有大小写，略过不表。

C - Just K

状压，枚举每一种选择方案，再统计出现次数恰为 $K$ 的字母个数取最大值，时间复杂度 $O(2^n\times26n))$

D - Index Trio

注意到值域较小，考虑开桶。

之后枚举每个数作为 $A_k$，再枚举 $A_j$ 来确定 $A_i$，乘法原理统计答案。复杂度为 $O(A_i\sum_{k=1}^{A_i}\frac{n}{k})$，调和级数也即 $O(A_i\ln A_i)$

E - RLE

前缀和优化组合计数类 dp。

首先想到设 $f_{i,j}$ 表示长度为 $i$ 的字符串，转化后长度为 $j$ 的方案数，转移时枚举 $k$ 为最后一段的长度，从 $f_{i-k,j-(l_{k}+1)}$ 转移过来，同时要乘上与上一段字母不同的 $25$ 种方案，时间复杂度 $O(n^3)$

考虑优化转移，发现所有位数相同的 $l_k$ 均相等，也即会从第二维相等的一段连续区间转移来。因此维护前缀和数组 $g_{i,j}=\sum_{k=1}^{i}f_{i,j}$，分为不同位数的数统一转移过来即可，时间复杂度优化到 $O(n^2)$

F - Ignore Operations

场上想到了枚举每个修改操作为最后一次修改，再从后面的加操作中选取若干个贡献。

因此考虑倒序处理，若为修改就记录一下答案，接着消耗一次跳过来保证这次不会修改，再继续向前寻找，直到次数耗尽。加操作中，若加的是非负数，加上一定不劣，而若是负数则先放到一个大根堆中，次数用尽时先从堆中拿出最大元素加上，来换取一次跳过，直到堆也空时才是真正耗尽了次数。

其实大根堆维护的类似于反悔操作，也即把已经跳过的再选回去来节省次数。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-04 22:32:15

记录

AB 10min 顺利过了，C 卡一整场，写了个假做法，最后看 D 结果切了。

VP 后发现 C 是简单题补了，E 蓝启发式合并，F 紫没读题，不补了。

题解

A. Three Doors

简单模拟，略过不表。

B. Also Try Minecraft

预处理每一位向右和向左的代价，分别做前缀和和后缀和，每次查询只拿出一段区间的代价即可。

C. Recover an RBS

VP 时想到了要转化为前缀和数组非负，由此可以想到从左向右依次处理，维护目前前缀值 ${cnt}$ 和未确定的位置数 ${res}$，容易想到 $cnt$ 为零时问号必填左括号，否则不合法。

由此扩展，若 $res+cnt=1$，也即这一位之前所有未填的全部为左括号恰能填满，则这一位也必须填左括号。

最后若 $res=\left|cnt\right|$，也即所有未处理的位置都是同种括号，就只有一种填法，否则有多种填法。

D. Rorororobot

显然起点和终点的横纵坐标必须分别模 $k$ 同余，否则无法每次走 $k$ 格走到。

由于被封锁的是靠近底部的一部分，因此考虑尽可能走高处的格，发现在起点所在列尽可能向上走，再横着走到终点列，最后向下走到终点的走法受到的限制最小。

这样就需要保证起点列和终点列之间在横着走的这一行没有被封锁，也即求起点列和终点列之间的最值，用 ST 表或线段树解决即可。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-05 16:17:50

记录

ABC 8min 切掉，D 30min罚了一发假做法切了，E 想了很久感觉是个单峰函数，好像要三分但不会（其实均值不等式能直接求），F想到是矩阵加速 + 状压但是不会转移，都没做出。

题解

A - Rock-paper-scissors

基本判断题，略过不表。

B - Nuts

基本循环题，略过不表。

C - Tour

基本搜索题，以每个点为起点分别跑 dfs 记录即可，时间复杂度 $O(n^2)$ 可过。

D - Cooking

直接贪心或排序后贪心显然都是错误的。发现数据范围不大，考虑用 dp 解决。

发现分出的两部分中，一定是不小于总和一半的那部分成为答案，考虑处理所有可能分出的部分和，找不小于总和一半的最小值即可，用可行性 $01$ 背包即可解决。

E - Rush Hour 2

由于最终需要到达时间最小，考虑到达时间 $f_t$ 在 $c,d$ 固定时随 $t$ 的变化，有 $f_t=c+\lfloor\frac{d}{t+1}\rfloor$，根据均值不等式推出 $t=\sqrt d+1$ 时 $f_t$ 最小。

又由于 $f_t$ 先减后增，所以在该 $t$ 之前到达就等待至 $t$，否则直接出发一定最优，跑最短路即可。

F - Hanjo 2

矩阵快速幂加速 dp。

发现 $h$ 很小 $w$ 很大，考虑对 $h$ 状压并对 $w$ 进行矩阵加速。

同时每一列的状态跟上一列有关，所以设 $f_{i,j}$ 为前 $i-1$ 列全部填满，第 $i$ 行已填状态为 $j$ 的方案数，发现 $f_i$ 只与 $f_{i-1}$ 有关，考虑预处理所有状态之间的转移方式进行矩阵加速。

所以要解决从上一行为 $i$ 状态转移到这一行为 $j$ 状态的方案数。考虑设 $g_k$ 表示前 $k$ 位的方案数，且横向的 $1\times 2$ 的在后一列考虑，变为一个线性 dp。

若有某一位在上一列和这一列均空，则方案数为 $0$，否则若有一列上为空，则只有唯一填法，$g_k=g_{k-1}$；若两列上都有，则可以随意放。若这个和上一个都可以随意放，就可以竖着放 $2$ 的，$g_k=g_{k-2}+g_{k-1}$。

这样分别处理出所有状态之间转移的方案数，用矩阵加速转移即可。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-06 08:23:54

记录

A 切掉了，B 卡了很长时间，后来跳过看 CD 切了，B最终也没做出来，寄。

题解

A. Marketing Scheme

可以发现 $a=2l$ 时对于 $l$ 满足条件且范围最大，因此判断 $r < 2l$ 是否成立即可。

B. Reverse Binary Strings

发现每次反转可以减短连续段长度，具体地，每次可以同时减小一段黑和一段白或两种中一种，所以答案为两种颜色分别需要减短的长度和，也即每个连续段长度 $-1$ 的和。

C. Chef Monocarp

发现一定有一种最优方案使得按照 $t_i$ 不增排序时，$T_i$ 递增。因此按照 $t_i$ 排序，之后可以使用 dp，设 $f_{i,j}$ 为前 $i$ 个物品处理完且最后一个物品在时间 $j$ 的最小代价，则可以从 $f_{i-1,k},i-1<k<j$ 转移过来，取最小值即可。

D. Minimal Height Tree

发现在 bfs 序上每个节点的所有子节点都是一段连续递增的子串，又因为高度最小就要让每个节点的子节点尽可能多，所以选极大上升子串一定最优，同时每开到下一层就记录一下答案即可。

E. Make It Increasing

发现所有无法修改的位置会把整个序列分成若干段，每一段是独立的。可以加入边界 $a_0=-\infty,a_{n+1}=+\infty$

考虑对每个区间 $[l,r]$，因为要求严格上升，所以需要 $a_r-a_l\ge r-l$，也就是 $a_l-l\le a_r-r$，进一步地可以把 $a_i$ 转化为 $a_i-i$，原序列的上升子序列就变为新序列的不下降子序列。

所以在这个区间内，不在 $[a_l,a_r]$ 区间内的必须改，剩下的元素中最长不下降子序列可以不修改，其他的必须修改，统计答案和即可。

由于区间端点必然属于最长不下降子序列，所以不用特殊处理。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-06 12:03:34

记录

ABCDE 顺利切了，F 罚了一堆，最后过了。G 紫的，Ex 点分树不会，不补了。

题解

A - camel Case

基本循环判断题，略过不表。

B - Trimmed Mean

基本排序题，略过不表。

C - LRUD Instructions 2

模拟，用 map 记录访问情况。

D - Flip Cards

发现每一张卡片只与其左右相邻的卡片有关，因此依次处理时只需要知道前一张卡片的状态即可转移，考虑 dp。

设 $f_{i,0/1}$ 表示前 $i$ 张卡片处理完，第 $i$ 张卡片不翻面/翻面的方案数，只需要从 $f_{i-1}$ 且与这一位不同的状态转移过来即可。

E - Find Permutation

考虑把大小关系转化成一张图，由较小的元素向较大的元素连边，那么：

• 若图中有环则无解，但保证有解所以不用考虑。
• 若有多个无入边的元素则一定有多解，因为这些元素都可以作为 $a_1$。
• 之后便有唯一的 $a_1$，若从 $a_1$ 开始的最长链长度为 $n$，则有唯一的排列，否则没有。

最长链用拓扑排序即可。

F - Teleporter and Closed off

由于要删掉每一个元素并询问，很容易想到处理前缀和后缀答案，删除 $k$ 时只特殊处理 $k-m$ 到 $k+m$ 的答案，把前后缀维护的值加上即可。

所以设 $f_i$ 表示从 $1$ 走到 $i$ 的最少步数，$g_i$ 表示从 $i$ 走到 $n$ 的最少步数，分别顺序和逆序 dp 即可。统计答案时枚举 $i\in [k-m,k-1],j\in[k+1,k+m]$，若从 $i$ 能到 $j$，则用 $f_i+1+g_j$ 更新答案即可。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-06 22:28:55

情况

场正常切 ABC，D 题想了一半感觉很多漏洞，最终没做出，赛后发现没看的 EF 都紫，不看了。

题解

A. Immobile Knight

基本循环 + 判断，略过不表。

B. Array Recovery

发现不降的序列一定合法，因此只要某一位可以变为减去 $d_i$ 就有多种情况，否则唯一合法的 $a$ 即为 $d$ 的前缀和数组。

C. Card Game

对第 $n$ 和第 $n-1$ 张牌的情况进行分讨：

• 若先手有第 $n$ 张牌，直接打出必胜，先手必胜方案数 $\binom{n-1}{\frac{n}{2}-1}$
• 若先手没有第 $n$ 张牌且没有第 $n-1$ 张牌，则后手直接打出 $n-1$ 必胜，先手必败方案数 $\binom{n-2}{\frac{n}{2}}$
• 若先手没有第 $n$ 张牌且有第 $n-1$ 张牌，只能直接打出消耗掉后手的第 $n$ 张牌，然后后手变为先手，$n$ 减小 $2$

因此记录先后手递归下去累加即可，特判 $n=2$ 时必胜 $1$ 种平局 $1$ 种，其实数据范围还可以再大一点的。

D. Reset K Edges

最大值最小，容易想到二分最大深度 $x$，考虑怎么判断深度是否合法。二分复杂度为 $\log n$，所以要在 $n$ 的复杂度内判断。

考虑从哪里断开所用次数最小。发现若从根开始保留到深度为 $x$，可能会导致需要的次数变多，例如在深度为 $x+1$ 的那一层有多个点有同一父亲，完全可以直接把父亲接到根上。

所以应该用深度尽可能低的祖先节点连，因此从叶节点向上搜索，若某一节点已有 $x$ 级子节点，直接将这一节点改到根节点上即可，并不再用其向上更新祖先节点，这样一定是最优的。

由于每个节点的父节点都比其编号小，直接倒序枚举就能保证子节点全部处理过。由于每一个节点只会被其父节点使用一次，再乘上二分的复杂度 $\log n$，总复杂度 $O(n\log n)$

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-08 23:05:18

记录

ABCD 切得还行，就是 C 罚了一发假做法调了一会。EFG 都看了，感觉 F 最好做，然后吃饭去了回来写了 F 发现全是漏洞，改到最后也没过。

感觉这场题目质量挺高的，好好补补。

题解

A - New Generation ABC

基本判断，略过不表。

B - How many?

基本循环，略过不表。

C - Distribution

如果暴力用每颗宝石都更新一遍，时间复杂度 $O(n^2)$，无法通过。

考虑断环为链，变成线性 dp，发现 $t_i$ 最小的 $i$ 答案一定是 $t_i$，以这里为开头断开，答案 ${ans_i}=\min(t_i,ans_{i-1}+s_{i-1})$

D - Sum of Maximum Weights

容易想到计算每一条边的贡献再求和，问题在于如何求出每一条边的贡献次数。

发现一条边能贡献当且仅当路径上没有边权大于 $w_i$ 的边，考虑按照 $w_i$ 不降依次加边，用并查集维护连通块内点数，这样每次 $u_i$ 连通块中每个点和 $v_i$连通块中每个点分别都可以使用不大于 $w_i$ 的边连成路径，因此可以用乘法原理累加答案。

E - Packing Under Range Regulations

首先发现尽量往左放一定不劣，所以依次考虑每一位 $x$（实际上只需要考虑 $n$ 个位置），每次从所有 $l_i\le x$ 的点中找 $r_i$ 最小的填上即可，用堆可在 $O(n\log n)$ 内实现。

F - Substrings

场上想对了写假了，关键在去掉重复的字符串。考虑设 $f_{i,j}$ 表示考虑前 $i$ 位，结尾为 $j$ 的可行 $T$ 数量。

则 $f_{i,a_i}=\sum_{j=0}^{25} f_{i-2,j}+1$，也就是所有前 $i-2$ 位的串后面接上这一位以及这一位本身。对于另外的 $k$ 则是 $f_{i,k}=f_{i-1,k}$，设 $g_i=\sum f_{i,j}$ 即可 $O(1)$ 转移。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-10 14:54:41

记录

只会 ABC，C 还卡了很久。D 题赛后发现是用 set，以后要多练练 map/set。

题解

A. Shuffle Hashing

处理各个字母前缀的出现次数，枚举每个区间作为 $S$ 判断即可。

B. A and B

发现要求就是依次加 $1,2,3\cdots$ 给某个数，最终使两数差为 $k=\left|a-b\right|$

所以先求和直到 $i$ 时 $sum\ge k$，然后分讨：

• 若 $sum=k$，则答案为 $i$

• 若 $sum\neq k$，设差值 $x=sum-k$，若 $x$ 为偶数可直接从前面的数中选出 $x$ 的一半放给另一个数，否则需要 $i+1$ 或 $i+2$ 中为奇数的一个来确保奇偶性。

C. Berry Jam

问题可以看成要选 $a$ 数组的一段前缀和 $b$ 数组的一段后缀，发现要两者数量相等，也就是两段中 $1$ 和 $2$ 的数量差互为相反数，因此设 $f_i$ 和 $g_i$ 分别表示两种的数量差为 $i$ 在 $a$ 和 $b$ 中的最大长度。

用前缀和后缀处理 $f_i$ 和 $g_i$，由于数组下标非负，可以加上常量 $n$。最后枚举 $i$ 并计算 $f_i+g_{-i}$ 的最大值，用 $2n$ 减去即为答案。

D. Segment Tree

发现 $i,j$ 两点间有边当且仅当 $l_j<l_i<r_j<r_i$，所以用树状数组可以统计边数，若边数不为 $n-1$ 则一定不是树。

之后用 set 维护所有的线段，每次在 set 上二分，把所有边加进去，最后并查集判断连通即可。

E. Tests for problem D

首先发现如果 $x,y$ 两点都与 $u$ 有边相连，则 $x,y$ 之间必定无边，所以需要两点分别在 $l_u$ 和 $r_u$ 或两点的线段有包含关系，因此想到每个点的左边连接所有子树，右边只连接它的父亲。

所以进行树形 dp，每次先递归下去处理完子树的左端点，接着确定根的左端点，最后逆序确定所有子节点的右端点，这样所有子节点是逐个包含的，保证不会有边。