noip2016考前总结

小雨点点789

　　之前的代码和题解都是发在http://blog.sina.com.cn/u/5753494554，但是新浪麻麻的胃口太大把代码吞得面目全非，给发代码和过后的复习都造成了极大的麻烦，所以说当时开开博客的时候太冲动后来又太懒...悔不当初//之后会把那边比较有意义的文章粘过来，也是作为复习
　　前段时间的考试成绩不太好，一直都比较低沉...然后昨天放松了一下，结果一松就到现在都还没缓回来...exciting
　　所以今天趁没有心情写代码把知识点和平时写题以及最近三周的考试得到的经验和注意事项写一写。
　　csdn上有一篇很棒的总结考纲的博客感觉还是很靠谱http://blog.csdn.net/txl199106/article/details/49076113

　　所以从这个图上面看，绝大部分的算法是初中就学过了的...以及暴力出奇迹
　　主要知识点
　　模拟
　　高精（ex：国王游戏，矩阵取数游戏）
　　二分
　　贪心
　　//常常用于辅助，ex：二分+贪心，二分+前缀和，贪心+dp,etc.
　　图论
　　最小生成树及其变形应用（dp，次小生成树）
　　最短路算法及其变形应用（常常将问题建图->spfa）
　　差分约束（？）
　　拓扑序
　　dfs序
　　dp+优化
　　环形（能量项链）
　　树形（加分二叉树）
　　背包和背包分治（eden）
　　前缀和优化
　　单调队列优化
　　堆优化
　　滚动数组优化
　　两个数组互相更新（ex：substring）
　　//斜率优化我真的不知道考不考我真的不会...
　　搜索+优化
　　剪枝（mayan游戏）
　　  迭代加深
　　双向BFS（ex：华容道？还没写）
　　基础数论
　　快速幂快速乘
　　筛素数
　　gcd
　　 exgcd（同余方程）
　　容斥
　　数学杂题（解方程->秦九昭算法，hankson，到现在都是骗的）
　　 排列组合
　　//我的数学知识果然都是骗人的TAT
　　字符串
　　kmp（？）（next数组的思想）
　　  hash
　　栈和队列（双栈排序）
　　线段树和树状数组
　　st表与树上倍增
　　stl的set和map（开车旅行）
　　以及可能出现在最后一个的：状压dp，连通性dp（而且这三者都时属于几乎不可能的...），树链剖分（与树上倍增一起成为两种解法，很有可能考），点分治，tarjan
　　以及一些辅助性的算法和知识点：并查集，置换，逆序对，进制转化，etc，不一一罗列
　　然后上面大概标了一下我完全不会的和不太熟练的
　　wow exciting
　　//所以也不是看起来那么稳...
　　之后应该会把刷过的noip的题都写一遍题解作为复习
　　考试策略：
　　1.考试开始前，调界面，写模板，写头文件，测试dev是否可用
　　2.看题目时注意数据范围，时限，仔细，不要猜测出题目没有说明的affairs
　　3.关于数据范围..
　　   20：O(2^n)，搜索
　　100：O(n^3)，Floyed/搜索
　　1000：O(n^2)，动态规划/spfa/最小生成树
　　500000：O(nlogn)，二分答案/快排/线段树/st表/树链剖分/遍历（DFS可能爆栈）
　　1000000：O(n)或O(1)，数学问题/改变思维方向/贪心/kmp/dp
　　当然只是一般情况下...
　　4.long long一定注意在传递参数和快速幂中不要开漏了...
　　5.以及最近经常把头文件写错（忘记写iostream，忘记写stdio.h之类的...）
　　6.写代码前想好，能够证明最好证明，否则多出几组特殊数据测试
　　7.想好需要的每一个函数再开始写，并估算好时间空间复杂度
　　8.永远不要尝试不熟悉的算法orz...
　　9.一定要写对拍...
　　注意datamake里面出现不合法的情况（构造树？）



//头文件
#include<time.h>
int main()
{
     srand(time(NULL));      
}
　　对拍代码不知道linux可不可以用，明天去问问（?）现在暂时是这样的



//头文件
#include<windows.h>
int main()
{
     int t=100;
     while(t--)
     {
         system("data > 1.in");
         system("zj < 1.in > zj.out");
         system("dp < 1.in > dp.out");
         if(system("fc zj.in dp.out")
          break;
     }
}
　　问了zmc学姐学姐说linux系统不可以这样写...windows之类的头文件不能编译，虽然也是意料之中...
　　linux版这样写：



#include <cstdlib>
int main()
{
    int t = 100;
    while(t--)
    {
     system("./data > 1.in");
     system("./zj <1.in> zj.out");
     system("./dp <1.in> dp.out");
     if(system("diff zj.out dp.out"))
      break;
   }
}
　　刚刚看到了考试环境通知，系统还是window7，配noi linux的虚拟机，所以还是可以用上面的上面的对拍，最后到虚拟机上跑一跑就好...
　　所以后面写了写虚拟机的用法（不会用的我
　　10.千万不要在最后15分钟改代码必错无疑百发百中
　　11.绝对不要对答案被虐无疑
　　12.写完一题检查一题，不要赶时间去做T3，保证前两题的正确性，T3除非是遇到了会写的算法，不要思考超过15分钟，直接写骗分
　　13.写完之后再留45min再检查，数据测试，阅读代码，查看细节
　　14.查看文件名，有没有把暴力程序交城正解
　　15.前两题想不出来调不出来不要慌张，根据时间和难度判断好是否继续写继续调，或者先写第三题，，决定之后不要犹豫，不要患得患失
　　16.避免day1认真day2水
　　17.检查时，对于学过的知识再过一遍，看看有没有漏掉简单的算法或者小的优化
　　18.输入换行符的处理
　　19.lld
　　20.DFS函数记得写return
　　21.变量名如time屡错不爽...
　　22.把memset，memcpy写在for或者dfs里面忘记算复杂度....
　　23.cout，cin输出不是必须（bignum）不要用，有TLE的风险
　　这里是虚拟机用法
　　1.虚拟机软件 VMware Workstation
　　2.点开之后长这样：

　　点那个红色的框框= =

　　密码是123456
　　在主界面的上方找到状态栏，在左上方找到位置按钮，点开下拉菜单

在下拉菜单中找到主文件夹选项并单击进入，打开主文件夹，里面“noip”文件夹和windows下的noip文件夹是共享的，打开来用guide编译就好

　　有遗漏的话之后再写喽
　　大概就是这样（摊手