NOIP 历年真题一句话题解

NOIP2012

TG:

D1T1:签到题
D1T2:根据两大臣情况推出贪心公式,记得高精
D2T1:逆元,exgcd or 费马小定理
D2T2:线段树维护区间最小值,如果变成负数就退出

NOIP2014

TG:

D1T1:签到题
D1T2:枚举中间节点,然后前缀和优化
D1T3:超过天花板的地方强行赋值到天花板,其余常规背包
D2T1:签到题
D2T2:建反图,正反两遍 SPFA

PJ:

T1:暴力,记得认真读题
T2:暴力,注意取的是两数相减不是绝对值
T3:递归,一层一层向内
T4:状压 dp,预处理合法状态

NOIP2016

TG:

D1T1:签到题
D2T1:杨辉三角求一波组合数然后二位前缀和统计
D2T2:开三个队列,分别存原数列、砍掉的前一半和砍掉的后一半,这三个队列都有单调性,所以就可以把暴力算法的优先队列换成这三个单调队列,减掉一个 (log) 的复杂度

PJ:

T1:签到题
T2:枚举年月日,转换为正整数再判断
T3:队列 + vector
T4:距离设未知数,推关系,前缀和优化

NOIP2017

TG:

D1T1:赛瓦维斯特定理,(ab-a-b)
D2T1:并查集加 (mathcal O(n^2)) 暴力枚举

PJ:

T1:签到题
T2:暴力
T3:dfs 加一个 dp 数组(存起点到当前点的最小金币数量)。一个小技巧:可以加一个 now_color 参数来处理格子颜色的改变
T4:二分套 dp(要用单调队列优化)

NOIP2019 CSP2019

PJ:

T1:签到题
T2:模拟,怎么做都行
T3:背包
T4:奇偶最短路

原文地址:https://www.cnblogs.com/juruo-zzt/p/13598108.html