11月集训赛后反思总结

· · 个人记录

写点反思总结一下，记录不熟的点。排名总人数不计得0分的。

11.4模拟考

成绩:100+0+0+100

排名:3/16

T1

知识点:剪枝(n^2 \ln n)、拓欧(n^2 \log n)

正解是爆搜剪枝,但是我看题第一眼想到的是扩欧,但是扩欧特别不好调,和模板P5656类似。而且爆搜复杂度是完全跑不满的 O(n^3) ,细算出来是 O(n^2 \ln n) 而我的是 O(n^2 \log n) ,这场比赛就耗时在这里。

T2

知识点:组合数学，计数

每次遇到方案计数题我就只能爆搜,这题爆搜还写错了,真的是毫无办法。只能多加练习,对增加方案的操作性质要在考场上分析清楚。

T3

知识点:特殊性质+背包

是不算难的一个套路背包,但是考场上我想错了以为是贪心,而且样例过水全是对的。每次想完得好好想想算法正确性才行,不然写完才发现或者考完了那是真的极其严重.

T4

知识点:dj全源最短路(n^3 log m)/最短路树+floyd(n^3)

dj做法比较暴力，最劣时间是 O(n^3 log (n^2-n)) 。跑满 6e8 但是时限 2s 可以通过(而且跑不满)。

相对之下法二时间复杂度更优但是思维难度较大，如果只允许法二通过我写不出来。

正常发挥正常切,且耗时20min,比较理想。而且估计是放在了T4的缘故导致很少人开题来切,给了我拉分的机会。

总结

计数和背包不熟练

11.6模拟考

水题场,人均300+

成绩:100+100+100+80

排名:1/19

前三题没啥好说的,说说T4

一开始我只想到状压,因为选物品的时候不能确定顺序,不记录状态没办法像常规dp一样考虑选前i个(埋下伏笔)。但是状压只有40分,有啥办法能更高呢?

观察大样例,答案实际的值特别小。我赌这题的数据一定是随机生成的,因此选任务的时候如果随便选很容易就把 T 爆了,因此爆搜的时候只要加上这个剪枝就可以把很多不合法的方案提前判掉。而且大样例跑的很快也证明了这点。

最后事实证明我的爆搜理论上限是 O(logn*n*n!) 快到起飞拿了80,比很多接近正解的 O(n^2)~dp 还多拿10分。(事实上写得出 O(n^2)~dp 的,通过人类智慧计算下就知道选的物品一定不超 cbrt(T) 而O(n*cbrt(T))) 可以通过。)

这场T4就可以说明,即使你比别人菜想不出正解dp或者接近正解dp,但是一些人类智慧仍然可以帮助你拿到比他们高的分。

本场比赛卡住的点:这题能想到 O(n^2) dp的关键就是想到对 p_i 排序,因为 p_i 大的往后选一定是劣的。满分做法上对选择个数进行上限估计优化。

总结

对特殊处理后的dp不熟

11.8模拟赛

成绩:100+20+50+20(大众分)

排名:7/19

这场比赛略微挂了,来分析一下。

T1

知识点: 三分

是个很版的三分题,但是我一开始竟然跟个傻子一样认为 O(1) 就可以算出,然后推矩阵值的时候又花了不少时间, 2h 才切出 T1

T2

知识点:随机值异或技巧+二维前缀

读完题以为是数学计数题又没思路,写了个暴力结果大样例答案是错的(实际上是题面给错了,赛后给我们都加上了),把我心态都搞炸了因为我觉得自己写的毫无问题。因为(以为)暴力都没过所以压根没心情想更优的做法,还好我还是交了我的暴力上去不然20分就没了。

这题考完学会了一个小 trick

如果矩阵内判断要么不选两个数要么选两个数可以给这个数字的位置搞一个随机值然后做矩阵前缀异或,值为0就是这种情况。(显然维度没有限制,这种思想都可以用)

T3

知识点:线段树，乘法原理计数，分讨

正宗计数题了,依旧不会,爆搜跑路。

要想到每个位置一定有一个下限 low_i 然后往这个位置填的时候不能小于这个值,后面就比较简单了,做一个分类讨论,因为是排列所以还是简单的。

