NOIP前刷题记录

因为本蒻实在太蒻了。。。对于即将到来的NOIP2018ssfd,所以下决心要把自己近期做过的题目(衡量标准为洛谷蓝题难度或以上)整理一下,归归类,简单地写一下思路,就当作自己复习了吧qwq

本随笔持续更新,自2018.9.19开始,计划更新到2018NOIP截止

(但是因为最近写的比赛题比较多。。但是没有办法把这些题放上来。。所以只能放上主流OJ上面有的题)

如果本蒻今年有幸没有AFO掉,flag先里在这里——之后学省选知识点的时候会重开一贴更新的,到时候希望是更有难度的题目吧。


搜索

[NOIP2013]华容道
最短路+带剪枝的搜索,是一个思维难度比较大的题目。

CF1064D Labyrinth
考虑贪心,用双向队列bfs

[NOIP2017]宝藏
剪枝搜索出奇迹
题解:https://www.cnblogs.com/fengxunling/p/9777606.html

luogu 有趣的数

[ZJOI2007] 时态同步

[NOIP2002] 矩形覆盖
这题数据太水。。。
题解:https://www.cnblogs.com/fengxunling/p/9841614.html

[NOIP2016] 斗地主
题解:https://www.cnblogs.com/fengxunling/p/9862768.html


单调队列

[USACO12MAR]花盆Flowerpot(相似题目:CF1041D Glider)
维护deque,根据差值弹出

[USACO13OPEN]照片Photo
线段树,单调队列
题解:https://www.cnblogs.com/fengxunling/p/9839101.html


单调栈

CF547B Mike and Feet


Tarjan

[USACO08DEC]在农场万圣节Trick or Treat on the Farm(相似题目:luogu 缩点)
就是缩点之后DP找最长的一个链


拓扑排序

[SDOI2009]Elaxia的路线
求无向图中,两对点间最短路的最长公共路径。
四边spfa最短路,标记第一个点对的最短路上面的边,然后标记第二个点对的最短边种在刚才被标记的路径上的边,构建拓扑图进行DP。


组合数

noi.ac count
一道比较巧妙的组合计数问题。

noi.ac 求和
巧妙的实际应用组合数的转化


图论相关

luogu 通往奥格瑞玛的道路
二分答案+spfa最短路

[NOIP2017]逛公园
最短路+记忆化搜索
题解:https://www.cnblogs.com/fengxunling/p/9860984.html

CF938D buy a ticket
对于每个节点需要付费的情况怎么办呢......我们可以开一个超级源点,将节点权值赋予成它到超级源点的路径长度,然后跑最短路就可以了(CF上数据很强,需要dij)

CF986A Fair
注意到需要的颜色数量很少,所以先把相同颜色的压在一起,然后用floyd把两两颜色的距离处理出来,bfs搜索递推即可

[NOIP2013]华容道
一道比较难的搜索+图论。
题解:https://www.cnblogs.com/fengxunling/p/9773648.html

bzoj3714 [PA2014]Kuglarz
转化成最小生成树的想法很巧妙
题解:https://www.cnblogs.com/fengxunling/p/9812432.html

[NOIP2007] 树网的核

[USACO09FEB] 改造路Revamping Trails
分层图
题解:https://www.cnblogs.com/fengxunling/p/9870871.html

[JLOI2011] 飞行路线
分层图
题解:https://www.cnblogs.com/fengxunling/p/9870871.html

[HNOI2005] 狡猾的商人
差分约束
题解:https://www.cnblogs.com/fengxunling/p/9930396.html

[ZJOI2006] 物流运输
DP+最短路
题解:https://www.cnblogs.com/fengxunling/p/9871886.html

luogu 玛丽卡


数学相关

[SDOI2008]仪仗队
只要能看出来只取正方形的一半然后求坐标x,y互质就可以,之后就是很简单的欧拉函数板子了qwq

[CQOI2007]余数求和
先是利用整除的思想化简式子,\(n*k-\sum_{i=1}^{n}\lfloor \frac{k}{i} \rfloor\),然后这运用到了整除分块的思想(听说是莫比乌斯反演的前置技能??)

luogu 花园
矩阵运算+数学
题解:https://www.cnblogs.com/fengxunling/p/9712045.html

luogu 萨塔尼亚的期末考试
斐波那契数列结论推导+矩阵快速幂
题解:https://www.luogu.org/blog/fengxunling/solution-p4834

luogu 浏览器

[NOIP2012] 国王游戏
数学推论+高精度

luogu 十一月月赛 咕咕咕
组合数+DP
题解:https://www.cnblogs.com/fengxunling/p/9903460.html

[NOIP2006] 2^k进制数


bsgs

luogu 多少个1?
bsgs+快速乘(~~比赛的时候这个题叫做“签到题”)


树形结构

[HNOI2003]消防局的设立
树上半径为k的最小覆盖问题,维护祖先递推即可

[NOIP2012]疫情控制
综合倍增,二分,贪心,排序的一道码量很大的题。。。。。
题解:https://www.cnblogs.com/fengxunling/p/9759052.html

[AHOI/HNOI2018] 道路
见下DP专题

[NOIP2015] 运输计划
题解:https://www.cnblogs.com/fengxunling/p/9909619.html

CF455C Civilization | luogu HXY造公园
树的直径+并查集
题解:https://www.cnblogs.com/fengxunling/p/9915351.html

