《算法竞赛进阶指南》做题记录
devout
2020-11-18 20:20:35
## tips记录
- 97 $a^p\bmod p\neq 1$
- 102 卡精度毒瘤题，因为double存数的特性，所以实数二分之后 $r$ 是更接近于正确答案的，应该用 $r$ 输出
- 109 倍增的优势是在重复计算影响复杂度的时候我们可以通过利用上一次的计算推出这次的答案，二分的题目通常可以用倍增实现。
- 127 注意有两个数组的时候不要写混而导致在样例水的时候可以过去
## 未解决的问题
- 163 莫名WA
- ~~202 关于 $a^x\equiv 1(\bmod\ p)$ 在 $\gcd(a,p)\neq 1$ 时的解决方法？~~ solved on 2021.1.7 显然无解，$\gcd(a,p)|a^x,\gcd(a,p)\not| kp+1$
## $\texttt{ACWing95.费解的开关}$
**description**
一个 $5\times 5$ 的01矩阵，每次可以选一个点，让他和和他相邻的点的值取反
问最少多少次操作可以让矩阵全变1。
有 $T$ 次询问，$T\leq 500$
**solution**
显然一个点不会被按两次，并且按的顺序是无所谓的
所以我们可以枚举第一排的哪个位置被按了，这样当考虑下一行的时候，就可以确定哪个位置需要被按了，最后判断一下第五行是否全是1就可以了
复杂度 $\mathcal O(Tn^22^n)$
**[code](https://www.acwing.com/problem/content/submission/code_detail/2977002/)**
**algorithm/tag**
状压，枚举
## $\texttt{ACWing97.约数之和}$
**description**
给定 $A,B$,求 $A^B$ 的约数之和 $\bmod\ 9901$
$A,B\leq 5\times 10^7$
**solution**
考虑质因数分解，然后根据约数和公式求，计算等比数列用逆元解决一下就好了
注意有可能质因数取模之后为 $0$，这个时候是没有逆元的，所以我们需要特判
**tips**
$a^p\bmod p\neq 1$
**[code](https://www.acwing.com/problem/content/submission/code_detail/2970004/)**
**algorithm/tag**
乘法逆元，约数
## $\texttt{ACWing100.Incdec}$
**descripton**
给定一个长度为 $n$ 的数列 $\{a_i\}$，每次可以任意选一个区间 $[l,r]$ 让区间内所有数同时 $+1/-1$，问最少经过多少次操作可以让区间内所有的数相等，以及这个相等的数有多少种不同的可能
$n\leq 10^5$
**solution**
考虑将数组差分一下，那么问题就转化成了，每次可以在一个位置上 $+1$，一个位置上 $-1$，问最少经过多少次操作使得整个序列全是 $0$（除了第一位）
设所有差分值为正的部分之和为 $x$，差分值为负的部分之和（绝对值）为 $y$，
那么我们就得到了第一问的答案：$\max(x,y)$
但是注意我们可以把一些没有意义的操作扔到 $1$ 或者 $n+1$，所以我们可以选择我们扔几个到 $1$，相当于就确定了整个序列最后的值，所以我们第二问答案就是 $\max(x,y)-\min(x,y)+1$
**[code](https://www.acwing.com/problem/content/submission/code_detail/2968380/)**
**algorithm/tag**
差分
## $\texttt{ACWing101.最高的牛}$
**description**
有 $N$ 头牛站成一行，被编队为 $1,2,3\cdots N$，每头牛的身高都为整数。
当且仅当两头牛中间的牛身高都比它们矮时，两头牛方可看到对方。
现在，我们只知道其中最高的牛是第 $P$ 头，它的身高是 $H$，剩余牛的身高未知。
但是，我们还知道这群牛之中存在着 $M$ 对关系，每对关系都指明了某两头牛 $A$ 和 $B$ 可以相互看见。
求每头牛的身高的最大可能值是多少。
**solution**
显然最优的时候每个条件中间的牛都之比两边矮1
所以在维护一次查询的时候可以做一次差分，把中间部分减一
最后在h的基础上进行查询就可以了
**[code](https://www.acwing.com/problem/content/submission/code_detail/2982687/)**
**algorithm/tag**
差分
## $\texttt{ACWing102.最佳牛围栏}$
**description**
给定一个序列，问他的一个长度大于等于 $m$ 的子区间的平均数最大是多少
$n\leq 10^5$
**solution**
考虑二分答案，把所有序列减去这个二分值之后，如果存在一个长度大于等于 $m$ 的连续段使得区间和非负就可以
**tips**
卡精度毒瘤题，因为double存数的特性，所以二分之后 $r$ 是更接近于正确答案的，应该有 $r$ 输出
**[code](https://www.acwing.com/problem/content/submission/code_detail/2982383/)**
**algorithm/tag**
二分
## $\texttt{ACWing105.七夕祭}$
**description**
在一个 $n\times m$ 的区域里有 $t$ 个黑点，其他的为白点，每次可以交换相邻的两个点，问能否交换使得每行/列的黑点个数相同，如果可以，求最小交换次数。
每行每列最后一个位置和第一个位置也算作相邻。
$n,m,t\leq 10^5$
**solution**
显然，行和列是相互独立的。
考虑行，显然之后 $t\bmod n=0$ 才可以交换成功。
如果没有环形的情况，那么就是一个均分纸牌问题，考虑对于一个数列 $\{a_i\}$ 的答案
设 $t=\dfrac{\sum a_i}{n},s_i=\sum_{j=1}^i a_i$
答案为 $\sum_{i=1}^n |s_i-t|$
如果把所有 $a_i$ 减去 $t$ 的话，答案就是 $\sum_{i=1}^n |s_i|$
发现转圈的时候一定有一个位置，他一定不会和他左边的位置发生交换，所以我们枚举这个位置，设为 $k$，那么每个位置的答案应该变成了
$s_k-s_k,s_{k+1}-s_k,s_{k+2}-s_k\cdots s_n-s_k$
$s_n-s_k+s_1,s_n-s_k+s_2,s_n-s_k+s_3\cdots $
发现 $s_n=0$，所以相当于给每个位置减去 $s_k$
问题转化成了，对于 $k\in[1,n]$，求 $\min \sum_{i=1}^n |s_i-s_k|$
这样就很好的解决了
**[code](https://www.acwing.com/problem/content/submission/code_detail/3016340/)**
**algorithm/tag**
贪心
## $\texttt{ACWing108.奇数码问题}$
**description**
一个 $n\times n$ 的网格，里面不重复的填有 $1\sim n^2-1$ 和一个空格，空格可以和上下左右任意一个方向交换，给定初始状态和结束状态，问初始状态能不能推到结束状态
$n\leq 500$
**solution**
考虑把矩阵问题变成一个数列问题
对于空格的横向交换是不会影响数列的奇偶性
对于空格的竖向交换，他会影响到数列在他前面的两个数，发现上下交换也不会影响奇偶性
同时发现转三次就可以完成一个 $2\times 2$ 的循环，所以只需要开始和最后的数列的奇偶性相同就可以转移过去。
**algorithm/tag**
奇偶性，逆序对
## $\texttt{ACWing109.天才ACM}$
**description**
对于一个整数集 $S$，定义 $misaka(S)$ 表示从中任意取 $m$ 对数 $(x_i,y_i)$ （如果不足 $m$ 对就尽量取取到不能取） 的所有方案中 $\sum (x_i-y_i)^2$ 的最大值。
现在给定一个数列 $\{a_i\}$，现在要将其划分成几段，使得每一段的 $misaka$ 值都不超过 $k$，问最少能分成几段。
$n,m\leq 5\times 10^5,k\leq 10^{18}$
**solution**
显然我们要尽量往右取直到不能取，这样的时候肯定是最优的。
显然最大的配最小的是最优的。
所以我们应该初步想到的是二分的方法，每次二分长度，然后暴力求它的 $misaka$ 值，这样总复杂度是 $\mathcal O(n^2\log^2n)$。
发现二分的时候可能会出现之前算过的又扔掉的情况，这个时候我们进行了重复的计算，我们考虑优化这些计算。
我们假设现在要考虑的起点为 $s$，每次我们倍增，找到最后一个 $[s,s+k)$，使得 $misaka(a[S,s+k))\leq k$ ，然后我们再从 $k\sim 1$ 去考虑能不能往右去做，这样重复的计算量大大减少。
考虑这样做的复杂度，相当于我们每次利用了 $\mathcal O(k\log k)$ 的时间，减少了 $\mathcal O(k)$ 的势能，所以总复杂度 $\mathcal O(n\log n)$
**tips**
倍增的优势是在重复计算影响复杂度的时候我们可以通过利用上一次的计算推出这次的答案，二分的题目通常可以用倍增实现。
**[code](https://www.acwing.com/problem/content/submission/code_detail/3024467/)**
**algorithm/tag**
二分，倍增
## $\texttt{ACWing115.给树染色}$
**description**
给一棵 $n$ 个节点的树，每个点有权值 $a_i$，现在要求安排一个顺序，使得 $\sum i\times a_i$ 最小，同时一个点必须排在他的所有父节点之后。
$n\leq 1000$
**solution**
对于一个当前子树中最大的点，显然当他的父节点选完之后一定下一个就要选他。
设当前最大的点为 $b$，他的父节点为 $a$，另一个节点为 $c$，若要先选 $a$ 的话，要满足 $a+2b+3c\leq c+2a+3b$，即 $c\leq\dfrac{a+b}{2}$。所以我们可以每次将最大点和他的父节点合成一个新的点，点权为他们两个的平均值。
考虑如何计算答案。
如果一个大小为 $x$ 的点接在了一个大小为 $y$ 的点的后面，那么显然在 $x$ 里面的点都会加上一个 $y$ 的偏移量，所以直接答案加上 $sum_x\times y$ 就可以了
复杂度 $\mathcal{O}(n^2)$
[**code**](https://www.acwing.com/problem/content/submission/code_detail/3036369/)
**algorithm/tag**
贪心
## $\texttt{ACWing120.防线}$
**description**
有 $n$ 个形如 $(s_i,e_i,d_i)$ 的条件
对于每个 $x\in[s_i,e_i],x\bmod d_i=s_i$，会在该位置放置一个看守
现在保证整个数轴上最多只有一个位置有奇数个看守
现在要把这个位置找出来
$n\leq 2\times 10^5,s_i,e_i,d_i\leq 2^{31}-1$
**solution**
发现如果对这个数轴上的位置求一个前缀和的话，那么在这个奇数位置之前的前缀和都是偶数，而之后的都是奇数
发现一个位置的前缀和我们可以 $\mathcal O(n)$ 来求
所以我们可以二分找到这个位置
复杂度 $\mathcal O(n\log v)$
[**code**](https://www.acwing.com/problem/content/submission/code_detail/3136955/)
**algorithm/tag**
二分
## $\texttt{ACWing123.士兵}$
**description**
有 $n$ 个点 $(x,y)$，一次操作可以给一个点的纵坐标和横坐标加一或减一，问最少多少次操作可以使得每个点的 $y$ 坐标相同，且 $x$ 坐标在同一直线上，其中每个点不能位于同一个位置
$n\leq 10^5$
**solution**
可以将 $x$ 轴和 $y$ 轴分开考虑
$y$ 轴就是一个绝对值模型，直接取中位数
$x$ 轴考虑对于坐标排序，如果位置选在 $p$ 处，答案为 $\sum_{i=1}^n |x_p-(x_p-x_i)-x_i|$
所以我们可以对于每一个 $x_i-i$ 求中位数
$\mathcal O(n\log n)$
[**code**](https://www.acwing.com/problem/content/submission/code_detail/3145563/)
**algorithm/tag**
贪心
## $\texttt{ACWing127.任务}$
**description**
有 $n$ 个机器要搭配 $m$ 个任务，一个机器最多只能做一个任务
每个机器和任务都有两个属性 $x_i,y_i$
第 $i$ 号任务可以在第 $j$ 号机器做当且仅当 $x_i\leq x_j,y_i\leq y_j$
第 $i$ 号任务完成之后可以获得 $500x_i+2y_i$ 的利润
问最多能做多少个任务，以及在最多做的任务之下的最大利润
$n,m\leq 10^5$
$x_i\leq 1440,y_i\leq 100$
**solution**
难度虽然是困难但是其实挺简单的一道题
我们发现根据这个神奇的计算利润的公式，如果 $x_i<x_j$，那么 $i$ 的利润一定小于 $j$ 的利润
根据这个我们就可以按照价值从大到小排序
然后考虑 $i$ 任务的时候把所有 $x$ 比 $x_i$ 大的机器的 $y$ 扔到一个 multiset 里，只需要看有没有比 $y_i$ 大的就好了，如果有取最小的那个
$\mathcal O(n\log n)$
[**code**](https://www.acwing.com/problem/content/submission/code_detail/3161882/)
**algorithm/tag**
贪心
## $\texttt{ACWing128.编辑器}$
**description**
编辑器共有五种指令，如下：
1、“I x”，在光标处插入数值x。
2、“D”，将光标前面的第一个元素删除，如果前面没有元素，则忽略此操作。
3、“L”，将光标向左移动，跳过一个元素，如果左边没有元素，则忽略此操作。
4、“R”，将光标向右移动，跳过一个元素，如果右边没有元素，则忽略次操作。
5、“Q k”，假设此刻光标之前的序列为a1,a2,…,an
,输出max1≤i≤kSi，其中Si=a1+a2+…+ai。
**solution**
可以不用写平衡树，我们可以借鉴此前对顶堆的思想，用两个栈就可以解决了
$\mathcal O(n)$
[**code**](https://www.acwing.com/problem/content/submission/code_detail/3176606/)
**algorithm/tag**
栈
## $\texttt{ACWing134.双端队列}$
**description**
达达现在碰到了一个棘手的问题，有N个整数需要排序。
达达手头能用的工具就是若干个双端队列。
她从1到N需要依次处理这N个数，对于每个数，达达能做以下两件事：
1．新建一个双端队列，并将当前数作为这个队列中的唯一的数；
2．将当前数放入已有的队列的头之前或者尾之后。
对所有的数处理完成之后，达达将这些队列按一定的顺序连接起来后就可以得到一个非降的序列。
请你求出最少需要多少个双端序列。
$n\leq 2\times 10^5$
**solution**
考虑把所有的数按照大小排序，记录该数在原数列上出现的位置
现在问题转化成了一段区间能不能用一个双端队列搞定
显然满足贪心的性质，我们让区间尽量的大
发现一个区间如果可以，一定满足原数列位置先减后增
所以我们只需要计算数列极小值的个数
但是注意相同的数我们无法确定他的排列顺序，这个时候我们需要把他们合并在一起。
[**code**](https://www.acwing.com/problem/content/submission/code_detail/3181019/)
## $\texttt{ACWing157.树形地铁系统}$
**description**
现在有一棵树，从根节点出发，进入到某棵子树中，记录为 $0$，如果没有子树就返回到父亲节点，记录为 $1$，这样可以得到一个 $2n-2$ 的串，现在给定两个这样的串，问这两棵树是否可以同构。
$n\leq 3000$
**solution**
即判断这两棵树的最小同构树的 dfn 是否相同，如果相同那么就是 same，否则就是 different。
如何判断一个最小同构树，就把每个点的子树的同构序列按照字典序排序，然后拼在一起就好了
注意最开始的时候我们应该给根节点也设立一个超级父亲节点，否则会出一些问题。
$\mathcal O(n^2)$
[**code**](https://www.acwing.com/problem/content/submission/code_detail/3222646/)
## $\texttt{ACWing158.项链}$
**description**
给定两个字符串，问他们的最小同构是否相同
$|S|\leq 10^6$
**solution**
最小同构的定义是，平移若干次，得到的字典序最小的字符串。
其算法流程为
- 将原字符串复制一遍
- $i=1,j=2$
- 找到第一个 $k$，使得 $s[i+k]\neq s[j+k]$
- 比较 $s[i+k],s[j+k]$，若 $s[i+k]>s[j+k]$，则 $i\sim i+k$ 这一段都不可能作为最小同构的开头， $i=i+k+1$，若此时 $i=j,i=i+1$。反之亦然
- 重复 3,4，直到 $i>n\ or\ j>n$
- $i,j$ 中 $\leq n$ 的那个开始的长度为 $n$ 的字符串就是原字符串的最小同构
复杂度 $\mathcal O(n)$
[**code**](https://www.acwing.com/problem/content/submission/code_detail/3222830/)
## $\texttt{ACWing159.奶牛矩阵}$
**description**
给一个 $n\times m$ 的字符矩阵，求最小的矩形面积，使得这个矩形经过无数次复制粘贴（不能重叠）可以变成原矩阵。
注意假设你的矩形大小为 $a\times b$，他只能从以 $(1,1),(a,b)$ 为顶点的矩形开始复制粘贴
$n\leq 10000,m\leq 75$
**solution**
显然可以对于行和列分开求循环节，这样问题就转化成了一维的问题
枚举长度，哈西判断，复杂度 $\mathcal O(nm\ln n)$
[**code**](https://www.acwing.com/problem/content/submission/code_detail/3227426/)
## $\texttt{ACWing163.生日礼物}$
**description**
给定一个长度为 $n$ 的数列，求它的 $m$ 段最大子段和（可以为空）
**solution**
显然对于一段正数和负数，我们要么都不选，要么都选，所以我们可以把它缩成一个点来考虑
考虑先把所有正数都选上，这个时候如果段数不超过 $m$，那么就直接输出。
否则我们有两种选择
- 删掉一段正数 $x$，答案减去 $|x|$，减少一个区间。
- 加上一段负数 $x$，答案减去 $|x|$，减少一个区间。
但是注意对于相邻的两个区间，我们是不能都选的。
所以问题转化成了，对于缩完点的数列，选出不相邻的 $k$ 段最小的的和。
这道题和 [P3620 [APIO/CTSC 2007]数据备份](https://www.luogu.com.cn/problem/P3620)是一样的。
我们考虑带反悔的贪心，每次取出堆中最小的，然后再往里推入左右的和减去他的值，重复 $k$ 次即可
不知道为啥一直WA（
## $\texttt{ACWing202.最幸运的数字}$
**description**
给定 $n$，问最少多少个连着的 $8$ 构成的数是 $n$ 的倍数。
无解输出 $0$
$n\leq 2\times 10^9$
**solution**
设答案一共有 $x$ 位，那么
$$8\times\dfrac{10^x-1}{9}\equiv 0(\bmod\ n)$$
$$10^x\equiv 1(\bmod \dfrac{9n}{\gcd(n,8)})$$
设 $\dfrac{9n}{\gcd(n,8)}=p$，那么就是求
$$10^x\equiv 1(\bmod\ p)$$
当 $\gcd(10,p)\neq 1$ 时，显然无解
当 $\gcd(10,p)=1$ 时，根据欧拉定理，显然存在一解 $x=\phi(p)$
但是题目要求最小的解
此时最小的 $x$ 一定是 $\phi(p)$ 的因数
证明：
假设最小的 $x$ 使得 $10^x\equiv 1$，且 $x\not|\ \phi(p)$
那么，$10^{x\lfloor\frac{\phi(p)}{x}\rfloor}\equiv 1,10^{\phi(p)}\equiv 1$
那么 $10^{\phi(p)-x\lfloor\frac{\phi(p)}{x}\rfloor}\equiv 1$
而 $\phi(p)-x\lfloor\frac{\phi(p)}{x}\rfloor<x$，与假设不成立
证毕
[**code**](https://www.acwing.com/problem/content/submission/code_detail/3332694/)