NOIP 2022 考前学习日记

发布时间 2023-10-31 13:32:05作者: 静观默察

前言

学习记录本写太乱了,所以在这里打个草稿

顺便记录一下学习过程,后面总结的时候康康有没有问题


11月2日(今日运势:中平)

上午:

再次做了一下CSP-S 2022的题,除了T4以外的都订正完了

听yjy讲了一下 kruskal重构树,还没做练习

下午:

看线性代数看的想睡觉;

尝试做了一下【模板】矩阵快速幂,挂了

做了道区间DP的题,然后下午就结束了?!(时间过的真tm快

晚上:

又水了道区间DP~

开小号在灌水区回答问题

双水了道区间DP~

被区间DP切了...(40分)


11月3日(今日运势:中吉)

上午:

模拟考试,T1不会;T2没打完(只考了2h就去上体育课了...);T3自信AC自动机,结果爆 $ 0 $ 了?话说那道题的输出格式要求好严。 不过为啥每次考试做字符串的题本地没问题,交上去就爆 $ 0 $......;T4没看清时限,以为是 $ 1 $ s (其实是 $ 7 $ s),然后就把题想复杂了(讲真,我搜索真的不好,如果看到是 $ 7 $ s 的时限我也不一定写得出来)

总的来说,一句话,爆掉了

下午:

本来是想补救一下T3的(难得遇到AC自动机),但试题来源只写了cxm,于是去baidu了一下,不知不觉就逛起了百度贴吧(从cxm到lyd再到kkk(看 "《CCF中学生计算机程序设计》错误集合" 看了将近0.5h......)最后到CCF)

终于把这道题切回去了,到底还是int的锅,记录一下:

(__int128)(1 << N)//这样写如果 (1 << N) 的值超过了int范围会炸
((__int128)1 << N)//这样写就没问题了

听czx讲了一下上午考试的T1(应该是数论),他讲的很努力、很认真,可惜我数论没怎么学,听不懂

晚上:

看了看 tiger2005 在知乎上的一个回答,然后感慨了半天,再emo了半天,半个晚自习就结束了。

lzz临时让我们做了一道入门题,正好拿来试试模拟退火

写不出P4170的暴力搜索,也写不出它的DP解法

讲真,今晚好划......


11月4日(今日运势:中吉)

上午:

报复性的把P4170写完了(可惜看了题解)

更新了下系统(主要是它一直叫我更新)

划了一下射线排序,然而并没有AC,但是至少不想睡觉了

实在是困,所以睡了半个小时(然后上午就结束了)

吃午饭前用错误算法(用玩2048几周的经验想出来的)+特判A了这道题还拿了榜一......真意外, 下午再来写正解了

下午:

用正解A了这道题,(虽然说看了题解(感觉每次差那么亿点点就想出来了)并且中途还因为数组开反了WA了好几次)

意外的事情 : sjs祭天,三发A了射线排序

P4302没写完,但写了个预处理交上去就有60分,感觉学到了骗分的新知识

晚上:

终于把写完啦!一步步地靠近正解,感觉这才是做题的正常过程,可惜这种感觉很少

半懵半懂的情况下推出了DP式子,然后就把这道题A了。怎么说呢,感觉对区间DP产生了一些感悟。(

感觉这道题简单处理一下就变成刚刚那道题了,但是没时间了,明天再来写 ,TNND明天好像还要讲可持久化线段树 + 考试,尽可能快的写完吧(也不知道明天状态怎么样


11月5日(今日运势:大凶)

上午:

模拟考试,光速写完T1&T2(签到题)后,果断放弃T3&T4(都不会);

悄悄做了道区间DP,还意外的拿到了最优解(虽然中途因为复制状态转移方程时忘记将 $ 1 $ 改成 $ 0 $ 使得 $ 100 $ -> $ 82 $(话说这数据是不是有点水))

下午:

上网课,听上午模拟考试的四道题的解法

T1好像可以用递归(但我用的是栈);T2打的是正解(线段树);T3听了一下,是组合数学,矩阵DP(可惜我都不会);T4好像乱搞就行了;

总的来说,一句话,爆掉了一半

晚上:

回家哩


11月6日(今日运势:小吉)

上午:

下午:

回学校哩

晚上:

尝试了第一场Codeforces上的模拟赛,20min做完T1&T2,然后想了1h37min的T3&T4(真想不出来),最后3min写完了这段话

实在忍不住看了一下T3题解,竟然考的是位运算(看到算法标签的时候人傻了)。

听完lzh讲T4后,发现自己又犯了老问题(想出正解后搞个错误的样例把正解Hack了),难受

又打了一场今晚Codeforces上的比赛


11月7日(今日运势:凶)

上午:

补了下昨晚的T3

欸,怎么这么多水啊

下午:

写了道树上DP(但我总觉得是区间DP)的题

又写了道树上DP的题,嗯,这很树上DP(只是不知道如果随机跳题跳到这题能不能做出来)

体育课回来最后写了道树上DP的题,可惜在疯狂小优化后与榜一还是差1ms

说实话感觉这几道树上DP都很显然(有点慌)

晚上:

写了道树上DP(咋感觉我写的像暴力)的题

题外话:今天大吉(CSP 145 -> 201)

写了半天P3698都没写出来,得明天来了 ,或许是因为今天满负荷了?(雾(逃


11月8日(今日运势:中平)

上午:

随便写写这道题就过了?自己对F的定义和F的实际值几乎完全不符竟然也行......(或许是我定义错了,但它转移对了)

P4342写挂了一上午,最后发现是输入的问题...记录一下:

如果要输入如:"t -7 t 4 x 2 x 5"的数据
尽可能这样写以防止出错:
  scanf("%s%d",s,&n);
  if(s[0]......)
  ......

下午:

好吧,虽然想出来了CF149D的一种解法,但是比较麻烦,最后还是看了题解(果然之前做的都是很简单的DP)

晚上:

UVA12991没写出来

Thoth布置的DP练习都不会的样子

Codeforces上打了一场模拟赛,又是只做出T1&T2


11月9日(今日运势:中平)

上午:

NND,终于把写完了,小错误一大堆

补了一下昨晚的C1

10min又做完了这道DP题,有点蒙了,感觉DP好神奇啊

下午:

写了几乎一个下午的P3354,自己的做法调来调去最高只有52分(感觉自己的是假DP),最后还是看了题解才写出来

晚上:

轻轻松松打完P3554,虽然说要树形DP,但我觉得二分答案+搜索中没用到树形DP(也许是我对它有什么误解?)

P1272收尾,感觉树形DP+背包问题很常见,至少最近做的树形DP题目中经常出现,应该是个常见的组合吧(练习DP的同时还能练习背包,针不戳~)


11月10日(今日运势:中平)

上午:

看着题解把P3177写完了,但是对其中的一些细节还是不太理解,下午再来了(done)

下午:

貌似什么都没干?

晚上:

Codeforces上打了一场模拟赛,这次多做了个T3,但是由于我把T5想的太简单了,加上把T3想的太麻烦了,于是一直在做T5,结果不仅没做出来还浪费了48min

P5911由于数组开小失50分(数据顶水的,本来要开2^16结果只开了20还有50分),还调了许久

欸,仿佛置身海底

明天不能再这样了


11月11日(今日运势:凶)

上午:

做了道状压DP,记忆化搜索里没有用记忆化挂了16分(竟然才16分)

考试,T1暴力,T2假线段树,T3不会,T4 rand()。感觉最近几次考试要不就是好难要不就是看上去简单但就是不会做

抽空又做了道状压DP

下午:

又是看了题解才把P1896写出来,位运算好用是好用,就是有亿点点难想

晚上:

P1879,没啥好说的,P1896的另一个版本

P3694,刚开始看题的时候连怎么排都不知道,然后看了题解,明白暴力怎么打后才写出来

P2704状态烤CL少了,明天来了


11月12日(今日运势:凶)

上午:

P2704写完了

A了这道题,和P3694顶像的

下午:

重新做了一下P3809,打算做点 Suffix array 的练习

想多了,写不出来

我太菜了,月赛只打了25分,下午还一题没A

晚上:

打了一把Codeforces上的比赛,做出了T1&T2&T3,终于比之前好点了


11月13日(今日运势:中平)

上午:

签到100天祭

欸,怎么这么多水啊

下午:

P4407,写 Trie + DFS 死活调不出来,于是决定写 Hash (虽然不是正解,但是开O2能卡过去)

P4407的Hash调了一下午,map超时,优化后又TLEWA,于是改二分 + 优化,又TLEWA,于是改二分 + 暴力,过了?(众所周知,for循环循环20次比加减3次更快)

(2022.11.24:今天考试的时候又想到了Hash判相等,突然明白P4407的优化为啥错了,模了又除)

晚上:

听学长讲数学,听不懂


11月14日(今日运势:大凶)

上午:

写了道DFS的简单题第二了(这段时间写的代码效率都好低)

看数学,学数学,做数学, 做不出数学

中午没睡觉,强行注册了个超理论坛的账号

下午:

啊好困好困,没干啥,一直在逛超理论坛

晚上:

超理论坛

做了道数学题(看题解的qwq)


11月15日(今日运势:中平)

上午:

模拟考试,T1写挂了,T2不会,T3不会(但好像大家都A了),T4KMP写挂了

下午:

尝试补上午的题,虽然T1没写出来,但至少知道自己树上倍增求最值哪里想错了(方法可用)

P5018,树上Hash不会写,于是用回文的写法水过去了(加了点优化,manacher打起来有点麻烦所以没打)

晚上:

学习单调队列+做单调队列的模板

上午考试的T2写完了,不过我的代码不开O2过不了,可能是用deque的原因吧(雾,比赛时还是手写队列好了

到底还是要写学习记录本,我直接开抄

kruskal重构树还没尝试过!还好抄了一下学习日记,不然都快忘记了


11月16日(今日运势:大凶)

上午:

看数学,昨天考试的题明天再补了

做完了P2158

做完了P2568

下午:

做完了P2398但是为啥我代码比别人长了一倍, 原来还有别的方法啊,一下子看不懂,溜了溜了~

双倍经验

由于某些地方没写好,所以7倍经验变双倍了QWQ(正在修改中ing...)

一下子想不明白了,冷静一下好了(去cf了)

晚上:

半蒙半懂地写完了UVA11424&SP3871

感觉自己理解到了,于是自己推了一下&A了UVA11426(虽然和UVA11424的过程相同,但至少自己尝试推了一遍吧)

PS:还好今晚没讲数学,不然估计又是罚坐一晚上(晚上状态好像不太好)


11月17日(今日运势:小吉)

上午:

模拟考试,学数学直接旷掉qwq

学数学

下午:

模拟考,考炸了

晚上:

听数学,尽力了,但还是半懂不懂的样子,预习也没预习完


11月18日(今日运势:大吉)

上午:

学数学,补题的事后面再说吧...

woc怎么今天这么想睡觉......

勉强做了AcWing 202

下午:

P4139

晚上:

P2613

P1082

戒florr的第一天,原因:我要好好学习 放屁啦,其实就是摸鱼被抓,不想被抓第二次而已


11月19日(今日运势:大吉)

上午:

P3951

P1516,自己推出了式子,但是一堆小细节没处理好

下午:

学数学

咕咕咕~

晚上:

回家哩


11月20日(今日运势:凶)

上午:

下午:

回学校哩

晚上:

学数学

在题解的帮助下做完了P5656,感觉自己对ExGcd的理解更深了吗?

开始思考P4180


11月21日(今日运势:中平)

上午:

今天才想到可以在用prim求最小生成树的同时把结点的深度和父结点求出来

写完了P4180,解法是对的,但是细节又错了一大堆 ,但是prim真好用

下午:

终于做完了P4777,出现了许多奇奇怪怪的问题

晚上:

靠题解建模做完了P1852,自己除了建模以外的都想出来了,可惜建模没想出来一切都白想,话说这建模真是人能想出来的吗?要不就是我不是人要不就是出题人不是人qwq

开始思考P1712


11月22日(今日运势:中平)(全局/kk)

上午:

模拟考试,A了T1,T2忘记初始化被卡掉了,T3&T4不会

下午:

写完了P1712,不仅自己没想出来,写的时候线段树大小还开小了

晚上:

发现自己不会证明T1贪心的正确性,于是和dl讨论了一下贪心的证明方法,于是想不出来求助了一下万能的谷民,于是没完成Thoth布置的两道练习

敲了一下P6584的暴力贪心搜索法,喜提55分,T了5个点


11月23日(今日运势:凶)

上午:

补完了P6584

睡觉

中午没睡觉,在机房写CF786B的自己想到的正解(自己想到的线段树建边,其实是假的,只起到了去重边的作用),结果不仅没AC,还比纯暴力更劣(空间&时间)

下午:

看了一下题解,写完了CF786B,感觉自己思维变拉了

晚上:

写完了P1505,感觉自己的编码能力得到了提升(雾


11月24日(今日运势:中吉)

上午:

模拟考试,T1二分+最短路不知道为啥挂了95分;T2纯暴力;T3KMP+Manacher+二分,二分的复杂度多了一个N,但是过了(CF上被卡了,但是优化一下也过了);T4几何,不会;

下午:

仿佛置身海底~

晚上:

看博客


大概就这样了吧,后面的内容就写到游记里好了