正文
【总结】2022GDOI普及组试题与题解(缺两天的T4)
小程序:扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序
【扫一扫了解最新限行尾号】
复制小程序
标签
2022 广东省选普及组 GDOI
试题
前往Luogu下载
Luogu下载:This
Day1题解T1 邹忌讽齐王纳谏
打卡题,建议模拟
建议使用map
,时间复杂度为\(O(nlogn)\)
特判注意数据——
\[0 \leq A,B,C
\]
\]
需要特判为0的情况
T2 数列游戏
首先求出前缀异或和,\(sum_1,sum_2,sum_3,.....sum_n\),
如果一个区间\([l,r]\)异或和为0,那么\(sum_r⊕sum_{l-1}=0\)
移项得\(sum_r=sum_{l-1}\)
特别注意——如果\(sum_x=0\),那就已经可以筛掉\(x\)了
因此问题是在这些前缀异或和求有多少个不为0的不同的数
T3 流水线
堆优化贪心,一开始\(m=1\)(在1上)
随\(m\)的变大,每次往下加入节点,让\(max(w_1, w_2, · · · , w_m)\)尽可能小,
求出过程中的最小值就是答案
也可以使用二分,线段树
这个正确性十分显然
T4 小学生计数题
枚举数字和公差的做法可以拿到60分
蒟蒻也不会,求讲解
大概是求出一整条链,在当中取部分的方案数,使用前缀积+区间逆元解决
希望有犇犇在评论区补充
Day2题解T1点指兵兵
我们设有\(x\)个物品,那么最后会指到\(n\;mod\;x\)
根据题意,我们不能让\(n\equiv0,1,2(mod\;x)\)
根据同余的可减性,我们得到
\[n\equiv0(mod\; x)\\
n-1\equiv0(mod\; x)\\
n-2\equiv0(mod\; x)\\
\]
n-1\equiv0(mod\; x)\\
n-2\equiv0(mod\; x)\\
\]
现在很明显了,如果不想让\(n\equiv0,1,2(mod\;x)\),那这个\(x\)不是\(n,n-1,n-2\)的因子
我们可以用\(O(\sqrt{n})\)的复杂度求出三者的因子数量
根据同余性质,是不可能出现重复的,不需要容斥,直接区间-部分即可
\[ans=n-3+1-n的因子数量-(n-1)的因子数量-(n-2)的因子数量
\]
\]
T2网页浏览
首先不需要返回操作,替换+返回=新建+删除,后者操作性更强
然后,对于一棵树,最优显然是前几个儿子新建,最后一个儿子替换
因为一个网页只有一个父亲,在所有儿子被访问之前,爸爸不能死
但最后一个儿子被访问后,爸爸就可有可无了,这时候使用替换步数更少
对于下面的叶子结点,除了访问,还要删除
我们不难得出一个结论,\(answer=n+Leaves\;Number\),
\(Leaves\;Number\)是叶子节点的个数
因为使用上述方案,每个结点恰好被访问一次,有儿子的节点被最后一个儿子替换,而叶子节点还需要删除自己
所以就是上面的式子了
T3 教室的电子钟
思路非常简单,做法很多,但题目很恶心
最好的做法是六十行的前缀和做法
记录0年1月1日0时0分0秒到\(x\)年\(y\)月\(z\)日\(a\)时\(b\)分\(c\)秒一共消耗了多少单位的电为\(A\)
记录0年1月1日0时0分0秒到\(x’\)年\(y’\)月\(z’\)日\(a’\)时\(b’\)分\(c'\)秒一共消耗了多少单位的电为\(B\)
\[ ans=B-A
\]
\]
比本蒟蒻近300行对错未知的做法好多了
T4 机器人
正解是迪杰斯特拉最短路,蒟蒻没听懂
蒟蒻利用一个三维DP得到了大概50分(成绩没出)