SDSC2025

day 1

模拟赛

T1

答案由前后缀 gcd 和中间加 k 的 gcd 组成，前缀 gcd 一共有 log 段，每一段一定是取最大的 l 最优，后缀同理，枚举 l 计算答案就行了，时间复杂度 $O(n\log V)$。

---

T2

记录二元状态 $(c,m)$ 表示工作次数与剩余钱数，两者构成严格偏序关系，因为走得越远越有可能工作得少。记 $f_{i,x}$ 表示走到 $i$ 路径上最大值在 $x$ 的状态，dij 转移即可。

---

T3

观察到只需要选择最大值和次大值的点所确定的路径即可，设 $f_{i,x}$ 表示点 $i$ 连了权为 $x$ 的点的答案，$g_i$ 表示考虑到 $i$ 的子树内的答案，有转移

$$f_{u,i}=\max\{f_{u,i}+g_v,f_{v,i}+\sum_{v'<v}g_{v'}\}$$

$$g_u=\max\{g_u+g_v,f_{u,i}+f_{v,i}+\min(i,j)\}$$

对每个点开 seg 维护 $f_{u,i}$ 的最大值与 $f_{u,i}+i$ 的最大值做线段树合并就行。

---

T4

$c_i=i-b_i$ 的含义是 $b_i$ 的前缀中 $p_i$ 的排名，扫 $i:1\rightarrow n$，由定义设 $p_i=c_i$ 然后把 $p_j\geq c_i$ 的 $p_j$ 加一，于是可以构造出唯一的 $p$。这样可以做到 $O(qn)$。

对于一个区间，定义 $t(x)$ 表示 x 经过区间之后会变成的数，这是一个分段函数，并且每一段的斜率都是 1。这个东西不好维护，转而维护 $f(i)$ 表示表示如果 $x\geq f(i)$ 那么 $x\rightarrow x+i$，考虑合并两个区间的函数 $f_l$ 和 $f_r$，考虑一共增加了 $k$，枚举分别加了 $i,j$，那么 $f(k)\geq f_l(i),x+i\geq f_r(j)$，于是 $f(k)=\min_{i+j=k}\{\max(f_l(i),f_r(j)-i)\}$。发现这样合并有很好的性质：如果 $k$ 是由 $(i,j)$ 转移而来的，那么 $k+1$ 就只能从 $(i+1,j)$ 或者 $(i,j+1)$ 转移过来！原因是 $f$ 单调不降，$(i,j)$ 能多贡献就多贡献，不会回退，就得到了 $O(len)$ 合并信息的做法。线段树维护这个信息就能做到 $O(n\log^2 n)$。但是这样维护单调修改的话就是 $O(n)$ 的，考虑分块平衡复杂度，分成 $B$ 块，每块开线段树，这样修改时间复杂度 $O(B)$，查询时间复杂度 $O(\frac{n}{B}\log n)$，平衡一下令 $B=\sqrt{n\log n}$ 就可以做到 $O(n\sqrt{n\log n})$ 了。

讲课：基础算法 神秘题目

？？？是正常人能想到的？？？

---

Latin Square

$n\times n$ 的矩阵，每行每列都是 $1$ 到 $n$ 的排列，有如下几个操作：

• 每行向右/左循环移位
• 每行向上/下循环移位
• 将每行/列的排列变为逆排列（一个排列 $p$ 的逆排列 $q$ 指 $p_{q_i}=i$）

求最终矩阵的样子

平凡的记 $(i,j)$ 维护前两种操作是方便的，但难以维护逆排列的操作，考虑记 $n^2$ 个三元组 $(i,j,a_{i,j})$，那么逆排列操作就变成了交换 $(i,j)$ 中一维和 $a_{i,j}$，直接维护三元组中的位置最后到了那以及偏移量就行了。

提交记录：https://codeforces.com/contest/1458/submission/330299272

---

Cloyster

