标签：10 le frac key 训练复杂度 times 2024 暑假

2024 暑假集训记录

Day 1 - 7.7

cszhpdx 生日快乐！

教练发了 2015 BJ JL HN 省队集训，大概把 BJ 的题顺了一遍，感受是十年前的题目都好板啊...

ppt 还没来得及看，只简单看了几个

2015 BJ 省队集训

Day 2 - 7.8

2021.8.30 - 2024.7.8

继续看 BJ 省队集训题，写题解。发现即使很板，但是数据范围好鬼啊...

我是不是该写几个板子复健了（？

Day 3 - 7.9

中考 653pts rk149，能上 bsz 了捏（

上午学习 Splay，下午写树套树，已经没有码力了/kk

经过一下午的努力我的树套树从 70 变成了 80（笑

Day 4 - 7.10

沐昕姐姐的简单模拟赛也 AK 不了/wtcl

题目质量的确不高，不过 std 写的不错。

queue

求长为 n，不包含 111 和 101 的 01 串数量，答案对 10007 取模。

数据范围 $n\le 10^{18}$

key: 矩阵优化 dp

记录后两位的值，写出转移矩阵，直接矩阵快速幂就做完了。

神奇的 std：$A^{2p-2}\equiv I\pmod p $，故只需递推前 20012 个即可。

paths

n 个点的树，树上有 m 条路径，问最多能选几条不相交路径。

数据范围：$n,m\le 2\times 10^5$

赛场做法：树剖 + 树上 dp

设 $f(u,0/1)$ 表示点 u 的子树内，选/不选 u 的最多路径数。

$f(u,0)=\sum \max f(v,0/1)$

枚举以 u 为 lca 的路径 (a,b)，记路径上的点为 $a_1=u,a_2,\cdots,a_k=a$

$f(u,1)\leftarrow \sum f(a_i,0)-\max f(a_{i+1},0/1)$

把求和号拆开，得到两个和都可以用树剖维护。
注意后面那个不包括 u。

std：贪心

若路径相交，选 lca 深度较大的一定不劣。

感性理解，正确性大概比较显然。

palacinke

n 点 m 边的有向图，每条边上有四种货物中的某几种。经过一条边需要 1 分钟，买货物需要 1 分钟（不管买了多少）。从点 1 出发，最终回到点 1，四种货物必须都买。求在 T 分钟内，有多少种方案。

数据范围 $n\le 25,m\le 500,T\le 10^9$

sub1&2 $T\le 500$ ：暴力状压 dp

$f(t,u,op)$ 表示时间 t，位置 u，买东西状态 op。

$\begin{aligned} f(t,u,op)&\to f(t+1,v,op)\\ &\to f(t+2,v,op|w) \end{aligned}$

复杂度 $O(mT2^k)$

sub3 $n\le 5$ ：矩阵优化 dp

压成一个 $r=5\times 16\times2$ 的矩阵，复杂度 $O(r^3\log T)$

sub4 所有边都是四种都有：随便走 - 完全不买

key：拆点，把“买东西”拆出一条边

只需一个 $50\times 50$ 的邻接矩阵。

正解：容斥

随便走 $-$ 一个不走 $+$ 两个不走 $-$ 三个不走 $+$ 四个不走

枚举 16 种情况，建邻接矩阵时有些买东西的边不连就行。

key：建立汇点，强制最后一次回到 1 是回到汇点

在汇点建立自环，让“不超过T”都变成 T，最后答案就是汇点的矩阵值。

ogledala

有 m 个石子，初始已经挖掉 n 个 $a_1,a_2,\dots,a_n$。

重复下列操作：

找到当前最长的一段连续的石子，若有多段，取最左边的
挖掉最中间的石子，若段长为偶数，则挖掉靠左那个

Q 次询问第 $b_i$ 次操作挖掉的是哪颗石子。

数据范围：$n,Q\le 10^5,m\le 10^{14}$

sub1&4 $b_i\le3\times 10^5$：堆模拟

正解：二分

初始连续段最多只能分出 $\log$ 种不同长度的段

