2020CSP全国信息学联赛 游记

  时间:2020-11-08 10:11:20  阅读量:254  评论数:0  作者:2020linweitong

程序员早期的人生规划很重要,因为技术是靠点滴积累的,2020CSP全国信息学联赛 游记,小编作为门外汉看了也觉得获益良多,做这类工作的可以参考看看这种美文。

2020CSP全国信息学联赛 游记

Day -4

中午打了树的直径,做了复习,下午回来看了一下例题。
晚上估计是复习 l c a lca lca等树上算法。

Day -3

中午机子坏了。
晚上没来。

Day -2

期中考试,发挥失常,数学没有AK,大概116。
中午没来,晚上来了。
不知道干啥——做USACO。
感觉要挂科。

Day -1

期中考试。英语贼简单。
其它感觉还行。
然后什么时候都没来。
期中考试感觉总体还可以

Day 0

早上在讲试卷。
不难,语文考得不错???
怎么可能???
感觉很累,看三体看疯了。
然后中午没来,下午打了球。
就感觉心情不佳。
晚上没上晚修,早写完作业就来了,被老师叫了一下(还好)。来写会游记,看看资料。
好怕呀!
注意事项(由于本人是蒟蒻,所以不会高深算法):

  1. 不要着急。
  2. 背包问题:01是倒,完全是正。
  3. 要多多对拍。
  4. 注意时间。入门组要抓紧时间,最好每道题都想到正确方法;提高组也尽力而为。
  5. 小心粗心等问题,最后想好再写代码。
  6. 不要想任何与考试无关事情。
  7. 背包问题输出方案,记录直接更新。
  8. 总方案数用01/完全。一样方法。
  9. 区间 d p dp dp注意好循环顺序。
  10. D A G DAG DAG上的 d p dp dp没打过,但是也不难,按正常 D A G DAG DAG求法再 d p dp dp
  11. 树形 d p dp dp d f s dfs dfs或者是 d f s dfs dfs序。
  12. 换根 d p dp dp要思考一下,其实不难。
  13. 状压 d p dp dp要注意状态。
  14. 单调队列优化要思考。
  15. 哈希表的 m o d mod mod要定为质数,如果很容易重复,就用双哈希或者三哈希。
  16. 并查集要压缩路径。
  17. 可以用启发式合并提升速度。
  18. 堆打的时候要多在草稿纸上模拟。主要是这些数据结构不常用。
  19. 解决区间静态的可重复贡献问题是用 S T ST ST表,思想是倍增。
  20. 树状数组记得如果 d e f i n e define define时就要将 l o w b i t lowbit lowbit里面的运算打上括号,或者直接写函数。 l o w b i t ( x ) = x & ( − x ) lowbit(x)=x\&(-x) lowbit(x)=x&(x)
  21. 线段树要掌握其精髓,不要盲打。记得要开4倍空间。
  22. 链式前向星:最好不要用 s t r u c t struct struct,记得无向图或树要开而被空间。
  23. 记得 2 n 2n 2n n < < 1 n<<1 n<<1
  24. 树的直径用两遍 d f s dfs dfs可以做完。
  25. 树的最近公共祖先要用倍增做,如果忘了就思考一下 d f s dfs dfs序的 R M Q RMQ RMQ问题,尽量 不要用 t a r j a n tarjan tarjan,我也不会。
  26. 以树的重心为根,所有子树的大小小于等于整棵树大小的一半。
  27. 拓扑排序记得将访问的点标记。
  28. 最小生成树尽量用 k r u s k a l kruskal kruskal不要用 p r i m prim prim
  29. 最短路 s p f a spfa spfa不行就打 d i j k s t r a dijkstra dijkstra的堆优化。
  30. 强连通分量 t a r j a n tarjan tarjan不要打错。
  31. 网络流本质:找增广路。
  32. 要多思维发展。
  33. 多想一想高奆给我们讲的故事。
  34. 不会一定打暴力。
  35. 对拍尽量10组+。

Day 1(正式比赛日)

Before CSP-J

在本校。
很早就起了,被同学吵醒了。
打铃之前就醒了。
继续追三体。。。
然后7:00去拿身份证然后没吃早餐。
等会去吧。
感觉这天有点奇怪。。。secret

CSP-J

感觉要凉凉。。。
第一题很水,直接一个二进制搞一搞,好像9:00做完了并对拍了。
第二题想了三种方法:每个区间排序、插入排序、桶。还是打了桶,时间复杂度 O ( 600 n ) O(600n) O(600n)。感觉可以过。正解是对顶堆???没学过。
第三题比较难,首先打了暴力,然后就想到了用后缀树,建了后缀树之后就开始想了一个树上修改的方法,好像要树剖优化,然而我不会,一直做到10点左右。正解是预处理出是否对结果影响,然后可以的就做一些事情。
第四题没有时间,想了一种 d p dp dp再重复四次,结果挂了,然后就打了 d f s dfs dfs,结果没时间打记忆化。。。
估分:100+100+50+20=270。
可能没有一等。。。自闭了

Before CSP-S

来了机房写了总结。
下午感觉要凉凉。。。
希望最难的数据结构是平衡树。

CSP-S

在上午的教室的旁边,旁边一堆高中的。
然后发了下来题目。

14:30-15:00

看题时间,其中第二题有点没看懂,最后还是懂了。

15:00-15:20

第一题不难,但是细节很多,不想推数学公式,所以打了一个暴力。

15:20-16:00

调了很久,第二个样例死活过不去。
很慌,检查了很久,最后发现把4713写成4173。
暴力总算过了。

16:00-16:30

打第二题。
从20分打到40分,结果后面想到了乘法原理。
然后就应该可以满分了,大样例过了。
时间复杂度是 O ( n k ) O(nk) O(nk)
应该行,但是好像要开unsigned long long。
而且还要特判 n = m = 0 , k = 64 n=m=0,k=64 n=m=0,k=64的情况,只能打表。

16:30-17:00

暴力解决第三题。
直接一个 d f s dfs dfs
不想打了。
后来发现可以优化。

17:00-18:00

第一题打了一个常数为 1 365 \frac{1}{365} 3651的方法。
然后没有注意到某一年的10月,我挂了,从50到40。
然后想用二分,但是不会。

18:00-18:30

检查了无数遍。

After CSP-S

感觉要凉凉,luogu自测提高组150,oi题库自测普及组265。
普及T4直降15分,原因到底是什么。
提高组T2还真的毒瘤,出了三个大于long long的数据,还有一个是 2 64 2^{64} 264,选择打表。
然后自闭了。
然后拿完东西回家了。

Day 1.9

听zhy奆他普及300+,提高200+。
晚上很晚了,提高组T3感觉很水,一个类似线段树的方法想了出来。
太水了还是。
终究还是没有发挥好。
普及T4,类似我的 d p dp dp方法,用 0 / 1 0/1 0/1存状态。
提高T1,数学题,但是不想打。
提高T3,直接一个线段树?
提高T4,堆/平衡树?

Day 2

自闭中。
在写作业。
今天又要回校了。
明年加油!

关键词:全国,信息,信息学,联赛,游记


程序人生周排行榜

    程序人生月排行榜