算法篇

算法 Algorithm

模拟 Simulation

模拟是基础，体现出你的代码能力，同时也考察你的阅读理解，以及情况是否考虑清楚

基本功：字符串输入[蓝桥杯 2022 国 AC] 内存空间

计算某年某月某日是星期几：如果纯模拟非常麻烦，但是用蔡勒公式非常简便

点击查看代码

int weekday(int y, int m, int d)
{if (m <= 2) m += 12, --y;int w;if (y < 1582 || (y == 1582 && (m < 10 || (m == 10 && d <= 4))))// 儒略历w = (d + 2*m + 3*(m+1)/5 + y + y/4 + 5) % 7;else// 格里高利历w = (d + 2*m + 3*(m+1)/5 + y + y/4 - y/100 + y/400) % 7;return w;  // 0=Sun,1=Mon,...,6=Sat
}

排序 sort

排序的算法有很多，大多数时候常用快速排序，其他的排序了解即可

• 简单思维题: 交换相邻元素

• 了解不代表不学，一个结合选择排序的思维题：
  困牛排序，题解

• 微扰法
  全局最优的必要条件是 “局部无法通过微小调整（如交换相邻元素）优化目标
  J. Stacking of Goods: 实际体积\(x_i = v_i - c_i × W_i\),v不变，只需要使得c*w最大,考虑相邻两个A,B。A在上和A在下的贡献差,\(Δ = [c_B(w_A + W_{up}) + c_A *W_{up}] - [c_A* (w_B + W_{up}) + c_B* W_{up}]= c_B * w_A - c_A *w_B\)，发现Δ<0时，需要A在下，\(c*w_{up}\)更大
  D. A Cruel Segment's Thesis:考虑交换两个区间，当他们合并之后的区间更大就交换，奇数时需要考虑，中间未被计量的区间是-l更小还是+r更大

快排使用方法

快速排序，除了调用函数sort以外，还能这样使用：

bool cmp(int a,int b){return a>b；
}

灵活地根据题目要求排序

递归

• 经典题
  汉诺塔问题
  上台阶
• 较难题
  分形之城：容易看出递归的思路，难点在于怎么实现坐标的变换

贪心 Greedy

贪心最难的不是怎么贪，最难的是证明

经典题

区间选点
均分纸牌
变式：七夕祭：可以看作环形的均分纸牌，题解

经典题总结

反悔贪心

（建议掌握stl之后再做）
超市

简单题

B. Shrinking Array
D - Transmission Mission:用最小的距离包括最多的基站
小红的01串：最终构造的形式就两种（注意到这点很关键），分别计算构造成两种形式所需最短次数就行

• 对答案的贡献
  战前准备:验证每个循环后的数组是否满足条件，暴力显然超时，而考虑对答案的贡献会发现，循环k和k+1位，影响只在于a[k]对答案产生的影响
  C2. The Cunning Seller (hard version):可以计算出最少次数，若最少次数都不满足输出-1，如有的多余的次数，那么可以发现将一次性交易\(3^{x+1}\)数量的西瓜换成3次交易\(3^{x}\)数量的西瓜所需费用更少
• 简单变换公式
  D - Match, Mod, Minimize 2:\(\sum_{i=1}^{n} (a_i+b_i) \mod M =\sum_{i=1}^{n} (a_i+b_i)-cM\)最大化c

模型 Model

除此之外，贪心经常与其他算法结合，还有很多模型需要总结

• 区间模型
  小红的区间修改（一）：鉴于多次询问且不能覆盖重复区间，所以已有的点存入集合，同时用二分在有序集合判断，是否有在之前重复存在的点
  扩展合法区间法：
  -数组的贡献:经典处理手法，对于\(a_i\)，合法的左右端点必须小于等于\(a_i\),分别处理后相乘即可，需要用到树状数组
  -「LAOI-15」天天爱阅读:这经典的处理方法，考虑每个价值对答案的贡献，扩展区间范围，计算能作出贡献的区间数量
  固定R,寻找合法的L法：小苯的数组计数:（前置知识：单调栈）固定右端点，找距离右端点最近的大于等于右端点的数，若是等于则无合法区间，如果是大于，有且仅有一个，对于小于右端点的，翻转处理

• 逆序对
  逆序对有三种求法，冒泡排序，归并排序，树状数组
  经典：奇数码问题:非常好的题解
  冒泡排序和逆序对的联系：超快速排序，冒泡排序本身是交换相邻元素（左边大于右边），而与相邻元素交换一次，就减少一对

枚举答案

与二分答案其实类似，我们可以判断出答案的范围，并知道答案是单调的

• [蓝桥杯 2022 国 A] 最大公约数 ：从小到大枚举区间长度检验gcd(a[i]~a[j])是否为1,题解

二进制问题 Binary problem

