SDOI2022 线上比赛游记

· · 个人记录

我提前 4 年打 \color{purple}\text{省选} 完全就是来找虐的（我现在初一六年级）。

Day 0 - 上午

先开 T1，一看题面说是 q 组询问，每一组询问都要维护一个数组 c，数组大小为 n，每个元素都为 0，1 或 -1。让求一个区间，使得 \sum^{r}_{l} b_i \cdot c_i 最大。n,q \le 10^6。
一看上去，这 c 数组还得根据题目每次自己生成，这还不得直接爆炸。想了一会，觉得这道题 O(logn) 平衡树查询某个数比较合适，但是过了一会 Hack 掉了自己的思路。然后就想想暴力分，我尝试使用 st 表实现 O(n^2logn)，但是想了一会发现假了。只得开 T2。
T2 让求的是 \sum^{n}_{1}x^i \cdot y^{a(i)} \cdot z^{b(i)}，a(i) 是十进制 i 转换为二进制之后包含的 1 的数量，b(i) 是十进制 i 转换为三进制后每一位的和。1 \le n \le 10^{13}。一看这数据范围，感觉应该是 O(\sqrt n \cdot logn)，但是想了一会想不出来。就盯上了 1 \le n \le 10^7 的暴力分。我快速打出了一个 O(nlogn) 的暴力，过了第一个样例。我又手造了一组极限数据，结果.......跑了 27s，不会省选就要这样爆零了把。
我就开始卡常，我把 long long 能换的全换成 int，一测，变成了 14s，快了一倍！我再思考别的卡常思路。我想起来我曾经通过循环展开用大暴力 AC 过一道紫题，我觉得可以试试把循环展开应用一下。然后........接下来 20 分钟都是在进行展开。展开完之后一测，Yeah！又卡掉了一半的常数，14s \rightarrow 7.5s。接下来我又把计算 a(i) 的函数从我自己写的换成 c++ 的内置函数，然后 7.5s \rightarrow 7.1s。这时候，我发现不能再优化了，开了 O2 也要跑 6.8s。没办法，我的算法彻底假了，只能去想 O(n) 算法。结果我发现我被降智了，只需要一遍预处理就能砍掉快速幂.............然后我把没优化之前的代码改了改，就过了暴力部分的极限数据（我花了一个小时来做的优化全白费了），差不多结束了。

估分： 0+15+0+0=15pts

Day 0 - 下午

看了看 T1，说是对于每个 i \in [1,n \cdot k]，计算有多少个可能的树的最大独立权集等于 i，（树的节点数为 n，每个点的点权为 [1,k] 中的任意一个数）。只能想到 O(n! \cdot k^n) 的暴力，能光荣的获得 \color{red}\text{0} 分。
那就先跳下一题，一看，这道题树链剖分板子，但是空间卡的很死，时限倒是很长。然后就盯着它的特殊性质研究了一个小时，发现做不出来，开 T3，woc 一道巨难的数学题，连题都读不懂，感觉这道题至少 \color{black}\text{NOI} 难度，只得跳回 T1。这时候发现它的 n \le 8,k \le 5 的部分可以使用树形 dp 来做（实际上这一部分就是 P1352没有上司的舞会)。设 f_{i,1} 代表当前点选的最优价值，f_{i,0} 代表当前点不选的最优价值。O(k^n) 枚举每个可能的树，对于每个树 O(n) 计算。这样就有了 25pts。写出来之后感觉再做下去没啥用，就提交代码离场了。
估分：25+0+0=25pts

最后

总分估计：15+25=40pts
我还是太菜了

UPD:

官方成绩出来了：15+25=40pts，和估分一样。另外看了一下 B 队最后一名的省选成绩是 199pts，还是差的很远很远