68th 2023/8/16 模拟赛总结51

发布时间 2023-08-24 21:38:27作者: Far_delivery

本次情况

呵,又一次在排行榜底部看到自己了

但,绝对不能说习惯了,迟早嘛,,迟早

题目这一次莫名的好理解,T1是一道数论,有一个条件已经提醒得很明显了,就是\(\left\{ \begin{array}{rcl} X^a\equiv b\\ X^c\equiv d \end{array}\right.\)中,\(\gcd(a,c)=1\),这摆明了有一个方法:exgcd的推导过程\(a·x+b·y\equiv 1\),也是辗转相除,但当时对这些知识点太过生疏,竟生疏到完全忘却

exgcd是个好东西,得好好复习才是

T2是一道人类智慧题,题目是输出N-1个N个数两两组合的方式,所有组合不能重复

为安排顺序,考虑用余数的方式定下方法,轮流进行

T3是一道树形DP+树形背包

这道题需要较强的对状态进行归纳的能力,比如从意义上将一个点“缩”掉

而且\(O(N^2)\)时间复杂度的树形背包还没研究过

T4,一道有意思的题目,首先可以发现,每次转化后,这个数列的和在%3意义下仍然相同,再推可以发现,一个序列经过若干次操作后,这个数列必定可以变成一个和%3与原本数列和%3相同的数列,且这个数列必定有两个相邻数相同

因此可以转换成一道简单DP

但还不止于此,这些结论在N<=3时不生效,因此要打3以内的表

前面推出来固然重要,后面的细心才能AC

总结

细心,再细心

需要的细心还远不止于此……