这题考场上没想出来，就死在没想到是去考虑每个位置的约束值，而不是每一个值的约束位置(后者实际上特别难写)

T4

知识点:数论分块，树状数组

把原始式子推出来了,虽然想到 k/a_i 这个部分可以用数论优化,但是对 k \mod a_i 这一步真的没思路。

又学到了一个小 trick

a \mod b=a-\lfloor \frac{a}{b} \rfloor\times b

然后对值域为下标做数论分块,能想到这一步后面就很容易了

总结

数论方面不熟，计数依旧烂，需要掌握随机异或技巧。

计数无非就几种，dp或组合数学或(乘法/加法)原理，下次遇到推一下看看属于哪一种解决方式。

加法原理太简单一般不考。

11.9模拟赛

最炸的一集,就是今天开始打算写赛后反思的

分数:76+0+20+0

排名:16/22

T1

知识点:全源最短路+k边限制

神秘挂分,明明是正解大样例都过了结果挂了24我真的服了,大样例不能出强一点吗?不过我写的确实有点问题没检查出来，记得写对拍!

::::warning[警告] 不要把dis数组和存边的合并在一起用不然会有大问题 ::::

T2

知识点：计数dp、矩阵加速

数学题,狂推1h但是仍旧推不出来,发现有一堆重复计算的但是不会计算减掉贡献。但是大家都推出来了我咋就这么傻。

这道题7个人都切了,比T1切的还多,严重提醒着我的数学就是一坨。

刚听完老师讲,感觉其实我想不出来很正常。我来重新捋一下思路。我赛时只想到前四种矩形方案,而且因为我的神秘做法要考虑新加的矩形要填头还是尾,然后判重就会特别复杂完全不可做。

题意:有七种俄罗斯方块,分别是

可以将他们旋转 90°\times k,k∈[1,4]

用它们拼出来 2*n 的矩形,问你有多少种方案,两种方案不同当且仅当存在一个及以上的格子颜色不同。

n \le 1e18

::::info[题解] 容易想到n为奇数答案是0,并且如果用了后3种,一定拼不出来。因此只考虑前4个能拼出来的合法情况:

其实赛时完全没想到最后三种情况

大概可以推出来有这几种,最后三种比较特殊这里单拎出来讲。

观察到倒数第三个形状,它是由三种方块拼接而来,显然旋转 180°后它是另一种方案而且合法的,而且中间可以放置k (k为奇数) 的蓝色长条

最后两个与其类似,虽然旋转后是同一个,但是它中间可以放置 k (k为偶数且至少为2) 的蓝色长条

开始推式子,设 f_i 为拼出 2*(2*i) 的矩形的方案

那么 $f_i=3*f_{i-2}+f_{i-1}+2*\sum_{j=0}^{i-3} f_j

怎么来的,首先它可以从 f_{i-1} 中直接填上一个橙色正方形,因此 f_i+=f_{i-1}

它还可以从 f_{i-2} 中用我画的图 1,3,4 的矩形方案转移过来,因此 f_i+=3*f_{i-2}

因为我画的图中,最后两种本质上来说一样,不妨就令6的矩形旋转可以得到矩形7,因此我们只需要考虑矩形5和矩形6,最后方案*2就可以了。

而矩形5的长度是 i*4+2,i 是蓝色长条的数量/2+1(即第几个奇数,比如i=2就是填了3个蓝色长条,i=3就是5个).

我们转移的时候是把长度除以2的。假设现在长度是 j ,那么它可以从 j-(i*2+1) 直接放一个矩形5转移过来,即

f_i+=f_{i-3}+f_{i-5}+f_{i-7}...

同理可得,另外一个矩形长度是i*4+4 ,填的方案就是

f_i+=f_{i-4}+f_{i-6}+...

注意这俩最后方案要*2,那最后就是

f_i=3*f_{i-2}+f_{i-1}+2*\sum_{j=0}^{i-3} f_j

最后矩阵快速幂优化就可以。 ::::

T3

知识点:分讨,dp,区间问题

