洛谷试炼场

ACM专题笔记

专题中比较好的题予以加粗。下面是专题的目录，可以直接点击转到对应专题

普及练习场

简单模拟

• 1003 铺地毯 因为只查询一个，所以对这个点倒序模拟即可。如果要对所有区域进行查询可以写线段树
• 1540 机器翻译 先进先出，表现出典型的队列特征。可以手写一个数组模拟队列也可以直接STL。
• 1328 生活大爆炸版石头剪刀布 怎样都行，直接查询的问题。

交叉模拟

• 1031 均分纸牌 找出结论后会比较好做，从前往后维护与平均数的总差值。总差值为0时这个纸牌处不需要移动。可以实现O(N)的时间复杂度。
• 1042 乒乓球 同时模拟两个就好了，水题。
• 1098 字符串的展开 分别实现就可以，水题。

排序

• 1177 【模板】快速排序 字面意思。
• 1059 明明的随机数 set容器直接调用即可。水题。
• 1068 分数线划定 写一个cmp结构体排序即可。

排序Ex

• 全是cmp重载一下结构体排序就解决的。（c++库函数真方便）

字符串处理

• 1603 斯诺登的密码 优先队列放进去依次拼接就可以。
• 1071 潜伏者 一个判重数组解决。
• 1012 拼数 不是直接字典序，我就是这么WA的。是先字典序排序完了后要再检查一下相邻两个数的先后拼接大小。
• 1538 迎春舞会之数字舞蹈 不是特别好写。

贪心

• 1090 合并果子 优先队列。水题。（和后面的合并石子的区别在于这题不要求只能合并附近）
• 1208 [USACO1.3]混合牛奶 Mixing Milk 排序后贪心。水题。
• 1803 凌乱的yyy 需要证明贪心方法。贪心顺序：在当前可取的线段中，右端点最靠左的线段。
• 1080 国王游戏 需要证明贪心方法。另外需要特判拿到的钱是0（发奖金不可能发0元）。

深度优先搜索

• 1219 八皇后 数据加强了，询问了13*13的棋盘。要优化一下记忆化的姿势（我一开始的姿势不够优越）
• 1019 单词接龙 判接龙的部分不是很好写。
• 1101 单词方阵 比较简单，记忆化无脑搜索就可以了。
• 1605 迷宫 最简单的深搜型迷宫。
• 1040 加分二叉树 区间DP。先序输出。
• 1092 虫食算 要剪枝。（据说官方正解是高斯消元然而我并不能看懂）

广度优先搜索

• 1162 填涂颜色 裸的联通块
• 1032 字串变换 简单BFS
• 1141 01迷宫 最简单的广搜型迷宫
• 1126 机器人搬重物 给的是格子，询问的是格子的交叉点，我自己没注意到要转化就WA了。另外本题的状态数组加方向。
• 1443 马的遍历 裸的BFS把马能吃的地方打上vis[i][j]=1就完了。
• 1379 八数码难题 可以利用map存储状态以解决空间不够用的问题

带有技巧的搜索

• 1118 [USACO06FEB]数字三角形 观察出有杨辉三角的特性，然后剪枝+记忆化搜索。由于深搜的第一个就是顺序最小的，直接输出结束即可。
• 1433 吃奶酪 一开始我还纠结了一会儿要不要先贪心取一个值然后再根据这个值进行搜索（觉得好像能多剪一些枝）事实证明并没有，这题就是一个简单的记忆化搜索+普通剪枝DFS。
• 1434 滑雪 这个也是DFS但是也可以用DP做。据说DP是快一点。（然而我想了一会儿感觉其实差不多？）

分治算法

• 1226 取余运算||快速幂 板子题啦
• 1010 幂次方 我打表做了（打表好写）不打表的话简单递归。
• 1908 逆序对 我用STL的Vector二分卡时间过的，题解的做法说是可以树状数组啥的弄掉（然而我还是觉得Vector简单……）

简单数学问题

• 1045 麦森数 高精度乘法的板子题。
• 1147 最大连续自然数和 我暴力过的…不暴力的话可以算下通项公式。
• 1029 最大公约数和最小公倍数问题 简单GCD。