交互。$n\times n$ 的矩阵，每个格子有互不相同的正整数值你不知道。除了最大值所在的格子，每个格子都存在一个相邻的格子值比自己大。相邻指的是有公共边或点。每次可以询问一个格子上的值，要求出最大值的位置，询问次数 $3n+210$ 次。

非常好题目，考察了基础算法。先问出一列来，把这一列的最大值位置的周围八个格子都问出来，如果最大值在左侧就往左走否则往右走，这样会问 $n\log n+8n<3n+210$ 次。不写了，太屎了。

---

Replace

对于排列 $\{a_n\}$，定义 $f([l,r])=[\min(a_l,\dots,a_r),\max(a_l,\dots,a_r)]$，多次询问 $[l,r]$，求最小的 $k$ 使 $f^k([l,r])=[1,n]$.

引理：对于 $[l_1,r_1]\cap[l_2,r_2]$，那么 $f([l_1,r_1]\cap[l_2,r_2])=f([l_1,r_1])\cap f([l_2,r_2])$。

由此可推广到多个区间以及高次复合的情况，于是选取每个 $[i,i+1]$ 作为答案区间，倍增预处理 $f^{k}([i,i+1])$，st 表做到 $O(1)$ 查询。

提交记录：https://codeforces.com/contest/1707/submission/330310685

---

四舍五入

对于 $x$，操作最小次数成为 $y$。操作形如选择一个不超过 $m$ 的进制 $k$，将 $x$ 写为 $k$ 进制形式然后四舍五入将末尾变成 0。

我们发现能形成 $y$ 的 $x$ 是连续的，所以倍增预处理 $f^k(l,r)$ 表示 $[l,r]$ 中的数进行 $k$ 次逆操作之后的区间，用 st 表维护即可。

day 2

模拟赛

T1

神秘题。

---

T2

从每个黑点开始 01bfs 把第一个遇到的点扔到联通快里然后跑 Kruscal 就行了，但是我数组开小卡了半个上午。

---

T3

维护 lcm，gcd，sum 一车可能有用的信息然后算复杂度就做完了。

---

T4

困难，不会。

讲课：构造

写 day 1 的笔记里了，反正都很神秘就对了。

day 3

模拟赛

T1

文 艺 平 衡 树。

---

T2

必要的观察是删除的三条边一定分别在三条主干道上，并且如果有 $(S,T)$ 这样一条边那么答案是 0。对于主干道内部相连的点把他们中间的扔掉，用差分前缀和就可以快速询问主干道的某个区间有多少边可以割。对于额外边相当于限制主干道要么都割在左边或右边，考察具体的某一条便，相当于限制另一条主干道的割只能在 $[l,r]$ 内。预处理 $x$ 主干道上一个区间在 $y$ 主干道上的影响 $[l_i,r_i]$，四个指针表示 1 主干道限制了 2/3 主干道的区间，枚举 1 的时候指针右移，时间复杂度 $O(n+m)$。

ppt 里面的另解没看懂，感觉很假。

---

T3

最后区间的情况肯定是每个区间都是首位相连中间没有空，找到每个区间都覆盖的点 $P$ 把它平移到原点。如果 $n$ 是奇数，那么一定存在一个区间不动，否则加上区间 $(0,0)$ 即可，设为 $Y$。考虑左边的区间从左到右的序列是 $P$，右边的区间从右到左构成的序列是 $Q$，那么答案就是

$$\sum(r_{P_i}+i\times(r_{P_i}-l_{P_i}))+\sum(-l_{P_i}+i\times(r_{P_i}-l_{P_i}))+(-l_Y\times|P|+r_Y\times|Q|)$$

由排序不等式得 $P,Q$ 肯定是等长并且单调递减，设 $dp(i,j,0/1)$ 表示前 $i$ 个区间选 $j$ 个放左边的，是否确定 $Y$ 的答案就能 $O(n^2)$ 转移了。

讲课：数论与计数

[SNOI2019] 数论

