2022寒假集训做题总结

这里专门用来放 2022 寒假集训做的题。

也算是对课上知识的一点补充和应用吧。

年前做题记录

Line Graph Matching

关键词：ywy，Tarjan

题目大意-by ywy

定义一个带权无向连通图的最大权线图匹配为，若两条边有公共端点且未被匹配，则它们可以匹配，最终使得匹配边的权值和最大。

求最大权线图匹配的权值和。

思路

考虑在偶数条边的图上，每条边必然可以被匹配。

如果只有奇数条边，那么整张图至少有一个边不能被匹配。

某条边不是割边。随便删，不影响图联通。
某条边是割边。贪心的去想，
1. 如果删去之后剩下的两个连通块边数均为偶数，那么可删；
2. 删去之后一定不如在随机一个连通块中删去一个非割边（因为就算你不删他，他也匹配不了了）。

对于 1 类边和 2.(1) 找一条权值最小的边即可。

Roads and Planes G

关键词：ywy, Tarjan, Dij, 卡常

题目大意-by ywy

给个图，有一些带权有向边和无向边，保证：1. 有向边不会出现在环上，2. 无向边边权都是正的。给你起点，求单源最短路。

思路

这个题被 $Shu-kuang$ 秒了，所以课上没有什么思路。

根据题意，可以先缩点，点内跑最短路，点外跑拓扑排序。

但由于记录店内信息时忘记了 vector 这个东西，就拿数组搞了搞，结果被卡常到不开 O2 1min 多？开了 O2 秒过，一道题调了俩小时。自闭了……

Emails

关键词：ywy, 图论杂题，思维， Debug

题目大意-by ywy

有 $n$ 个人，初始时每个人有一个通讯录（若 $i$ 在 $j$ 的通讯录中，则 $j$ 一定也在 $i$ 的通讯录中，双向的），每天早上，所有人都会将自己目前通讯录的内容发送给自己通讯录上的所有人，到了晚上，每个人会把自己今天接收到的且不在自己通讯录上的人名加入通讯录（更新）。

求几天后每个人的通讯录上都有其他 $n-1$ 个人的名字。你可以输出 $ans$ 或 $ans+1$ 。

$n \le 1e5$ ，初始时通讯录大小之和 $\le1e5$

思路

被 $ljx$ 大佬切了 qwq

一道思维题，可以发现每天任意两个人的距离都会变成前一天的 $\frac{1}{2}$ 。所以答案即为 $log_2d + 1$ (d 为图的直径)。然后发现输出 $ans$ 和 $ans + 1$ 都可以。可以发现一个性质：对于任意一个点为根的广度优先搜索树，设它的深度为 $h$ ， $h \le d \le 2h$ 。所以可以直接输出 $\lceil log_2h\rceil + 1$ 。

然后就写挂了。

Joint Excavation

关键词：ywy，图论杂题，构造，审题

题目大意-by ywy

有一个无向连通图，你需要找一条简单路径，使得把这条路径上的点删去后，可以把剩下的点划分为大小相等的AB两个集合，并且所属集合不同的两个点不能相连。

构造任意一个方案或说明无解。

思路

先把所有点设为 $A$ 集合，随机找一个点开始 $dfs$ ，经过的点设为路径，回溯时设为 $B$ 集合，当某一时刻 $|A| = |B|$ ，输出答案即可。

正确性证明：

考虑题目中的所有约束条件

简单路径
A, B 之间不能相连
集合内部可以不相连（课上就在这里卡了很久）

由于搜索树上当前某一分支一定是一条简单路径，满足第一个性质。当某个点已经被回溯之后，只可能与一个路径上的点相连，不可能与没访问过的点相连，满足性质 2。

证毕。

需要注意的点：

路径上的点一定要按照访问顺序输出，不能打标记按编号顺序输出，集合内没有要求。

City Brain

关键词：ywy, 图论杂题， debug

题目大意-by ywy

$n$ 个点 $m$ 条边的无向图，每条边长度 $1m$ ，初始时每条边上的限速为 $1m/s$ ，现在 $A$ 和 $B$ 两人要分别从 $S_1$ 和 $S_2$ 出发到达 $T_1$ 和 $T_2$ 。

现在你有 $k$ 个金币，你每次可以花费一个金币使得某条道路的限速增加 $1m/s$ 。

最小化 $AB$ 两人走路的总时间（实数）。

$n,m\le 5000，k\le 1e9$

思路

课上能想到的是枚举路径交，计算两种边边数，考虑分配。

实际上要用三分进行分配，在计算边数时需要适当剪枝。

因为计算边数时少了特判而导致爆炸调了一下午。

Tax