这题赛时卡住的点和11.6 T4一模一样我服(伏笔收回)。也是直接dp无法确定顺序，但是我还是硬着头皮把我错的dp交了上去骗了20，实际上可以观察到一点，如果一个区间包含着另一个区间，那么这个区间要么自己开一组，要么对答案没贡献(被包含的区间给交了)，怎么理解，看下面(称这种区间为特殊区间)

假设我们分两组

为什么，因为你涵盖了别人说明你一定比别人大，你去和其它线段匹配让它一条一组很明显没有你自己一条一组优(虽然匹配部分你比他优，但是在自己一组的时候会包含优的部分，因此一定是长的单独一组)。

因此把这些特殊线段单拎出来，对其它线段进行正常dp，然后最后再相加这些特殊线段取个 max 就可以了。

T4

知识点:思维题,带权并查集(树上合并)

前提:得会推式子得性质

呃，原本只是想赛时打个菊花图的20分部分分，结果挂掉了。赛后得知其实压根没出菊花图的数据(我真求你了)，然后随便把我菊花图的贪心二分排序从a升序改成b降序，结果拿了70分。

何意味？

题解更新了，原来在不考虑父亲限制下，按 b 降序排序是最优的，有严谨证明。那给70分啥意思，造了70分的菊花图？还是说数据水了？

正解是先排收益正的大于收益负的，如果均正则门槛(a)小的优先级高，均负则补偿(b)大的优先级高。后面排完序按优先级从高到低处理。如果该节点优先级高，意思就是选了它父亲之后立刻选它，因此合并两个点并合并价值。统计答案的时候，如果这个点父亲未被选就合并(可以打时间戳，合并的点后面不需要单独处理)，否则直接选这个点然后标记已选。

总结

树上问题不太熟练、计数问题依旧不行、提前处理再dp还是不熟、每一题写完写的有点悬的一定要对拍。

11.11 模拟赛

双十一，购物的好日子。

但是我并不好

成绩:100+65+0+0

排名:27/34

懒得骂了，我就是个铸币

T1

知识点:扫描线

签到题

T2

知识点:洪水填充/缩点/并查集 + dfs

麻的我脑子是有坑吗，缩点之后不跑dfs

T3

知识点:树上求距离+边数限制+推性质

麻的我脑子是有坑吗，这题数据难得造的水暴力可以90分，我tm没写出来暴力

正解需要找到每个条件的下限，找出dep最大的要求。在这满足这个条件下找到dep最小的点，如果这个点满足所有条件那么可行，否则都不可行。

T4

这题太难了真没招，赛后能第3个写出来已经满足了。

小trick(知识点):根号分治，同余分类优化建图，图论建模

总结

还是要对拍，暴力尽量写(SPJ的题目还不熟练)

11.13模拟赛

还行,但是又挂分了，但是T3用狗运补回来了

成绩:100+40+50+30

排名:9/36

T1

知识点:端点处理/双指针

签到

T2

知识点:拆位计数

陷阱:同余方程(假做法，会遇到无法处理的情况)

傻了，考场上想到解同余方程，但是可能会出先一种情况同余方程解不了，但是因为情况不多所以还是有一部分的分。正解不难。

T3

知识点:性质推导+dfs序优化+双指针

通过直觉想到一种做法，对答案贡献的一定出现在直径的两个点上。赛后被证伪了，但是在随机数据面前依然有不错的正确率。

赛时用set暴力维护拿了50，赛后用正解dfs序维护有90，正解是去做换根dp再拿dfs序维护，双指针处理。

T4

知识点:线段树区间容斥

不是很好想的一种分讨，至今没看懂题解。暴力做法是线段树上二分比较简单。

总结

容斥计数及其不熟、分讨情况不完整(t2+t3)(没发现解同余方程会有不可处理情况)(没有对拍导致的)

11.15 模拟赛

成绩:100+85+60+0

排名:11/36

T1

知识点:性质推论+模拟

T2

知识点:拆位计数

但是log^2有点小卡常，被卡了15分，还要小优化一下。

T3

知识点:dp+性质优化(可选区间连续)+构造

考场上依旧爆搜剪枝碾标算，但也说明dp能力不够强。

T4

知识点:离线线段树分治/在线极难推式子+滑动窗口+均摊证明