以 $\operatorname{lcm}$ 为周期，每个周期直接算，考虑最后的散段怎么做。考察一个经典结构，对于 $[0,Q-1]$ 中的数建立一个点，每个点向 $(i+P)\bmod Q$ 连边，那么整个图会被分为 $\gcd(P, Q)$ 个环，每个环的点数是 $\dfrac{\operatorname{lcm}(P,Q)}{P}$。假设 $P\leq Q$，在这个结构上考虑问题，枚举 $a_i$，我们要找 $a_i$ 这个环上有多少个 $b$，在环上做前缀和就可以了。

---

HDU 5728（共加五个 0）

相较原题 $n\leq 10^{10},m\leq 10^9$。

对于 $\sum \varphi(in)$ 经典做法是

$$\sum_{i=1}^m\varphi(in)=\sum_{i=1}^m\dfrac{\varphi(i)\varphi(n)}{\varphi(\gcd(i,n))}\gcd(i,n)$$

然后各种经典套路往里扔，最后推出来

$$Ans=\varphi(n)\sum_{T|n}(\sum_{d|T}\dfrac{d}{\varphi(d)}\mu(\dfrac{T}{d}))(\sum_{i=1}^{\lfloor\frac{m}{T}\rfloor}\varphi(iT))$$

而 $\mu^2(n)=1$ 告诉我们 $n$ 没有平方因子，于是对于 $d$ 可以预处理每个因子 $d$ 的价值，左边那一坨直接 $O(3^{\omega(n)})$ 剥蒜，右边的地柜下去知道 $n=1$ 是跑一遍杜教筛就做完了。

---

CF1034C Region Separation

设权值和为 $S$，分成 $k$ 份，那么 $u$ 的父边需要被断掉当且仅当 $s_u\bmod S/k=0$，考虑求 $f_k$ 表示多少个 $u$ 满足条件，则符合约束当且仅当 $f_k=k$，考虑求 $f$，等价变化一下，条件等价于 $S/k|\gcd(s_u,S)$，进一步等价于 $\frac{S}{\gcd(s_u,S)}|k,k|S$,然后将所有 $\frac{S}{\gcd(s_u,S)}$ 标记出来做 Dirichlet 前缀和即可。

day 4

模拟赛

省流：MikeFeng 没有唱歌，严厉谴责！！！

---

T1

dsu on tree 板子。

另解：特判阳历然后全输出 2。

---

T2

猫树板子，但是 ST 表比猫树块，只不过需要卡空间，具体方法是利用 vector 动态分布内存。场上不会这个直接挂成暴力分了。代码如下：

using poly=vector<int>;
struct table
{
 poly pos; vector<poly>f; int st[N],ed[N];
 inline void build()
 {
  int siz=pos.size(),lg=__lg(siz);f.resize(lg+1);
  fo(i,0,lg)f[i].resize(siz+1); fo(i,1,siz)f[0][i]=e[pos[i-1]].w;
  fo(i,1,lg)fo(j,1,siz)if(j+(1<<i)-1<=siz)f[i][j]=max(f[i-1][j],f[i-1][j+(1<<i-1)]);
  fo(i,1,n)st[i]=ed[i]=-1;
  int j=0; fo(i,1,n){if(pos.back()<i)break;while(pos[j]<i)++j;st[i]=j+1;}
  j=siz-1; Fo(i,n,1){if(pos.front()>i)break;while(pos[j]>i)--j;ed[i]=j+1;}
 }
 inline int qry(int l,int r){int k=__lg(r-l+1);return max(f[k][l],f[k][r-(1<<k)+1]);}
}tr[55];

---

T3

发现颜色改变时会回收所有标记，先用 $(\min,+)$ floyed 跑出不同色之间的最小距离，然后 $(\min,\max)$ floyed 跑最短路。

---

T4

兔队板子。

讲课：图论与树上问题

图论：https://www.cnblogs.com/mikefeng/p/18994175
树上问题：https://www.cnblogs.com/mikefeng/p/17459007.html

day 5

模拟赛

T1

我的做法是数据范围分治+莫队，std 就是把我的莫队改成主席树。赢！