关键词：ywy，图论杂题，爆搜，复杂度证明，卡常

题目大意-by ywy

有 $n$ 个点 $m$ 条无向道路，每条道路由一个公司控制并有一个代价。你现在要从 $1$ 号点走到其余每个点 $i$ ，如果一条道路是你经过的第 $k$ 条属于这家公司的道路，你需要交 $k\times \text{道路代价的路费}$ 。

现在你只会走边数最少的路径，在这个条件下对每个点求1到它的最小代价。

$n\le 50$ ，图连通

思路

看到最短路径条数，构造分层图，分层图上跑爆搜。不能#define int long long，会被卡常。

一定要记住，不满足最短才入队的题，不能直接用全局最短路来更新当前局面答案，而要在当前过程维护当前路径长度。

CF1080E Sonya and Matrix Beauty

关键词：ywy, 字符串杂题， hash

题目大意-by ywy

有一个 $n\times m$ 字符矩阵，求有多少这样的子矩阵，满足对每一行重排后，能够使得每一行和每一列都是回文串。

题目思路

课上想出来了 qwq

大概是先枚举那几列，用基于字符集而不是序列的 hash 压成一个字符串然后再跑 manacher 就行。

然而 hash 写挂了。直接暴力跑字符集比对的。

[POI2012]OKR-A Horrible Poem

关键词：ywy，字符串杂题， hash，素数筛法

题目大意-by ywy

给个串，q次询问某段子串的最小整循环节长度。

$|S| \le 5e5，q \le 2e6$ ，时限1s

思路

基本上就是考了几个性质

最小循环节长度一定为字符串长度的约数。
任意整数长度的循环节长度一定为最小循环节长度的倍数
令最小循环节长度为 $k$ , 满足 $s(l, r - k) = s(l + k, r)$ 。

可以配合 $hash$ 用来 $O(1)$ 求最小循环节长度。

和一个思维方式：枚举约数通过反复除以最小质因数来实现。

需要线性筛预处理一下。

Elastic Search

关键词：ywy，字符串杂题，AC 自动机上 DP

题目大意-by ywy

给你n个字符串，你要用它们构造一个最长的互不相同的字符串序列，使得后一个串是前一个串的子串。

求最长的序列长度。

$n,\text{总串长}\le5e5$

思路

首先可以考虑把子串这个概念拆成前缀的后缀，这个东西在 $AC$ 自动机上就非常好维护。

于是先把 $AC$ 自动机建出来。每个串答案就是从源点沿着一条路径走到结尾，把中途所有经过的点的 $fail$ 数子树答案取最大值再 $+1$ 。

但是这样复杂度过不去，于是应该改成广搜，每次直接继承 $fa$ 和自己的 $fail$ 子树（因为广搜一定满足搜到他时 $fail$ 子树已被遍历）。

String Problem

关键词：ywy，字符串杂题， KMP，乱搞

题目大意-by ywy

给个字符串，对于每个前缀，求该前缀的字典序最大的子串。你只需要输出出现位置最靠前的子串区间即可。

$1\le|S|\le10^6$

思路

学长讲的方法是用链表维护，但是没听太懂。

于是换种思路。维护一个变量 $st$ 把 $nxt$ 的含义改成相对于 $st$ 变量的位置。然后每次改 $st$ 就行。

Popcount Words

关键词：ywy，字符串杂题， ac自动机，倍增

题目大意-by ywy

定义 $01$ 串 $w(l,r)=s_l, s_{l+1}, \cdots, s_r$ ，其中 $s_i=popcount(i)\%2$ （即二进制表示中1的个数的奇偶性）

给定n个区间，令大串 $S=w(l_1,r_1) + w(l_2,r_2) + \cdots + w(l_n,r_n)$

$Q$ 次询问某个给定 $01$ 串在 $S$ 中的出现次数。

$1\le,r\le1e9，n\le1e5，\text{询问串总长度}\le5e5$

思路

很惭愧，只有部分思路。

首先可以发现先关于 $w$ 的性质，那就是倍增取反。然后就可以预处理出所有的区间，但由于长度问题，并不能直接插入 AC 自动机。而是要利用打标记的思想，来对答案进行统计。

[PA2013]Raper

关键词：tbl，杂题， wqs二分，反悔贪心

题目大意-by tbl

你需要生产 $k$ 张光盘，生产每个光盘需要经过两步工序 $A,B$

你有 $n$ 天时间，每天你可以将至多一张光盘执行工序 $A$ ，随后将至多一张光盘执行工序 $B$ 。

