应该是最后一次参加NOIP了吧，已经高二了时间和心思也不能安心得抽出来了。就认真总结一下这次的初赛卷吧。
初赛分析
试卷及答案资源
说个笑话：试卷底部印着NOIP 2016 提高初赛
题目分析
有些题目我自己错了，而且只有答案，并不知道正解，所以打个*区分
单项选择
坑爹题目= = 日常摸奖(1/2)系列
[NOI官网]的官网神奇公告 其实这道题原本在圈子里听说了，所以可以做出来的，但是日期就是这么迷迷糊糊地记错了
2020年 NOI系列赛 不支持Pascal
2022年 NOIP系列赛 不支持Pascal…
结果错选了2020年。怎么说呢？ 记得不准确 吧。
常识，没什么好说的
直接丢一篇我当时复习时认为最好的文章 [CSDN]计算机原码、反码、补码详解
空间单位换算 $ 1600 * 900 * 16 / (8 * 1024) = 2812.5$
*数学题 （听说今年初赛考的数学题特别多？）
赛后分析：2016年10月1日是周六，2012年10月1日是星期一…然后发现 $ 365 \bmod{ 7 } = 1$ 。感觉不对劲？作了一张表
日期 星期真实 星期考试时猜测 2017.10.1 日 日 2016.10.1 六 六 2015.10.1 四 六 2014.10.1 三 六 2013.10.1 二 六 2012.10.1 一 五 2011.10.1 六 五 … … … 1950.10.1 日 三 1949.10.1 六 三 1948.10.4 五 三 这也差太远了吧！其实貌似推算星期也不只是隔4年变一天这么简单的
一开始发现 [CSDN]计算任何一天是星期几的几种算法 有一个 Zeller公式 可以使用，但是估计是记不住。
然后又找到了 [博客园]日历查询的算法 如何计算某一天是星期几 中详细的推导过程。
最朴素的计算方法是计算 $ 中间间隔的总天数 \bmod 7$ 。中间要注意2000年是闰年，还可以把1949年12月31日和2017年12月31日作为2个原点。然后
$ (2017-1949 = 68) * 365 + 17 = 24837 \bmod 7 = 1 $
写了段程序暴力验证结果也是 24837 天
然而还不是很确定这样解对不对，不过至少答案看起来是对的
图论+数学 基础题
树的基本性质：总边数 = 结点数 - 1
由此可以推得： $ m - k = n - 1 $ 解得 $ k = m - n + 1 $
*求时间复杂度 与NOIP2013初赛15题相类似。
正解都可以用 [网易博客]主项定理 Master Method 来求解，估计也是求时间复杂的的正解。我是还没怎么看懂，猜主要思想应该是把时间复杂度建立为一个 $ T(n) = a * T(n / b) + f(n) $ 的模型，然后比较 $ f(n) $ 与 $ n^{\log_b a} $ 两者的变化幅度（也就是数量级），取其中较大的那一个。
这题解也不是很确定，猜可能带入特殊值是这样观察的：
$ T(1) = 1 $
$ T(2) = 2T(1) + 2 \log 2 = 2+2 \log 2 $
$ T(3) = 2T(1) + 3 \log 3 = 2+3 \log 3 $
$ T(4) = 2T(2) + 4 \log 4 = 4 + 4 \log 2 + 2 \log 2 $
$ = 4 + 3(\log4) \approx n\log n $ ???
$ T(5) = 2T(2) + 5 \log 5 = 4 + 4 \log 2 + 5 \log 5 $
好吧， 复盘带入计算也不知道 怎么能得出C解。
不过总结了下主项定理，应该是判断出 $ f(n) = n \log n =n^{\log_22} $ 即 数量级相当 ，然后得出时间复杂度在 $ f(n) $ 的基础上乘以 $ \log n $ 得出 $ O(n \log^2 n) $ 的。
常识，模拟栈操作
*目测是图论+“极简单”的排列组合
先明确一下定义：简单无向连通图
连通：指任意2个点有路径相连[1]
无向：任意一条连接u、v的边都表示u连v和v连u[1:1]
简单图：不存在平行边和自环的图[2]
所以说我的思路是找那些可以90°旋转4次而各不相同的种类数，再寻找只能180°旋转和不能旋转的种类数。但是貌似 漏了2条对角线加一条边 的这种情况，而且遗漏了其它能旋转的图形。 可能是 枚举的方法 不对（我是按加边枚举的，不知道有没有更好的方法）
隔板法！这玩意在考试之前还仔细研究过，是一个好东西。[百度百科]隔板法
就是 $ C^{空隔数}_{要插入的隔板数} $ 在本题中则为 $ C^9_3 $ 再牢记 $ C^n_m = m! / (n!(m-n)!) $ 轻松解决
*据说正解是递推公式求通项公式，（感觉用微积分可以做，然而没学），我是手工暴力到 $ 21/32 $ 或者多少分之64然后找规律做的。
*估计应该是 题目意思弄错了 。题目给的2个数组是 有序数组 ，而 [百度]归并排序-复杂度 中所得出的时间复杂度应该是指数组无序的情况。有序的最坏情况可能是：
设 $ n=5 $
1-1;1-2;2-2;2-3;3-3;3-4;4-4;4-5;5-5
共 $ 2n-1=9 $ 种这个意思，而不是无序数组的从头归并。
经典数学题
A与B比较，若相等，则假币必在C，否则假币在A。最后统计n数量确认是否继续搜索
经典dp [Luogu]P1216 [USACO1.5]数字三角形 Number Triangles & IOI94 数字三角形
印象特别深，因为据说是OI界第一道dp的题目。思路很简单，从左和从右路径中取一个较大路径继续走即可。 注意！此处由于所求的是路径上的数之和，与种数等无关，因此不可作死+1
*数学 计算概率，至今不会计算
数学 水题 $ 1 / 20 * 360 = 18 $ 几何概型
不定项选择
- 对归并排序的还不是很熟悉，这张卷子又考了很多次归并，所以漏选了
- 栈模拟
- 这道题我备考时找到了这篇文章，挺不错的[cnblog]稳定排序和不稳定排序
- 常识
- 摸奖日常蹦(2/2) 王选奖貌似是CCF承办的一个奖项
问题求解
- 这道题在挑战程序设计竞赛上有类似的题型[3] ，貌似是用数学方法做的
- 暴力求解的，最小方案数漏了一种？
阅读程序写结果
暴力递归，把整棵树都画下来即可
看不出有什么规律
和拓扑排序有关的题目，应该是考你会不会拓扑的实现一类的
非常巧妙的几何题，从给定坐标出发不断以斜率为1或-1反弹，直到4角终止
完成程序
好吧，大整数除法一开始没看到题目中有%的操作，所以说做得非常迷茫，最后答案也没对几个。
最长路径，感觉在哪里想过
个人总结
虽说是复盘，但是再看一遍还是好多题目不会。看来还是太水了。
感觉最后一个星期狂刷往届试卷非常非常有用。
20171020
成绩终于还是出来了，13.5+4.5+2+10+7=37。嗯，怎么说呢，果然还是太菜了呢，需要更加努力。
P150 3.2.2 — 挑战程序设计竞赛 第二版·人民邮电出版社·【日】秋叶拓哉 岩田阳一 北川宜稔·ISBN 978-7-115-32010-0 ↩︎