由于任何时刻，一定是从长度最长的段开始分，于是我们可以顺序计算出每种长度的段都有多少个。

排序询问，利用双指针思想，定位分的是长度为 len 的段，并知道是初始第 id 段里的第 num 个 len。

知道在哪一段后，就可以二分出位置。因为可以计算出任意长度的连续段分出的长度为 len 的段的数量。

code：

LL f(LL nw,LL want){// 原长为 nw，能分出长为 want 的段的数量
    if(nw<want) return 0;
    if(nw==want) return 1;
    if(dp.find(nw)!=dp.end()) return dp[nw];
    return dp[nw]=f(nw>>1,want)+f((nw-1)>>1,want);
}
LL query(LL l,LL r,LL len,LL num){
    LL mid=(l+r)>>1;
    if(r-l+1==len) return mid;
    if(f(mid-l,len)>=num) return query(l,mid-1,len,num);
    return query(mid+1,r,len,num-f(mid-l,len));
}

Day 5 -7.11

每日上班 0.5h 的 devout 小姐姐可爱捏

interview

给定序列 $a_n$，求最小的 $x$ 使得前缀 $a_1 \dots a_x$ 中，可以选出 $m$ 个数，极差不超过 $k$。

数据范围：$n,m,k\le 10^5$

key：转化为值域上问题

二分 + 值域上滑动窗口
记录 $num_i$ 表示值域 $[i,i+k-1]$ 有多少个数，线段树维护

task

两台机器 A B，有 $n$ 个任务要安排，要求第 $i$ 个任务开始时，前 $i-1$ 个任务均已完成或正在运行。每个任务在 A B 上运行的时间不同，问最少需要多长时间完成所有任务。

数据范围：$n\le 2000,tA,tB\le 3000$

sub 1&2 $n\le 200,tA,tB\le 300$：$O(n^2w)$ dp

$f[i][j][0/1]$ 表示第 i 个任务在 A/B 上运行，开始时间为 j，另一台机器最早结束时间。

转移平凡，注意第 i 个任务要等第 i-1 个任务开始才能开始。

正解：$O(nw)$ dp

key：最优解时间差不超过 $2mx$ 且某个任务可以开始的时间区间很小

$f[i][j][0/1]$ 表示第 i 个任务在 A/B 上运行，自己的结束时间，且与另一台机器的结束时间差为 j

转移同样平凡，注意数组别开小了。

diamond

有一个序列 $p_i$ 服从 $[1,m]\cap \N$ 的等概率分布，从 1 到 n 执行如下操作：

若 $p_i\in S_i$，选择 $p_i$，结束操作
否则，$i\to i+1$，且之后不能再选择 $p_i$

对于每个 $i$，构造 $S_i$ 使得最终选择的值期望最大，求这个期望。

数据范围 $m\le 10^5,n\le 10^9$

key：期望 dp + 分段矩阵乘

记 $E_i$ 表示序列长度为 i 时的期望值（倒推）
$E_i=\frac{1}{m}\sum\limits_{v\in S_i}v + \frac{m-|S_i|}{m}E_{i-1}$

若干结论：

$S_1$ 一定是全集
$S_i$ 一定选一段后缀
$|S_i|$ 单调不升
key：$S_i=[\lceil E_{i-1}\rceil,m]$（不选还有 $E_{i-1}$，更小的干脆不选）

显然可以线性递推 $E_i$。

发现 $E_{i-1}$ 的系数只与 $\lfloor E_{i-1} \rfloor$ 有关，而 $\lfloor E_{i-1} \rfloor$ 只有 $m$ 种取值，于是可以分段矩阵乘。

二分出每段的右端点，check 方法就是直接判断 $\lfloor E_{cur}\rfloor=k$

复杂度 $O(m\log n)$

control

$n$ 个点的有根树，根节点为 1。
对于 $k=1,2,3,\cdots,n$，在树上选择 $k$ 个关键点。设 $t_i$ 表示 $i$ 到根的路径上距离 $i$ 最近的关键点到 $i$ 的距离。设 $a_k=\min_{所有选择关键点的方案}\{\max t_i\}$，求 $a_1\dots a_n$ 的异或和。

