省冲笔记(Save Chong notes)

暴力枚举 前缀和

例1

十次函数 $f(x) = \sum{10}_{i=1}a_ixi+a_0$,已知 $f(1), f(2),f(3),\dots,,f(11)$,求 $f(12)$

疯狂求导

例2

读入 $n$ 个数字,有一个数字出现次数大于一半,剩下的数字随机出现,求出现次数最多的数字。(空间限制 $100$ 的数组)

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

例3

题面同例2,大于一半改为大于 $k/n$

  • 每次抵消 $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

给定长度为 $n$ 的数组,求有多少个区间 $[l,r]$ 满足 $\sum \limits_{i=l}^ra_i ≤ k$。

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

例2

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

  • 双指针直接扫

例3

给定长度为 $n$ 且只含 $\texttt{R G B}$ 的字符串,求要获取长度为 $k$ 且形式为 $\texttt{RGBRGB}\dots$ 的字符串最少需要修改多少个字符。

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

例4

给定长度为 $n$ 的数组,求有多少个区间异或和等于他们的和。

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

例5

给定长度为 $n$ 的数组 $A,B$,求 $\sum\limitsn_{i=1}\sum\limitsn_{j=1}(A_i+B_j)$ 的异或和。$n≤2\times10^5, 0 ≤A_i,B_i<2^{28}$

  • 当 $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(环形序列)

有一个环形序列,$A$ 可以指定一个位置将环拆开,接下来和 $B$ 轮流玩游戏,$A$ 先手。$A$ 可以任意取走一个元素,$B$ 只能从最左边拿,求 $A$ 能得到的最大分数以及拆的位置。

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

贪心算法

经典模型:偏序关系

例1

给定 $n$ 个正整数,求其首尾相连能连成的最大整数

  • 当成字符串处理,对于结果中任意两个相邻的数字元素,满足 $\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 P1803 凌乱的yyy / 线段覆盖

  • 截止越早,影响越小

例2

给定 $n$ 个线段,求最多有多少个线段有交集。

经典模型:按位贪心

例1

给定数组 $a$,$q$ 组询问给出 $k$,求 $k \oplus a_i$ 最大值。

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

例2

给定一个由 组成的算式,如 ,给定 $k$,求 $m$ 取何值且 $m \in [0,k]$,式子的结果最大。

|, ^, &
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

俯视一个蓄水池,$n\times m$ 的矩阵中有每个点的高度,水会向四周流,求要使水不溢出边界,最多能蓄多少水。

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

例3

有 $n$ 个矮人和 $n$ 个精灵,每个矮人、精灵都有一个能力值,能力值两两不相同,矮人排成一个 $1$ ~ $n$ 的环,第 $i$ 个精灵会从第 $a_i$ 个矮人开始挑选第一个无对手的矮人比赛,如何安排精灵出场顺序使胜利场数最多。

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

例4

有 $n$ 个形如 $\texttt{15}$ $\texttt{15}$ $\texttt{15}$ $\texttt{14}$ 的字符串,将 $\texttt{*}$ 替换成数字并使 $n$ 个数单调递增,并使最后的结果数字尽量小,输出方案。

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

  • Task 1: 枚举 $1$ 至 $10^6$ 的数字
  • task 2: 将星号组成数字开始二分
  • task 3: 从高位贪心

二分

模板

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

例1

四个长度均为 $n$ 的数组 $A,B,C,D$,任意 $a, b, c, d$ 求多少种方案使 $A_a+B_b+C_c+D_d = 0$

  • 转化为 $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$,则可以,

例4

无限长数轴,有一个机器人一开始在 $0$,有一连串指令形如 $\texttt{LRRLRLLRLRLRRLRLLR}$,希望最终停在一个之前没有走过的地方,但是可以放墙,若下一步撞墙则不会走,最少需要几堵墙?方案数?

思考题

有一个动物园,动物都被关在左上角格子,逃出动物园必须从右下角逃出,上下左右均有边界,有两种动物老虎 $T$ 和牛 $C$,走过的路径会留下自己的脚印,后面的会覆盖前面的脚印,给定矩阵最后状态,求最少逃出去了几只动物。

例5

字符串,形如 $\texttt{.Y..YYY.YY..}$,最多可以交换相邻两个字符 $k$ 次,最后最多能得到多少个连续的 $\texttt{Y}$

  • 二分答案。

例6

有一堵墙,堆沙袋最左边位置高度不能超过 $H$,向右堆和左边一堆相差不能超过 $1$,要求到最右边得堆个 $1$,要恰好用完 $n$ 个沙袋,问最少堆多少列。

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

搜索

例1

见题解

