NOIp2018考前的一些总结和骚话,不用管它...

NOIp一些专题

模拟/搜索

把重要的信息在题目中标注或在草稿纸上写下来.

还没想清楚的时候就一定不要开始写代码,最后如果花的时间过长又没调出来要及时调整好心态.该放弃的时候就写好暴力放弃吧

Dp

状压 字符串 期望概率 背包 记搜 topsort 区间Dp??? 数位Dp??? 斜率优化??? 数据结构优化???

Dp一直以来是我比较弱的部分,但似乎近几年的题并没有出很难的Dp题.(flag)考试的时候如果一些题目完全没有头绪就可以往Dp方面想.

大胆设状态,一开始可以多设几维状态,然后不断优化.

对于一些比较难的Dp,状态转移方程要在草稿纸上写好,一定要考虑清楚Dp的边界!!!

状压Dp拿部分分很重要

树上问题

二分答案 倍增 LCA 差分 线段树合并

近几年的树上问题基本都放在了T3的位置,不过幸好都做的差不多了,发现考来考去也就那么几种考法.去年没考树上问题,奶一口今年会考

遇到树上问题如果实在想不出来,可以多猜猜找找性质,考虑贪心/二分答案.

如果想到大概的做法,但是没想清楚怎么维护的话,可以考虑差分/线段树合并等技巧

数学

找规律 解一元二次方程 组合数 扩欧 质数 线性筛??? 高斯消元??? 矩阵快速幂???

数学实在是弱啊,希望千万不要考去年Day1T1那种结论题了.

以前考过的数学方面的题并不是太难,实在不会就找规律猜结论吧...

数据结构

并查集 堆 树状数组 线段树 (平衡树) 分块???

NOIp范围内的数据结构也就那些比较基础的东西,而且一般来说数据结构题的部分分都比较多,比较好拿.如果不能够A掉的话就一定要把部分分拿满

码代码的时候一定要静下心来,不要求快,稳一点,否则查错会很痛苦,而且很容易造成心态爆炸

注意:线段树中查询千万不要Chkmin,Chkmax!!!!

图论

最短路 生成树 倍增 tarjan 缩点 dfs bfs

图论好像没怎么考过,考过的都比较基础.

考前把最短路,最小生成树,tarjan都复习好,奶一口今年会考tarjan

其他

贪心 二分 高精度 差分/前缀和 乱搞??? 三分??? bitset??? meet in middle???

这些就是一些常用骗分优化技巧吧

字符串???

Hash Kmp AC自动机

字符串从来没考过,今年会考吗?

猜测要考的话也应该能用Hash做(毕竟第一次考)

网络流???

二分图匹配 最大流 费用流

这个东西也没考过,不过二分图匹配考的可能性比较大.

把Dinic板子准备好,费用流不大可能考吧....

考试注意事项

考前

目标: 保400, 争取450+,反正做梦都上不了500的.

虽然说目标定的这么多,但真正考试的时候还是先把暴力写满,万一题目太难淦不出来又没写暴力就真完蛋

考前再看一遍Debug注意事项,一定不能犯低级错误.

考试

进考场马上做的几件事情:

  • xmodmap -e 'clear Lock' -e 'keycode 0x42 = Escape'

  • 调整控制台首选项:半透明、字体及大小(Ubuntu Mono 16)(暂定)

  • 配vimrc:

    11-6-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
autocmd BufNewFile *.cpp 0r ~/template.cpp
set fdm=indent
set autochdir
set autoread
set autoindent
set smartindent
set cindent

set ts=4
set sts=4
set sw=4

set nocompatible
set nobackup
set nowritebackup
set noswapfile

set mouse=a
set backspace=eol,indent,start
syntax on
set number
color slate

map <C-h> 7h
map <C-j> 7j
map <C-k> 7k
map <C-l> 7l
map <C-a> ggvG$

map <F9> :call Run()<CR>
map <C-F9> :call Run_O2()<CR>
map <F5> :call Debug()<CR>
map <C-F5> :call Debug_O2()<CR>
map <F12> :call Fp()<CR>

func! Run()
​	exec "wall"
​	exec "!g++ % -o %<"
​	exec "!time ./%<"
endfunc

func! Run_O2()
​	exec "wall"
​	exec "!g++ % -o %< -O2"
​	exec "!time ./%<"
endfunc

func! Debug()
​	exec "wall"
​	exec "!g++ % -o %< -Wall -Wextra -Wshadow -fsanitize=address -ftrapv"
​	exec "!time ./%<"
endfunc

func! Debug_O2()
​	exec "wall"
​	exec "!g++ % -o %< -O2 -Wall -Wextra -Wshadow -fsanitize=address -ftrapv"
​	exec "!time ./%<"
endfunc

func! Fp()
​	exec "40vsp %<.out"
​	exec "new %<.in"
endfunc

  • 写template缺省源:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    #include <bits/stdc++.h>

    #define x first
    #define y second
    #define y1 Y1
    #define y2 Y2
    #define mp make_pair
    #define pb push_back

    using namespace std;

    typedef long long LL;
    typedef pair<int, int> pii;

    template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
    template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }

    inline void proc_status()
    {
    	ifstream t ("/proc/self/status");
    	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) <<endl;
    }

    inline int read ()
    {
    	int sum = 0, fl = 1; char ch = getchar();
    	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
    	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
    	return sum * fl;
    }

    inline void Solve ()
    {
    }

    inline void Input ()
    {
    }

    int main()
    {
    	freopen(".in", "r", stdin);
    	freopen(".out", "w", stdout);
    	Input();
    	Solve();
    	return 0;
    }

  • 写好每道题的gen,check,静下心等待发题

拿到题目不要慌,一般来说NOIp题面都很长,静下心来读题,在题面里标注重点.

花30min把三道题都看完,大概口胡一下简单题/难题部分分的做法,按难度顺序开题.

想题/码代码的时候尽量不要收到其他人的影响,专注于自己的做题,不要去管其他人. 码代码的时候冷静一点,求稳而非求快.不要图快而定义非常多暂时性的,无实际意义的变量名(如tmp tmpp tmppp),这样会导致调试浪费大量时间

不管有没有发大样例,暴力能不能写,都要自己造gen,测极限数据.(自己多造一点强数据,想办法卡自己的程序)

用 -fsanitize=undefined/address 看看有没有爆 int 以及数组,看 /proc/self/status 有没有炸空间.

一定不能在一道题上花太多时间,哪怕是会做但是没调出来也要及时放弃,少点分总比爆零好!!!

考后

Day1不管考的怎么样,都不要影响到Day2的心态,毕竟有yyc去年的神奇翻盘经历摆在那里(可是我并没有那么强)

11.21 Update

发现西除了树上问题+二分答案奶中了之外,其他都没奶中啊,不过幸好考前搞了下树上问题,不然就凉了

而且居然一道傻逼Dp题没做出来

似乎这次考试花在检查+造数据+拍的时间上太多了,结果还有很多有可能拿到的分没有拿到.但是正因为如此,所有题目加起来才挂5分(数据实在是太水了...)

其他的问题放游记里写吧