本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-05-13 19:11:12

我提前 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，还是差的很远很远