省选集训日记

Author Avatar
WildRage 3月 19, 2018
  • 在其它设备中阅读本文章

2018-3-19 多云

第一天写日记
昨天打了一场UR今天把题改了一下。
又做了一下放假前的那场考试题,还没有做完,还要找时间补。
今天一天下来打的题都不简单,刚放假回来状态也不是很好,主要是比较困。
中午起来想了很多,想到去年的我这时在干什么,不知不觉都过去一年了。
好怀念那时轻松的日子。
但现在还是要面对啊,先过了省选再说,无论结果如何,也都会确定了。

2018-3-20 ~ 21

生活就是改题吧。。
一连考了两天, 题还都没有改完
都是神题。
D1T1贪心, D1T2 是一道2-SAT + Trie, D1T3 是一个DP
D2T1计算几何的DP, D2T2 是一个平横树维护的模拟, D2T3是一个多项式算法。
博客还是要尽力更新的吧。

2018-3-22

终于把题给改完了
D2T3,D1T3真是不好改。
晚上打了一道题,还没打完,一道CRT合并的组合数的题目
组合数模非质数: 将模数分解质因子,对于每一个$P ^ k$都算出$\%$他意义下的答案, 然后用CRT合并, 对阶乘搞一下拆成$a*p^b$ 以为$a$与$p^k$互质所以可以求逆元了。
然后听ryf分享一道题UOJ76懒癌, 看到题面感觉很熟悉啊。 解法也是非常的强大, 将搜索转化为图论。

2018-3-23

又是考试的一天
第三题有点熟悉, 这道题的处理方法和昨天那道题好像一样啊。
然后就打了, 结果还是没A, 有一个地方没开long long在计算过程中炸掉了。
前两题都是神题, 第二题是一道看不出来是杜教筛的杜教筛, 用的容斥系数$\mu$ 然后推一下式子。
第一题又是一道记忆化搜索DP

2018-3-24

今天没考试,那就去刷题吧。
简单的做了一下数学专题
学了一下高斯约当消元法。 又打了一道$LCT$的题目
补了一点博客。
计划再看看概率期望相关的题目

2018-3-25

考试考试考试
第一道题是一道比较简单的网络流, 可以先二分然后跑类似于文理分科的最小割
第二题是一道三维的几何题, 考试的时候没敢写, 主要是没想到用单位向量的倍数来列方程, 然后就用一些高考数学的知识就能解决了
第三题是一道$DP$对小质数状压,大质数枚举,可以跑过纯状压跑不过的测试点
然后就没了

2018-3-26

考试考试考试
第一题看起来是一道莫比乌斯反演? 推了推没推出式子,先打个部分分再说吧。
然后看第二题,暴搜有分? 等等, 我好想会$n^3$的做法, 码码码, 打完调过样例, 好让我打个对拍, $n = 3$一拍就出错,额,调调调,调过了我的小数据,再一测样例,(⊙o⊙)… 又不对了,啊啊啊。 我这个好像不对??? 不要啊,然后还是弃疗了2333
弃疗后看第三题,好像不难啊,等等,这不是半平面交裸题么,十几分钟就打完了,结果死活不出样例,什么鬼啊? 我半平面交没错啊。 考试结束也没改出来, 最后发现代码里这样一句const int eps = 1e-8成功把我炸死。 改了就过了。
第一题的正解是一个优化了的暴力, 根据调和级数得复杂度为$n^2log(n)$还卡常。
第二题是一个看起来很简单的$DP$,不知道是因为想的太难还是真的很难没做出来。
明天还考试。。

2018-3-27

一天两试真爽啊
上午考了一场,第一题先把暴力打了,然后看第二题,咦,这不是原题么? 好像连样例都一样的啊。 码码码, 打完之后简单拍了一下感觉没问题了去做第三题,第一眼二分图,感觉不对,在一眼好想可以用网络流,先建了个最大费用最大流,发现不对,然后想是不是可以最小割啊。画了画图,然后发现这图好想有点熟悉啊,等等, 我是不是做过一道和这个一样的题啊, 然后就开打了, 没对拍, 眼动查了几发错, 好想没什么问题。
最后得分和我的估分一致,没有什么问题。
考完之后, 于老师说, 下午再考一场, 我心里一惊,我的天还考啊。啊啊啊。
下午起来之后有点困,一点四十七到了机房,坐着犯困,本来说好的两点考试, 然后老师看我们没什么事干, 就直接开考了
上来先浏览一下题面,发现暴力分给很多,这种类型题做起来也挺舒服。 看完题面, 周围一片键盘声, 心里有点慌, 他们不会都要$A$题了吧
不,我要冷静一下,我想的和他们应该也差不多,那,先让我上个厕所冷静一下。
回来之后发现,三道题好想都可以拿到不少的分数啊, 然后剩下的时间就用在码题上了。
第一题是一道分类讨论, 看起来不是很好搞。
第二题前$30$分可以直接枚举, 还有二十分可以$DP$出来。
第三题我好想会一个$nlog^2(n)$的做法啊, 考完试后才发现是$nlog^3(n)$的。 然而拿到了不少分啊
第二题的正解是将我的那个$DP$扩展到树上,打出来后发现其实非常简单, 我觉得在$NOIP$前都有可能会做,我是被省选模拟赛吓到了吗? 怎么不敢打正解了啊?
第三题可以在我的程序上稍加修改去掉一个比较大的$log$就可以轻松过掉了,其实我的程序开了O2也是可以过的啊, 说好的开O2呢。
明天还考试, 题还没改完呢啊。。