数据范围 $n\le 2\times 10^5$

key：转化为使 $\max t_i\le x$ 至少需要 $b_x$ 个关键点

贪心地从深度最深的不合法点开始，选择它的 $x$ 级祖先，标记子树内所有点为合法。

神奇的事情在于，对于某个 x，最多只可能做 $O\left(\frac{n}{x+1}\right)$ 次标记。于是复杂度是调和级数 + 线段树维护标记（注意不应重建线段树，而应撤回标记）。

写法上，可以使用标记永久化的思想（类似李超线段树），但需注意 pushup 时要判好左右儿子分别被标记的情况。

Day 6 - 7.12

构造之神 —— devans

记录常见的错误，调代码的时候可以对照着排查——zzj

中午拉着全机房的人测 mbti 捏（
呈现了 mbti 多样化的局面...

CF1983B Corner Twist

唯一自己会做的题/kk

$n\times m$ 的 012 矩阵，每次操作：

选择一个至少 $2\times 2$ 的矩形
对其中两个对角格子 $+1$，另外两个 $+2$

问可否通过若干次操作，把矩阵 $A$ 变成 $B$。

key1：必要条件 $\to$ 加强成充分条件

整个矩阵的和 $\bmod 3$ 意义下不变（每次操作 +6）
每行 & 每列的和 $\bmod 3$ 意义下不变（每次操作 +3）

下证为什么是充要条件。

key2：简化操作 $\to$ 局部依次满足

显然，每次操作都可以拆成若干次选 $2\times 2$ 矩阵。
只考虑满足左上角，从左到右，从上到下依次操作。由于行列和不变，所以满足前 $n-1$ 行、前 $m-1$ 列后，第 $n$ 行、第 $m$ 列一定已经满足。

CF1730B Meeting on the Line

数轴上有 $n$ 个点 $x_n$，钦定一个点 $x_0$，最小化 $\max\{t_i+|x_i-x_0|\}$。

这题有弱智的 $O(n\log n)$ 三分做法，但思维点在线性做法。

key1：弱化问题 $\to$ 发现性质

如果 $t_i=0$，显然是选最左和最右点的中点。

key2：转化问题 $\to$ 保留性质

拆点成 $x_i-t_i$ 和 $x_i+t_i$，于是满足上述性质。

CF1391E Pairs of Pairs

给定 $n$ 点 $m$ 边的无向连通图，选一个问题完成：

找到一条点数 $\ge \lceil \frac{n}{2} \rceil$ 的路径
找到一个大小 $\ge \lceil \frac{n}{2} \rceil$ 的集合，对所有点两两配对，满足任意两对点的导出子图有 $\le 2$ 条边。

key：dfs 生成树没有横叉边

若存在深度 $\ge \lceil \frac{n}{2} \rceil$ 的点，直接选它到根的路径即可。

否则树的层数较小，直接每层的点两两配对，一定满足要求。

没有横叉边，所以导出子图最多有两条返祖边
每层最多扔掉一个点，而一共只有 $< \lceil \frac{n}{2} \rceil$ 层

三道类似的例题：

CF1508C Complete the MST

$n$ 个结点的完全图，给定 $m$ 条边的边权。给未赋权值的边赋值，使得所有边权异或和为 0，并最小化最小生成树的边权和。

数据范围 $n,m\le 2\times 10^5$

key1：一条边赋异或和，其他全 0

若有边不选进最小生成树，那么直接把这条边赋成异或和
否则怎么赋值都一样，这样做肯定不劣

key2：考虑给定边的稠密程度

$n\le O(\sqrt m)$ 即 $n\approx 750$，枚举哪条边赋值成异或和，直接跑最小生成树，复杂度 $O(m\sqrt m)$
$n> O(\sqrt m)$ 即给定边稀疏，一定有未赋值的边不选进最小生成树，直接当所有边权为 0，缩连通分量，跑给定边的最小生成树即可

如何求完全图删去 $m$ 条边的连通分量？
子问题 CF920E Connected Components?

key3：最大值 $\ge$ 平均值

