关于我在SSL做纪中题目这档事（2021.8.23）

成绩

做题

看 T1 发现又是方差&＃xff0c;然后看了一下觉得一定是长度为 $l$&＃xff1f;没证&＃xff0c;先去看下一题。
看 T2 发现很数学题&＃xff0c;想到了质因数分解却感觉会质因数个数太多。
T3&＃xff0c;有点懵&＃xff0c;想了一下没有什么思路&＃xff0c;然后想了一下 $50$&＃xff0c;就是一个简单树形 DP。
T4 笑死题都有点看不懂&＃xff0c;先想了 dfs 要怎么跑。

然后去搞 T1&＃xff0c;搞着搞着发现可以搞出反例&＃xff1f;
&＃xff08;后来发现它是最优的一定是 $l$&＃xff0c;我的反例显然选右边两个是最优&＃xff09;
&＃xff08;我的反例是 $36$ 和 $366$&＃xff09;
然后就去化式子打暴力。
然后把 T2 暴力也写了&＃xff0c;然后看到 $40$ 的挡就多判了一个 $\gcd$。
然后 T3 直接每次询问跑一次树形 DP。
T4 搞出了 dfs&＃xff0c;尝试打标找规律&＃xff0c;然后发现有数据点是 $\gcd$ 为 $1$&＃xff0c;去看了一下发现答案都是 $0$&＃xff1f;
直接上。然后发现跟 $1$ 有关的似乎都是 $1$&＃xff1f;&＃xff08;没看到 $11$ 是 $2$&＃xff0c;痛失五分&＃xff09;&＃xff0c;然后就加了一个特判。

预估&＃xff1a;50&＃43;40&＃43;50&＃43;40&＃61;180

出成绩

果然我的暴力还是会炸了的&＃xff0c;T4 没有判 $11$ 是 $2$&＃xff0c;没了 $5$ 分。
笑死前面一排全部都有 A 的就我没有。

讲题

T1 就是长度为 $l$&＃xff0c;然后就是 ** 题了。
T2 其实质因数的个数&＃xff08;不同的&＃xff09;每个数不会超过 $8$ 个左右&＃xff1f;然后就其实复杂度是可以过的。
T3 子树相关的线段树&＃xff0c;然后维护最长的链长度和两段点&＃xff0c;然后神奇的合并。
T4 是个神仙结论题。

总结

感觉这次勉强可以&＃xff1f;
&＃xff08;起码暴力能拿很多分了&＃xff09;

但感觉前两题其实都是正解了&＃xff0c;但自己的证明又有问题&＃xff0c;没有去细想是否可行&＃xff0c;到时没有打正解。
自己在证明的时候思路还是要严谨一点&＃xff0c;多考虑一些情况吧。

做出来的题目博客

Robert 的军队
Ned 的难题
Snow的追寻
网格图