---

T2

建出操作树来，容易证明每个子树的取值范围是一个连续区间 $[l_i,r_i]$，然后递推。

---

T3

完全无法理解 solution 里面写的是什么。

嗯似乎理解了，大概就是说扫值域然后钦定这个位置前都填满算方案数。

讲课：数据结构

day 6

模拟赛

省流：出成省选场了。

---

T1

二分答案，一个区间 $(j,i]$ 合法当且仅当 $s_i-s_j\geq mid$，扫序列贪心，记前一个选的是 $k$，如果存在 $j\in [k,i)$ 满足 $i-j$ 是质数并且 $s_i-s_j\geq mid$ 那么就一定能划分出一段来。set 维护可选的 $j$，直接遍历，期望 $O(log n)$ 次找到一个质数，时间复杂度 $O(n\log (nV)\log n)$。

---

T4

PAM 板子。我不会 PAM。

讲课：动态规划

[AGC061C] First Come First Serve

考虑一种顺序有两个对应的方案，对于一个不同的 $i$，一定不会有其他人在 $(a_i,b_i)$ 中选择，此时 $i$ 选 $a_i,b_i$ 对顺序没有影响，尝试建立顺序到字典最小的方案的映射，可以认为每个顺序对应的选择方案是对于每个选了 $b_i$ 的 $i$，$(a_i,b_i)$ 中有被选择的元素，显然这样的方案是唯一的。考虑容斥，对于每个 $i$，可以选择 $a_i$ 或 $b_i$，系数是 1；也可以选择 $b_i$ 并钦定 $(a_i,b_i)$ 中不被选择，系数是 -1，发现对于每次这个情况，都可以确定一个 $[l,r]$ 内的选择情况，注意到这些区间有交的时候贡献是 0，所以只需要考虑无交的情况。我们要求的答案写出来就是 $2^n\sum_{S\subset U}[\forall i,j\in S,N(i,j)]\frac{1}{2}\sum_{j\in S}(r_j-l_j+1)$，其中 $N(i,j)$ 表示 $[l_i,r_i]$ 与 $[l_j,r_j]$ 无交，我们发现这个形式可以 dp，设 $f_i$ 表示分配了前 $i$ 个的方案数，有转移 $2f_i\rightarrow f_{i+1},f_{l_i-1}\rightarrow f_{r_i}$，时间复杂度 $O(n)$。

day 7

模拟赛

T1

观察到次数不超过 11，直接爆搜剪枝。

---

T2

首先发现多次添加相同的数据肯定不优，所以限制每组数据最多选 1 次。考虑维护添加了一部分数据后的信息，发现只需要维护 $(S_1,S_2,S_3)$ 分别表示跑到非 OK 的点/最大时限的点/最大空间限制的点的代码集合，并且 $S_1\not\subset S_2$ 或 $S_1\not\subset S_3$ 的状态都是没有意义的，状态数变成 $5^m$，通过预处理可以做到 $O(n5^m)$。

---

T3

访问的代价是恒定的 $n-1$，因此只用算更改权值的代价，设为 $f_i$，设 $A_i$ 表示 $[1,i]$ 中后缀最大值的集合，$B_i$ 表示 $[i,n]$ 中前缀最大值的集合，那么 $f_i=|A_i\bigcup B_i|-1$。考虑一个位置值的改变会对多少 $A_i,B_i$ 产生影响，这样交换的时候就需要减去原来的影响，交换过来再加上现在的影响。一个位置 $i$ 在 $b_j$ 中，当且仅当 $\max_{k=j}^iR_k< R_i$，于是可以线段树二分出最左端的位置 $l$，此时只需要讨论 $[l,i)$ 中的点的 $A$ 是否包括了 $R_i$，发现除非 $R_l=R_i$，$i$ 一定会对其中的 $A$ 有贡献，否则不会产生贡献。对于 $A$ 同理，用线段树维护，从大到小把数据塞进去就行了。

讲课：杂题选讲