• 直接法
  Make It Beautiful:为了数组内，二进制下的1的数量最多，需要不断的使低二进制位有1，对于i个二进制位，消耗1<<i的操作次数.
• 结论
  纯粹的数学符号: $ (a_i | a_j)$ + \((a_i \& a_j)\)= $a_i + a_j $，用单独的一位bit可证

有些题明显涉及到二进制，直接求解会超时，而从二进制的角度求解反而更加简单

• 求值
  E. Boneca Ambalabu，直接异或超时，而统计每一个位上1的个数，然后按位异或，就能高效解决。题解

• 构造
  汉堡猪猪分糖果:显而易见尽量在高位全部分配1，难点在于某位不够分，这时分类讨论，该位不分配，后面取1能够分完，否则该位选取一些分配，使得后面的位数全部取1

与优先队列结合 Combined with priority queue

经典：
ProblemC.GooseGooseDuck:对于当前人数now,尽可能从l<=now的区间内，选出最小的大于now的r区间，用优先队列来维护l<=now的区间
井然有序之窗：题解

二分

二分主要是：二分查找与二分答案
总结

经典题：

• 青:二分答案+分段检验
• 检讨:二分答案+前缀和，检验平均值是否存在

线性复杂度优化技巧

差分 Differential

1. 一维差分

• 线段区间覆盖：
  胖达的山头,题解
  最高的牛：可以推出不存在区间交叉，注意：可能有重复区间出现
• 角度区间覆盖（稍稍变型）：[蓝桥杯 2025 省 A] 地雷阵,题解
• 双重差分： 平衡细菌，题解
• 进阶(增加对差分的理解)：增减序列

2. 二维差分

总结：差分使用的时机，是一种静态的区间修改，对于我们进行区间内改变相同的值或者求某一个点值因此修改后的值时，可以降低时间复杂度

前缀和 Prefix

1. 一维前缀和
   分段化：这个考法较为常见，主要是需要将区间划为3段，利用前缀和记录间接计算区间值
   -截断数组,题解
   -小红的华撃串:注意到01，10的产生只会在连续的0,1的交界处，最终的状态可用0101，1010表示，于是可以枚举三个间断点，计算变成最终态的最少次数，用前缀和记录某个区间内变成0或者1的次数
   -气球谜题,题解
   经典：计算\(\sum_{i} a_i*a_j\)，令\(sum_i=\sum_{k=1}^{k=i}a_i\)，则\(\sum a_i*a_j=\sum a_i*sum_{i}\)
   中等题：
   C. Incremental Stay：前缀和的变形
   C - Rotate and Sum Query:难点在于求和的范围
2. 二维前缀和
   二维的公式更为复杂，画图更好理解：
   激光炸弹
   A - 2x2 Erasing:读懂题

总结：与差分类似，前缀和是差分的逆，差分也是前缀和的逆

双指针

E. Split: 固定左端点计算，扩展区间右端点，对区间的贡献

动态规划

动态规划，主要的是弄清楚，状态的定义和状态的转移
状态的定义有许多不同的模型需要总结，背包就是一类典型

小tips:如果发现题目能用搜索解决，很有可能也可以用DP解决

线性DP经典模型

下标的转移

1. 最长上升子序列/导弹拦截

• 三元上升子序列：题解可以推广到n元，结合树状数组优化
• 分级：需要证明引理，构造的每个B一定是A的值

2. 最长公共子序列

• 编辑距离: 以字符串形式出现，但本质未变

3. 同时存在多种dp，相互关联:例如 DP[i][0]和DP[i][1]

• 小红的01串（五）:对于"?"，需要同时转移
• Yummy:需要分别考虑，当前位置i为前缀和为\(0，-k^{i+1},k^{i+1}\) 三种情况
• C. Non-Descending Arrays
• 小苯的数字变换: 计算满足条件区间的典题

• 从后往前转移：当我们设计的状态是从当前状态开始转移到末态时，那么就需要从后往前进行动态规划
  Takahashi's Expectation：设计状态为dp[i][j]是收到第i个礼物后，心情为j，到最终心情，因为此时的状态只由后方的状态确定，所以从后往前dp

通过值的转移，而非下标转移

下标的转移有时候不一定能达到想要的时间复杂度，最长上升子序列的优化也是通过这一思想达到的

• 森友会里打音游: 以值为状态，值的约数，倍数关系为状态转移关系

方案问题

这两个题都是典型问题，必会
放苹果：苹果是相同的
隔板：小球是不同的

概率问题

D. Segments Covering:设f[x]为从1到x，选取一些线段，恰好一次覆盖的概率，但是忽略了未选的概率，解决办法：存在概率/不存在概率 作为答案 ，最后在乘上所有不存在的概率的总和，就是答案，没选上的等于乘上了它的不存在概率，选上了再乘不存在概率就是存在概率

线性DP练习题：

