11-5
模拟赛。
以下是 notes.txt。
目前已写：100+31+35+55=221.
目前期望：100+31+35+55=221。
A. 1s/ 256MiB
把每个数转到大于它的概率算出来，然后贪心选大。
B. 2s/ 512MiB
只会暴力。
C. 2s/ 256MiB
算出相邻数字间可以的差（会有两个，可以相等），得到一个长度为 n-1 的序列 B。
B 中的元素都是一个二元组，初始时都取 first。
然后操作等价于任意翻转元素，设最少让所有元素互不相等的翻转次数是 An，那么答案就是 ceil(An/2)。
35 分做法：直接枚举翻转元素。
应该可以转化成图论题的。
D. 3s/ 512MiB
直接 ST 表可以通过前两个子任务，获得 20 分。
Bi=1，直接获取转化后 Ai 的最小值可以通过子任务 3，获得 2 分。
Bi 很大，转化之后，要求最小值最大，发现答案单调不下降，倒着加数就行，带权并查集维护，获得 33 分。
可能可以倍增+根号分治？
以上是 notes.txt。
做题时间：2 小时 30 分钟。
实际得分：100+31+35+55=221，一分没挂，但是排 84 名，一共才 246 人啊。
这场没有发现代码能力的问题。但是思路还是不够开窍。目前在补需要的分（只有一个 T2 AC，因为有了这个总分直接来到了 100+100+35+55=290，应该够用了，当前排行榜排名会到 37），补完了会更新 T2 题解。
T2 题解
二级结论背少啦！机房里一群人长茄的自己不会。
本题二级结论：对于一棵树 T=\{V,E\} 和一个定点 u，在 T 上选一个点 v，使得 u,v 之间的距离最大，那么最大的点一定是 T 上的任意一条直径的两端点之一。
推广一下：对于一棵树 T=\{V,E\} 和一个定点 u，在 T 上若干点组成的集合 S 中选一个点 v，使得 u,v 之间的距离最大，那么最大的点一定是 S 所有点构成的虚树上的任意一条直径的两端点之一。
于是根据这个结论，就可以使用场上想到的一个框架思路了：将点按点权值从大到小排序，加点，维护已加的点构成的虚树的直径，然后对加入点求解答案。权值相同的就先一起加，然后一起求解，加完之后点集合不需要动。
维护直径的方式为：假设直径端点是 x,y，那么加入新点 p 之后，直径的端点就只可能是 x,p，y,p 或 x,y。三个都看看就好了。
11-6
模拟赛，毁了，连签到都没签上。
以下是 notes.txt。
目前已写：20+0+20+10=50
目前期望：20+0+20+10=50
可能有不少的 dp 题。
A. 3s/ 1024MiB
前缀和，有单调性，让分母减得多，分子减得少。
然后没一点用？？？寄。
B. 1s/ 512MiB
完全不会。
C. 1s/ 512MiB
20 分：全排列直接搞。
先从小到大排序。
f[i][j] 表示答案 i，考虑到第 j 个积木是否可行。01 dp。
bitset 必不可少。
D. 1s/ 512MiB
什么样的排列可以用这个栈排序？
换言之，什么样的排列的合法出栈序列是：
1, 2, 3, ... , n？
这样的排列是，对于每一个数，他之后一定是比他小的集合在一起，然后接上比他大的。
10 分：就可以枚举全排列了。
以上是 notes.txt。
做题时长：2 小时 30 分钟。
实际得分：20+0+20+10=50。暴力都难打，毁了。
被这个场创出 ptsd 了。看看能不能补 T1 和 T3 吧。
11-7
模拟赛，毁了，简单题都不会做。
吐槽：这个怎么没有大样例的，差评。
以下是 notes.txt。
目前已写：100+40+0+40=180
目前期望：A+40+20+40=A+100
A. 1s/ 512MiB
猜想答案并不大。
B. 1s/ 256MiB
应该是分治，但我不会。
做法：分治比较路径长短，路径有两个：
a) 从 A 所在层直接到 B 所在层，是两个分治距离+1。
b) 从 A 跨一个再到 B，是两个隔开的分治距离+2+2^(n-当前层)。
C. 1s/ 256MiB
你发现可以只要指定了每个点在第几次走就确定了路线。
20 分：暴力枚举第几次走。
D. 1s/ 256MiB
排序，一个子矩形符合的充要条件是：
这一段序列构成了“类-permutation”。
直接模拟只有 10 分。还要转化。
“类-permutation”的充要条件是：
最大-最小=r-l，这段可以 ST 表。
以上是 notes.txt。
做题时长：2 小时 30 分钟。
实际得分：100+30+20+40=190。笑不活了。
11-11
你看人家鸽鸽，双十一了不去购物在机房里搞那模拟赛，你可千万不能变成那样。
以下是 notes.txt。
目前已写：100+100+30+20=250
目前期望：100+100+30+20=250
A. 1s/ 128MiB
蠢。
B. 3s/ 512MiB
模 1e9+7。
20 分做法：直接 dp。
之后可能需要打表找找规律。
也可能推一点狮子。
A[i][j]=C_{i+j}^j。
然后最优的方案一定是从大的开始往 1 那边走然后下来。
可能要交换一下 n 和 m。这样的话，组合数之和是很好计算的（<= 1e6）。
预处理阶乘以及其逆元就行了。
注意一些可能的特判。
假设 n<=m。
答案 Ans=m+sum{A[1~n][m]}
需要进行一定的约分工作。
C. 1s/ 256MiB
30 分做法：直接暴力。
或许要先看看 b 序列长什么样子，以及 b 序列满足什么特性。
没找到特性。
60 分做法：开线段树。
D. 1s/ 512MiB
20 分做法：直接暴力。
剩下的可能是推狮子，但我不会。
以上是 notes.txt。
做题时长：2 小时。
实际得分：100+100+30+20=250，T3 感觉可以线段树做但是没把握写对。T4 是真的不会做了。
T4 题解
设 g=\gcd(a,b), a'=a \div g, b' = b \div g。于是
而 $(a'+b') \bot a'$ 且 $(a'+b') \bot b'$，所以 $(a'+b') \mid g$ 且 $a'+b' \leq g$。
又 $g(a'+b') \leq n$，所以得出 $a'+b'$ 的范围是 $[2,\sqrt{n}]$。枚举 $k=a'+b'$，那么满足 $a' \bot b'$ 的数对个数是 $\varphi(k)$，合法的 $g$ 有 $\lfloor \dfrac{n}{k^2} \rfloor$ 个，据此计算答案即可。
评价是不会数学的做起来相当困难。
### T3 题解
并不会。
递归处理。
对于偶数部分，答案就是【每个数除以 $2$ 之后的答案】乘 $2$。
对于奇数部分，需要额外减去数的个数。这样维护就行。~~忽略 $60$ 分，感觉是数据问题。~~
## 11-13
不模拟赛。做点题。以下是做题记录，包含自己总结的题解和思考过程（20 分钟没想出来就会去看题解）
### P3722
```plain
P3722
2s/ 500MiB
不存在 Ks -> 所有的 Ks 都不超过两头的，贡献为 p1
最大值在两头值之间 -> 所有的 Ks 最多超过一个头，且有至少一个 Ks 超过一个头，贡献为 p2
其他情况 -> 至少有一个 Ks 超过了两头，贡献为 0
考虑拆贡献，但我不会。
不会就是不会，但是还是得去糊，毕竟 OI 是一个你不想写也得写的东西。
可以是：满贡献（max(p1,p2)）减去那些贡献是 0 的和贡献是 min(p1,p2) 的。
但是如果这样做那和直接求没有任何区别。所以还是得正着求。
20 分钟无果。看题解。
```
### P5012
```plain
P5012
1s/ 125MiB
询问是假的。完全可以从 1 枚举到最大值，算出：
它的分数。生成的区间个数。
然后按区间个数排序。使用 ST 表求解询问。
那么这题难点就变成了如何求出分数和生成的区间个数。
这也不是很难，使用带权并查集求解就好了。
这真的是紫吗？
```
看了题解。出题人卡空间可还行。
那做法差不多也比较明显了。在 notes 的基础上，把 ST 表改成分块 ST 表就行了。于是这题真正的难点（对我而言）就是怎么写分块 ST 表了。
再次更新：分块 ST 表可以不写，普通 ST 该成存信息编号就好了，用时间换空间，~~虽然不是最优解了。~~
### P2518
```plain
P2518
1s/ 512MiB
如果你删了 0 的话那怎么排列都是比原来的小的。
这个咋计算呢？可以统计每个数字的个数，那就是总的阶乘除以每个重复数的阶乘，并且减去签到零。
考虑不删。
还是可以统计数位。然后用 f[i][j][lmt][zcro] 表示第 i 个位置上填入数字 j，有没有达到限度，可不可以用 0（前导零问题）的答案。
转移起来还挺容易的。
然后再注意到，开始发现的那个性质没有用。直接把长度削了之后减去对应的数字，然后 lmt 改成永远是 0 就行了。
```
阅读题解。我去还有高手。
我们思考什么时候这个会比原来的小？当然是一段相同的前缀，一个小的位置，后面随便摆啦！直接枚举前缀和这个小的位置上面填写的数字然后用数论分解法（质因子直接除）就行啦！开始想的性质是有用的。
## 11-14
以下是 notes.txt。
```plain
目前已写：100+?+60+20=180+?
目前期望：100+100+60+20=280
A. 1s/ 128MiB
简单二分答案，注意固定二分次数。
B. 2s/ 512MiB
假设没有金币捡。那么答案是：
F(i,j)=C_(i+j-2)^(i-1)
以 i 为第一关键字，j 为第二关键字排序。
设 f[i] 表示从上一个金币到 i 的答案。
转移的时候，直接从上一个转移，如果上一个过不来那直接输出零。
这个取模很神秘，估计是这题难点。
C. 1s/ 512MiB
肯定是拆贡献，计算每一个点处在几个四元环当中。
30 分：枚举对角线的两个点，然后扫一下两个点的出点，公共点个数取 2 个方案。
60 分：枚举对边（会有 2 条），然后检验四个点是否合法。
D. 2.5s/ 512MiB
把 phi 用那个乘积的形式转化一下就行了。
哇，答案错了。完了。拼暴力了。
```
最终分数：$100+82+80+20=282$。
### P3168
```plain
P3168
2s/ 512MiB
强制在线了。应该需要使用可持久化线段树。
具体咋做呢？
修改操作：每一秒的状态可以直接维护，用双指针辅助调用 modify 函数。
询问操作：主席树上二分。
诶？那我咋写啊？不会。寄寄复寄寄。
```
## 11-18
### P6004
二分答案，并查集。
### P6005
简单 dp。天数上界直接大胆取 $1000$。
### 模拟赛
以下是 notes.txt
```plain
目前已写：20+100+100+0=220
目前期望：20+100+100+0=220
A. 1s/ 256MiB
求 LCIS。
dp 一下，记录 last 就行了吧。
f[i][j] 表示第一个序列以第 i 个元素结尾，第二个以第 j 个元素结尾的答案。
转移的时候，肯定从 i-1, j-1 转。如果不上升不转移。上升判断公共。
并不好转移。完全不会做。寄。
B. 1s/ 512MiB
数的大小关系构成了一棵二叉树。
递归处理，[rt][l][r] 中，rt 放最小的，左半边放后面的下标，右半边放前面的下标。
可以用 siz 辅助处理。
C. 10s/ 256MiB
草莓树，西瓜树，土豆树，字典树，树套树。。。
你知道的，如果 A=B=C 直接输出 A/3 向下取整是可以 30 分的。
我去，蠢题。直接枚举 x,y,z 然后求解最小的最小，再更新答案就行。
D. 1s/ 128MiB
余 30mins: 读错题了。
直接开摆吧。
```
实际得分：$20+100+100+0=220$。
看看 T1 和 T4 咋做吧。需要练习 dp。
## 11-28
上午模拟赛。发现 T1T2T3 全是唐。
看 T4。发现可以先让 $i-1$ 个数加进去，加入第 $i$ 个时可以分别产生 $0$ 到 $i-1$ 个逆序对，显然这样产生排列的个数也是 $n!$。所以原问题等价于：
> 求关于序列 $a_i$ 的不定方程 $\sum a_i = n$ 的自然数解的个数，其中解需满足 $|\{a_i\}|=n, 0 \leq a_i \leq i-1$。
容斥一下做完了。第一次在 noip 难度的模拟赛中通过全部题的样例！期望 $100 \times 4 = 400$！
实际得分：AK 了，爽。
> remind: 考场上还是得像这场 T4 一样谨慎。
## 11-29
写模板。写黄思维题。
口胡 tribool。
写 SCC,EDCC,VDCC。
记得给考场机子测速。
晚上：好冷，是不是又感冒了，喝 999。
## 11-30
GD-0953.
noip。天冷。
进厂。发题。
看看 T1。看明白出题人啥意思了，感觉可以直接贪心，那就比较容易写错，是个 Exschwasion 题，不如放置看 T2。但是还是想了十分钟。很好啊！不会！完蛋了！
看看 T2。没看明白出题人啥意思。而且小 F 知道存在和答案是零是不是矛盾了。怎么是数数。不喜欢。不会。寄。
看看 T3。题面好长但是好懂。好可爱的题，但是不会。发现不会 $k=1$，是不是要以一个丑陋的姿态退役了。
看看 T4。看懂了，但是我咋只会 $8$ 分？啊？是不是真的要完蛋了？
时间已经过去了 $90$ 分钟但是我还一点代码都没写。
上厕所。回来发现 T2 可以做。每个位置的答案存在一定的独立性，可以将每个点的答案乘在一起。那么可以考虑猜构成了。手模大样例前几个测试数据发现有错误，但是为什么 $v=2$ 的时候答案存在质因子 $5$？一定是减了什么东西。什么地方会减？似乎只有这样的：
```plain
【定值】【空洞】*N【定值】
```
探究会减成什么样。猜了几个结论都不对。于是开始暴力枚举可能的答案并去排除。找到了结论：要减去的是顺着推但是最后一个不是要的。如下方例子所示。
```plain
2 ? ? ? 1
显然
2->1
1->1
1->2
2->2
([ci,di])
([2,1],[1,1],[1,2],[2,2])
不合法。
```
直接每个段减就行了。写一写在 $120$ 分钟通过了所有大样例。
看剩下题目有什么比较能做。锁定在 T1。能匹配则匹配似乎就是对的。直接写，写 $20$ 分钟就通过了所有的大样例。$150$ 分钟，有 $10$ 分钟的时间在思考细节。
只剩 $2$ 小时，应该开始拼部分分了。
看 T3 能打什么。菊花图不会。链似乎输出 $1$ 就是对的，翻阅大样例。不是哥们？你咋把这个链也放进去了？尝试击破 $k=1$，画图模拟发现失败了。$4$ 分跑路。
看 T4 能打什么。$f_{u,v}$ 表示区间 $[u,v]$ 的答案。直接预处理就行了。$20$ 分到手。特性 B 咋做啊？预处理的似乎不太行了。（赛后吐槽：你**的不能离线询问吗？）快结束了。
看 T3 能不能写暴力。似乎可以。写写写。诶？题目读错了！完啦！于是把暴力改成了全输出 $2$。祈求 CCF 再施舍 $4$ 分。在 T3 的末尾注释写下了如下内容：
```plain
//Away from OI.
// by McIron233
```
考试结束。估分 $100+100+4+20=224$，低于绝大多数人的水平。
## 12 月
T3 末尾注释进了迷惑行为。
出分了。分数和预期一致，但排名远远低于预期。
GD rk 255/1223（没有排除初中生和已获奖者）。
省一悬。