# 省冲笔记(Save Chong notes)-其他

## 省冲笔记(Save Chong notes)

### 例2

• 法一
统计每一位上 $0～9$ 出现的次数
• 法二
每次抵消掉两个不相等的数，剩下的那个数

### 例3

• 每次抵消 $k$ 个数，统计没有被消除掉的数字的历史出现次数

### 例4

$2n+2$ 个数字，其中有两个数字是单独出现的，剩下的数字出现次数都为偶数，分别求那两个数字

• 异或之后的结果是两个数的异或值，这两个数必定有一位上互不相同，令 $f[i]$ 表示二进制表示第 $i$ 位上是 $1$ 的所有数的异或值

### 例1

$n\times m$ 的灯泡矩阵，每次改变一个位置的状态会影响上下左右的状态，给定初始状态问能不能全灭

• 一个位置上下左右包括他自己最终操作次数和模 $2$ 的结果是定的 —> 列 $nm$ 个线性方程（时间复杂度起飞）
• 枚举第一行的开关方法，一路求到最后一行看最后一行能不能全灭 （$O(2^n\cdot nm)$）
• 设 $a_{i,j}$ 表示某一位置需要的操作数，$c_{i,j}$ 表示某一位置的状态，则 $$c_{i,j} + a_{i-1,j} + a_{i,j+1} + a_{i,j-1} + a_{i + 1,j} \equiv 0 \pmod2$$，从第一行开始将下一行的 $a$ 表示一下， 一直到最后一行判断是否合法即可

### 例2

$n\times m$ 的灯泡矩阵，每次可以选择一列或一行将灯泡反向，给定初始状态，问操作恰好 $k$ 次最多能让多少列灯泡全为 $1$

• 暴力枚举某一列是否亮着以及这一列按了没有，行的状态就确定了，时间复杂度 $O(2nm^2)$
• 有一性质：对于任意两列而言，当且仅当他们初始状态相同或互补，则他们可以同时变亮，将初始的列分类即可

### 例3

$n\times m$ 的矩阵，每个位置都有 $a_{i,j}$ 个地鼠，有一个 $r \times c$ 的锤子（$r, c$ 任意），每次可以将这么大的范围内地鼠全部减一（必须保证这一些格子里至少有一个），至少用多少次打完？

• 暴力枚举 $r, c$ ，

### 例1

• 双指针直接枚举，注意 $r$ 过不了 $l$ 的情况

### 例2

$n$ 张 $m$ 种卡片，只能买连续的，求最少需要多少钱集齐 $m$ 种。

• 双指针直接扫

### 例3

• 统计每个长度为 $k$ 的串，按除以 $3$ 的余数分类统计即可

### 例4

• 性质：$A \oplus B ≤a+b$，所以当且仅当区间做与等于 $0$，满足题意，直接双指针扫

### 例5

• 当 $A_i+B_j$ 第 $28$ 位 为 $1$，当且仅当 $A_i+B_j\in[2{28},2{29}-1]$，即 $B_j\in[2{28}-A_i,2{29}-1-A_i]$，对 $B$ 排序后二分即可。对于 $27$ 位，对每个数对 $2^{28}$ 取模，剩下的依次操作即可。

### 例6

• 考虑子任务 $1$： 对于任意一行 $sum >2k$，直接双指针扫；对于任意一行 $su m \in [k,2k]$，直接输出；

### 例7（环形序列）

• 考虑链的情况，将前 $\frac{n}{2}$ 个元素记为 $1$，后 $\frac{n}{2}$ 个元素记为 $-1$，满足题意的前缀和一定属于 $(-∞,1)$，直接将输入前缀和，找出最后大于等于 $2$ 的位置，将其后作为链的开始，一定满足题意。
• 考虑上述前缀和的情况，如果将前 $n$ 个移到后面，也就是后面的前缀和要减去前面的前缀和，即是区间修改区间最大值的题，线段树即可

### 例1

• 当成字符串处理，对于结果中任意两个相邻的数字元素，满足 $\texttt{A}+\texttt{B}>\texttt{B}+\texttt{A}$，即为最优解

### 例2 P1080 [NOIP2012 提高组] 国王游戏

• 贪心策略：左手右手乘积小的在前。证明：考虑相邻的两个大臣 $i,j$ ，且 $i$ 前面所有左手的乘积为 $S$，则采用此策略 $\max(\frac{S}{r_i},\frac{S\cdot l_i}{r_j})$，不采用此策略 $\max(\frac{S}{r_j},\frac{S\cdot l_j}{r_i})$，又因为

• 截止越早，影响越小

### 例1

• 给 $a$ 做 01-Trie，贪心即可。

### 例2

|, ^, &
m | 124 ^ 235 & 12423 ^ 12312

### 思考题

$n$ 个数字，$1 ≤a_i≤10^{8}$，设 $S(i,j)$ 表示十进制下 $a_i+a_j$ 进位次数，求 $\sum\limitsn_{i=1}\sum\limitsn_{j=1}S(i,j)$。

• 对任意一个数字，个位有没有数字进位显然可以 $O(n)$ 处理，十位有没有数字进位可以直接将其看作两位数处理，问题转化为每个数字的每后 $i$ 位大于等于特定 $k$ 的有多少个数，排序后对每位二分即可

### 例1（随机数生成器）

$n\times m$ 的矩阵中有 $[1,n\times m]$ 中的每个数，左上角走到右下角，经过 $n+m-1$ 个数，排序后将其视作字符串的 $\texttt{ASCII}$ 码，求给定矩阵后生成的所有字符串的字典序最小的字符串。

• 一定将较小值包含在路径里更优，先求能走到 $1$，能经过的路径组成的矩阵，再求能走到 $2$，能经过的路径组成的矩阵，取交集后递归。具体实现可以维护每一行可以经过的区间。