不会，赛后打了35分的环形01背包跑路了。

总结

dp能力还需加强，背包部分分也没拿到

11.16 模拟赛

成绩:100+30+0+20

排名:22/35

T1

知识点:简单博弈

T2

知识点:树上简单路径处理+斐波那契数列性质推导范围上界

考场上一直在想有什么方法可以快速判断一群数内有三个数可以组成三角形。但实际上，根据斐波那契数列(无解最紧的条件)的增长速度可以大致推导个数上限，在上限内暴力跑，上限外肯定有解。

T3

知识点:异或性质+拆位处理+逆序对

因为先^i再移动再^j本质上相当于^(i^j)再移动。因此可以推断出操作二最多只有一步。考场上想不到这个性质因此1分未得。随后进行拆位，对每一位(是否异或)会产生的逆序对进行统计，答案取最小值累加。

T4

知识点:隔板法的应用(组合数学)+线段树维护(分块亦可)

考场上只想到每次询问都dp一次效率很低，没有想到组合数学隔板法解法。赛后大家都用线段树解决但我发现O(n\sqrt n) 的时间也可以通过因此果断写分块写了233行，改到凌晨1:30终于过了。两者的处理本质没有区别。

总结

对性质推论/推导及其不熟(考场上根本没发现有性质或者推不出来)、组合数学计数也需加强。

11.18模拟赛

祝我生日快乐呀！

成绩:100+100+80(假)+8

排名:4/36

T1

知识点:分层图最短路

T2

知识点:并查集

T3

暂时没有正解做法，题解假了。刚好我想的是题解的一种暴力优化，所以混了80，实际上我再加个bitset就是题解做法了。

T4

知识点:括号序列/复杂dp/卷积+卡特兰数

题解看 这个

总结

今天题出的太失败了，前两题签到的不能再签到，第三题题解是错的导致目前所有做法都是假做法，第四题属于难度较大的计数，非省选选手需要想到出入栈操作转括号序列再算卡特兰数，否则需要写一个分讨且复杂的dp或者是卷积。

计数还是差

11.20 模拟赛

分数:100+20+10+20

排名:25/52

T1

知识点:三分/数学

这题发现是单峰函数可以直接三分，实际上可以直接数学推导出顶点，因此也可以直接 O(1) 判

时间复杂度 O(n \log_3 n) 或 O(n)

T2

知识点:数学(偏移量计算)

考场上看出来是一个类似滑动窗口的东西，但是不会计算贡献。赛后学习到窗口偏移的贡献可以推式子预处理。

正常来说枚举每一个中心直接暴力是 n^2 。考虑优化，设中心位置是i ,中心的系数实际上是 d，偏移量就是 d-i ,设其为 x。因为实际上贡献的是一整段，因此可以用前缀和。不考虑开头的情况下，式子长这样:

\sum(i+x)^2 \times s_i =\sum i^2 \times s_i+2x\sum i\times s_i+x^2\sum s_i

因为我们枚举每一个中心的时候 x 是可以直接求出来的，因此维护\sum i^2和\sum i*s_i和s_i即可。求出区间贡献直接 [1,r]的值减去[1,l-1]

T3

知识点:dp+线性优化

能推出dp式子并发现dp具有单调性这题就做完了，但我考场上没推出来

T4

原题

知识点：分讨+复杂dp

正解没仔细看，好像有爆搜找规律写dp的，但是这题在k=0,1,2的情况都很简单，因此 60 分是必须要拿到的。

总结

数学和dp差，必须严补

11.22模拟赛

分数:100+20+100+0

排名:16/51

T1

知识点:dp+优化

挺不好想的一个dp,要不是我同学告诉我贪心的dp是假的我估计就死这了。后来联想到这题和方格取数那题相似度95%只是多了个有格子不能走的限制。只是这道题需要严格 O(n^3) 做法。(当然可以用费用流，我不会罢了)

事实上想到不能分开枚举两个路线，因此必须合并成一个dp一起写。最直接的想法是四维，分别存储两条路线的两维坐标。但是想到两条路线的总长一定是一样的， 并且满足(步数=水平方向位移+竖直方向位移)于是可以压成三维。剩下的就很简单了。