每天执行 $A,B$ 的花费是不同的(你可以在某些天不执行工序，这样就无需花费）

求生产 $k$ 张光盘的最小花费， $n\le 5e5$ ,花费的值域为 $0$ 到 $1e9$

思路

经过一顿玄学分析可以发现它是凸函数。同时，知道总权值求最大个数比知道个数求最小权值要好求。

然后就可以考虑 $wqs$ 二分，这个东西可以算是一种思想，简单来说就是二分斜率，来使直线与凸函数相切。

在这题的具象意义就是给所有步骤二分一个虚拟权值。然后进行反悔贪心。求出虚拟权值加持下使得总权值为 $0$ 时的最大光盘数。

至于反悔贪心，考虑对于每一个 $B$ ，找到它前面最小的 $A$ 来进行匹配。同时插入一个权值为 $-b_i - val$ 的点，如果之后选了这个点，就相当于拆散了原来的组合。并且将当前点进行匹配，但要注意这次选择并不能使答案增加。

这个过程可以用堆来维护。

[SDOI2016]生成魔咒

关键词：zrq, SAM

题目大意-by zrq

给定一个字符串，请你求出 $prefix_{1,⋯,n}$ 的本质不同子串个数。 $n≤1E5$

思路

在这道题之前，先明白一个 trick ：

对于一个字符串，他所有的本质不同子串数即为对于任意一个 SAM 上的节点，它里面所有等价类 $maxlen - minlen + 1$ 。即 $len_x - len_{fa_{x}}$ 。

有了这个 trick 再加上 SAM 本身即为在线算法。每插入一个字符，只会有至多一个节点能够影响答案。即可线性解决这题。

年后做题记录

Best ACMer Solves the Hardest Problem

关键词：ywy，杂题， Debug

题目大意-by ywy

题意：维护一个初始有n个带权关键点的二维平面，支持m个下列操作：

1 x y w 添加一个权值为w坐标为(x,y)的关键点（保证那里没关键点）

2 x y 删除在(x,y)的关键点

3 x y k w 将距(x,y)为√k的所有关键点权值+w

4 x y k 询问距(x,y)为√k的所有关键点权值和

$n,m\le 1e5，k\le 1e7$ ，所有坐标都是 $\le 6000$ 的正整数

时限是 12s

思路

考虑由于圆上的整数点很少，可以暴力预处理出对于所有的 $k$ ，在圆上的点相对位置。然后每回暴力做即可。

这道题坑点也不少。

首先发现数据组数过多，所以不能用 memset，而应该给所有修改过的点打上标记。

其次在坐标轴上的点要注意只能算在两个象限里。

第三，可能算自己搞出来的坑点吧。为此调了一个小时。具体：

for (int i = 0; i < 4; ++i) {
  // …………
  if (nx > 6000 || ny > 6000 || nx < 1 || ny < 1) continue;
  // …………
  if (!j.first || !j.second) ++i;
  // 对于坐标轴上的点，只进行 1, 3 象限，保证不重复。
}

理想是美好的，但然而 continue 导致第 5 行执行错误。。。

Necklace

关键词：ywy，杂题

题目描述-by ywy

有 $n$ 个点按照 $1,2,3,\cdots ,n$ 的顺序排成一圈，其中 $m$ 个点是关键的。现在要在环上把它们划分为 $m$ 段，每段必须有一个关键点。

最小化最长段长度，输出这个长度。

$n\le 1e18,m\le 1e6$ ，1s

弱化版：序列操作。

思路

在学长说出弱化版标签之后才知道怎么做。考虑直接求不好求，但是二分之后就可以贪心去找。二分+贪心挺常见的？但是在圆上的话起始点并不一定在第一个关键点，所以需要进行一些平移操作。

听说貌似有线性做法，方法就是找局部最大下界。即:

$\max(\lceil \frac{n}{m}\rceil,\ \max_{i \ne j}^m\lceil \frac{x_j - x_i + 1}{j - i + 1} \rceil)$

然后这个东西可以用单调栈来找，然而没写出来。

Cactus

关键词： ywy，杂题，诈骗题

题目描述-by ywy

设 $f_n$ 为n个点仙人掌图的数目，求

$\sum_{i=1}^n\prod_{j≠i}\frac{1+f_i−f_if_j}{f_i−f_j}$

$n \le 3e5$ ，模 998244353

思路

其实这个题和 $f$ 取值没有关系，就是一个斐波那契数列。然后就没有然后了。

Interstellar Hunter

关键词：ywy，杂题，计算几何

题目描述-by ywy

现在在二维平面的原点上，接下来有 $q$ 次事件：

你学会了一种跳跃技能，表示为向量 $(x_i,y_i)$ 。
在点 $(X_i,Y_i)$ 处有一项收益为 $w_i$ 的任务，你可以立刻从当前点跳跃若干步到那个点获得收益，每一步都可以是你已经学会的某个向量的 $1$ 或 $-1$ 倍。

当然你也可以选择留在当前点不做这任务。求最终最大总收益。 $q\le 1e6，0\le \text{输入坐标}\le 1e6$

思路

首先可以发现一个性质，那就是如果能从原点到达某个点，那么一定可以回到原点。

这样就可以转换成有多少个点能够由原点到达。

由于有多个向量不好使用。所以可以尝试逐步把向量合并。

由于只有一维的向量比较好处理，所以考虑在等效状态下尽量将向量削成一维。但如果向解二元一次方程组那样对一个向量乘某个数值则不能保证等效，所以要进行辗转相减。可以只保留两个向量 a, b 其中 b.x 为 0。每次插入一个 c 向量时，先将 a, c 消出来一个 x 为 0 的向量，然后和 b 合并作为新的 b, x 不为 0 的向量为新的 a。

然而当合并次数多了之后非常容易出现某个值为意料之外的 0 的情况。因此要多加特判。

P2634 [国家集训队]聪聪可可

关键词：zrq，点分治

题目描述

给定一个 $n$ 个点的树，求 $\bmod 3 \equiv 0$ 的路径条数。

思路

点分治一道比较偏向板子的题目。考虑哪些路径可以拼成符合要求的路径，分别是 $\bmod 3 \equiv 1$ 和 $\bmod 3 \equiv 2$ 配对以及 $\bmod 3 \equiv 0$ 和 $\bmod 3 \equiv 0$ 配对。分治合并就行了。

对于去重，容斥就好了。

CF715C Digit Tree

关键词：zrq，点分治

题目描述

给定一棵树，边权 $1 \leq w\leq 9$ 。给定一个数 $M$ ，保证 $\gcd(M,10)=1$ 。

对于一对有序的不同的顶点 $(u, v)$ ，他沿着从顶点 $u$ 到顶点 $v$ 的最短路径，按经过顺序写下他在路径上遇到的所有数字（从左往右写），如果得到一个可以被 $M$ 整除的十进制整数，那么就认为 $(u,v)$ 是有趣的点对。

求有趣的对的数量。

思路

把题目转化成子树内的点到根的路径的拼接的话，设 $u, v$ 分别是子树内的两个点， $(u, v)$ 满足条件当且仅当 $dis0_u \times 10^{len_v} + dis1_v \equiv 0(\bmod M)$ 其中 $0$ 代表从 $x$ 到根， $1$ 代表从根到 $x$ 。发现两条路径都与第二条有关系，无法进行复杂度正确的分治，但是由于题目保证了 $gcd(M, 10) = 1$ ，所以可以求出 $10^{len_v}$ 的逆元，同乘，变成 $dis0_u + dis1_v \times 10^{inv(len_v)} \equiv 0 (\bmod M)$ 这下就相互独立了，可以将某一个离散化，拿另一个来找。现在的问题就变成了分别求出并记录下两种路径。 $1$ 相对简单，可以直接求，对于 $0$ 需要预处理出 $10^x$ 来方便计算。

对于去重，容斥就好了。另外如果当前计算的是分治重心，需要额外计算上本来就符合条件的单条路径。

P2056 [ZJOI2007]捉迷藏

关键词：zrq，点分树

题目描述

树上黑白点，动态修改，求最近黑点距离。

思路

这个题的重点是如何去重。自己思考的成分很少，主要是学长的思路：

对于每个点，建两个可删堆。 $1$ 号堆维护自己内部所有黑点到父亲的距离， $2$ 号堆维护自己每个儿子中到自己的最大距离，对于每个点用 $1$ 号堆来更新父亲的 $2$ 号堆。再维护一个全局堆表示对于每个子树中包含两个黑点的点它的答案。

本文作者：CloudySky
写作时间： 2022-01-23
最后更新时间： 2022-03-04
遵循协议： BY-NC-SA

CloudySky || AFO

永远相信美好的事情即将发生。

2022寒假集训做题总结

年前做题记录

Line Graph Matching

Roads and Planes G

Emails

Joint Excavation

City Brain

Tax

CF1080E Sonya and Matrix Beauty

[POI2012]OKR-A Horrible Poem

Elastic Search

String Problem

Popcount Words

[PA2013]Raper

[SDOI2016]生成魔咒

年后做题记录

Best ACMer Solves the Hardest Problem

Necklace

Cactus

Interstellar Hunter

P2634 [国家集训队]聪聪可可

CF715C Digit Tree

P2056 [ZJOI2007]捉迷藏