s5o 时隔一年复活状态修复过程记录
zzx0102
·
·
个人记录
同步发表于 cnblogs
1.6
T1 傻子都会。
T2 高级数学题，不会。
T3 线段树维护一个区间做的工序，pushdown 比较好实现，注意维护糕点彻底废了的情况。
赛时 100+20+70=190，rk2，但是 T2 想不到预处理，怒挂 40pts。
Liujiaxin 怎么这么强，给 Liujiaxin 磕头了/bx /bx。
rating：1310\rightarrow1513
1.7
T1 想到平衡树想不到权值树状数组，被核膜 2log BIT 爆踩，怒挂 50pts。
T2 傻子题，开个队列随便搞我却不会，再挂 50pts。
T3 神秘树形 DP，我肯定不会。
赛时 50+50+0=100，rk5，ljx 怎么又 AK 了。/bx
rating：1513\rightarrow1573
1.15 ~ 1.17
期末考，但是生物倒三，甚至比语文都差。
1.19
从今往后都只有小基班。
T1 唐诗物理题。
T2 逆序对判断无解然后冒泡乱搞能过，不知道为啥。
T3 单调队列优化 DP 我都不会，已经被初二大神单调队列了。
T4 神秘状压 DP，我肯定不会。
赛时 100+100+35+10=245，rk1，拜谢 ycy 用正解过了 T2。
rating：1573\rightarrow1730
1.20
T1 神秘找规律，大概和进制有关，推一推就找到了。
T2 暴力 DP 可过，我没过，望周知。
T3 RBIT 傻子题，拜谢 zzx 爆切权值线段树。
T4 直接 CV 题目给的 code 拿了 30。
赛时 100+40+100+30=270，rk1。膜拜巨佬 ymz 和 tyh 过了 T2。
rating：1730\rightarrow1835
1.21
换成 J 组模拟了，不想写。
unrated 了，rk2。
1.22
还是 J 组模拟，但是 T1 不开 long long 不特判翻车了，怒挂 20。
T2 非常唐，T3 用个 multiset 模拟一波就完事了。
T4 好像是余弦定理加上 S=\dfrac{1}{2}ab\sin C 找到夹角正弦值最大，然后枚举 a,b，后面不会了。
好像大家都过了 T1。
赛时 80+100+100+40=320，rk1。
rating：1835\rightarrow1915
五场合计升了六百多分，状态保持地还算不错（主要是一起打比赛的人变了）。
1.23
被 TheShuMo 和 Scene 还有 Qshuqi 大神炸鱼了，%%%%%%%%%%%%%%%，我是唐诗。
罚时惨败 qsq 2h，喜提 rk4。
T1 n,m\le 10，一开始误导了我正解的复杂度，但是后面发现不会 \mathcal{O}(n!m) 之类的做法，结果发现可以神秘 \mathcal(n^7) 记忆化搜索，好像也可以直接 DP。
T2 看见删除想到可以离线反过来加边，然后暴力 Floyd 可做，复杂度 \mathcal{O}(n^3)，直接秒了。
T3 写了神秘 25 分暴力，T4 一点不会。
这几天 S 组模拟赛加上两次正式的 CSP-S 的 T4 一共喜提 0+0+10+30+0=40 分，还是太菜了。
赛时 100+100+25+0=225，rk4。拜谢 TheShuMo 和 Scene 过了 T3。
rating：1915\rightarrow1913，如果罚时战胜 qsq 的话能上分的。
1.24
又被 TheShuMo 和 Scene 炸鱼了。
T1 枚举虱子对答案的贡献，先搞下来虱子出现的信息，然后排个序，差分一下，然后用异或前缀和统计只有一个信息对应这一天的信息编号，统计一下就完事了。
Scene 大神是枚举每一天对答案的贡献，然后去找这一天这只虱子只有一条信息的答案，反正也差不多，%%%。
T2 只会 \mathcal{O}(2^nn^3) 的做法，卡卡常能过 n\le 16，喜提 40。
T3 好像卡常能过。拜谢 TheShuMo 卡常过了 2s。只能说人唐常数大。
T4 直接 01 背包，但是我没有发现背包大小只有 5n 而不是 x，怒挂 20。
赛时 100+40+40+60=240，错失反杀 TSM 和 Scene 的绝佳机会。
TheShuMo 大神 100+0+100+60=260，Scene 巨佬 100+0+60+80，但是最后罚时惜败 Scene 1.5h，喜提 rk3。
致敬传奇线段树分治 -296 巨佬 qsq。
rating：1915\rightarrow1947，不知道为啥到了榜七，但是明天 ljx 大神 WC 结束强势回归，又要被炸鱼了，到时候要是拿个 rk5 可要掉大分了。
1.25
今天没被炸鱼 /bx
T1 写了 \mathcal{O}(2^n) 暴力，但是 tyh 写了 n^2 的，膜拜。
T2 不难发现后手不能改变两个不互质的数的先后顺序，所以先手需要把不互质的数对中小的数卡在前面，然后先手可以直接把序列从小到大排，这样小的数一定会卡在前面。
我们找到所偶遇不互质的数对，建立有向边（小的一定在大的前面），后手用 priority_queue 拓扑排序即可做到字典序最大。
T3 不会，写了暴力，而且忘记判重边保龄了。
T4 打了 \mathcal{O(nq)} 暴力。
% zzx 爆切 T2。
赛时 20+100+0+21=141，rk1。
rating：1947\rightarrow1998。
下午 lg gks，100+100+0+26，rk21，上大分。
放个小基班所有人每天的内部排名（不算炸鱼的），这样有助于 TSM 等巨佬判断谁有实力（反正我肯定没有）。
| 1.19 |
1.20 |
1.22(pj) |
1.23 |
1.24 |
1.25 |
| sto_5k_orz |
1 |
1 |
1 |
1 |
1 |
1 |
| bbbzzx |
6 |
2 |
9 |
3 |
3 |
2 |
| yemengzhi |
9 |
6 |
8 |
6 |
4 |
10 |
| YDMaYi |
5 |
5 |
5 |
6 |
7 |
7 |
| Dicer_L |
7 |
8 |
10 |
9 |
7 |
7 |
| tyh_27 |
4 |
3 |
3 |
2 |
2 |
3 |
| 54ycy |
2 |
7 |
2 |
4 |
10 |
5 |
| ljc_07 |
10 |
10 |
4 |
8 |
6 |
6 |
| fly_fire |
8 |
9 |
6 |
10 |
7 |
9 |
| lzh301 |
3 |
4 |
6 |
5 |
5 |
4 |
名次总和不想算，大概 tyh 第二。% tyh。
bbbzzx、tyh27 和 54ycy 一人拿了两次单场第二，%%%
寒假还有一波集训，估计还有比赛。
综上所述，前半期我没有打出任何 pj 难度以上的算法（RBIT 板子不能算），我就是 fw。
2.6
开场半个小时后才发现有比赛。
T1
我们令 x^2-y=a^2，移项，得到 y=(x-a)(x+a)，显然 x-a\le \sqrt n，直接枚举 x-a 即可。
T2
先进行一次差分，得到差分数组 b，然后任务就是给一个点 +x，另一个点 -x，最后前 n 项全为 0。
我们定义一个 dp_i 表示将状态 i 包含的数全部清空为 0 的最小步数。
然后考虑如何从 dp_{i-2^j} 转移至 dp_i。
如果 b_j=0，那么可以直接转移过来。
如果这些 i 包含的所有位置的差分值之和为 0，可以发现最后把所有数赋值成一样的之后不用再全变为 0 了，所以也可以直接转移。
否则加个一。
T3 不难发现给的那个 G(i,j) 是可以快速算的，复杂度应该是 O(1) 的。
所以我们直接枚举 y 和 \lfloor\dfrac{x}{y}\rfloor，然后直接算 G(x,y)，枚举 x，找到 g(x,y)=G(x,y)，就可以得到方案数非常小，只有 25n 不到。
赛时数组只开了 20n 挂了 10 分，好像直接开大会 T，还要加快读。
赛时 100+100+90+0=290，rk1，算是比较好了。
rating：1998\rightarrow2056
2.7
寄麻了，被初二爷单调队列了。
T1
明显的背包，不难发现回文数只有 500 个，直接 O(nm) 的背包就完事了，但是我写了前缀和优化 DP，记 dp_{i,j} 表示和为 i，最大的回文数为 j 的方案数，然后前缀和优化一下，也能过。
T2
不会，写了特殊性质（但是没有写 O(na) 暴力，因为 a\le 10^9）。
T3 看不懂，T4 写了暴力。
最后 100+20+0+40=160，rk3，被初二爷单调队列了 5 分。
T2 O(na) 暴力能多过一个点，T3 全输出 -1 有 5 分。
拜谢 ycx2010 T4 打了 70 分。
rating：2056\rightarrow2061。
2.8
小基班寄麻了，怒拿 rk6。
T1
非常简单，这个不会可以去喂猪了。
T2
我们令 g=\gcd(n,k)。
不难发现当 g=1 时无论 s 的值是几答案都是 \sum\limits_{i=1}^n a_i，g>1 时周期是 \dfrac{n}{g}。
当 s 和 g 是定值时，可以发现单个周期内经过了 i 当且仅当 i\equiv s\pmod g，而且每个点的次数都不变，所以答案只和 s 和 g 有关。
由于 g\mid n，我们可以以 \mathcal{O}(d(n)) 的复杂度枚举 g，然后预处理每种 s 的和，单点修改的时候枚举 g 修改和就可以了，对于每个 g，我们用 multiset 统计最大值，最后乘周期出现的次数就可以了。
T3 不会 AC 自动机，T4 写了 $30$ 的哈希暴力结果 string 没 resize 变成 $10$ 了，草。
rating：$2061\rightarrow 2017
2.9
红温场，又寄麻了，挂了比前两场加起来都多的分，但是 rk2 了（不挂 rk1 了）。
T1
不难发现答案只能是 0、1 或 2。
$1$ 的情况是满足割一个点就行了，我们用 DP 统计 $(1,1)$ 到 $(n,m)$ 的方案数 $d$，然后统计 $(1,1)$ 到 $(i,j)$ 的方案数和 $(i,j)$ 到 $(n,m)$ 的方案数 $a$ 和 $b$，然后乘法原理得从 $(1,1)$ 经过 $(i,j)$ 到 $(n,m)$ 的方案数为 $ab$，当 $ab=d$ 时 $(i,j)$ 割掉 $(i,j)$ 就够了。
然后有个 sb 写了这个 DP 我不说是谁。
```cpp
f[n][m] = 1;
for(int i = n; i; i--) {
for(int j = m; j; j--) if(!wall[i][j]) {
f[i][j] = f[i + 1][j] + f[i][j + 1];
}
}
```
他甚至算 $(1,1)$ 到 $(i,j)$ 的时候都写对了。
```cpp
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) if(!wall[i][j]) {
if(i == 1 && j == 1) continue;
dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
}
}
```
因为这个怒挂 $70$。
T2 是 P9401 原题。
我们可以先全选 $b_i$，然后只能选 $a_i$，这样答案一定不大于 $a_i$。
如果两个 $(a_i,b_i)$ 和 $(a_j,b_j)$，当 $a_i=a_j$ 时，可以将两个数对合并为 $(a_i,\gcd(b_i,b_j))$，因为选一 $a$ 一 $b$ 肯定不如两个 $a$。
然后枚举答案 $ans$，当 $ans\mid a_i$ 时，一定可行，然后我们记 $B_{a_i}=b_i$，对 $B$ 数组建立 ST 表，然后看 $[k\times ans+1,(k+1)\times ans-1]$ 的 $\gcd$ 能不能被 $ans$ 整除即可。
然后各种神仙乱搞做法都能过，我强烈怀疑数据是不是就是生成个随机数然后乘个 $g$ 就完事了，甚至 $\mathcal{O}(2^n)$ 都能过 $10^6$。
T3 直接暴力 DP 有 $60$ 分，T4 权值树状数组也有 $60$ 分，但是有个 sb 没开 ll，我不说是谁。
最后 $30+100+60+30=220$，罚时大胜 bbbzzx 和 zhuhangyu，喜提 rk2。
% ycx2010 连续三天榜一。
zhenghong 最后几秒把 T3 交 T4 上来了，绷。
rating：$2017\rightarrow 2053
2.10
又 tm 寄麻了，200\rightarrow 110，并列第一但是 OI 赛制有罚时变成 rk6 了，也是第一次没有拿到小基班 rk1（bbbzzx 太巨了）。
T1
显然每个串自己的逆序对是必然要算的，这个不重要。
记 o_s 为 s 内 1 的个数，z_s 为 s 内 0 的个数。
对于两个串 s_1,s_2，将 s_1 排在 s_2 前面的逆序对数是 o_{s_1}z_{s_2}，s_2 排在 s_1 前面的逆序对是 z_{s_1}o_{s_2}，比较大小即可，用这个拿来贪心，不难证明是对的。
T3
链式前向星记住了清空 head 记不住清空 idx，然后没加快读，100\rightarrow 10。
我们令两个人奔袭的周期是 len_1 和 len_2，这是路径长的两倍。
我们考虑对每个点 i，得到 Alice 和 Bob 经过的时间，都用 k_1\times len_1+d_1 和 k_2\times len_2+d_2 表示（d_1 和 d_2 都是常数），由于在 i 这个点这里相遇，所以
k_1\times len_1+d_1=k_2\times len_2+d_2\\
k_1\times len_1-k_2\times len_2=d_2-d_1
很明显这是 exgcd 的形式，而且 len_1 和 len_2 是定值，可以预先求好 xlen_1+ylen_2=\gcd(len_1,len_2) 的解，然后乘一下，甚至都可以不用 exgcd，直接暴力也没事。
注意到 d_1 和 d_2 有两种情况（回来的 d 是不一样的），一共四种情况，全算一遍。
复杂度 \mathcal{O}(nq)。
超级唐诗 5.0k 代码
rating：2053\rightarrow 2004，写出 T3 就能上大分了。
2.11
30pts 惜败 ycx2010。
过了 T3 没过 T1 是什么水平。
T1
不会，不知道为什么打了链表还是 TLE。
T2
不会，写了 \mathcal{O(2^nm)} 的分，m 是非 0 的数的个数，比较简单骗了 70。
T3
求
\sum\limits_{i=0}^{n} (-1)^i\gcd(n,i)
考虑枚举 $\gcd$，令 $\gcd(n,i)=g$。
如果 $n$ 是奇数，那么所有 $g$，$(-1)^i$ 是 $1$ 和 $-1$ 的情况是一样的，所以答案是 $0$。
否则，根据 $g$ 的奇偶性可以判断 $\dfrac{n}{g}$ 的奇偶性（实在不行你就算 $\dfrac{n}{g}$ 都行），然后按照 Longge 的问题做就完事了。
虽然 $n\le 10^{12}$，复杂度是 $\mathcal{O}(d(n)\times \sqrt n)$ 的，但是 $\mathcal{O}(\sqrt n)$ 是算 $\varphi$ 的，如果 $d(n)$ 特别大那么 $n$ 的小质因子就特别多，所以 $\varphi$ 就跑不满。如果 $\varphi$ 跑得满说明 $d(n)$ 不大，所以复杂度可以接受。
最后 $50+70+100+0=220$，rk2，但是 T1，T2，T3 得分单调递增是什么成分。
但是又被 ycx2010 杀完了，我是 fw。
rating：$2004 \rightarrow 2053$。
ycx 有一场看题没交但是现在已经 $2013$ 了，幸好没有下一场，不然我就寄了。
初二巨佬 zcq、zyx、hlc 都要来小基班，%%%。
### 2.17
虽然这场前年打过，但是打得比前年都低，喜提小基班 rk7，rating -154。
就这水平还能 CSP-S 1=，真是个笑话。
T1 非常简单，把每个面包当成坐标系的一个点，斜率最大的直线一定是 $x$ 相邻的两个点，新插入一个点的时候直接和边上两个连线算一下斜率就完事了。
我不能理解为什么这种题我都能翻车。
T2 是 CF1710C，但是我不会数位 DP。
T4 本来打了树的分和暴力，结果一个数组开小一个 $\ge$ 写成 $>$ 一分没得。
赛时 $70+10+20+0=100$，rk7，rating -= 140。
真不知道就这水平凭什么能进复赛。
### 5.5
Dicer_L 对着网络最小费用最大流专场。
T1 和 T2 就是板子。
T3 最小割 = 最大流。
T4 经典拆点最大费用最大流。
T5 餐巾计划。
某 sb 将 $i$ 拆成 $2i$ 和 $2i+1$，然后汇点写了 $2n+1$，我不说是谁。
T6 T7 不会。
最后 $100+100+36+100+100+10+2=448$，rk9。
赛时 T3 数组开小了，可以退役了。
rating：$1905 \rightarrow 1852$。
rk6 五题都是是贺的，无敌了。
Dicer_L 喜欢用 AI 生成的代码。
### 7.7
省流：运气非常好。
时隔两个月（说两年也可以）再碰 OI。
T1 纯搞笑题。可以把每条直线的函数表达式都算出来，然后就能发现可以用 $x+y$ 和 $x-y$ 的范围判断。
T2 写了个数据分治，但是不知道为什么 $\mathcal{O}(n^2)$ 能过 $10^5$ 但是 $\mathcal{O}(n\sqrt n)$ 过不了。
正解是 bitset，但是某 sb 没想到，我不说是谁。
如此肺雾，如何 NOIP？
T3 “每个节点最多连接 $3$ 条边”被我略过了，然后可以边三。
注意到两个点之间的最大流最多只有 $3$，不连通说明是 $0$，联通但是不在一个边双说明是 $1$，在同一边双但是不在同一边三说明是 $2$，在同一边三说明是 $3$。
某 sb 订正 T3 的时候并查集没有初始化 $rt_i=i$，好难猜是谁啊。
很显然两个点 $x,y$ 在同一个边三当且仅当删除任意一条边时，$x,y$ 均在同一边双。可以枚举删除的边跑一遍 tarjan，记 $scc_{i,j}$ 表示 $i$ 在删除边 $j$ 的时候所在边双的编号，然后 hash 一下就完事了。
不知道为什么 EK 跑得比 Dinic 还快。
T4 不会，遂输出 $-1$。
喜提 $100+80+45+10=235$，rk7/52，小基班 rk1，运气好了属于是。
### 7.8
省流：$60+60+30+0=150$，rk20/52，小基班 rk3，非常糟糕的分。
T1 纯纯 kruskal 重构树 + 倍增板子题但是我没 AC，望周知。
T2 打出了个 $\mathcal{O}(nP(\sqrt n)\log n)$ 的复杂度没过 $2\times 10^5$，以空间换时间导致的。
T3 P2664 原题，但是只写了暴力和菊花的分。
T4 会第一档但是只有 $5$ 分，所以没写。
### 7.9
省流：打得非常烂，绿题都没切。
T1 非常简单的一个前缀和优化 DP。
T2 看到 $k\le 10^{18}$ 不难想到倍增，但是赛时拼尽全力无法战胜交了暴力还忘记 $k=0$ 的时候也要取模了，赛后 20min 终于战胜。
T3 曼哈顿生成树模板题，但是我咋啥都不会。
遂写了货车运输拿了 $40$ 分，反正是 $\mathcal{O}(n^2\log^2n)$ 的所以没写倍增直接暴力爬树了。
T4 暴力有 $16$ 分，但是在看 T2 所以输出样例 $1$ 分跑路。
最后 $100+60+40+1=201$，rk12，小基班 rk1。T2 但凡记得取模就有 $70$ 了，这样就能 rk10 了。
绿题都场切不了还咋 NOIP 啊。
### 7.10
啥也没修复，所以今天的模拟赛记录被我吃了。
看题要用眼，想题要用脑。
### 7.11
生日场，靠着生日 buff 现场发明了笛卡尔树并且在本地跑了 8s 的情况下过了 T2。
最后 $100+100+40+0=240$，喜提 rk8，小基班 rk1。
T1 显然 $n=1$ 和 $n=2$ 的情况是 $1$，然后我们令 $P_i$ 为 $n$ 个点在同一半圆上的概率。
很显然我们需要前 $n-1$ 个点在同一半圆上，然后前 $n-1$ 个点连成的半径相互所构成的圆心角的期望是 $\dfrac{n-2}{n-1}\pi$（没有也用不着任何严谨的证明，看出来就行了），然后第 $n$ 个点要在半圆上必须在 $n-1$ 个点中间或两侧，且与最远端的圆心角小于 $\pi$，可得 $P_i=P_{i-1}\dfrac{n}{2(n-1)}$，裂项可得答案是 $\dfrac{n}{2^{n-1}}$。
T2 现场手搓出了笛卡尔树，但是寄搜常数巨大，本机跑了 8s，不过评测姬上过了。
赛时想的是算每个点的贡献。
令 $dp_{l,r,k}$ 表示 $[l,r]$ 区间内选了 $k$ 个数的答案的最小值。
然后对于一段区间找到最大值的位置 $mid$，然后枚举左右两边的数的个数，分治下去，不难发现状态数只有 $n^2$ 种，加个记忆化就能过了。
记录答案的数组用了个 unordered_map，然后赛时本机跑了 8s（赛后发现编译器忘记开 O2 了），然后一直回忆 custom hash 怎么写，甚至尝试手写哈希表。不过最后我认为本机 8s 评测姬上肯定过不了，拿个暴力分认了算了，没想到过了，fxt 大神的评测姬还是良心啊。
本质相同的正解：先建笛卡尔树，不难发现 $f(l,r)$ 就是 $a_{\operatorname{LCA}(l,r)}$，然后树上 DP 一下就行了。
怎么大家都会 T3，数据随机可还行，所以不难发现只取代价最小的 $200$ 条边可过。
T4 是集训队胡策题，弱化版甚至是个黑。
集训之前定的目标是要拿 15 天的小基班 rk1，现在 5 天了只拿了三次小基班 rk1，还得努力啊。
大基班都是巨佬，我基本上比他们四个都低，退役两年确实影响太大了。
### 7.12
啥也没修复，所以今天的模拟赛记录被我吃了。
看题要用眼，想题要用脑。
### 7.13
nmd T2 是个绿题你 tm 甚至还做过你还 tmd 过不了，你还是赶紧退役吧。
T1 是个整除分块板子。
T2 原题 P8097，注意到我 2023 年就过了这题，所以我这两年越来越菜了。
T3 是个线段树合并优化 DP，普及组选手表示不会。
T4 全场加起来拿了 10 分，还是个打表的。
最后喜提 $100+25+15+0=140$，rk18。
nmd 赛时过了 16 个 T2 我都没过，被绿题薄纱了你还咋 NOIP 啊？
### 7.14
你 tm 能不能憋 `// freopen` 了。
T2 `// freopen` $40\rightarrow 0$，rk12 -> rk26。
$100+0+0+0=100$ 很好玩吗。
### 7.15
黄蓝蓝绿，但是喜提 $100+75+15+0=190$，成功打出了普及组小朋友都不如的分数。
T1 唐题。
T2 可以拆贡献然后推出 $O(n^2)$ 的组合数的式子，但是我不会数学，所以优化不来，拜谢 Tyih 算出来了。
被打表找规律老哥爆踩了 /fn。
T3 是个树状数组，但是我忘记了有个东西叫树状数组了。想到了 $n\le 2000$ 是 bitset，但是由于暴力调了 1h 所以还没有很推明白就结束了。
T4 看错数据范围导致没开 long long，糖丸了。
最后喜提 $100+75+15+0=190$，rk11。
上 225 不是有脚就行。
九天总榜出了，挂的相当多，但是有 rk13，小基班 rk1。
差强人意吧，退役两年能和 Vector_net 和 hlc110516 平分秋色已经很不容易了。
### 7.16
省流：T1 黄题做了 2h，T2 遍历图不用 dfs，T3 还没看对题比赛就结束了。
喜提 $100+60+0+10=170$，rk10，我比普及组小朋友还菜。
但是不知道为什么很多人没有战胜黄题，所以十天总榜拿下 rk11。
Feather_Moon 270pts rk2，还有 10 天，100 分 / d 的分差已经足够抹平我前 9 天的总分了，总榜别被战胜了就行了吧。
T1 可以想到倒着做，非常唐。
T2 不难想到并查集（我都想到了），然后可以遍历整个图连接，不要 tmd 枚举每个点合并若干轮，而且 tmd 要开 ll（我 tm 开了就过了）。
T3 神秘组合数前缀和 + 莫队优化，这玩意能想出来莫队真的是太巨了，不过我相信 bbbzzx 一定能 AC 这道题。
式子推出来是 $\sum\limits_{i=1}^m \dbinom{n}{i}$，然后莫队转移 $m$ 是容易的，转移 $n$ 的时候可以用杨辉三角 + 前缀和优化做到单次 $O(1)$，所以总复杂度是 $O(m\sqrt n)$，但是这玩意谁 tm 能想出来莫队啊。
T4 不会。
### 7.17
这啥玩意啊，咋就 rk3 了。
T1 在 $n>m$ 时，打个表发现答案是
$$\dbinom{n}{m+n}-\dbinom{n+1}{m+n}$$
然后某 sb 没判 $n=m$，我不说是谁。（但是好像有两车人没判）
T2 树状数组，要让 $i$ 满足就要把 $i$ 前或后所有 $>a_i$ 的数交换掉，然后两种情况取个 $\min$ 就好了，算这个东西可以用树状数组。
T3 只会 $O(2^nn^2)$ 的 $40$ 分做法，但是好像就是这 $40$ 分拿下了 rk3。
T4 写了个树状数组 + 二分（不太会 RBIT 求 mex 导致的），反正你就说是不是拿了 $10$ 分吧。
T4 原题 P12485，我肯定不会。
最后 $80+100+40+10=230$，不知道为啥 rk3，小基班 rk1 了。
### 7.18
3.5h 狂攻 T2 获得 $30$ 分的高分，喜提 $100+30+70+0=200$，小基班 rk2，总榜 rk18，拜谢 Tyih 过了 T2，Feather_Moon 过了 T3，被单调队列了。
T1 傻子题。
T2 可以想到按照奇偶性做，然后发现是个括号序列问题，开个栈就维护类似于括号匹配的东西，中间统计一下最值就可以了。
T3 是个容斥。
### 7.19
寄飞了，T2 纯唐题挂成 60，rk7 $\rightarrow$ rk20。
为啥大家都过了 T1、T2，之前放黄题也没这么多人切啊。
Z 老师还是太会造数据了。
红温了，今天模拟赛记录被我吃了。
### 7.20
T1T2 都保龄还算人类吗。
$0+0+71+10$，rk30，总榜成功从 rk9 掉到 rk11。
### 7.21
T1 又保龄了，你 tm 赶紧退役吧。
$0+70+80+29=179$，本来 $279$ 是由 rk3 的，结果只有 rk19。
`#define int long long` 开到快读下面的是个人物。
[T3 题解](https://www.luogu.com.cn/article/yla37gh5)
### 7.22
被 T3 和 T4 创飞了。
$100+100+6+0=206$，rk19。
T1 纯唐，T2 纯唐（赛时有二十多个人场切了 T2，四十多人场切了 T1）。
A_zjzj：这个 T2 的难度和 NOIP T1 差不多。
T3 神秘随机化乱搞，甚至不需要会判偶环就能过。
彻底红温了。
### 7.23
又被 T3 创似了。
T1 唐题。
T2 $dp$ 前缀和优化简单题，我没做出来。
T3 也是个题。
T4 打了 $O(n)$ 暴力，打表打不出来，痛失 50pts。
喜提 $100+24+0+30=154$，rk14。
### 7.24
被 T1 唐诗记忆化创似了。
被 T2 唐诗树状数组创似了。
T3 两年前做过，那个时候看到题解写了个线段树分治就不想看了，结果打完听大神 wangkangyou 讲分治找中转点我才恍然大悟，谁 tm 说这题要线段树的来着。
T4 一点不会。
$40+50+20+20=130$，rk19，就这个 B 分数也配打 NOIP。
总榜被大神 wangkangyou 反超，现在第 12 了。
### 7.25
$100+100+0+50=250$，rk14，我是 250。
T1 唐诗树状数组维护题。
T2 唐诗贪心题。
T3 赛时做了 40min（前面俩唐题做了 3h 我太唐了没办法），甚至没有战胜 20pts。
T4 神秘 exkmp，不会。
### 7.26
成功被数学题创死。
T1
赛时甚至没有想到矩阵快速幂的 60pts。
T2
赛时甚至没有想到分块打表。
T3 T4 赛时甚至没有看。
喜提 3= 的分。
总榜也是成功掉到了 rk13，小基班 rk1。
qzez 小基班（马上大基班了）成功被义乌同届爆踩。
### 10.12
停更这么久仅仅是因为他们做的模拟赛是我两年前做过的。
$100+100+10+0=210$，rk5，被 ycy 爆踩。
T1 写假了，但是数据更假，反正我过了。
T2 考虑暴力，记 $dp_{i,j}$ 表示该字符串中出现子序列 $p[i+1,j]$ 的方案数。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 110, mod = 998244353;
int n, m; string s, p, t;
struct str {
int dp[N][N];
void init() {
for(int i = 0; i <= m; i++) {
for(int j = i + 1; j <= m; j++) dp[i][j] = 0;
}
for(int i = 0; i <= m; i++) dp[i][i] = 1;
}
};
str add(str s, char ch) {
str ans = s;
for(int i = m; i; i--) if(ch == p[i]) {
str now = ans;
for(int j = 0; j < i; j++) {
now.dp[j][i] = (now.dp[j][i] + ans.dp[j][i - 1]) % mod;
}
ans = now;
}
return ans;
}
str merge(str s, char ch) {
str a = add(s, ch);
str ans; ans.init();
for(int i = 0; i <= m; i++) {
for(int j = i + 1; j <= m; j++) {
for(int k = i; k <= j; k++) {
ans.dp[i][j] = (ans.dp[i][j] + 1ll * a.dp[i][k] * s.dp[k][j] % mod) % mod;
}
}
}
return ans;
}
signed main() {
freopen("multiply.in", "r", stdin);
freopen("multiply.out", "w", stdout);
cin >> n >> m >> s >> p; p = ' ' + p;
str ans; ans.init();
for(int i = 0; i < n; i++) {
ans = merge(ans, s[i]);
}
cout << ans.dp[0][m] << '\n';
return 0;
}
```
然后在合并串的时候合并一波 DP 状态，只需要写串和字符合并、串和串合并就行了。
T3 神秘数据分治出错，$20\rightarrow 10$。虽然但是好像 $220$ 也是 rk5。
由于写完 T2 还有 6min 所以没有写 T4，实际上 T4 暴力傻子都会。
### 10.30
$10+100+12+0=122$，rk7，我是这个。
T1 神秘简单绿题写挂。
T2 考虑启发式合并，如果会就秒了。
T3 将 $8$ 步分成从起点和终点各走 $4$ 步，然后按照 $k$ 的情况分讨，拜谢 bbbzzx 赛时过了 $k=6$ 的档。
### 11.16
模拟赛请注意起床时间。
8:00 开始的模拟赛 10:30 起床，我无敌了。
$100+100+50+5=255$，并列 rk2，rating：$1847\rightarrow 1929
起床速通唐诗 T1，然后 20min 写完 T2 线性。
第一段前缀和，第二段拆贡献。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000010;
int dp[N], n, p, sum[N];
signed main() {
ios::sync_with_stdio(0);
cin >> n >> p;
for(int i = 1; i <= n; i++) {
dp[i] = (sum[i - 1] + 1) % p;
int k = __lg(i);
for(int j = 0; j < k; j++) if(i & (1 << j)) {
dp[i] = (dp[i] - (sum[(1 << j) * 2 - 1] - sum[(1 << j) - 1]) + p) % p;
}
sum[i] = (sum[i - 1] + dp[i]) % p;
}
cout << sum[n] << '\n';
return 0;
}
```
T3 50pts 是 Nim 游戏，然后考虑直接倍增维护答案。
啥都可以二进制拼起来。
T4 不会。
rating：$1844\rightarrow 1929
11.17
T1 纯模拟。
T2 考虑将每个字符串用二进制表示，然后 bfs 找状态，将数字取反找最近的就说明原数是最远的。
T3 神秘树状数组，T4 神秘矩阵优化套线段树，我不会。
rating：$1929\rightarrow 1953
11.18
T1 神秘原。
T2 没找到规律，我是这个。
T3 预处理阶乘不取模，我是这个。
rating：$1953\rightarrow 2005
11.20
T1 m 写成 n 怒挂 70，也算是还 CSP-S 2024 的债了。
T2 n\le 3\times 10^5 开了 1e5 的数组，又挂 70。
T3 人唐常数大没卡过去，T4 暴力 45pts。
rating：$2005\rightarrow 1808
11.21
T1 傻子题，T2 初一写过。
T3 先删黑子树，然后手搓一下发现答案跑数奇偶点、直径有关。
然后某 sb 求直径写挂了，我不说是谁。
T4 O(n^2) 乱搞冲过了随机数据，喜提 70。
rating：$1808\rightarrow 1926
11.24
NOIP 模拟赛第一次上 300（不是第一次场切 T3），记之。
T1 过于唐。
T2 直接找最长的不交的数值相同的段即可，不难发现 DP 可做。
T3 神秘人类智慧，总之一定是头顶数字最大的那个人先知道。
然后可以根据手搓过程递归，个人觉得统计转了几圈比较方便。
#include<bits/stdc++.h>
using namespace std;
const int N = 510;
int t, x;
struct node {
int a, b, c;
};
vector<node> ans;
int dfs(int x, int y, int z) {
// cout << "x = " << x << ' ' << y << ' ' << z << '\n';
if(x == y || y == z || z == x) return 0;
int mx = max({x, y, z});
if(mx == x) return dfs(abs(y - z), y, z) + 1;
else if(mx == z) return dfs(x, y, abs(x - y));
else return dfs(x, abs(x - z), z) + (z > x);
}
int main() {
ios::sync_with_stdio(0);
while(cin >> t >> x) {
if(t == -1 && x == -1) break;
ans.clear();
for(int i = 1; i < x; i++) {
int ret = 0;
if(t % 3 == 1) {
ret = dfs(x, i, x - i);
if(ret == t / 3) ans.push_back({x, i, x - i});
}
if(t % 3 == 2) {
ret = dfs(i, x, x - i);
// cout << i << ' ' << x << ' ' << x - i << ' ' << ret << '\n';
if(ret == t / 3) ans.push_back({i, x, x - i});
}
if(t % 3 == 0) {
ret = dfs(i, x - i, x);
// cout << i << ' ' << x << ' ' << x - i << ' ' << ret << '\n';
if(ret == t / 3 - 1) ans.push_back({i, x - i, x});
}
}
cout << ans.size() << '\n';
for(auto it: ans) {
cout << it.a << ' ' << it.b << ' ' << it.c << '\n';
}
}
return 0;
}
rating：$1926\rightarrow 1991
11.25
神秘线下模拟赛，来自义乌中学。
已严肃完成《数据有梯度》大学习。
T1 神秘构造，直接取质因子只有 2,3,5,7,11 的数，然后统计一波，没到一半的质因子给他乘到一半，反正够用。
T2 神秘分治。考虑画笛卡尔树，然后记节点 u 的左子树大小为 L_u，右子树大小为 R_u，可以发现：
\sum\limits_{i=1}^n \min(L_i,R_i)=\mathcal{O}(n\log n)
证明思想类似于启发式合并，大概就是完全二叉树能取到最大。
于是枚举节点，计算每个较小子树中的 a_j，在较大子树中有多少数满足 a_k\le \dfrac{a_i}{a_j} 即可。这个可以离线二维数点解决。
注意到每个点的子树对应的都是一个区间，所以只需要单调栈求出左右儿子对应的区间就行了，不需要画出笛卡尔树。
总复杂度 \mathcal{O}(n\log^2n)。
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define mk_p make_pair
#define fi first
#define se second
#define int long long
unordered_map<int, int> tr;
const int N = 100010, M = 1e9 + 10;
int lbt(int x) {return x & (-x);}
void add(int x) {
// assert(x);
for(; x <= M; x += lbt(x)) tr[x]++;
}
int ask(int x) {
int ans = 0;
for(; x; x -= lbt(x)) ans += tr[x];
return ans;
}
int a[N], n, tot, le[N], ri[N], m;
pii b[N];
struct Query {
int id, x, flag;
} q[N * 40];
bool cmp(Query a, Query b) {
return a.id < b.id;
}
signed main() {
// freopen("pair.in", "r", stdin);
// freopen("pair.out", "w", stdout);
ios::sync_with_stdio(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) {
while(tot && b[tot].fi < a[i]) tot--;
le[i] = b[tot].se + 1; b[++tot] = mk_p(a[i], i);
}
tot = 0;
for(int i = n; i; i--) {
while(tot && b[tot].fi <= a[i]) tot--;
ri[i] = tot ? b[tot].se - 1 : n; b[++tot] = mk_p(a[i], i);
}
for(int i = 1; i <= n; i++) {
// cout << i << ' ' << le[i] << ' ' << ri[i] << '\n';
int L = i - le[i], R = ri[i] - i;
if(L <= R) {
if(i > 1) q[++m] = {i - 1, 1, -1};
q[++m] = {ri[i], 1, 1};
for(int j = le[i]; j < i; j++) {
// cout << i << ' ' << j << '\n';
q[++m] = {ri[i], a[i] / a[j], 1};
if(i > 1) q[++m] = {i - 1, a[i] / a[j], -1};
}
}
else {
q[++m] = {i, 1, 1};
if(le[i] > 1) q[++m] = {le[i] - 1, 1, -1};
for(int j = i + 1; j <= ri[i]; j++) {
// cout << i << ' ' << j << '\n';
if(i > 1) q[++m] = {i, a[i] / a[j], 1};
if(le[i] > 1) q[++m] = {le[i] - 1, a[i] / a[j], -1};
}
}
}
sort(q + 1, q + 1 + m, cmp);
int ans = 0, j = 1;
for(int i = 1; i <= n; i++) {
add(a[i]);
// cout << i << ' '
while(j <= m && q[j].id == i) {
// cout << "i = " << i << ' ' << q[j].x << ' ' << q[j].flag << '\n';
ans += ask(q[j].x) * q[j].flag;
j++;
}
}
cout << ans;
return 0;
}
注意二维数点之前应该先离散化，但是我懒所以直接写动态开点了。
T3 只会 \mathcal{O}(n^2)，拜谢 bbbzzx 切了。
T4 题都没看，但是拜谢 bbbzzx 切了。