T2

知识点:最优性排序+反悔贪心

T1卡我太久了，T2想到反悔贪心但是最优性排序没有时间严谨去推导致口胡错了。

T3

知识点:主席树/随机化/回滚莫队/摩尔投票

典题

T4

知识点:树剖(长链剖分)、倍增

黑题，不想看了

总结

对时间的把握还是要够，算法一定要想清楚是正确的再写不然会浪费很多时间。

11.24 模拟赛

分数:55+100+52+0

排名:109/456

第一场大型模拟赛

T1

知识点:dp优化

服了考场上只看到 1\le k\le n 没看到 1\le k\le 10 导致一直以为 n,k 同级。最后20min才发现但是无力回天。

选择物品在两个属性选一的时候，可以开两个dp数组表示选到最后是属性一和选到最后是属性二。

T2

知识点:线段树优化计数

计数有进步

T3

知识点:结论+线段树维护区间哈希+线段树二分

有点难，结论题+典题，线段树维护区间哈希太难写。

T4

知识点:(大模拟+分类讨论找规律+dp)

加强版:数学(生成函数+微分方程)

那还说啥了，弹了。

总结

计数题有进步，dp还需努力，看题还要仔细

11.25模拟赛

分数:100+85+4+0

排名:18/62

T1

知识点:简单数学

T2

知识点:分讨+双指针+模拟

考场上漏判一种情况，打完盾之后可以打实力为负数的士兵收益更大。

T3

知识点:贪心+线段树/延迟删除

考完后看见线段树码量巨大开始畏惧，但当看到一位大神写的贪心+延迟删除后瞬间被其折服，这里着重讲一下这种思路。

::::info[题解] 首先容易想到贪心，可以按g从大到小排序，依次选。因为要求最大值因此排在前面的一定是能选就选。

(™我蠢飞了觉得按g排序会影响区间顺序所以考场上认为这种做法不对)

但是如果是先排序再选我们会发现反悔操作特别难写而且时间也不对，考虑堆操作。

因为题目保证了每个人的区间左右端点单调不降，因此直接按原顺序来操作会更加方便。

我们每次先处理上个人左端点到这个人左端点中的区间，如果能放数那么就从大往小放。

然后加入这个人，如果此时堆中的容量超过了这个人[l,r]内的限制，那么就弹出最小的。

具体地，如果我们正在考虑第i个人，我们会先把 [l_{i-1},l_i-1] 中的元素处理。堆中放的元素就是可能成为 [l_i,r_i] 答案的元素(意思是说堆中的元素就是可以填在 [l_i,r_i] 中的元素)。

如果堆中的元素超过了 [l_i,r_i] 中能填的总和就从小到大弹出。

那如果下一个人的 l_{i+1}>r_i 怎么办，容易想到如果是这样，那么前 i 个人无论如何去填都填不了[r_i+1,l_{i+1}) 里面的，问题等价于[l_i,r_i] 。

那么每次左端点移动的时候，堆中的答案都是合法的，能填就填(一定是对的)。

这就是延迟删除的思想。如果每次加入线段就立刻去删或者去填会非常麻烦，时间复杂度也不对。但是如果拿一个堆维护一个区间内的答案，等端点在区间内移动的时候在去添加答案就会容易很多。

时间复杂度O((n+m)\log m)

::::

T4

知识点:dp+树剖思想优化

这个优化太无敌了，直接弹了/kk

总结

背包dp的部分分没能拿到，背包还是不熟练。分类讨论的时候要考虑完全不要漏，容易挂分。

11.26模拟赛

分数:100+100+60+10

排名:5/52

T1

知识点:数学(欧拉筛+预处理)

T2

知识点:组合数学

T3

知识点:贪心+人类智慧优化/线段树优化

这题人类智慧比较牛，依旧是有概率被卡但是随机数据完全卡不掉。线段树比较难写，需要有区间加，区间推平操作，区间求min。

T4

知识点:欧拉序+线段树优化(可加树剖)

没看懂题解，只知道大概做法，询问相同节点的时候不会处理。

总结

发挥正常，T3稍微努力下想一下人类智慧会更好，数学进步很大。