搜索技巧

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

剪枝(估价)

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

方向

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

记忆化

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

IDA*

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

– 剪枝

例2

例3 十六数码

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

例4

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

DP

思考题

给定数字 $n$,分成若干个数字 $a_1,a_2,\dots,a_k$,代价为 $\prod a_i$,求各个方案代价之和

状态转移方程

  • 考虑 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]);

最优子结构

在上个例子中,最优子结构意思就是在 $i,v$ 确定时,只有在此时的 $w$最大时,最终结果是最优解。

极小状态集

即用最少的参数表示状态,不唯一

技巧

二进制拆分(单调队列)

每个数字选或不选的两种状态,则拆成 $k$ 个数字最多能表示的数量为 $2^k$,需要注意当总量不为 $2^k-1$时,拆分总和不能超过物品总和

例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$ 一维。
————————

Enumeration prefix and

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

Example 4

The remaining two numbers of 2n $appear as even numbers, and those two numbers appear separately

  • The result after XOR is the XOR value of two numbers. The two numbers must be different from each other in one bit, so that $f [i] $represents binary and represents the XOR value of all numbers with $1 $in bit $I $

Below the split line is the problem

Example 1

For the bulb matrix of $n \ times M $, changing the state of one position each time will affect the upper, lower, left and right states. Given the initial state, ask whether it can be completely off

  • The result of a position up, down, left and right, including his own final operation times and module $2 $is fixed — > column $nm $linear equations (time complexity takeoff)
  • Enumerate the switching methods of the first line, find the last line all the way, and see if the last line can be completely extinguished ($o (2 ^ n \ cdot nm) $)
  • Set $a_ {I, J} $indicates the operand required at a certain location, $C_ {I, J} $$indicates the status of a location, then $$C_ {i,j} + a_ {i-1,j} + a_ {i,j+1} + a_ {i,j-1} + a_ {I + 1, J} \ equiv 0 \ pmod2 $$, indicate $a $of the next line from the first line until the last line to judge whether it is legal

Example 2

For the bulb matrix of $n \ times M $, you can select one column or one row of bulbs in reverse at a time. Given the initial state, ask how many columns of bulbs can be made to be $1 at most after just $k $operations$

  • The status of the row is determined by whether a column is on and whether the column is pressed. The time complexity is $o (2nm ^ 2)$
  • One property: for any two columns, if and only if their initial states are the same or complementary, they can light up at the same time and classify the initial columns

Example 3

The matrix of $n \ times M $has $a at each position_ {I, J} $hamsters, with a hammer of $R \ times C $($R, C $arbitrary), you can reduce all the hamsters in such a large range by one at a time (you must ensure that there is at least one in these grids). How many times do you use at least?

  • Violent enumeration $R, C $,

Thinking questions

Brute force enumeration double pointer

Example 1

Given an array with a length of $n $, find how many intervals $[l, R] $satisfy $\ sum \ limits_ {i=l}^ra_ i ≤ k$。

  • Double pointer direct enumeration. Note that $R $cannot exceed $l $

Example 2

$n $cards of $M $kinds can only be bought continuously. Please find out how much you need to collect $M $kinds at least.

  • Double pointer direct scanning

Example 3

Given a string with a length of $n $and only containing $\ texttt {R G B} $, find out how many characters you need to modify at least to obtain a string with a length of $k $and the form of $\ texttt {rgbrggb} \ dots $.

  • Count each string with a length of $k $and classify it according to the remainder divided by $3 $

Example 4

Given an array with a length of $n $, find how many interval XORs are equal to their sum.

  • Nature: $a \ oplus B ≤ a + B $, so if and only if the interval does and is equal to $0 $, it meets the meaning of the question and directly scans with double pointers

Example 5

Given an array $a, B $with a length of $n $, find $\ sum \ limitsn_ {i=1}\sum\limitsn_ {J = 1} (a_i + b_j) $exclusive or sum$ n≤2\times10^5, 0 ≤A_ i,B_ i< 2^{28}$

  • When $a_ i+B_ The $28th $bit of J $is $1 $, if and only if $a_ i+B_ J \ in [2 {28}, 2 {29} – 1] $, i.e. $B_ J \ in [2 {28} – a_i, 2 {29} – 1-a_i] $, sort $B $and divide it by two. For the $27 $bit, take the module of $2 ^ {28} $for each number pair, and the rest can be operated in turn.

Example 6

  • Consider subtask $1 $: for any line of $sum > 2K $, double pointer scanning directly; For any line of $Su m \ in [K, 2K] $, output directly;

Example 7 (ring sequence)

