一大早醒来一看九点半。
突然想起来有热身赛，急急忙忙起来洗漱。
G 楼好远，到了 G 楼已经十点半了。
打开电脑开始试机。
椅子很舒服。
登上网站开始热身赛。
第一题是输出冯佬朋友的缩写？
看到网站是 orz.grey.top ，那应该就是 grey 四个字母中的一个吧。
答案是 r ，试的第二遍对了。
第二题是将奇数偶数分别排序再输出。
第三题是网络赛最后一题的青春版，看到这题我就直接润了，将电脑锁屏后去帮老乔试机。
老乔电脑没啥问题后我就回宿舍了，路上去 1931 买了 40 块的补给来应对下午正式赛的 5 小时。
本想睡一觉，外卖到时已经十二点多了，吃完已经十二点半了，没办法吃完就往 G 楼赶。
匆匆忙忙赶到已经 12 点 50 ，敲了点模板，然后闭目养了会神。
比赛开始了。
A 位运算（2022版）
好像某年的新生赛也有一题叫位运算。
一看，这不就是 lowbit 吗。
诶， lowbit 是啥来着。
忘掉了，于是只能写一个模拟，通过了这题。
此时看榜，已经有不少人过了。
发现 C 题有人过了，去看 C 题。
C 除数强迫症
一个数学题。
拿笔算了算，得到了一个略微有点繁琐的做法。
统计 $1\sim n$ 中 $m^i$ 的倍数的个数 $cnt_i$ ，那么答案就是
这个 $cnt$ 直接用 $n$ 一直除以 $m$ 就能得到了。
时间复杂度不太会算，最坏应该是 $(T\log^2 n)$ 吧。
————————————
UPD ON 12.7，傻逼做法。
直接就逝 $\sum cnt_i$ 。
过了后看榜，发现 B 有人过了，又去看 B 。
B 接龙数列
第一次看时还以为是啥构造难题。
这次再看才发现也是一道送温暖的签到题。
直接扫一遍，发现不满足前尾后首相等的条件后加一个数就行。
时间复杂度 $O(Tn)$.
这题过了后发现没啥新题有人做了，于是自己看了看后面的题。
呜啊，D 的样例看起来好可怕，pass 。
呜啊，E 是一道以前见过的贪心，以前就没有做出来， pass 。
呜啊，F 是一道构造题，我没有脑子， pass 。
呜啊，G ，字符串， pass 。
诶，H 看上去好像是一个裸的线段树，于是开始写 H 。
H 洗把脸我安心
两个操作，一个单点修改，一个查询区间内第一个小于某个数的数的位置。
考虑用线段树维护区间最小值。
第一个操作很好搞。
第二个操作只需在 ask 函数中优先进入左子节点，超出询问区间的就直接 return INF ，最后取 min 就行。
测样例，过了。
交上去， TLE ？
很是疑惑。
此时只有我一个人交了这题。
一看时限， 0.3s 。
难不成 $O(n\log n)$ 的算法过不了，是 $O(n)$ 的算法？
想了一会儿，没啥思路。
此时看榜，树剖神已经 A 掉了这题。
继续看代码，终于查到了一个傻逼错误。
在 ask 函数中如果左子节点已经查到了一个位置，那么就没有必要去查右子节点了。
这个加上去提交后， A 掉了这题。
痛失一血 。
接着去看了 D 题。
D 楼层编号
读懂了题目后发现好像挺简单的?
把数字中的 $3$ 与 $4$ 提取在一起，把 $4$ 看成 $1$ ，把 $3$ 看成 $0$ ，将其看成二进制数，求出对应的十进制，然后对十进制进行如下的转化。
1-->A
2-->B
3-->C
....
26-->Z
27-->AA
28-->AB
....这有点儿像满 27 进 1 的 26 进制数。
写锅了好几次，发现如果是 26 的倍数需要特殊处理。
比如 52 ，应该是 AZ 。
52%26=0 ，因此需要特判，直接在当前位置加一个 Z ，然后将 52 减 1 后再除以 26.
这样处理 26 的倍数就过了。
此时看榜，发现很多人做出了 F 题。
于是去看 F 。
F 排排列列
感觉有点难搞。
但一想到这么多人都做出来了，那应该不会太难罢。
一开始写了个傻逼的模拟，样例过了，交上去，不出意料的 WA 了。
一直在想，如果用这三个操作能够实现交换这个操作的话，就那么这题就变得很简单了。
然后注意到操作次数限制不能超过 $3\times n$ ，想到这或许是个提示。
是不是能用 $3$ 次操作来实现交换操作呢？
动手模拟模拟，发现居然可行！！！
例如
两个数 a b
对其应用操作 2
变成了 a-b b
再用操作1
变成了 a-b a
再用操作3
变成了 b a如此就完成了交换操作。
那么扫一遍，遇到了不属于该位置的数，直接交换即可。
这样即使每个数都要交换，那么次数也不会超过 $3\times n$ 。
很是高兴，提交，傻了， WA 。
很是疑惑，感觉没啥问题。
再一看，哦，没输出操作的个数。
修改后提交，哈哈，还是 WA 。
写了个数据生成的代码，按照我的输出来复原一遍，还是没啥问题。
索性直接生成了一个 $n=10000$ 的数据，然后输入，发现居然不出解。
哦，操作有 $3\times n$ 个，我数组开的是 $n$ 。
哈哈。
喜提几发罚时。
数组开大后过了。
此时距离比赛结束还有一个半小时左右。
树剖神好像只剩最后一题了 orz 。
看到 E 有不少人去做，再加上其他的题一看也不是我这种蒟蒻能做出来的，果断去思考 E 题。
封榜前我是 rk3 。
试了好几种贪心，全都 WA 了。
距离比赛结束还有半小时，此时我的 1 点钟方向突然有拍手声。
一看，是树剖神！他 AK 了。
太强辣。
贪不出来辣，果断开摆。
在椅子上瘫了半个小时。
结束了，剩下的人拍了张合影
坐在树剖佬旁边 orz 。
剩下题就等题解罢。猪脑过载。
UPD ON 12.5
凌晨两点睡不着。
干脆把题拿出来看看。
J 题。
在板子上推了一会儿，发现好像可以化，最后化出来一个看起来可做的式子，矩阵快速幂加速递推。
感觉自己半夜脑子有点迷糊，推完后就放下板子闭眼了。
不知过了多久才睡着。
早上醒来，疯狂补工图。
间隙问了问出题人是不是矩阵加速递推。
确实是。
下午上完工图课，开始写 J 题。
发现自己之前的矩阵快速幂模板现在看不懂了。
从网上蒯了一个下来，然后开始写。
第一次忘了开 long long ，开了后过了。
恨，赛时应该把这题看看的。
J Artist
求
即
假设下标小于 $0$ 的 $f$ 值为 $0$
有
则为
故即为
则有
相减，得
即
故
所以根据
矩阵快速幂加速递推 $F_n$ 和 $f_n$ 即可。
时间复杂度 $O(\log n)$ 。
UPD ON 12.7
晚上七点讲题+滚榜。
吃完饭直接回了宿舍，翘掉了选修课。
坐在电脑前，开始等待讲题。
C 题听了后才发现我做法有多 sb ， 哈哈哈。
直接就是 $\sum cnt_i$
我这个做法属实有点 sb 。
开讲 E 题了。
发现是从位置的角度来考虑的。
E 经典问题
考虑从左到右决定每个位置填入哪一个数。
对于位置 $i$ ，可以填入其中的数为所有满足 $l_j\le i,r_j\ge i$ 的 $j$ 。
贪心：应该填这些数中 $r_j$ 最小的那个。
证明，直接贴 ppt 吧（
所以可以从 $1$ 到 $n$ 每个位置扫一遍，每个位置找 $r_j$ 最小的 $j$ ，这样直接写的话是 $O(n^2)$ 的，肯定 TLE。
考虑用优先队列优化，先把限制按 $l$ 从小到大的顺序排序，然后在扫位置的过程中，把 $l$ 小于等于当前位置 $i$ 的 $r_j$ 全都 push 进优先队列，然后直接取出队头放到当前位置即可。
若过程中队列为空或者队头的 $r$ 小于当前位置，那么说明无解，输出 -1 。
G 最大分割
要求最大子串长度与最小子串长度之差最小，那么意味着子串长度要么是 $\lfloor n/k\rfloor$ ，要么是 $\lceil n/k \rceil$ （ $n\bmod k$ 个 $\lceil n/k \rceil$ ，$k-\lceil n/k \rceil$ 个 $\lfloor n/k\rfloor$
设 $dp[i][j]$ 表示将字符串 $s[\dots j]$ 分为 $i$ 个子串能得到的最大价值和，则
那么问题就是如何求出 $val$ 了。
对于一个串，从前往后扫，设当前字符为 $c$ ，那么 $c$ 增加的贡献即为当前位置到上一个 $c$ 出现的位置的距离，所以维护每个字符出现的上一个位置，那么即可 $O(n^2)$ 求出所有子串的 $val$ 。
求出了 $val$ 后直接 $O(nk)$ 进行 DP 即可。
时间复杂度 $O(n^2)$ 。
I 正因子乘积
有
求所有的正因子乘积，考虑质数 $p_i$ 在答案中的幂次。
那么答案便是
代入
则
故取模后为
$N$ 不是完全平方数，所以必然存在一个 $m_j$ 为奇数，所以 $2 \mid \prod_\limits{j=1}^k(m_j+1)$ 。
所以做 $k$ 次快速幂即可。
或者还可以用欧拉定理，这样只用做一次快速幂。
K Hope
感觉不是现在的我能解决的问题。
贴个题解吧。
总结
发现封榜后的策略有些问题。
不应该去死扣 E 题。
感觉当时如果去做 J 题的话应该是能做出来的。
I 题当时其实看了看，计算方法其实也得出来了，但是当时就在考虑这个 $N$ 是不是要构造出来结果这个 N 事实上是唯一的 ，所以就放弃了。往下推推说不定能发现其实与 $N$ 是无关的。
总之就是菜。
讲完题就是激动人心的滚榜环节了。
rk4 ，挺好，一等奖第一 （
然后学长推荐我去找 rk3 和 rk10 组队，发现都是浪潮 ACM 组的。（事实上 rk2 也是
主动加了好友，成功组了队。
社恐的巨大突破！
抱紧 rk3 的佬的大腿（
rk10 的这位是零基础的 Orz，天赋真好。
希望能一起努力，在 acm 这条路上走下去吧！
