2022/3/22考试总结

时间安排

上午有课所以改成下午打复现赛

1:00~1:20

看完题感觉很难受
前两题都是位运算，T3是概率
不知为什么，前两题看起来都很可以FWT的样子
暴毙

1:20~1:50

写了T1，T2的暴力
期望得分30pts

1:50~2:10

想到数竞课上讲的自然数对3取余的规律
推了一会，发现对于二进制，在模3的意义下
加一个奇数位相当于加二，加一个偶数位相当于加一
顺便证明了一下
剩下的似乎只需要分类讨论即可

2:10~2:30

实现起来很简单
调了一会就拍上了

2:30~3:00

T2的式子直接把FWT写脸上了
但是只会写m=1
写完之后剩下的一点思路就没有了

3:00~3:10

想写T3的爆搜
太难写就弃了

3:10~3:40

考虑dp，一开始考虑区间dp
发现转移和左端点无关后，改成线性dp
复杂度$O(n^4)$

3:40~4:20

发现转移可以改成前缀和
复杂度变成$O(n^3)$
可以拿到60分
担心空间爆，所以卡了卡空间

4:20~4:40

测了T1的大样例
因为是spj，所以顺便写了个checker
发现了一个地方爆int了
改过就没问题了