[NOIP2016] 天天爱跑步


倍增

luogu 跑路
就是一个有重边和环的有向图,问你最少可以用多少个2的次方拼成1到n的路径长度。
我们可以倍增处理,用三维数组来表示i,j之间存不存在走2的k次方可以到达的路径,然后合并的时候用四层循环,枚举中间点,如果i到中间点和中间点到j都存在2的k次方长度的路径,就把他们之间的路径长度赋值为1,最后跑最短路即可qwq.

[NOIP2012]开车旅行
倍增+离散化+双向链表(/set)
题解:https://www.cnblogs.com/fengxunling/p/9755195.html

[NOIP2012]疫情控制
见上树形结构


位运算

cf1054D Changing Array
题解:https://www.cnblogs.com/fengxunling/p/9816452.html

[NOI2001] 起床困难综合征
题解:https://www.cnblogs.com/fengxunling/p/9866998.html


DP

luogu 过河
状态压缩(由于路径长度过长,但是不能跳到的点很少,所以把不能跳到的点中间的路径压缩起来)+简单递推

noi.ac ladder
一个高维DP的题目,状态设计极为巧妙,使用滚动数组,而且用0/1来优化掉当前层排放*的情况。

[AHOI2009]中国象棋
状态的设计十分精巧,不需要考虑棋子摆放的具体情况,只需要考虑摆放的个数,所以用三维的数组来记录有多少列摆放的个数为1,多少列摆放的个数为2,其余的注意一下加法原理和乘法原理的使用。

luogu 种树
DP时注意提供“反悔”选项,消除后效性

[ZJOI2005]午餐
贪心+设f[i][j]为在第一个窗口前i个人用j

[HAOI2007]理想的正方形
基于倍增思想的DP,关键是正方形的拓展和转移。

[SDOI2010]地精部落
代码很简单,但是思维难度有点大。是一个求波动数列合法序列个数的题目。
题解:https://www.cnblogs.com/fengxunling/p/9749462.html

luogu 拆分数列
搜索,字符串,DP
题解:https://www.cnblogs.com/fengxunling/p/9799154.html

[SCOI2005]互不侵犯
状压DP,其实也可以打表

[SDOI2009]学校食堂
状压DP

[NOIP2017]宝藏
状压DP

CF407B Long Path

CF883I Photo Processing
二分来check+DP

luogu 道路游戏
就是注意从原先哪个状态转移过来就可以了qwq

[HAOI2009] 逆序对数列
题解:https://www.cnblogs.com/fengxunling/p/9834917.html

[TJOI2007] 线段
题解:https://www.cnblogs.com/fengxunling/p/9835758.html

[AHOI/HNOI2018] 道路
题解:https://www.cnblogs.com/fengxunling/p/9836473.html

[HAOI2010]计数
运用数位DP的思想

[NOIP2007]矩阵取数游戏
高精+区间DP

*nowcoder tg7th T2 洞穴**
状压DP
题解:https://www.cnblogs.com/fengxunling/p/9864827.html

[SDOI2006] 保安站岗
树形DP
题解:https://www.cnblogs.com/fengxunling/p/9849108.html

[JLOI2013] 卡牌游戏
概率DP
题解:https://www.cnblogs.com/fengxunling/p/9867038.html

[HNOI2010] 合唱队
区间DP
题解:https://www.cnblogs.com/fengxunling/p/9920867.html

[ZJOI2006] 物流运输
DP+最短路
题解:https://www.cnblogs.com/fengxunling/p/9871886.html


背包

luogu 垃圾陷阱
背包,但是不是要么使用要么不用,是要么使用要么存起来

luogu 宝物筛选
可以用单调队列做,但是我选择二进制拆分qwq


较为复杂的模拟

[NOIP2017] 时间复杂度

[NOIP2003] 侦探推理
很恶心的字符串模拟题qwq(好像主流是搜索的做法?但是我没有用搜索。。竟然也没有用map。。。。)

[NOIP2016]斗地主
题解:https://www.cnblogs.com/fengxunling/p/9862768.html

luogu 情书


线段树

借教室
其实是二分+前缀和,但是我用线段树写的qwq


悬线法

[ZJOI2007]棋盘制作
就是悬线法的经典例题

luogu 玉蟾宫
悬线法经典例题


神奇的解法:

[POI2010]GRA-The Minima Game
先排序,然后设dp[i]为取到第i个最大的数量,因为\(dp[i]=max(sum[j]-dp[i-1])\),但是n方算法会TLE,所以可以考虑递推优化:\(dp[i]=dp[i-1],dp[i]=max(dp[i],sum[i]-dp[i-1]\)


莫队

noi.ac color
因为数据锅了,所以普通莫队也可AC,但是实际上是一个线段树的题目


模拟退火

[HAOI2006]均分数据
DP处理均方差的计算+模拟退火玄学优化算法时间复杂度

[JSOI2004]平衡点
模拟退火经典题目


高斯消元

[HNOI2013]游走
期望+高斯消元


数学期望

luogu 收集邮票
一个期望的神仙题。。。。。
题解:https://www.cnblogs.com/fengxunling/p/9771104.html


置换

[NOIP2005] 篝火晚会
题解:https://www.cnblogs.com/fengxunling/p/9851782.html


其他:

[FJOI2007] 轮状病毒

上一篇:jquery 相关class属性的操作


下一篇:使用line_profiler查看api接口函数每行代码执行时间