因为是线上，所以没得游记

Day 0

GDOI真奇怪，下载一堆奇奇怪怪的东西，因此换成了windows,配置了半天vscode

下午的信心赛打成泄气赛了，初一第四

T4用树的直径的思想做的，寄了

T6简单循环题思路错误，又想到分解了

我发现每次想到分解必出事是吧（NOI ONLINE的数学游戏也想成分解了，0分）

T8就是经典的模的循环问题，没打完

T7和T9是水分的

Day 1

完全爆炸，每一道AC的

T1没有判 $A=B=C=0$ 的情况

T2想错了，其实就是一个简单的前缀异或

T3打了一个 $O(n^2)$ 的树形DP

T4水分的

听完讲解觉得自己是世界上最大的SB

好吧，将一切希望寄托于Day2

经过一次实战，掌握了这个比赛的出题方向

Day 2

成绩出来了！210！还算可以吧.....

100+0+50+60

不是，为什么T2挂了啊，虽然想错了但不至于0分吧.....

T3T4比想象中的分高，好耶!

排名174左右

Day2尝试逆风翻盘

T1看两眼就切了，不就是同余吗，然后就写挂了...

哦，原来是

k=0(mod n)\\ k=1(mod n)\\ k=2(mod n)\\

得

k=0(mod n)\\ k-1=0(mod n)\\ k-2=0(mod n)\\

啊，那没事了，我写成加一减一了，改了就切了

T2照着样例模拟了一遍就想到正解了，返回有点难搞，哦，没用啊，那没事了

T3是什么垃圾烂题，u1s1，真的出的没水平，

差不多半个小时求完常数，糊了一个代码，希望得分

T4糊了一个 $O(nm|S|)$ 的DP

附一下DP代码

        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=ss;j++)
            {
                f[i][0][ss]=1;
                f[i][m+1][ss]=1;                
            }
        }
        for(int i=1;i<=m;i++)
        {
            for(int j=0;j<=ss;j++)
            {
                f[0][i][ss]=1;
                f[n+1][i][ss]=1;
            }
        }
        for(int i=ss-1;i>=0;i--)
        {
            for(int x=1;x<=n;x++)
            {
                for(int y=1;y<=m;y++)
                {
                    f[x][y][i]=f[x][y][i+1];
                    if(s[i]=='W'&&mp[x-1][y]==0)
                    {
                        f[x][y][i]|=f[x-1][y][i+1];
                    }
                    if(s[i]=='S'&&mp[x+1][y]==0)
                    {
                        f[x][y][i]|=f[x+1][y][i+1];
                    }
                    if(s[i]=='A'&&mp[x][y-1]==0)
                    {
                        f[x][y][i]|=f[x][y-1][i+1];
                    }
                    if(s[i]=='D'&&mp[x][y+1]==0)
                    {
                        f[x][y][i]|=f[x][y+1][i+1];
                    }                   
                }
            }
        }

比赛结束，中午出去吃饭，高兴坏了

T1的做法的教授是一样的，应该没问题

T2教授和我的结论不一样，他说是 $n+Leaves\;Number$ ,

$Leaves\;Number$ 是叶子节点的个数

我说结论不对，应该是贪心，他看我代码，发现其实我们两个是一样的，nice

T3我常数调对了，实现不知道怎么样，听前缀和做法好短啊，60行，我接近300行了

T3代码见后面的附录

T4的DP我的是 $O(nm|S|)$ 的啊，正确性没问题吧

HZX大佬说老师讲了，但我摸鱼没听到，呵呵呵

总结

分数

100+0+50+60+100+100+40+0=450

太失望了！

排名

\texttt{Day1}\;\texttt{174}\\ \texttt{Day2}\;\texttt{154}\;\color{red}{\texttt{Up 20}}

没记清楚，差不多这样

希望以后加强思维吧，这次有 $150$ 分都是不该丢的

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\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分（成绩没出）

2022广东省选普及组没的游记