2018noip复习

· · 个人记录 

11-1 整理
P1000 超级玛丽游戏    
字符串输入输出。    
P1001 A+B problem   
新手入门。   
P1002 过河卒   
简单DP。   
P1003 铺地毯 
数学题+逆序优化。   
P1004 方格取数  
同步型DP   
P1006 传纸条   
同步型DP（对比P1004）  
P1010 幂次方   
递归+字符串。 
P1012 拼数    
贪心+字符串。 
P1014 Cantor表   
数学归纳。   
P1015 回文数   
高精进制转换。 
P1020 导弹拦截  
输入毒瘤+子序列转换+序列DP。    
P1023 税收与补贴问题   
约束区间的数学题。   
P1031 均分纸牌  
贪心。 
P1033 自由落体   
数学题。    
P1035 级数求和  
数学问题+精度。    
P1044 栈 
栈模拟或数学归纳（卡特兰数）。 
P1045 麦森数   
高精快速幂+指对转换。 
P1048 采药    
01背包。   
P1049 装箱问题  
完全背包。   
P1051 谁拿了最多奖学金  
离散化排序（快排函数）。    
P1055 ISBN号码    
字符串运算。  
P1059 明明的随机数     
桶排去重。   
P1060 开心的金明 
01背包变式。 
P1067 多项式输出 
字符串模拟。  
P1068 分数线划定 
排序。 
P1071 潜伏者    
字符串对应（map）。 
P1077 摆花    
中级DP。   
P1080 国王游戏   
高级贪心（需证明）+高精乘除。 
P1082 同余方程  
扩欧裸题。   
P1086 花生采摘  
模拟搜索。   
P1088 火星人   
排列转换问题（可能能用康托展开）。   
P1090 合并果子  
贪心。 
P1091 合唱队形  
子序列DP。  
P1093 奖学金   
离散排序。   
P1095 守望者的逃离    
多坑贪心。   
P1101 单词方阵  
DFS。    
P1106 删数问题  
简单贪心。   
P1118 [USACO06FEB]数字三角形
杨辉三角+DFS+剪枝。    
P1126 机器人搬重物    
BFS+格点图转化+注意最优性。
P1135 奇怪的电梯
BFS。
P1162 填涂颜色 
BFS判断连通性+正难则反。
P1164 小A点菜
分类讨论DP。
P1177 【模板】快速排序
模版（学用sort）。
P1181 数列分段Section I 
贪心or二分。
P1182 数列分段`Section II`
二分答案。
P1192 台阶问题
推广fib数列（也可锻炼DP思想）。
P1200 [USACO1.1]你的飞碟在这儿
字符串基础。
P1219 八皇后
DFS+存储空间优化。
P1223 排队接水
排序+精度问题+贪心。
P1226 【模板】快速幂||取余运算
模版学习二进制思想。
P1233 木棍加工 
多对相独立因素下的贪心。
P1238 走迷宫
BFS+方向优先级。
P1294 高手去散步
DFS遍历。
P1303 A*B problem
高精乘板题。
P1314 聪明的质监员
二分+前缀和处理。
P1316 丢瓶盖 
二分答案。
P1339 [USACO09OCT]热浪
裸最短路算法。
P1342 请柬
最短路变式。
P1379 八数码难题
合理寻找BFS空间+哈希存储。
P1403 [AHOI2005]约数研究
数学归纳。
P1421 小玉买文具
智障。
P1423 小玉在游泳 
精度智障（等比数列可做）。
P1424 小鱼的航程(改进版)
智障。
P1433 吃奶酪
DFS+剪枝。
P1434 [SHOI2002]滑雪
DFS+记忆化搜索。
P1436 棋盘分割
高维DP。
P1440 求m区间内的最小值 
单调队列。
P1443 马的遍历
裸BFS。
P1469 找筷子
人类智慧!(与二进制有关)
P1541 乌龟棋
经典DP。
P1553 数字反转（升级版） 
字符串模拟。
P1563 玩具谜题
暴力模拟（可用map）。
P1577 切绳子
实数二分处理：转化整型or人类智慧。
P1582 倒水 
二进制数学题。
P1583 魔法照片 
多次排序题。
P1596 [USACO10OCT]湖计数
DFS or BFS判联通。
P1598 垂直柱状图
字符串模拟题。
P1601 A+B problem（高精）
高精模版系列。
P1603 斯诺登的密码 
字符串坑题（map）+贪心。
P1604 B进制星球
高级高精加。
P1605 迷宫
DFS模板题。
P1616 疯狂的采药 
完全背包。
P1702 突击考试 
小聪明or DP。
P1781 宇宙总统
字符串排序。
P1784 数独
DFS+状态压缩。
P1873 砍树
二分答案。
P1908 逆序对 
归并排序（没用）。
P1931 套利 
SPFA裸题。
P2142 高精度减法
高精系列。
P2165 [AHOI2009]飞行棋
数学知识。
P2197 【模板】nim游戏
经典博弈论+SG定理。
P2327 [SCOI2005]扫雷
穷举。
P2404 自然数的拆分问题
深搜（注意顺序）。
P2440 木材加工 
二分。
P2580 于是他错误的点名开始了
Tire树模版。
P2661 信息传递
并查求环。
P2678 跳石头
二分。
P2822 组合数问题 
二维前缀和预处理。
P2985 [USACO10FEB]吃巧克力
牛逼二分+贪心。
P3150 pb的游戏（1）
博弈论智障。
P3366 【模板】最小生成树
必要（两种写法）
P3367 【模板】并查集
必要。
P3368 【模板】树状数组 2
不必要。
P3371 【模板】单源最短路径（弱化） 
SPFA必练。
P3372 【模板】线段树 1
不必要。
P3373 【模板】线段树 2 
不必要。
P3374 【模板】树状数组 1
可以学习下lowbit等二进制问题。
P3378 【模板】堆
priority_queue重载。
P3379 【模板】最近公共祖先（LCA）
建议学习。
P3382 【模板】三分法
建议学习。
P3383 【模板】线性筛素数
必学。（另外最好学习欧拉筛）。
P3392 涂国旗 
DP高级题目。
P3395 路障 
灭顶之灾。
P3811 【模板】乘法逆元
必学。
P3818 小A和uim之大逃离 II
BFS的骚操作。
P3865 【模板】ST表 
不必要。
P3932 浮游大陆的68号岛
前缀和处理，上下三角前缀和。
P3938 斐波那契
数学归纳。
P3951 小凯的疑惑
数学归纳。
P3952 时间复杂度
暴力字符串模拟。
P4779 【模板】单源最短路径（标准）
Dij+堆优化必须一次保对。
P4942 小凯的数字
数学归纳。
11-4 更
P2123 皇后游戏
同贪心，交换次序证明。
P1865 A % B problem
预处理质数个数+前缀和+处理。
P1372 又是毕业季I
人类智慧。
P2158 [SDOI2008]仪仗队
欧拉筛。
P1739 表达式括号匹配 
模拟栈。
P1449 后缀表达式 
用栈维护数据，注意加减顺序。
P1115 最大子段和
注意负值情况。
P1996 约瑟夫问题
模拟过，好像有数学方法。
P1030 求先序排列 
树与递归。
P1087 FBI树
巧妙利用返回值。
P1305 新二叉树 
学会建图+数据BUG。
P1120 小木棍 ［数据加强版］
用链表优化重复进入！
P1280 尼克的任务 
反向dp。
P1508 Likecloud-吃、吃、吃
P1387 最大正方形
注意dp取对角线。
P1378 油滴扩展
DFS+注意未放的点不受影响。
P1514 引水入城 
贪心求最小覆盖全区间数。
P4995 跳跳！
贪心交换证明。
P4994 终于结束的起点 
不要被题目的无用信息蒙骗！
P1011 车站 
满足广义fib的说法，小样例可手推。
P1016 旅行家的预算 
注意不完备的贪心策略+精度。
P1017 进制转换 
复习进制转化的实质：短除余位为正。
P1018 乘积最大
高精修改注意保存。
P1019 单词接龙
map真好用。
P2615 神奇的幻方 
推出规律很好写。
P1313 计算系数
注意到处求模。

11-5 补充
需要写的板子
一、数论：
1.高精加减乘（整）除快速幂。
2.快速幂。
3.组合数递推。
4.（扩展）欧几里得。
5.乘法逆元->线性，费马，扩欧。
6.线性筛，欧拉函数。
7.哈希->康拓展开。
8.线性lg递推。
9.进制转换。
10.二进制操作。
二、图论
1.存图->前向星，矩阵。
2.最小生成树->prim,kruskal。
3.最短路->（dij+堆优化），spfa。
4.（负）环->并查集，spfa。
5.拓扑排序。
6.差分约束。
三、数据结构（使用stl）
1.并查集。
2.堆(priority_queue)。
3.单调队列(deque)。
4.队列(queue)。
5.栈(stuck)。
6.映射(map)。
7.前缀和。
8.差分序列。
四、其他
1.二分。
2.string串操作。
3.快读。
4.01背包，完全背包，多重背包。
5.LIS。
6.分治。

（发现的资料勿喷）
https://pan.baidu.com/share/link?shareid=958836744&uk=1514916726#list/path=%2F