There is a ring sequence, $a $can specify a position to disassemble the ring, then play the game with $B $in turn, and $a $takes the lead$ A $can take any element, and $B $can only be taken from the far left. Find the maximum score that $a $can get and the position of disassembly.

  • Considering the chain, the first $\ frac {n} {2} $elements are recorded as $1 $, and the last $\ frac {n} {2} $elements are recorded as $- 1 $. The prefix and that satisfy the meaning of the question must belong to $(- ∞, 1) $. Directly input the prefix and find the position greater than or equal to $2 $, and then take it as the beginning of the chain to satisfy the meaning of the question.
  • Considering the above prefix sum, if you move the first $n $to the back, that is, the prefix sum behind should be subtracted from the prefix sum before, that is, the question of modifying the maximum value of the interval, the segment tree can be used

Greedy Algorithm

Classical model: partial order relation

Example 1

Given $n $positive integers, find the largest integer that can be connected end to end

  • Treat it as a string. For any two adjacent digital elements in the result, if $\ texttt {a} + \ texttt {B} > \ texttt {B} + \ texttt {a} $, it is the optimal solution

Example 2 p1080 [noip2012 improvement group] king game

  • Greedy strategy: the product of the left hand and the right hand is small. Proof: considering two adjacent ministers $I, j $, and the product of all left hands in front of $I $is $s $, then this strategy $\ max (\ frac {s} {r_i}, \ frac {s \ cdot l_i} {r_j}) $, and this strategy $\ max (\ frac {s} {r_j}, \ frac {s \ cdot l_j} {r_i}) $, and because

Classic models: segment coverage

Example 1 p1803 messy YYY / line segment coverage

  • The earlier the deadline, the smaller the impact

Example 2

Given $n $line segments, find the maximum number of line segments with intersection.

Classic model: bitwise greed

Example 1

Given the array $a $, $q $group query gives $k $, find $K \ oplus a_ I $max.

  • Make 01 trie for $a $and be greedy.

Example 2

Given a formula consisting of, for example, given $k $, find the value of $M $, and $m \ in [0, k] $, the result of the formula is the largest.

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

Thinking questions

$n $numbers, $1 ≤ a_ Set $I ≤ 10 $, and set $I ^} to decimal_ i+a_ J $carry times, find $\ sum \ limitsn_ {i=1}\sum\limitsn_ {j=1}S(i,j)$。

  • For any number, whether there is a digit carry in one digit can obviously be handled by $o (n) $and whether there is a digit carry in ten digits can be directly treated as two digits. The problem is transformed into how many numbers each last $I $digit of each number is greater than or equal to a specific $k $. After sorting, each two points can be given

Example 1 (random number generator)

The matrix of $n \ times M $has each number in $[1, n \ times M] $. Go from the upper left corner to the lower right corner. After sorting the number of $n + M-1 $, treat it as the $\ texttt {ASCII} $code of the string, and find the string with the smallest dictionary order of all strings generated after a given matrix.

  • It is better to include the smaller value in the path. First find the matrix composed of the paths that can go to $1 $, and then find the matrix composed of the paths that can go to $2 $, and recurse after taking the intersection. The specific implementation can maintain the interval that each line can pass through.

Example 2

Looking down at a reservoir, there is the height of each point in the matrix of $n \ times M $, and the water will flow around. It is required to ensure that the water does not overflow the boundary and how much water can be stored at most.

  • Define the highest point on a path as the length of the path, then the maximum storage value of the point is the minimum value of all the paths that escape from the boundary, which is transformed into the shortest path problem. Then set a virtual point as the set of boundaries, and the problem is transformed into the sum of the “shortest path” from the virtual point to each point inside

Example 3

