NOIP2018在即，20181009总结一些易错的知识点和解题方法

——by ljc20020730 HGOI

• NOIP2018 No regrets youth !
• NOIP2018 No regrets youth !
• NOIP2018 No regrets youth !

解题方法概述

• 选择题（总分15+5共30分）

目标得分： 35.5 

时间控制：25 min

解题方法：

1. 注意审题（如NOIP2016 T2 别把CapLock当作输出），仔细解答
2. 程序模型题看清楚算法思想，保证拿分
3. 树的题目尽量带特殊数据，加快解题速度
4. 抓住题目关键性字眼，如非联通，正确还是错误，有关还是无关，包括和不包括，是还是不是，行优先还是列优先，
5. 关注选项的互译性，意思相同的选项作为单选题尽量不要斟酌
6. 分清楚一些已经错过的题目如插入排序和选择排序的原理问题，sin(sin(x))不是递归，二次探测的意思，散列的意思，子串包含空串
7. 注意控制答题时间以免后面的大题分数没有仔细斟酌，这里其实并拉不开差距
8. 一些斟酌的计算机基础知识的题目一定一定要专注于第一选项
9. 实在不行统计ABCD一般来说ABCD选项都是较为平均的分配的
10. 简单数学题不要花费大量时间注意采用验证法和归谬法和特殊值法来做（一定要看Master 算法）

•  问题解决题（2题，共10分）

目标得分： 5-10

时间控制：20 min

 注意一些常用的数学递推结论，

 如

1. 卡特兰数列(C(2*n,n)/(n+1))
2. 错排递推式f(n)=(n-1)*(f(n-1)+f(n-2),f(1)=0,f(2)=1)
3. 等比数列求和公式 (an=a1*q^(n-1),S=a1(1-q^n)/(1-q))
4. 第二类斯特林数（n个不同的球，放入m个无区别的盒子，不允许盒子为空，S（n,m）=S(n-1,m-1)+m*S(n-1,m)）
5. 重排列公式(a1+a2+a3...+an)!/(t1!*t2！*t3！...*tn！)
6. 第二类斯特林数的pascal三角 

　　　　     1    2     3    4    5     6    7    8
　　　　1    1    
　　　　2    1    1    
　　　　3    1    3    
　　　　4    1    7    6    1    
　　　　5    1    15   25   10    1    
　　　　6    1    31   90   65    15    1    
　　　　7    1    63   301  350   140   21   1    
　　　　8    1    127  966  1701  1050  266  28   1

　　7. 问题解决不一定是组合数，在情况复杂的情况下找找规律，不要急于暴
　　8. 不会做想Dp，比如一些n个苹果放到m个盘子里，考虑这样一个递推：

int f(int m,int n)
{
    if (m==0||n==1)  return 1;
    if (m<n) return f(m,m);
    if (m>=n) return f(m,n-1)+f(m-n,n);
}

对于一些最少最多的题目好好想想反例千万不要急于下笔，一般来说最值问题答案都是和第一次算出来的答案不相符合（真的没有更多了嘛？有没有反例？）
对于结论题千万不要相信自己第一次猜出的结论积极找反例
暴力枚举讲究方法有次序（如NOIP2017 T2暴力枚举上边和下边出错几率比较小）

• 阅读程序题（共4题共32分）

目标得分：32

时间控制：35 min

1. 对于简单题千万不要大意在这里丢分基本复赛没戏（我易人易，我难人难）
2. 注意隐藏在模拟条件中的优先级别(先算and再算or，xor)和取模运算（a%b=c中c的符号永远和a的符号相同）的事情
3. 注意列表法尽量保证第一遍就算对，对于不确定的复杂的推算的题目一定不能盲目找规律，尽量多推几遍，减少失误
4. 猜测题目的意思如最小生成树、dijkstra算法最短路、哈密顿路径（找一条路径使每个节点恰好出现一次）
5. 通过小样例模拟推大数据（找一些线性规律）
6. 递归题目细心算列树形图
7. 一些经典的问题：排序算法、约瑟夫问题（Jq(n+1) = ( Jq(n) + q ) / (n+1)）
8. 特征方程：

　　　　f(0)，f(1)已知 f(n)=c1*f(n-1)+c2*f(n-2) , 求出f(n)通项公式 

　　　　解出  x²-c1*x-c2 = 0 的解 x1 和 x2

　　　　若 x1=x2 那么 f(n)=(A+B*n)*x₁ⁿ

　　　　若 x1！=x2 那么 f(n)=A*x₁ⁿ+B*x₂ ⁿ

• 程序填空题（共28分）

目标得分：24

时间控制：30 min

1. 第1遍能填的填保证简单的填对
2. 第2遍根据算法思想推敲或者模拟计算规律或者根据数据结构做一定的操作
3. 关注初始化和条件语句（可以参考上下文），注意调用时参数的问题要仔细考虑
4. 分值特别标明的空格要格外当心
5. 第3遍一定一定要重新理清思路检查一遍

• 考场策略

1. 带（*）纯净水、餐巾纸、铅笔、橡皮、水笔、准考证
2. 提前半个小时一定要到达考场提早进入状态
3. 考试之前不要剧烈运动，最好做几道信心题或者复习错题
4. 减少答题时的干扰比如喝水、上厕所
5. 做好后一定要重点检查阅读程序和问题解决，尽量减少这里的失分

• NOIP2018 No regrets youth !
• NOIP2018 No regrets youth !
• NOIP2018 No regrets youth !

NOIP2018 No regrets youth

原文：https://www.cnblogs.com/ljc20020730/p/9762525.html