### 例2

• 定义某一条路径上最高点为这条路径的长度，则这个点的最大蓄水值为所有这个点逃出边界的路径的最小值，转化为最短路问题，再设一个虚点为边界的集合，问题转化为这个虚点到内部每个点的“最短路” 的和

### 例3

• 先考虑链的情况，若任意位置后缀和小于等于下标，则成为了链的情况，问题转化为区间田忌赛马。
• 环形情况证明同 [此题](# 例7（环形序列）)

### 例4

task 1: $len ≤6$ task 2: $len ≤18$ task 3: $len < 100$

• Task 1: 枚举 $1$ 至 $10^6$ 的数字

### 模板

int now = 0;
for(int stp = len; stp >= 1; stp >>= 1) {
if(now + stp <= len && check(now + stp)) now += stp;
}
// 倍增


### 例1

• 转化为 $A_a+B_b=-(C_c+D_d)$，暴力成两个数组排序双指针即可

### 例2

$n$ 件衣服需要晾干，含水量为 $a_i$，每分钟蒸发掉 $1$ 单位水，一个吹风机每分钟可以蒸发 $k$ 个单位水，求最小时间

• 二分总时间，晾干的不管，没晾干的统计需要吹多少分钟，总时间再和二分的总时间比

### 例3

$n$ 个项目组，每个项目组有 $a_i$ 个人，每次要从不同的 $k$ 个项目组里抽一个人，问最多能取多少次

• 二分次数 $t$，若 $\sum\limits^n_{i=1}\min(a_i,t) ≤tk$，则可以，

• 二分答案。

• 只和最高点有关，二分。

### 搜索技巧

• 剪枝（估价）
$now+h(x) ≥ best$。估价函数必须优于现实。

### 剪枝（估价）

• 方向
每一步最优+剪枝（？）但是有可能有问题。
可以每一步贪心地限制宽度

### 方向

• 记忆化
搜索记忆化：记录每个状态的最优解

### 记忆化

• IDA*
限制搜索树深度 $lim$，再加上估价函数。

### IDA*

• – 剪枝
两方玩家，一方目的是最大，一方目的是最小，搜索的两步中，假设第一步从大到小搜到了 $30$，第二步从小

### 例3 十六数码

• 将左边一列、上面一行 IDA*，剩下八数码。

### 例4

• 记忆化
• 搜索方向，每次必须打死目前活着的编号最小的鸟

• 考虑 DFS
• 考虑优化（搜索记忆化等）
• 方程？以及初始状态

### 例题：01 背包

• dfs(i, v, w) 表示搜过了第 $i$ 件物品，体积为 $v$，价值为 $w$
• 记忆化优化
• 令 $dp_{i,v}$ 表示第 $i$ 件用了 $v$ 的最大价值，那么显然 $d p_{i,v} = \max(dp_{i-1,v},dp_{i – 1, v – v_i}+w_i)$。接着考虑初始状态。
for(int i = 1; i <= n; ++ i) for(int j = 0; j <= C; ++ j) { dp[i][j] = dp[i - 1][j]; if(j - v[i] >= 0) dp[i][j] = max(dp[i][j], dp[i – 1][j – v[i]] + w[i]);
}

时间复杂度 $O(nC)$，空间复杂度相同。

• 考虑优化空间，发现每次递推只与上一行有关，利用滚动数组优化。
• 继续考虑优化空间，每一个点只与左下方以及下方有关，若从右边开始，则其正下方的点不需要被用到，直接替换即可
for(int i = 1; i <= n; ++ i) for(int j = C; j >= v[i]; — j)
dp[j] = max(dp[j], dp[j – v[i]] + w[i]);

### 例1 01背包，但是 $c,w ≤10^9,n≤100$

• 对于每一个 $i$，可以枚举可能的所有 $v$ 和 $w$，所有 $v$ 更大，$w$ 更小的状态都可以舍弃。

### 例2 最长上升子序列

• 令 $d p_{i}$ 表示前 $i$ 个的最长长度，则 $d p_i = 1 + \max \limits_{j < i,a_j < a_i} dp_j$，时间复杂度 $O(n^2)$
• 令 $dp_{i,len}$ 表示前 $i$ 个数选了长度为 $len$ 的 LIS 最后一个数，则能更新 $dp_{i,len}$ 的条件是 $a_i > dp_{i-1,len-1} 且 a_i < dp_{i-1, len}$，实际上也只用了 $len$ 一维。
————————

### Example 1

Decadal function $f (x) = \ sum {10}_ {i=1}a_ ixi+a_ 0$, known $f (1), f (2), f (3), \ dots,, f (11)$, find $f (12)$

Crazy derivation

### Example 2

Read in $n$numbers. One number appears more than half times, and the remaining numbers appear randomly. Find the number with the most times. (array with space limit of $100$)

• FA Yi
Count the number of occurrences of $0 to$9 on each bit
• Method II
Offset two unequal numbers at a time, and the remaining number

### Example 3

The problem surface is the same as example 2. Change more than half to more than $K / n$

• The number of $k$is offset each time, and the historical occurrence times of the number that has not been eliminated are counted

### Thinking questions

There is a zoo. Animals are locked in the upper left corner grid. To escape from the zoo, you must escape from the lower right corner. There are boundaries up, down, left and right. There are two kinds of animals, tiger $t$and cow $C$. The path will leave their footprints, and the back will cover the front footprints. Given the last state of the matrix, find out at least a few animals escaped.

### Example 5

String, such as $\ texttt {. Y.. YYY. YY..}$, The maximum number of consecutive $\ texttt {y} characters that can be exchanged between two adjacent characters is$k $times$