There are $n $dwarves and $n $elves. Each dwarf and elf has an ability value. The ability values are different. The dwarves form a ring of $1 $~ $n $, and the $I $Elves will change from $a_ I $dwarves begin to choose the first non rival dwarf to compete. How to arrange the order of elves to win the most games.

  • Consider the chain first. If the suffix sum at any position is less than or equal to the subscript, it becomes the chain situation, and the problem is transformed into interval Tianji horse racing.
  • The proof of circular case is the same as [this question] (# Example 7 (circular sequence))

Example 4

There are $n $strings in the shape of $\ texttt {1 < strong > 5} $\ texttt {15} $\ texttt {1 < / strong > 5} $\ texttt {14} $. Replace $\ texttt {*} $with a number, increase the number of $n $monotonically, and make the final result number as small as possible to output the scheme.

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

  • Task 1: enumerate the numbers from $1 $to $10 ^ 6 $
  • Task 2: form an asterisk into a number and start bisection
  • Task 3: greedy from high position

Dichotomy

Template

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

Example 1

Four arrays with length of $n $$a, B, C, D $, any $a, B, C, D $, how many schemes do you find to make $a_ a+B_ b+C_ c+D_ d = 0$

  • Convert to $a_ a+B_ B = – (c_c + d_d) $, which can be sorted into two arrays with double pointers

Example 2

$n $clothes need to be dried and the moisture content is $a_ I $, evaporate $1 $unit water per minute. A hair dryer can evaporate $k $unit water per minute. Find the minimum time

  • Two minutes of total time. No matter how many minutes it takes to blow if it is not dried, the total time will be compared with the total time of two minutes

Example 3

$n $project groups, each with $a_ I $individuals, one person from different $k $project groups at a time, and ask how many times you can take it at most

  • Bisection times $t $, if $\ sum \ limits ^ n_ {I = 1} \ min (a_, I, t) ≤ TK $, then it is OK,

Example 4

Infinite number axis. A robot starts at $0 and has a series of instructions, such as $\ texttt {lrrlrlrlrlrlrlllr} $. It hopes to finally stop at a place it hasn’t walked before, but it can put a wall. If it hits a wall in the next step, it won’t walk. How many walls are needed at least? Number of schemes?

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$

  • Two point answer.

Example 6

There is a wall. The height of the leftmost position of sandbags should not exceed $h $, and the difference between the right and the left should not exceed $1 $. It is required to stack $1 on the rightmost side, and it is required to use up $n $sandbags. Ask how many columns to stack at least.

  • It’s only about the highest point, two points.

search

Example 1

See the solution

Search skills

  • Pruning (valuation)
    $now+h(x) ≥ best$。 The valuation function must be better than reality.

Pruning (valuation)

  • direction
    Optimal + pruning at each step (?) But there may be a problem.
    The width can be greedily limited at each step

direction

  • Memorization
    Search memory: record the optimal solution of each state

Memorization

  • IDA*
    Limit the depth of the search tree to $Lim $, plus the valuation function.

IDA*

  • -Pruning
    Two players, one with the largest purpose and the other with the smallest purpose. In the two search steps, suppose that the first step is from large to small, and the second step is from small to large

-Pruning

Example 2

Example 3 16 digital

  • Take the left column and the top row of IDA *, leaving eight digits.

Example 4

  • Memorization
  • The search direction must kill the smallest bird alive every time

DP

Thinking questions

The given number $n $, is divided into several numbers $a_ 1,a_ 2,\dots,a_ K $, for $\ prod a_ I $, sum the costs of each scheme

State transition equation

  • 考虑 DFS
  • Consider optimization (search memory, etc.)
  • Equation? And initial state

Example: 01 Backpack

  • DFS (I, V, w) indicates that the $I $item has been searched, with a volume of $V $and a value of $W$
  • Memory optimization
  • Make $DP_ {I, V} $means the maximum value of $V $used in the $I $part, so obviously $D, P_ {i,v} = \max(dp_{i-1,v},dp_{i – 1, v – v_i}+w_i)$。 Then consider the initial state.
    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]);
    }
    The time complexity is $o (NC) $, and the space complexity is the same.
  • Considering the optimization space, it is found that each recursion is only related to the previous line, which is optimized by rolling array.
  • Continue to consider the optimization space. Each point is only related to the lower left and lower. If it starts from the right, the point directly below it does not need to be used and can be replaced directly
    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]);

Optimal substructure

In the previous example, the optimal substructure means that when $I, V $is determined, the final result is the optimal solution only when $W $is the largest at this time.

Minimal state set

That is, the status is represented by the least parameters, < strong > is not unique < / strong >

skill

Binary split (monotone queue)

If each number is selected or not, it will be split into $k $numbers. The maximum quantity that can be represented is $2 ^ k $. It should be noted that when the total amount is not $2 ^ k-1 $, the total amount of splitting cannot exceed the total amount of items

Example 1 01 backpack, but $C, w ≤ 10 ^ 9, n ≤ 100$

  • For each $I $, you can enumerate all possible $V $and $W $, and all States with larger $V $and smaller $W $can be discarded.

Example 2 longest ascending subsequence

  • Make $d p_ {i} $indicates the longest length of the first $I $, then $d p_ i = 1 + \max \limits_ {j < i,a_j < a_i} dp_ J $, time complexity $o (n ^ 2)$
  • Make $DP_ {I, len} $indicates the number of the first $I $. If you select the last number of LIS with a length of $len $, you can update $DP_ The condition of {I, len} $is $a_ i > dp_ {I-1, len-1} and a_ i < dp_ {I-1, len} $, actually only uses $len $one dimension.