2018-3-28

早上起来好困,到机房后继续看昨天的题的题解。
到了考试的时间就考吧。
上来一看,这好想和昨天的是一套题, 可是画风好想不大一样啊
看了看第一题,发现和昨天下午T2的一个部分分有点相似,可是数据范围大了不少,然后就开始推DP方程$O(n^3)$不用过脑子, $O(n^2log(n))$是NOIP水平的DP, 这样是$60$分, 然后想$100$分的做法, 想了一会发现好想没什么思路,然后看了一下第二题,发现没什么思路,暴力也不是很好打, 然后看第三题, 看起来好想很好拿分? 开始先把暴力打上,然后发现,好想可以用动态点分治, 是不是可以满分?(死+1), 然后开始打, 打着打着发现好像不能处理修改操作? 没事, 没有修改也有$50$分(死+2), 比暴力多了不少, 继续打, 调调调, 最后还是没调出来,再给我$10$分钟就行啊, 说好的四个半小时呢?为啥又是四个小时。
$T2$最后还是没打上。
最后$T2$好像是这三道题中最好做的?应该多给点时间给$T2$的。
这次考试最大是失误是错误的估计了我$T3$打法的难度,没有正确的处理好每道题的时间分配,否则第二题还是能拿不少分呢。
下次一定注意。

2018-3-29

又是考试的一天
开始考试后看第一题,想出了$70$分的$DP$然后想了想,也没想出怎么优化。
看第二题,只会暴力,第三题只会暴力。 然后就完了。
其实第一题的正解很简单,但是我没有想出来,主要的一个原因是$DP$数组转移的方式问题,以我的转移方式只能看出他是一个区间加, 但如果换一个方向, 就能看出前缀和了, 然后就是正解了。
第二题是一个很简单的线段树,但是我没想出来,主要是因为没有深入的挖掘$n \leq 100$这个条件。
第三题是真的很好,先将二维转化为一维,然后可以字符串匹配,$FFT$优化搞掉这道题, 这个真的是不容易想出来。

2018-3-30

没改完题。。。
T1上来一看是道水题, 结果老师说题面是错的, 然后就不会了, 其实正解也就是一个简单的$Hash$
T2没有什么思路, 就打了一点骗分, 其实可以用模拟退火水过去, 正解是拉格朗日乘数法。
T3题面中给出了精度问题, 然后就想到了取$log10$这个操作, 之后需要用线段树维护排序和区间和。

2018-3-31 ~ 4-1

3-31号上午考了一场试
上来先看$T1$发现一眼看出了非常水的$50$分,然后发现不会了,尝试去想$100$分发现复杂度一直不对,后来加了一个单调偏分,又多拿了$10$分。
然后看$T2$发现暴力不是很好打, 想了想, 发现他的状态的检验非常快, 然后想到了昨天学习的模拟退火, 然后一发退火上去, 过了样例, 然后造极限数据, 发现跑一次一个数, 每次都不是最优, 想了想算了, 应该能拿到点分, 但应该不多, 然后发现有$50$分,很开心, 真·信仰退火, $T3$真的是一点都不会。。。
其实$T1$可以通过两个单调用线段树维护, $T2$是网络流,$T3$是一道$Hash$+$BurnSide$的题。
4-1做题,先把前天的$T3$改掉, 用了快一个上午,真是打不动数据结构了啊。
然后做了做NOI泳池因为不会特征多项式,用快速幂跑了$90$分就这样了。 然后做【UER #4】量子态的棋盘 一道不是很显然的轮廓线$DP$,但打起来不是很难。
还要把Normal打完啊

2018-4-2

考了两场,两场的$T2$和$T3$都不难, 但是$T1$都不是很简单。
$T1$ 全场最佳。
题还没有改完。

2018-4-3

上午考了一场试,算下来还有一两天就省选了啊。
一看$T1$看起来部分分很好拿, 事实也确实如此, 先打$60$分的部分分, 然后想先看看其他题, 然后留一点时间给第一题。
然后看$T2$发现不是很会做, 先打了$20$分的暴力, 感觉还有$10$分好像可以拿, 然后我先看第三题去了。
$T3$不是很会打暴力, 打了一个多小时的暴力, 最后因为重边, 出了问题。
因为$T3$费了太多时间, $T2$和$T1$也没有再去打, 本来以为还有一个半小时的, 其实只要半个小时了。
然后就没打我本来应该得到的那部分分。

ENDL

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
本文链接:https://blog.wildrage.xyz/2018/03/19/138/