• 具有明显转移关系
  蓝：这个题需要估计转移次数最多为\(\log_2^{N}\)次，转移关系就是题目所说.
  移动服务：难点在于状态的设计，需要一个状态表示三个服务员的位置，开一个三维状态，注意服务员不具有特殊性，所以每一维并不指定某个服务员，一起表示三个服务员的位置，其中一维需要表示处理第i个请求的位置
  C. Against the Difference:令dp[i]为前i个最长的分块，dp[i]要么等于前一个，要么从当前加入当前的数字分块，此时需要需要计算当前数字x前x的下标y,dp[i]=dp[y]+x;

背包

1. 01背包

f[i][j]代表前i种物品，背包容量为j时可以取得最大价值
除了掌握基本模型，这里还有个滚动数组，需要学习

点击查看代码

for(int i=1;i<=n;++i)for(int j=m;j>=v[i];--j)f[j]=max(f[j],f[j-v[i]]+w[i]);

2. 完全背包

与01背包不同的是，物品可以无限选择，只需要改变状态转移就可以

由前往后转移，在有限的容量多次选择同一物品

点击查看代码

 for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){f[i][j]=f[i-1][j];//不选当前if(j>=v[i])f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);}

小红的01串（easy）:长度为i的1串，贡献i*(i+1)的子串，可以重复选，所以可以套用完全完全背包的思想
小红的01串（hard）:在上题的基础，同时记录方案构成

3. 多重背包

多重背包又有所不同，物品变成有限次数
也可以转化成01，背包的思想，将有限物品拆分成表示成0,1,2,..,k件，每i件看成一个整体，选与不选

点击查看代码

 for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)for(int k=0;k<=s[i];++k)if(j>=k*v[i])f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);

• 二进制优化

优化的核心在于，我们其实可以知道，构成最大的价值的背包中一定装了x件某个物体，而x一定可以由二进制表示出来，所以将物体的件数，拆分成二进制数，多余的数也看成一个整体，价值也与之对应

通过01的背包的做法，一样能够选出最大价值

点击查看代码

for(int i=1;i<=n;++i) {int a,b,c;cin>>a>>b>>c;int t=1;while(t<=c){v[cnt]=t*a;w[cnt++]=t*b;c-=t;t*=2;}if(c>0){v[cnt]=c*a;w[cnt++]=c*b; }}

4. [分组背包](https://www.acwing.com/problem/content/description/9/): 与01背包类似，不过多一重循环，只考虑每组选一个

点击查看代码

for(int i=1;i<=n;++i){for(int j=m;j>=0;--j){for(int k=0;k<s;++k){//s是组内数量if(j-v[k]>=0)f[j]=max(f[j],f[j-v[k]]+w[k]);}}}

区间DP

• 经典题：
  • 石子合并：模板题
    变式：[NOI1995] 石子合并：实际上是环形的石子合并，破环成链的操作（必会）
  • D. Palindromic Distance:回文串+区间dp
• 最优子结构
  多边形：注意，乘法时的最优子结构不一定是由小区间的最大值相乘得到的

树形DP

以树的关系为转移
经典例题：没有上司的舞会

练习题：
F. Sheriff's Defense

状压DP

状压DP顾名思义利用状态压缩来实现DP，常用二进制来表示压缩后的状态

• 典型例题：
  最短Hamilton路径
  C - Mixture
• 简单变式：
  [蓝桥杯 2019 省 A] 糖果，每包糖果具有的口味可以看成M位的二进制串(状态)，而状态的转移通过每包糖
• Kingdom Path: 很明显地涉及到二进制，提醒我们从二进制的角度思考问题

分治

分治思想

根号分治

G序列与整数对:题解
F. Remainder Problem:注意数据范围

搜索 Search

DFS

深度优先搜索，以搜索的深度优先.

• 小红与好数组:简单

• 小猫爬山:深搜的对象是缆车，枚举所有把猫分到不同合法缆车的可能

• 新婚:显然的需要预处理，搜索的同时记录路径组成的二进制数，枚举其子集，标记对应的十进制数

• 连通性
  4004. 传送阵

  • 类似做法的题：F幻形之路

• 剪枝
  小苯的前缀gcd构造:简单剪枝

BFS

• 思维
  173. 矩阵距离:带点思维，搜索方式是广搜，考虑好的搜索的起点

• 反向广搜：由于一些情况，反向广搜更加方便，具体结合题目
  冲刺：正向搜索会使得搜过数据不断增多，而反向搜索时，则不会

• 多源bfs
  世界树上找米库: 把所有的度为1的点当作bfs起点，这样进行广搜，保证每个点第一次被搜索到的距离是距离叶节点最短距离
  小镇购物：发现k较小，可以将具有相同的商品的点作为起点（多个），再用多源bfs,就可以轻松解决了

• 状压搜索
  典型例题
  H. Genshin Impact Startup Forbidden III :题解，参考代码