删去 $m$ 条边相当于删去 $2m$ 个度数，也就是说剩下度数的平均值是 $n-1-\frac{2m}{n}$。

从度数最大的点开始考虑，不与它联通的点很少，最多只有 $\frac{2m}{n}$ 个，枚举每个点的联通情况，总复杂度 $O(m)$。

CF1508D Swap Pass

平面上 $n$ 个点，每个点上有值 $p_i$，若干次操作：

选择两个没有连边的点 $(i,j)$，连接 $(i,j)$
交换 $p_i,p_j$

要求线段不能有交（除端点外），给出操作方案使 $\forall i,p_i=i$。

保证不存在三点共线，$n\le 2000$

key1：局部问题 $\to$ 优秀性质

置换环：对于排列 $p_i$，连接 $(i,p_i)$，一定得到若干个环。

只有一个置换环的排列可以用菊花图完成
操作就是不断交换根 $x$ 和 $p_x$，显然这些边不会有交

key2：合并问题 $\to $ 保留性质

置换环内部交换 $\to$ 拆解置换环
置换环之间交换 $\to$ 合并置换环

考虑能否把所有点合并到一个置换环中。
首先连出一个菊花，显然的可以连接最外面的所有边，这样就全部合成一个置换环，且不会相交。

具体的，选择最左边的点为根，斜率排序，顺时针/逆时针合并置换环（并查集维护），若在一个置换环里就跳过，否则连边。
操作顺序是先合并置换环，再做菊花图。

习题： CF1491G Switch and Flip

CF1523D Love-Hate

$n$ 个人，$m$ 种货物，每人喜欢不超过 $p$ 种货物。求一个最大的子集，使得有 $\ge \lceil \frac{n}{2} \rceil$ 个人喜欢所有子集内的货物，输出方案。

数据范围 $n\le 2\times 10^5,m\le 60,p\le 15$

key：答案被超过 $\lceil \frac{n}{2} \rceil$ 个人喜欢 $\to$ 随机到喜欢答案的人概率极高

随机到某个人 x，认为答案是被他喜欢的，于是只有 $2^p$ 种可能。
扫一遍 $n$ 个人对这 $p$ 种货物的态度，一共也只有 $2^p$ 种，可以用桶存每种态度的人数。
每种态度只对它的子集有贡献，可以证明枚举子集的子集复杂度 $3^p$。
再扫一遍 $2^p$ 种答案，看哪些有 $\ge \lceil \frac{n}{2} \rceil$ 个人喜欢。
单次随机复杂度 $O(np+3^p+2^p)=O(3^p)$ 大约是 $2\times 10^7$，故可以随个差不多 50 次的。

证明枚举子集的复杂度
$\sum_i^p C_p^i \left(\sum_j^i C_i^j\right)=\sum_i^p C_p^i\times 2^i=3^p$（二项式定理）
还有一种高维前缀和的做法是 $O(p2^p)$ 的

CF1804F Approximate Diameter

$n$ 点 $m$ 边的初始无向图，$q$ 次添加一条边，询问图的直径。允许 $\frac{1}{2}ans\le out\le 2ans$ 的误差。

key1：$q=0 \to$ 类比树的直径

钦定一个点为起点，dfs 出最远点，这个距离一定在 $[ans/2,ans]$ 之间，记为“较优答案”。

key2：允许误差 $\to$ 二分可行区间

正确答案 & 较优答案单调不增

记正确答案为 $A_p$，“较优答案”为 $C_p$。
重复下述过程：

当前有答案 $C_{cur}$，二分可行区间右端点 $r$
check(p)：判断 $C_{cur}\le 2C_p$
$cur\to r+1$

为什么？$C_p\in [\frac{1}{2}A_p,A_p] \to 2C_p\in[A_p,2A_p]$，故 $C_{cur}\le 2C_p$ 一定安全，否则可能不安全（但我们不知道）。

显然 $C_{cur}$ 每次至少砍半，故只需二分 $\log$ 次。
总复杂度 $O(n\log^2n)$

标签：10,le,frac,key,训练,复杂度,times,2024,暑假
From： https://www.cnblogs.com/Cindy-Li/p/18294636

2024 暑假训练记录