递推与递归二分

• 1192 台阶问题 斐波那契数列的变形。
• 1025 数的划分 DFS可做。
• 1135 奇怪的电梯 记忆化BFS。
• 1316 丢瓶盖 找最大值中的最小，典型的二分法。

线性数据结构

• 1996 约瑟夫问题 动态加点动态减点的问题用Vector。
• 1739 表达式括号匹配 后入先出。典型的栈。
• 1160 队列安排。 插入修改删除，典型的链表。

树形数据结构

• 1087 FBI树 典型二叉树，自下向上构建。
• 1030 求先序排列 二叉树经典题目啦。
• 1305 新二叉树 森林合并二叉树问题。

动态规划的背包问题

• 1060 开心的金明 01背包。
• 1164 小A点菜 01背包，求满足条件的方案数而非求价值。
• 1064 金明的预算方案 有附件的01背包问题
• 1048 采药 01背包。
• 1049 装箱问题 01背包，求剩余空间最小的方案。
• 1616 疯狂的采药 多重背包。

线性动态规划

• 1880 [NOI1995]石子合并 区间DP题。不同的是这个题是一个环而不是一个链，因此要从所有可能的位置剖开一遍。然后记忆化区间DP。
• 1282 多米诺骨牌 正常01背包可做。优化成数量有限的多重背包效果并不好。
• 1091 合唱队形 其实就是最长上升子序列问题。
• 1020 导弹拦截 本题实质上第一小问是最长不上升子序列，第二小问是最长上升子序列。

多维动态规划

• 1508 Likecloud-吃、吃、吃 虽然是从下往上走的，但其实可以从上往下DP。效果是相同的。
• 1387 最大正方形 转移方程：若该处为1，则判断左方、上方和左上方是否为1，然后加1/置0；若为0，直接置0
• 1417 烹调方案 条件排序+01背包
• 1736 创意吃鱼法 最小子单位矩阵问题。和1387比较像。
• 1006 传纸条 从给定的起点出发，寻找到指定位置的两条最短严格不相交路线。维护同一个斜线上的两个纸条的状态F[sum][i][j]。过程中，只需要保证i不等于j，那么就一定能保证传纸条的两条路线不重合。

更要技巧的动归与记忆化

• 1064 金明的预算方案 带附件的01背包
• 1541 乌龟棋 物品数量有限制的多重背包
• 1063 能量项链 环状区间DP问题

高精度算法

• 字面意思。写两次就会了。（然而人生苦短，我用python）虽然py容易超时

贪心Ex

• 1080 国王游戏 需要证明贪心结论。
• 1031 均分纸牌 维护前缀和。
• 1233 木棍加工 需要证明贪心结论。
• 1315 观光公交 贪心结论不好弄出来 （感觉应该叫乱搞题）

简单数学

• 1865 A%B Problem 线性筛素数+树状数组维护前缀和可做。
• 1582 倒水 从题目推导出$2^N$个瓶子可以合并一瓶，然后就简单了写个bool数组存二进制然后找lowbit(x)进行更新。
• 1372 又是毕业季 lv.1 水题不解释。
• 2158 [SDOI2008]仪仗队 欧拉函数问题，判断最多有几个互质的数对。

BOSS战普及练习1

• 1478 陶陶摘苹果（升级版） 带限01背包。
• 1363 幻想迷宫 可拓展型迷宫。BFS和DFS似乎都行。（题解说这题DFS不能写递归的版本会导致爆栈）
• 1736 创意吃鱼法 最小子单位矩阵问题。和1387比较像。

BOSS战普及练习2

• 1058 立体图 暴力大模拟。

BOSS战普及练习3

普及常见模板

• 1177 【模板】快速排序 快排就是快排。
• 3366 【模板】最小生成树 并查集求最小生成树。
• 3367 【模板】并查集 并查集就是并查集。
• 3371 【模板】单源最短路径 SPFA算法是基于BFS的。
• 3383 【模板】线性筛素数 线性筛就是线性筛。

