2022.8.21 多校周报


总结

牛客第九场

A

一眼看出是尺取法,就A了。

B

一道很简单的概率dp,状态和转移方程都写出来了,但想着搞前缀和优化,没想到差分,就卡死了,有点可惜。

G

马拉车加哈希,但卡了除了双哈希的算法,题目很简单,但队里没有人学过字符串,就无了。

E

非常妙的构造题,利用了二进制的思想结合最长上升子序列的特点进行构造。虽然场上一点都没想对,但赛后补上,写一题就是赚一题,能开拓思维。

牛客加赛场

M

模拟签到题没什么好说的。

H

树形dp,也很简单。先统计子树节点个数,方便求因子重复次数,再dp求某个节点的因子数乘上子树大小就是贡献,rty直接A了。

E

朴素博弈题,但坑很多,主要是题意不清楚,导致很多次要猜题意,最后得到了 /(n/%p/) 和每轮必取两个关键结论就A了。

J

差分结论题。先搞成差分数组,再讨论所有情况,得到一个只要 /(1/) 数量不少于 /(2/) 即可的结论。

牛客第十场

H

卡了很久,后面发现选仆从不影响结果,最后才A。

F

一个简单的图论题,直接反向遍历,如果某点有大于等于 /(2/) 的路径能走,那这个点就是能走的,最后看看起点有没有被踩到即可。

I

哈希碰撞的题。一开始其实想到了把两组序列当幂次,用FFT多项式乘一下,系数大于等于 /(2/) 的就是可行的,但不会写FFT。最后看题解才知道能通过哈希碰撞,用 /(O(nm)/) 的暴力写法在 /(2 /times 10^7/) 的遍历次数内解决。

杭电第九场

1010

签到题,但写炸了,原因是没考虑取模减法要加一下,发现这个问题后就A了。

1008

考虑到了求区间互质,但因为不知道怎么处理就做不下去了,实际上要用容斥去做。

1007

一个dp题,但当时状态和方程都没想到正确的。赛后看题解,要现预处理每个娃娃的可行数量,只后就可做了。

杭电第十场

1007

简单的树形dp,但我写的时候刚学不久,想了有好一会儿,不过也是A了。

1003

一道贪心题,但一开始想到dp了,后面思路歪了,就无了。虽然过程中想到直接贪心求,但被自己莫名其妙否了。

总结

这周比赛连着五场,比较累,但收获还是挺多的,学到了许多知识,也见识了挺多。比如之前做不出的dp,也有点想法了,甚至能做出来了。但也意识到基础知识还是太少了,许多题想到了,但写不出来就很可惜。

原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/281498.html

(0)
上一篇 2022年8月22日
下一篇 2022年8月22日

相关推荐

发表回复

登录后才能评论