NOIP提高真题整理(2011-2018)-标签

加粗的后面应该会有相应的简单解析(如果没咕的话:))。

2011

day1

T1:铺地毯:逆着铺

T2:选择客栈:按颜色分类枚举+二分答案

T3:Mayan游戏:大模拟dfs+剪枝

day2

T1:计算系数:(求((ax+by)^k)(x^n*y^m)的系数)杨辉三角,数学,快速幂:(C(k,m)*(a^n)*(b^m))

T2:聪明的质监员:二分答案(往中间靠)

T3:观光公交:二分答案+贪心排布


2012

day1

T1:Vigenère密码:模拟

T2:国王游戏:贪心(相邻交换)+高精乘除

T3:开车旅行:双向链表模拟+倍增

day2

T1:同余方程:exgcd

T2:借教室:线段树或二分答案

T3:疫情控制:二分答案+贪心排布


2013

day1

T1:转圈游戏:快速幂

T2:火柴排队:简单的yy+树状数组辅助计数

T3:货车运输四种做法(启发式合并,按秩合并,整体二分,最大生成树+倍增)

day2

T1:积木大赛:思维题直接扫一遍,或分治去做

T2:花匠:简单Dp

T3:华容道:大模拟,bfs,spfa


2014

day1

T1:生活大爆炸版石头剪刀布:模拟

T2:联合权值:计数水题(记录前缀值)

T3:飞扬的小鸟:Dp模拟(分步骤转移,注意转移顺序)

day2

T1:无线网络发射器选址:暴力枚举

T2:寻找道路:预处理ban掉一些点,然后跑一边dijkstra最短路

T3:解方程:高精(或者对大质数取模),秦九韶公式


2015

day1

T1:神奇的幻方:模拟

T2:信息传递:求最小环,可以直接tarjan秒掉,也可以带权并查集或dfs之类的

T3:斗地主:大模拟,爆搜,细节

day2

T1:跳石头:二分答案

T2:子串:计数Dp,前缀和优化

T3:运输计划:(对于一棵树,给定m跳路径,让你删一条边,使得所有路径的最大值最小)二分答案+乱搞或者抽直径


2016

day1

T1:玩具谜题:模拟

T2:天天爱跑步:好题,dfs作差,或者dsu on tree

T3:换教室:Dp,细节,模拟

day2

T1:组合数问题:组合数,二维前缀和

T2:蚯蚓:思维题,队列

T3:愤怒的小鸟:搜索,状态压缩


2017

day1

T1:小凯的疑惑:打表盲猜,证明需要exgcd

T2:时间复杂度:栈,模拟,细节

T3:逛公园:记忆化搜索,最短路

day2

T1:奶酪:排序模拟

T2:宝藏:状压Dp,(官方数据水,放过很多错误做法)

T3列队:线段树,平衡树


2018

day1

T1:铺设道路:同2013的day2T1

T2:货币系统:简单的yy一下,然后类似背包的打标记

T3:赛道修建:二分答案+贪心排布

day2

模拟赛还没考,先略了。

原文地址:https://www.cnblogs.com/Tieechal/p/11665132.html