提高历练地

数论

• 2152 [SDOI2009]SuperGCD 高精度GCD
• 1306 斐波那契公约数 $gcd(F[n],F[m])=F[gcd(n,m)]$

搜索EX

• 1378 油滴拓展 数据量比较小，直接DFS就可以了。注意油滴可能产生覆盖的情况，当发现距离小于零的时候计算半径平方和时应该为0。
• 1441 砝码称重 先DFS再DP。

并查集

• 1111 修复公路 裸的并查集
• 2024 食物链 要开3n的并查集（可以证明，不能将其优化成n），一个存本身，一个存天敌，一个存猎物。
• 1197 [JSOI2008]星球大战 离线，反向建图，每添加一个新的节点先添加一个联通块个数，然后再进行合并操作

图的遍历

• 2661 信息传递 拓扑找环
• 1330 封锁阳光大学 转化为染色问题
• 1341 无序字母对 欧拉图判断
• 2921 [USACO08DEC]在农场万圣节Trick or Treat on the Farm 拓扑找环+记忆化搜索

最短路问题

• 1339 [USACO09OCT]热浪Heat Wave 最短路的板子题。
• 1462 通往奥格瑞玛的道路
• 1346 电车 挺简单的一个SPFA。当是默认开关时下一个节点的最短路径与上一个节点直接比较，当不是默认开关时下一个节点与上一个节点路径长度+1进行比较。
• 1119 灾后重建
• 1144 最短路计数 求最短的路程个数而非路径长度。
• 1522 牛的旅行 Cow Tours

最小生成树

• 1546 最短网络 Agri-Net 裸的最小生成树。
• 2330 [SCOI2005]繁忙的都市 （好气哦检查了好几天才发现是把M写成N所以WA了…）最小生成树的性质：最小生成树同时也是最大边权最小生成树。
• 1991 无线通讯网 这题题面写的太不清楚了…我读了好长时间题目折腾样例才搞明白啥意思…总之是去掉了几个点后的各种子图的最小生成树。

较复杂图论（一）

• 1113 杂务 从前继节点中选择最大时间然后加上这个点自己的时间即可，简单的DP（升级版：如果数据不是有序的，需要先找出前继为0的节点然后做DFS给出层次，然后按层次排序之后更新）

线段树树状数组基础

• 1198 [JSOI2008]最大数 我写的静态线段树T了……看不懂题解里写线段树过的大佬怎么操作的（另外神奇的是刘总写的N方的更新算法竟然跑的贼快，分析了一波觉得应该是因为题目数据的询问远多于更新，导致写静态线段树更新的层次太多从而T了）
• 1972 [SDOI2009]HH的项链 离线 + 树状数组的话复杂度 $O(NlogN+MlogM)$ ，这个方法常数会比较大（我最后一个测试点T了算了一下最后一个点我用了1012ms…真是令人头秃）需要写一个能查询last的东西（我用了STL的map）

提高模板-nlogn数据结构

• 3374 【模板】树状数组 1 维护前缀和的树状数组。
• 3368 【模板】树状数组 2 维护某处值的（常用于区间修改）的差分树状数组
• 3372 【模板】线段树 1 区间更新 and 区间查询
• 3373 【模板】线段树 2 升级：两个pushdown
• 3378 【模板】堆 即C++中的priority_queue

省选斗兽场

省选基础-读入读出优化

• 2393 yyy loves Maths II long double 解决。

省选基础-位运算

• 2114 [NOI2014]起床困难综合症 利用 0x7fffffff 和 0 搞出来对应每一位的真值表，然后贪心每位的最大值求和即可。

省选基础-打表

• 1149 火柴棒等式 就是简单的递归一下解决掉（并没有省选的难度）

分块

• 3396 哈希冲突 基础分块题目，分sqrt(N)个块即可。预处理的时间复杂度是O(Nsqrt(N))，每次更新和询问的复杂度上限都是O(sqrt(N))，整体复杂度是O((N+M)sqrt(N))。

网络流-最大流

网络流-费用流

动态规划1