多校联考九场总结

总算考完了九套试题,天天早上坐五个小时,下午都会头痛的要死QAQ

不过考的貌似不错?

九场平均分 215.78

数一数考场上没有1A的题目吧(不算有毒的OJ卡我常数):

1、超立方体

QAQ 当时并不会FWT,矩阵乘法搞出系数来之后只能暴力贡献

然后输入的时候没有直接取模爆了long long,于是暴力也被炸飞了

后来学了FWT发现是水题

2、IP地址

没有使用合适的转化询问的方式 使得这道题目可以用打标记的方式来做

转化的一些经典方式:差分,叶节点查询转化为链求和,区间可减性查询转化为前缀查询

3、打字机

考场上推出了60分的DP,然后题解居然是用60分的dp判断增量是否相等找循环节

(事实是考场上并没有发现循环节的性质)

4、数学问题

考场上算法A了这道题目,但是需要写恶心的高精度(当时懒得写)

刨去高精度就是个很简单的容斥

5、Fibonacci矩阵

这道题目说起来好悲凉,我会做k=1,然后我把矩阵T搞了出来

然后并没有发现当k>1的时候,我只需要求T^k就可以了

实际上是没有发现每一次扩维的本质

然后学习到了矩阵倍增的算法并进行了一些扩展

6、重组病毒

考试的时候看错题目了,导致没有把这道题目的性质和LCT结合起来

然后因为看错题目,暴力也写挂了

实际上有了LCT的思路之后就是码农题,关键是观察性质

7、图样图森破

QAQ 现在让我重新写一遍依旧没有信心写对 QAQ

题解是从一个很简单的暴力入手,把暴力转化成了图论模型

进而变成了构图之后判环求最长路

但是构图的细节及其复杂QAQ

8、欧拉图

非常水的一道题目,但是考场上不知道欧拉图是什么就挂掉了

就是图连通性一类问题的计数,n<=2000,直接O(n^2)dp就可以了

这类问题通常都可以FFT的(我还无聊的写了一份)

9、觉醒力量

没有注意到模数可以拆分成若干小质数的乘积,这样暴力做线段树之后CRT就可以了

考场上一直以为模数是质数,以后考试的时候遇到不熟悉的模数一定要尝试着分解一下

10、维修机器人

完全没有想到是贪心,实际上是由这道题目只能增加的性质决定了

如果可以减少可以做到O(n*a)用单调队列优化即可

只要想到贪心,剩余的就不难维护 (吐槽一句一套题目考两个贪心是什么鬼啊

感觉最近的考试题目变水了?(还是自己变强了?

不管怎么样,无论什么原因,自己还是一场也没有AK

自己还是太弱了,一定要变得很强很强才可以啊

八月份!三个月! QAQ

原文地址:https://www.cnblogs.com/joyouth/p/5552146.html