省流
两人打女生赛，\(8t\) 冲进金牌区。谁说女生赛金不是金？
10.8
内含剧透，请vp后再来。
不是题解！！！！！！！
赛前
不知道为什么，今天白天突然选择了睡大觉一上午，可能就是转换一下，结果中午突然接到教练要求让打一场女生赛的 \(vp\)，其实不是非常想去。现在每周虽然只有三场区域赛，但对我来说时间仍旧很紧张，每场区域赛包括补题和游记至少要花十个小时，考虑到 \(whk\) 和别的比赛的时间，其实已经相当紧张了，但还是过来打一把，但就想不多补题了，不过不往后补感觉也就是浪费时间。总之也没好好吃饭就来了，叶还没回学校，于是只有我和简两人。
赛时
一开始我开了 A，简开了 C。两题都不到 \(CF\) A 题的难度，省略不谈。我说 A 很简单，于是也没给简讲直接丢给他了。
我接着去看 H，题目给了一个 \(01\) 串，\(0\) 作为分隔符，然后连续的 \(1\) 会提供长度的根号的分数，问把一些 \(1\) 变成 \(0\) 后最大的分数。很容易看出切的越碎越好，所以分奇数偶数长度两类，奇数就是直接除二加一，偶数就是除二后变成一奇一偶，再递归下去是一个 \(log\) 的复杂度。简码完前两题后我和他讲了，然后他直接把偶数换成了只有最后留一个 \(2\)，前面都是 \(1\)，就让他去写了。
我们这个时间段一直是堆着题目的，我在讲 H 之前去看了 M。M 题是给了一棵树，要求从叶子节点拉线到他的某个祖宗节点，问最长的线最多拉多长能覆盖每一条边。可以发现一个点想要到这个点只用选他所有子节点中最短的那个拉上来就行。此时简还没写完 H，我就去读了后面的题目，本来应该开 L，L 是有四种拼图问最大能拼的矩形是多大，感觉我不是很擅长。
于是我跳过去想 G 去了，G 题给了一个 \(2e5\) 的数组，和一个数 \(k\)，问有多少个数 \(x \leq k\) 与数组异或后数组是不下降序列。很明显是从前到后位运算的题，把样例玩一下，发现是如果某位是一个单调的 \(01\) 或 \(10\) 串，那么可以通过固定这一位来让这一位递增，如果都是同一个数那么这一位都可以取，如果不是上面的情况就挂掉。在固定某一位后，已经被固定的总比前面的数大了，所以可以直接无视掉。剩下的数位 \(DP\) 就可以了。
此时简码完 H，我简单说了一下 M，但我担心他的树形 \(DP\)，所以我就提出他是否擅长，要不我上机，他同意了。现在想我也不知道他听懂我说的没有。我码完之后发现和预想的不一样，简此时问我要多久他两分钟可以写过 L，我就下机让他写，他写完挂了。我在机下发现是根节点多算了一节长度，\(-1\) 后就对了。交了一发未知原因未知理由挂了，随便改了一点东西换了个 c++ 版本就过了。这场比赛的开局时期就这样结束了，大概相当于正常区域赛的一两道签到吧，时间在 \(50min\)，罚时 \(120\)。
然后我继续留在机上写我的 G，写出前面预处理 \(x\) 的要求后，在写数位 \(DP\) 之前简要求上机改 L，交了又挂，然后我继续写 \(DP\)，他又改了两次，过了。通过时 \(96min\)，三发罚时。
我码完之后交了 G，这是我这场噩梦的开始。一开始是 TLE，我前面两发都在调整各种常数的东西，最后发现是数位 \(DP\) 的存 \(DP\) 状态的变量写错了，把 \(DP\) 变成了暴力，修改了从 \(TLE\) 变成 \(WA\)。然后简说 \(E\) 没什么想法，他去做大模拟的 \(K\)，我就下机让他码。然后我发现了各种 \(DP\) 转换中的错误，改了但又都是 \(WA\)。我在 \(WA\) 了很多次后，简友善的告诉我让我重新思考中间的过程，然后我发现原来想的并不对，因为虽然后面的被固定比前面的大，但是后面的块内部的大小仍未被确定，所以要把每个块都统计，然后我写了是如果有两个块都要固定就不行，但是还是 \(WA\)，然后想到如果两个块固定的一样就仍旧可以选择这个数，终于过了。\(195min\)，八发罚时。
然后看 E 题，题目给了一棵树，每棵树的父节点都小于他的所有子节点，然后给出一个父节点所有子节点所在的子树上的重心，问这颗树的样子。虽然这题在“金牌线”上，打出且罚时少可以拿金，但其实这题，我尝试找答案而答案很简单简单的很遗憾，遗憾如果先开的是这个而不是 G 就好了。很快发现是不是重心并不太关心。因为父节点给的是一个子树上的节点，那么这颗子树上的根就是这个父节点的子节点，而编号小的节点在上面，所以只要倒序处理一定可以找到这个点所在子树的根，用并查集就可以解决了。\(217min\) 一发通过。
最后看了总罚时，\(852\)，金牌线 \(7t\) 罚时 \(866\)，我们金了。
非常高兴，旁边的学姐表示可是这是女生赛，我说女生赛金也是金，她说我又打不了女生赛。
无论如何我就没什么动力继续写下去了，反正争不了冠（这样对吗）。然后我就回寝室小憩去了，爬起来一看简在 \(285min\) 一发入魂通过了 K，我们从金尾变成了 \(8t\) 罚时 \(1136\)，排名 \(rk14\)。
赛后
谁说女生赛金不是金？！不过下来还是要好好感觉一下的，我个人感觉也就刚拿个银，但 \(Gemini\) 坚称这个表现是银中，抛开简单挑的 \(K\)，可能就是一个银尾但也有银了，而简可以自豪的说拿了银中。接下来就是补题。
L 题是有四种拼图各一些，问拼成一个最大的矩形的面积。容易发现拼图的构成为 \(4\) 个 \(1\)，\(2* (x + y-2)\) 个 \(2\)，\(2* (x + y-2)\) 个 \(3\)，和 \((x-1)* (y-1)\) 个 \(4\)。数据范围要求不能模拟两边长，于是选择枚举 \(x\)，然后可以通过 \(x\) 和 \(4\)，以及 \(2\) 和 \(3\) 的数量计算出两种面积，选择其中较小的就是当前 \(x\) 能构成的最大矩形，这样能压缩一维的时间。
F 题给定了一个长度为 \(n\) 的序列，每个数小于 \(1e6\)。要求构造出新序列，每个数都是原序列的约数，新序列所有数之积是一个完全平方数。求所有能满足条件的新序列的积开方后的和。容易想到新序列的每个质因子的出现次数都是偶数，那么就可以考虑 \(dp\)。但是直接 \(dp\) 所有质因子出现次数的所有情况很明显会超时，考虑怎么优化。可以发现，对于一个质因子出现的次数，当出现次数为偶数时，贡献的值就是他本身乘 \((i/2)\)，而奇数时贡献是根号的他本身乘 \((i/2)\)，所以可以提前预处理出一个质因子出现 \(i\) 次时对整体的贡献，再将所有这个质因子在不同位置上的贡献相乘就得到这个质因子的总贡献，再把所有质因子的贡献都乘起来就行。需要注意的是取模是 \(1e9+7\)，以后交题之前要检查的包括取模的模数。
出于各种原因，其实就是懒了，不补 B D I J K 了，下班！
2025年9月24日