2024 Mar. Week-3 Summary
2024.03.18 - 2024.03.24
感觉超级久没写总结...虽然但是题解之类的一直在写
补题
上周主要做 数据结构，把 lxl 的题单补到 \(Day~4\) 乐
主要板块：树套树，分块
但是效率还是有点低，一道题要做 \(INF\) 分钟，可能还是不够熟练
自己切题的能力比较差，很多时候还是要看题解的思路
模拟赛
还是挺菜的...但是开场先调了两小时昨天没做完的 分块
节约时间，赢！
\(T1\) 是一眼打表找结论的题
看到 数据范围，只能 \(O(\log N)\) 或者 \(O(1)\)
那肯定答案得是一个 单项式 或者 简单多项式 了
简单写个暴力，打个 \(10 \times 5\) 的表，试了 \(10\) 分钟左右
胡了个结论，写了，小样例过了，大样例挂了
但是样例这么多，没道理小样例都对了还能出正确性问题，合理怀疑 没有取模
查了一下，还真是！\(N - M + 1\) 有可能爆掉 int，和前面的乘就会爆掉 long long
绷不住... 取了模就对了，这个时候 \(11:00\) 差点
\(T2\) 是有结论的
注意到在 任意 \(2N - 1\) 个 正整数 内一定能找到 \(N\) 个数使之为 \(N\) 的倍数
就是 \(EGZ\) 定理，典，好像 \(N\) 可以拓展到 正整数 而不只限制为 质数
但是不会构造啊...只能想到 \(O(N ^ 2)\) 的 \(DP\)，但是开始没想到 方案怎么记录
如果全记下来的话就是 \(O(N ^ 3)\) 的... 最后才想到 只去记录从哪儿转移过来的
最后 找一下路径 就行... 然后没写完，\(GG\)
赛后发现 \(\textsf{H} \color{red} \textsf{angHang}\) 的 随机化 糊了 \(65 ~ pts\)，很神秘
后面找到 原题 了，发现这 \(UOJ\) 上的 最优解 也是 神秘随机化
有点绷不住，但是仔细想了一下发现 好像确实很难卡掉的...
就是本身很难构造出 解数很少的序列
比较唯一的方式是放一大堆 \(0\) 进去，但是最优解的随机又会把 众数放后面
放多了就和没放（或说放一个）没有本质区别了...
\(T3\) 据说还是神秘打表找结论题，但是还没有看...
感觉以后 赛时还是要多看看题，不能留题不看...
下周继续补 \(DS\)，感觉还是想先把 lxl 讲的给补完
主要板块：平衡树，树分治
\(Nityacke\) 果咩纳塞捏