fvv的挣扎之路

Bugbread · 2024-11-16 11:33:05 · 个人记录

fvv挣扎之路

题记

CSP-S废了（分数别问，说多了都是泪），反思之后觉得自己态度有问题，练习不够，思维很不到位，决定之后写日记记录自己每天的做题情况和补题情况，以此检验和提醒自己。本人是个菜狗，大佬勿喷！

Day 1

OI模拟赛

T1-flandre

思路跟题解一样，该证明的也证明了，实现细节也跟题解一样，但是仍然WA了几个点，主要是因为自己写复杂了，不需要先求正数再求负数，直接求后缀即可，还有一点：没开long long！ 考试的时候还以为会爆空间，结果赛后我是消愁

T2-meirin

只能打20pts的暴力，数学能力有限，没办法

T3-sakuya

交了好几发，终于找到爆零的原因了，原来是在用 next_permutation 函数前，没有对原数组进行 sort 操作！导致全WA！（警钟长鸣）其他部分没错，赛后得分15pts

T4-scarlet

暴力思路没错，就是将序列分为 \dfrac{n}{x} 段，每段进行一次前缀上的加法，用线段树实现即可

总结：73+20+0+65=158pts，有待改进，我甚至没有lwb考得高，lwb都把第一题做出来了！

Day 2

CodeForces（Educational Round 161）

A-Tricky Template

赛时脑子混乱，第一题想了整整20min！赛后发现这只是一道红题（我是不是没救了？），但本人感觉应该是道橙题

B-Forming Triangles

分析出来了性质，必须选至少两个相同的 a_i 才能构成一个三角形，调了半天，WA了4发终于过了（笑），写了整整47min，hhhh

C-Closest Cities

挺简单的，只用了16min，一遍过，维护前缀和和后缀和即可，感觉比第二题简单

D-Berserk Monsters

赛时发现E题通过人数居然比D题多，很疑惑，一看就知道这题不简单

赛后看了题解思路恍然大悟，用两个 set 分别记录该回合中还活着的怪物和该回合中死了的怪物，用 l,r 两个数组分别记录当前怪物左边和右边最近的活着的怪物的下标，再用 f 数组记录当前怪物是否活着，具体操作不写了

E-Increasing Subsequences

想了一会儿没想出关键性质，赛时也没时间做了，放弃

赛后看题解才知道有两个关键性质（设当前构成的序列中的最小值为 l，最大值为 r）：

当在序列中的最后一位插入 l-1 时，对答案的贡献 +1
当在序列中的最后一位插入 r+1 时，对答案的贡献 \times2

由上可知，当 x 为奇数时，则向下递归 x-1；否则，则向下递归 \dfrac{x}{2}，中间用 vector 记录答案即可

总结：场切了3道，不够

AtCoder（ABC 360）

A-A Healthy Breakfast

没什么可说的，切了

B-Vertical Reading

最开始的时候因为用垃圾有道翻译，翻译出来后题意读了一会儿没读懂，所以先去做了其他题，这道题我留在最后做的

只需要按照题意进行三重循环模拟即可，然后WA了两发，原来是理解错了，服了，拿去跟字符串 T 匹配的是所有子字符串中第 c 个字符连接起来构成的整个字符串，而不是这个字符串的前缀！

C-Move It

也没什么可说的，按箱子编号从小到大排序（若箱子编号相同则按重量从大到小排序）后按照题意计算即可

D-Ghost Ants

第一眼看到 N\le 2\times10^5，以为要用数据结构，但是因为懒，所以没写，去想了其他方法，猛然之间想起可以用二分实现！

~~天哪，做题第一次想起用二分来做，太感动了，呜呜呜~~

题目给了 (T+0.1)s 的时间，但是分析题意后就知道这多给的 0.1s 屁用没有！由于每个蚂蚁的运动速度相同，所以同向的蚂蚁永远不可能相遇，记录每个蚂蚁的朝向并按照所在坐标从小到大进行排序，再维护两个前缀和分别统计前缀中 0 和 1 的个数；要想在 Ts 内相遇，那么两个相向的蚂蚁之间的距离最多为 2\times T ，然后用二分找出最后一个坐标小于等于 x_i+2\times T 的蚂蚁的下标即可，最后前缀和计算这个区间中 0 或 1 的个数即可

E-Random Swaps of Balls

这道题对我这种没学过期望的人来说太不友好了，真的服了，想了半天对题解给出的思路似懂非懂；以后再也不想做涉及到期望的题了！

F-InterSections

这道题对我这种fvv来说没有一点思路，教练也说补这道题目，以你们这个水平补了也没有太大意义，所以直接放弃不补了

G-Suitable Edit for LIS

暴力思路差不多，只是不知道该如何用树状数组实现，赛后已AC；又踩了一个坑，导致我RE了4发！就是树状数组要注意 x=0 的情况！（警钟长鸣）

总结：场切了4道，还行

Day 3

OI模拟赛

T1-难题（math）

赛时做这道数学题死磕了2h左右，辛辛苦苦算了半天，还打了个表，结果拿样例检验，惊讶地发现数据小一点的样例都是对的，大一点的莫名其妙输出比答案多4，直接崩溃，再这样折腾下去其他题怕是要爆零，果断放弃先去做其他题，反正我这道题60pts多半没问题（结果确实是60pts）；赛后发现这个性质我已经推导出来了第一步，只差一步就是正解了！（悲）

将暴力代码每次求出的结果输出，可以发现 x 是偶数相当于 f(x) 都大于 2，因为 1,2 是所有非负偶数的因子；x 是 6 的倍数相当于 f(x) 大于3，因为 1,2,3 是所有 6 的倍数的因子；由此可知，f(x)>v 的数字个数为 \dfrac{n}{\operatorname{lcm}(1,2,3...v)}，计算每个数的贡献即可

可以欣赏一下我赛时的代码（乐）

ll ans=n/6*16+n/12+n/60*2+n/420+n/840+n/2520*2+n/27720*2+n/360360*3+n/720720+n/12252240*2+n/232792560*4+n/5354228880*2+n/26771144400*2+n/80313433200*2+n/2329089562800*2+n/72201776446800+n/144403552893600*5;

T2-矩阵游戏（matrix）

赛时是冲着30pts的暴力打的，结果赛后居然有66pts？！严重怀疑数据过水；赛后看完题解发现根本没想象中的那么难，还以为要各种dp和搜索，结果只需要贪心

定义两个数组 f_i,g_i 分别表示前 i 次都对行/列进行操作的最大分数值，最后可以很轻松地得到答案：\max(f_i+g_{k-i}-i\times(k-i)\times p)，之所以要减去 i\times(k-i)\times p 是因为重叠的矩阵方格在这之前只被减了1次，要再减1次才符合题意

T3-括号序列（seq）

得了40pts暴力分，看到 n\le 20 如此小的范围，赛时没有反应过来，赛后才想起可以用状压DP ~~但我就算赛时想起了状压DP，我也不会啊~~

补题挺难受的，每次补状压DP的题都要拿出以前讲课时发的PPT，才知道题解里面的位运算在干什么，表示什么（乐），平生最讨厌状压DP！

有个疑惑：为什么输入用 char s[] 就能过，用 string 就只能得60pts？调来调去，思来想去，还以为是忘开 long long 了，问了同机房大佬，他说最后不要用 string ，因为 string 出问题的概率比 char 大（？）

T4-路程（road）

刚看过去还以为是图论，结果是构造；这是我做过的最简单的T4，但是时间不够了，打了10pts暴力就回去看第一题了；补题也比较轻松，不算难，只是有1发忘记看题目限制了，导致那一发没补到理想的分数

总结：60+66+40+10=176pts，不错，要是赛时能把第一题做出来，第四题多骗点分就更好了

Day 4

CodeForces（Educational Round 159）

A-Binary Imbalance

WA了1发，最开始以为最多执行 \lvert s\rvert-1 次操作，重新读了题目后才发现可以执行无穷多次（又是题意理解错了！）

很容易发现，只要字符串中含有字符 0，便可以在 1 和 0 之间插入无穷多个 0，当然，若没有 1 可以直接输出 YES；所以只需要判断字符串是否全部由 1 构成，如果是，则输出 NO；否则输出 YES

B-Getting Points

一道简单的数学模拟题，思路有点复杂，想了好一会儿，一遍过了，思路不讲了

C-Insert and Equalize

看第二个样例看半天都没看懂样例答案 27 是怎么来的，结果又是因为题意理解错了（乐），hhhhhh，我都佩服我自己！

由于每个数最后要变成相同的数，且只能加 x（赛时理解成了可以加或减 x，就是因为这个想了半天！），那么肯定得先让所有数变成序列中的最大值；因为要操作数最少，所以 x 要尽可能大，分析可得，x 即为所有数（除去最大值）与最大值的差的最大公因数，并不是两两之间的差的最大公因数，我因为这个WA了两发，刚开始还以为没开 long long！后面过了

D-Robot Queries

赛时没做出来，一道挺难想的数学题，个人认为主要难点在于推导反转后的坐标

题解

E-Collapsing Strings

一道有关字符串计算的数学题

题解

总结：场切了3道，而且每道题花的时间挺多，罚时也吃了不少，急需锻炼自己的阅读能力（笑）和思维能力！

AtCoder（ABC 358）

A-Welcome to AtCoder Land

判断字符串是否相同即可，切了

B-Ticket Counter

模拟即可，过了；不知道为什么，明明编译器编译成功且没有报任何错，交上去却CE？后来把变量名 time 改了才对

C-Popcorn

根据题意和 N,M\le10 的范围，全排列枚举所有情况即可，赛时把用于枚举的编号 a_i 写成了 i ，是说样例怎么过不了，改了之后过了

D-Souvenirs

最开始想的是先从小到大排序，然后二分，去找第一个糖果数量大于等于 B_i 的盒子，把它送给第 i 个人，但是如果两个人的糖果需求相同呢？难道用 vis 数组去判断当前盒子是否已经送人了？然后一个一个往后找，直到找到第一个还没有送人的盒子？这样做多半会TLE，遂放弃了这个想法

猛然想起可以用优先队列来做，开两个小根堆 g,p 分别记录盒子中糖果的数量和每个人需求的糖果数量，比较堆顶，若 g 的堆顶比 p 的堆顶小，则只弹出 g 的堆顶；否则将 g 和 p 的堆顶都弹出，并记录答案；若在这个过程中 g 中元素已经全部弹出但 p 非空，说明不能满足所有人的需求，输出 -1；若 p 中元素全部弹出，则直接退出循环

E-Alphabet Tiles

懒得写了，直接看题解吧

题解

F-Easiest Maze

太难了，也没时间补了

G-AtCoder Tour

看完沉石鱼惊旋大佬的题解后恍然大悟，感觉没自己想象中的那么难

题解

总结：场切了4道，后面的3道全都不会，做完前4道后就在坐牢，绿题还是不能切，有待提高！

Day 5

CodeForces（Educational Round 158）

A-Line Trip

简单数学题，先找出 a_i-a_{i-1} 的最大值，最后再跟 2\times(x-a_n) 比较取最大值即可

B-Chip and Ribbon

WA了1发，我是所有做出来的人中做的最久的一个，做了25min！

其实思路挺好想的，若 c_i\le c_{i-1} ，那么在完成 c_{i-1} 之前一定能先完成 c_i ，不需要额外传送；若 c_i\ge c_{i-1} ，那么需要多传送 c_i-c_{i-1} 次，所以答案即为 \sum\limits^n_{i=1}\max(0,a_i-a_{i-1}) ，最后要 -1 ，因为机器人最开始在第一格，这一次不算

C-Add,Divide and Floor

赛时做了整整74min！自我鉴定为fvv中的“不可回收物”，想了好一会儿才找到思路和关键性质

可以观察到，每次操作后，数字的相对大小关系不变，因此我们只需要关心数组中的最大值和最小值，让它们最后变成相同值即可

记 a,b 分别是数组中的最大值和最小值，对于每次操作，我们可以根据 a,b 的奇偶性来分类讨论：

若 a,b 均为偶数或奇数，x 可以取任意值
若 a 为偶数，b 为奇数，x 可以取任意奇数
若 a 为奇数，b 为偶数，x 可以取任意偶数

不停地操作直到 a,b 相同，中间用 vector 记录答案即可

D-Yet Another Monster Fight

由于B、C题花了很多时间，导致这道题根本没时间做（悲）

假设最开始选择了怪物 i，对于其他怪物 j，我们可以根据它们的位置进行分类讨论：

若 i>j，这个怪兽在最开始的怪兽的左边，那么最坏情况就是在怪兽 j 右边的所有怪兽都被打败时才来打它，因此需要用 a_j+n-j 才能打败
若 i<j，跟上面同理，需要用 a_j+j-1 才能打败

综上，最坏情况下最少的初始威力为：\max(a_i,\max\limits^{i-1}_{j=1}(a_j+n-j),\max\limits^n_{j=i+1}(a_j+j-1))

定义 x_i=\max\limits^i_{j=1}(a_j+n-j)，y_i=\max\limits^n_{j=i}(a_j+j-1)，那么答案为：\min\limits^n_{i=1}\max(a_i,x_{i-1},y_{i+1})，其中 x_i,y_i 可以 O(n) 预处理

总结：成fvv了，前面做的时间太长了！后面根本没时间做其他题，不知道自己赛时在想什么

AtCoder（ABC 358）

A-Subsegment Reverse

反转的部分倒序输出即可，过了

B-Nutrients

对每一列求和并判断是否大于需求即可，过了

C-Keys

思维量不大，主要考码力，枚举所有状态并一一进行测试，若满足所有测试结果，则对答案 +1 即可

D-Masked Popcount

完了，不能做出黄题，真成入机了！要怪只能怪自己数学底子太弱了，悲！

我们可以先枚举 0\sim15（4,3,2,1 表示二进制下的位数）

4   3   2   1

0   0   0   0
0   0   0   1
0   0   1   0
0   0   1   1
0   1   0   0
0   1   0   1
0   1   1   0
0   1   1   1
1   0   0   0
1   0   0   1
1   0   1   0
1   0   1   1
1   1   0   0
1   1   0   1
1   1   1   0
1   1   1   1

我们可以发现，第 i 位总是以 2^{i-1} 个 0，2^{i-1} 个 1 不停地循环下去，因此我们可以先将 m 转换成二进制形式，若二进制下 m 的第 i 位为 1，那么对答案的贡献即为：

\lfloor \dfrac{n+1}{2^i}\rfloor \times 2^{i-1}+\max(0,(n+1)\bmod 2^i-2^{i-1})

之所以要 +1，是因为题目要求从 0 开始枚举，而不是从 1 开始！这就是为什么我WA了1发的原因

E-Max/Min

枚举值域中的数 i 并将其作为除数（即分母），再枚举商 j，既然知道了除数和商，那么也就知道了被除数的范围（记 n 为被除数）：

i\times j\le n<i\times (j+1)

记 sum_x 为小于等于 x 的数的个数，方便统计答案；因为 j 从 i+1 开始枚举，所以要减去不符合题意的答案。记 tmp 为 x 出现的次数，任意取两个（可重复）的方案数为 tmp\times tmp，而第一个数下标比第二个下标小的方案有 \dfrac {tmp(tmp-1)}{2} 种，所以不合法的贡献为 (tmp\times tmp-\dfrac {tmp(tmp-1)}{2})\times 1，之所以 \times 1 是因为两个数相同，它们的商为 1

总结：从这次比赛可以看出我的数学基础太弱了！在赛场上遇到这种数学题只能打暴力。不知道该怎么补数学基础，只能靠多做题？

Day 6

OI模拟赛

T1-基于1的算术（add）

赛时一看题目描述这么少，n<10^{15} 这么巨大的范围，肯定是数学题！于是死磕了好久，好不容易把自己手搓的样例过了，结果赛后只有20pts（乐）

没想到是一道搜索黄题，还是CF上的原题，瞬间蚌埠住了（我真的太下饭了，没救了）

题目要求用只包含数字 1 的整数，可正可负，由于 n 最大只有 15 位数，并且只包含数字 1 的整数很少，因此我们可以爆搜解决此问题

先预处理出所有只包含数字 1 的整数，可以打表也可以递推，然后爆搜；从高位开始逐位地贪心，记 x_i 表示由 i 个 1 组成的数（例：x_4=1111），对于搜索过程中的第 i 位，设 n 最多由 k 个 x_i 组成，将 n 对 x_i 进行取模，于是我们有两个操作可选（此时的 n 已经进行完取模操作）：

递归搜索 n
递归搜索 x_i-n

解释一下，举个例子：假设此时递归到第 2 位，n 为 72，它的最优解可能是由 66 或 77 加减而来，此时我们可以向下递归 72-66=6，或者递归 77-72=5，这是因为整数可正可负，所以最优解有可能是由比它更大的数的加减而来；若是由比它小的数递归而来，那么对答案加上 k\times i，若是由比它大的数递归而来，那么对答案加上 k\times (i+1)

为方便理解，附上代码：

ll n;
ll one[17];
ll dfs(ll n,int i)
{
    int k=n/one[i];
    n%=one[i];
    if(!n)
    {
        return k*i;
    }
    return k*i+min(dfs(n,i-1),i+dfs(one[i]-n,i-1));
}
int main()
{
    for(int i=1;i<=16;i++)
    {
        one[i]=one[i-1]*10+1;
    }
    cin>>n;
    cout<<dfs(n,16);
    return 0;
}

T2-逃离（car）

看到这道题就想起了CSP-S考场上做的T2-超速检测，一眼看过去，太复杂了，没思路，放弃，跟当时考场上的状态一模一样，当然，结果也一样，0pts，hhhh

看了题解感觉没自己想象中的那么复杂（我就是当代简单问题复杂化代师！），然后惊讶地发现：题意又理解错啦！ 我以为每辆车最多装 1 个加速器，结果是可以装多个加速器，666

sub1（n=1）

此时只有一辆车，那么可以将所有加速器全部装在这辆车上，所以很容易便能得出公式：

T_{min}=\dfrac{t-l_1}{v_1+m\times k}

sub2（所有 v_i 相同且 m=1）

此时给最后面的那辆车装上加速器是最优的，为了找出最后面的那辆车，我们可以排序并按照在数轴上从左到右的顺序依次给它们编上号，然后我们需要进行分类讨论

记 t1 为第 1 辆车追上第 2 辆车所需的时间，t2 表示第 2 辆车完全离开大桥所需的时间

若 t1\ge t2 ，说明第 1 辆车追不上第 2 辆车，答案即为 \dfrac{t-l_1}{v_1+k}；否则说明第 1 辆车能追上第 2 辆车，因为第 1 辆车追上第 2 辆车后速度会变成 v_2，第 1 辆车车尾离开大桥后才算完全离开，所以答案为 \dfrac{t-l_2+r_1-l_1}{v_2}

sub3（m=0）

这个subtask很考验思维，也很重要，对正解有很大启示

可以知道，如果从左往右第 i 辆车不想对自己左边的车辆产生影响，那么它至少要在第 i-1 辆车追上来之前行驶到离开大桥 \sum\limits^{i-1}_{j=1}(r_j-l_j) 这么远的位置才行，每辆车都满足这个约束条件，才能使最后一辆车在离开大桥的过程中不会减速。若左边的车追上了右边的车，那么它们两个的速度相同，会同时到达各自的约束位置

有了这个关键性质，我们便可以在每辆车到达约束位置所需的时间中取最大值即可，即

\max\limits^n_{i=1} \dfrac{t-l_i+\sum\limits^{i-1}_{j=1}(r_j-l_j)}{v_i}

sub4（n\le1000 且 m=1）

我们只需要找出 \max\limits^n_{i=1} \dfrac{t-l_i+\sum\limits^{i-1}_{j=1}(r_j-l_j)}{v_i}，将其 v_i 加上 k，然后更新它到达约束位置所需的时间，因为所需时间最大的 i 对所有车离开时间的限制最大，最后再从中找出最大值即可

正解

在sub4的基础上开一个优先队列 priority_queue，让时间最大的排在最前面，每次将其弹出，并让 v_i 加上 k，重新入队，这个过程重复 m 次，最后找最大值输出即可

T3-南斯拉夫（yugo）

挺容易骗分的题，subtask很好打，评测时老师的SPJ写错了，只有40pts，SPJ改了之后变成80pts

对于前四个测试点，数据规模很小，m\le20，直接暴力枚举每个状态，最后检验是否都为 0 即可，在这个过程中，我们不需要枚举 4 个状态，只需要枚举 2 个状态就可以了，因为我们只需要判断一个民族是否被选了偶数次，然后让前一半操作增加不满值，后一半操作减少不满值即可

对于第5个和第6个测试点，分别输出 \dfrac{m}{2} 次 2,3 和 2,4 即可

剩下的没时间补了

T4-数数（count）

又是一道数学题，赛时打完20pts暴力就没看了

第一个subtask已经解决了，接下来看第二个，p\le7000 的情况

既然我们在第一个subtask中逐个枚举 a_i 和 a_j 是否满足条件，那么我们也可以枚举值域中的每一个数是否成立，记 cnt_x 表示 x 出现的次数，cnt_y 表示 y 出现的次数，若成立，则对答案加上 cnt_x\times cnt_y

正解

需要对式子进行转换，原题面求满足 a_i^2+a_i+a_j^2\equiv a_i\times a_j(\bmod\ p) 的数对个数，其中 1\le i,j\le n，i\neq j

设 x=a_i+1,y=a_j，则：

(x-1)^2+x-1+y^2\equiv (x-1)y(\bmod\ q)

x^2-xy+y^2\equiv x-y(\bmod\ q)

对两边的式子同时乘上 (x+y)：

x^3+y^3\equiv x^2-y^2(\bmod\ p)

x^3-x^2\equiv -y^3-y^2(\bmod\ p)

只需要依次枚举，用两个 map 维护所有的 x^3-x^2 和 -y^3-y^2 出现次数，即 (a_i+1)^3-(a_i+1)^2 和 -a^3_j-a^2_j 的出现次数，实时计算新的一项与前面的数列项产生的数对个数即可

Day 7

CodeForces（Educational Round 157）

A-Treasure Chest

不难，根据 x 和 y 的大小关系分类讨论即可

B-Points and Minimum Distance

将所有数排序，x 坐标按从小到大的顺序输出前 n 个数，y 坐标按从大到小的顺序输出前 n 个数即可

C-Torn Lucky Ticket

想了1h多，我用了一个四维数组，cnt_{a,0/1,b,c} 的四个维度分别表示长度，前/后缀，前/后缀长度，剩余和与前/后缀和的差，然后累加，计算答案即可。转移很简单，代码不放了

D-XOR Construction

题目要求 a_i=b_i\oplus b_{i+1}，刚开始我天真地以为这道题能配绿？这是在欺负不知道 a_i\oplus b_i=b_{i+1} 的人吗？高高兴兴交上去直接WA，原来还需要满足 b 是 0 到 n-1 的排列的要求，思路看题解

总结：只做出来3道，第3道题想太久了，别人都做出来好一会儿了，我才把它A掉，下来有必要去学习别人的思维

AtCoder（ABC 353）

A-Buildings

简单红题，切了

B-AtCoder Amusement Park

简单模拟题，切了

C-Sigma Problem

先用 sum 记录和，每个数会出现 n-1 次，累加起来，暂时不取模；然后统计需要取模的次数，排序后用二分找出第一个大于等于 10^8-a_i 的数的下标，那么之后的数与 a_i 相加的和一定大于 10^8，统计完次数 cnt 后，减去 cnt\times 10^8 即可

D-Another Sigma Problem

不难，推一推性质就行

对于 A_i，假设它有 x 位数，那么对于前面的 A_j(1\le j<i)，就有 f(j,i)=A_j\times 10^x+A_i，因此我们只需要定义一个二维数组 cnt_{i,j} 表示从后往前的 i 个数中，数字为 j 位数的个数。根据数据范围 1\le A_i\le 10^9，可知 A_i 最多只有 10 位数，所以 j 很小，具体实现不写了

E-Yet Another Sigma Problem

刚开始用 map 捣鼓了一会儿，老是TLE，突然之间想起上午写第四题用的字典树，秒过

总结：C、D、E题都是Sigma problem，都在求和，挺有趣的，比较考验自己的数学思维，希望这种数学黄题多来点

Day 8

昨晚上学习了平衡树，虽然思想不难，但毕竟是8级知识点，还是数据结构，实现起来真的难！跟平衡树相比，我突然间觉得线段树真好写！

上午写代码的过程中顺便重新整理了昨天晚上学的，弄懂了每步在干什么，也画了图验证，但是光调试一道模板题就花了我2h+，真的恶心，从0pts调到7pts，又调到65pts，中间还变成了58pts，65pts的程序交了8发，实在是调不动了，崩溃了。静下心后只好挨着挨着看，结果是在删除结点的过程中漏写了一个 pushup，没有及时更新！哎，数据结构的板子需要注意的细节太多了，少写一句话或者打错几个字符就能WA掉！

上午写的是“普通平衡树”，下午才开始写“普通平衡树（数据加强版）”，本以为自己再写一遍模板，中间部分根据题意改一改就能过，结果我还是太天真了，第一发直接“大红大紫”（如下图），后来发现数组空间没开够，忽略了接下来的 m 次操作可能新插入的数，用来调试的输出代码也忘记加注释了。改了之后却发现仍然只有40pts，正在琢磨为什么的时候，突然看见 x<2^{30} 的范围，原来是初始的 inf 不够大，改成 0x7fffffff 之后便过了

然后去写“书架”，写完模板后发现不知道该如何实现 Insert 操作，死磕了一会儿发现 Insert 操作理解错了（乐），又重新思考，写好代码后交上去直接爆零，只好去看题解，在题解的帮助下终于过了这道题。FHQ Treap真是个好东西！实现起来比普通的Treap容易多了，根本不需要左旋、右旋操作

Day 9

OI模拟赛

T1-返乡（home）

一道找规律题，赛时花了40min，过了

T2-连接（connect）

原来所有的数除了 n 都有可能是小数，都应该用 double 类型存储，没注意到这一点

可以证明最优解的左端点或右端点一定是不同密度钢管之间的分界点，记，通过二分找出边界的下标，将下标 j 的可取范围求出来，然后整块整块地移动，求得当第 i 个钢管全取时的最大密度即可，时间复杂度 O(n^2) ，期望得分50pts

T3-习惯孤独（lone）

赛时没看懂样例，只好随便乱输出一个式子，结果居然有10pts！

T4-车站（station）

乱写了一个subtask，得了5pts

总结：100+20+10+5=135pts，听教练说从这次开始，模拟赛没有简单的了，这次排名难得进了前三，希望能够保持

Codeforces Round 987（Div.2）

A-Penchick and Modern Monument

将一个非递增序列通过修改一定次数将原序列变成非递减序列，原本想的是若 a_i\neq a_{i+1}，则次数 +1，但是我自己手搓了一个能hack这个想法的样例：

1
5
4 4 3 2 2

分析可知，最少次数为 3，但如果按刚才的想法写，会输出 2，说明这个思路是错的，重新分析后可知答案即为 n 减去最长的连续且数字相同的序列的长度

B-Penchick and Satay Sticks

做这道题的时候真觉得自己是个rz，sb。md，想了好久，感觉自己比fvv还fvv

我的思路很复杂，由于只能跟相邻的且差为 1 的数交换位置，并且每个数（除了 1 和 n）都有两个跟其差为 1 的数，所以最多交换 2 次，如果 \lvert p_i-i\rvert>2 ，那么无解；如果是 1 或 n，并且 \lvert p_i-i\rvert>1，那么也无解；还要接着判断与 p_i 差为 1 的数是否在其附近，如果 \lvert p_i-i\rvert=2，并且它们中的其中一个与其距离超过 2，那么无解；如果 \lvert p_i-i\rvert=1，并且它们与其距离都超过 2，那么无解；1 和 n 的情况就不讲了

C-Penchick and BBQ Buns

赛后听大佬的一番解释瞬间懂了，首先我们肯定得找最小的勾股数，即 $3,4,5$，那么在 $1,10,26$ 的位置放上 $1$，$1\sim 10$ 之间（不包含 $1$ 和 $10$）有 $8$ 个位置可放，放入 $2,2,3,3\cdots$ 就行，但问题是如何解决 $10\sim 26$ 之间的奇数个位置，原来在 $23,27$ 的位置各放一个 $2$，便能完美解决问题，赛时就卡在这一点，赛后补题秒过 ### D-Penchick and Desert Rabbit 若同时满足 $j<i$ 和 $a_j>a_i$，或者同时满足 $j>i$ 和 $a_j<a_i$，那么兔子就能从第 $i$ 棵树跳到第 $j$ 棵树，换言之，兔子能往左跳到比它目前所在的树高的树，也能往右跳到比它目前所在的树矮的树观察到若兔子在第 $n$ 棵树上，那么它一定能跳到最高的树上，所以 $ans_n=\max(a_1,a_2,\cdots a_n)$，再来看在第 $i$ 棵树和第 $i+1$ 棵树上的关系，我们记 $p_i=\max(a_1,a_2,\cdots a_i)$，$s_i=\min(a_i,a_{i+1},\cdots a_n)

若 p_i>s_{i+1}，说明一定能从第 i 棵树跳到第 i+1 棵树，即 ans_i=ans_{i+1}；否则，说明第 i 棵树一定跳不到第 i+1 棵树，ans_i=p_i

时间复杂度 O(n)

总结：赛时第二题做成sb了，第三题差一点点就能做出来了，但就是没做出来，经大佬点拨后恍然大悟。自己也总结了一个经验：赛时不要去看别人的做题情况，很影响自己的心态，越急越做不出来，反而会WA很多发，这个时候必须静下心来重新思考

Day 10

学习了笛卡尔树，这个知识点在21年提高组初赛考过，但当时没学，只能乱蒙

笛卡尔树比平衡树好写多了，码量跟平衡树比少太多了，而且思想也简单，就是需要注意细节，这是模板题

Day 11

OI模拟赛

T1-密文板（ciphertext）

赛时写挂了，只有10pts，跟个sb一样

一道贪心，用两个栈存储左括号和问号，遇到右括号时优先用左括号去匹配，若没有左括号，则用问号匹配；若问号也没有，那么不能被匹配的括号数 +1

处理完右括号后，去访问两个栈的栈顶，若问号的下标大于左括号的下标，则将当前的问号变为右括号；最后处理剩余的问号，若数量为奇数，则答案 +1

T2-挑战NPCⅢ（color）

一道不是特别难的图论，写了个暴力得了40pts

赛后调了好久，终于在同机房大佬的帮助下A了

T3-escape from whk 3（kuhu）

一道数学题，最开始打了个 O(n^4) 的暴力，优化后变成了 O(n^3) 的暴力，得了35pts

T4-伤痕累累的心，在暴雨中仍然放声歌唱（scar）

难得见T4暴力这么好打，题面简洁清晰，对每次操作建一个大根笛卡尔树就行了，得了50pts（~~居然是四道题里面得分最高的一道题~~）

总结：10+40+35+50=135pts，暴力全都打满了，但是第一题挂了，服了；离正式考试没几天了，首要任务是保证T1不挂分，T1要是挂了那基本没戏了

Day 12

CodeForces（Educational Round 156）

A-Sum of Three

一道简单数学题，分类讨论：

若 n\bmod3=0，那么 a\bmod3=1，b\bmod3=1，c\bmod3=1。因为 a,b,c 互不相同，所以 a_{min}=1，b_{min}=4，c_{min}=7，n_{min}=a_{min}+b_{min}+c_{min}=12，只需要分别输出 1,4,n-5 即可
若 n\bmod3=1，那么 a\bmod3=1，b\bmod3=1，c\bmod3=2。因为 a,b,c 互不相同，所以 a_{min}=1，b_{min}=4，c_{min}=2，n_{min}=a_{min}+b_{min}+c_{min}=7，只需要分别输出 1,4,n-5 即可
若 n\bmod3=2，那么 a\bmod3=1，b\bmod3=2，c\bmod3=2。因为 a,b,c 互不相同，所以 a_{min}=1，b_{min}=2，c_{min}=5，n_{min}=a_{min}+b_{min}+c_{min}=8，只需要分别输出 1,2,n-3 即可

B-Fear of the Dark

真好，第二题就是个黄题，不知道为什么，WA了3发才过

记 ao,bo 分别表示两个灯笼到起点的距离，ap,bp 分别表示两个灯笼到终点的距离，ab 表示两个灯笼之间的距离

那我们可以分类讨论：

灯笼A覆盖起点和终点
灯笼B覆盖起点和终点
灯笼A覆盖起点，灯笼B覆盖终点
灯笼B覆盖起点，灯笼A覆盖终点

第 3,4 种情况还需要使灯笼A，B照亮的范围有交集，若灯笼A，B照亮的范围有交集，那么所需的最短半径r为 \dfrac{ab}{2}，将上述情况对应的半径r比较取最小值即可

答案为：

\min(max(ap,ao),max(bp,bo),max(\dfrac{ab}{2},ao,bp),max(\dfrac{ab}{2},ap,bo))

C-Decreasing String

赛时思路已经跟正解很接近了，但忘记了将一个字母删除后，其他字母相邻的左右字母可能会变

可以发现：若 s_i 不是剩余字符串中的最后一个字符且 s_i>s_{i+1}，那么将 s_i 删除后，字典序一定会变小，并且 i 越小，字典序越小；若 s_i 是剩余字符串中最后一个字符，那么就直接删去 s_i

因此，我们可以用一个栈来模拟这个过程

遍历当前字符串中的每一个字符，若栈中有字典序比 s_i 大的字符，那么弹出，重复这一过程直到栈中没有字典序比 s_i 大的字符或栈为空，每出栈一次，pos\gets pos-n，n\gets n-1。若在某次操作后，pos\le n，说明找到了第 pos 个字符所在的字符串

为方便最后一步输出，用 vector 模拟，输出 v[pos-1] 即可

D-Monocarp and the Set

666，居然是道逆向思维题，没想到啊

既然插入操作很难思考，那么可以将其转换成删除操作，从 n 个数中不断删除数字

如果是 >，那么只能删除最大值，即只有一种选法
如果是 <，那么只能删除最小值，也有一种选法
如果是 ?，说明可以删除除最大值和最小值之外的任意一个数，有 i-2 种选法

所以对于初始答案，若 s_i 是 ?，那么乘上 i-2 即可。需要注意的是，如果第一个字符是 ?，根据题意，可知不存在合法方案，直接输出 0

对于修改操作，若 s_x 原本为 ?，对答案除以 x-2，若将 s_x 修改为 ?，那么乘上 x-2 即可

总结：这场比赛是我遇到的最难的CodeForces Educational Round，赛时只做出来2道（菜），对题意的理解和对题目的分析有了一定提升，但是绿题还是做不出来，代码能力急需提升，以及自己考场上的心态还需要调整

AtCoder（ABC 352）

A-AtCoder Line

rz红题，切了

B-Typing

还被数据范围卡了一小会儿，突然间想起用双指针，过了

C-Standing On The Shoulders

简单数学题，过了

D-Permutation Subsequence

刚开始没想出来该怎么做，先去做了E题，再回来做D题

看了5分钟左右才把题意弄明白，还以为要用数据结构，但是STL的 set 是个好东西！每次进行删除和插入操作，再比较取最小值即可

E-Clique Connect

感觉更应该评绿，一道关于kruskal的偏模板的题，思维难度不大

根据最小生成树的思维，我们可以在结构体中用 vector 存储顶点子集，并记录边权，按边权大小从小到大排序，然后剩下的就是kruskal的模板了，比较轻松地过了

总结：场切了5道，挺不错的，但希望能继续保持

Day 13

OI模拟赛

T1-异或（xor）

赛时没想出来正解，只能打暴力

一道挺不错的题，让我对二维前缀和和二维差分有了全新的理解：不是所有的二维前缀和数组都在维护子矩阵的大小，例如本题，需要另开一个二维前缀和数组维护子三角形的大小

我们用 b_{i,j} 维护以 (i,j) 为顶点的子三角形的大小，于是我们可以得出转移公式：b_{i,j}=b_{i-1,j-1}+b_{i-1,j}-b_{i-2,j-1}，即黑色部分的和 = 橙色部分的和 + 黄色部分的和 - 蓝色部分的和 + 最右下角黑色方格的大小，最后再用二维差分求出对应位置的真实大小即可

T2-游戏（game）

赛时写了个贪心，得了15pts，主要是因为开了subtask，不开subtask得62pts，刚开始不知道为什么会错，难道不是贪心吗？后来发现是我太天真了

我们可以进行递归处理，记 l,r 分别表示是 b_i 倍数的数的集合和非 b_i 倍数的数的集合，sum 记录一个集合内所有元素的和

在递归求解过程中，若已经递归了第 m+1 层，则返回剩余集合中所有元素的和；若集合为 \varnothing，则返回 0；若此时递归的次数为奇数，返回 \min(q(l_p,cnt+1),q(r_p,cnt+1))，否则返回 \max(q(l_p,cnt+1),q(r_p,cnt+1))

有一个关键性质：就是当 m\ge 2\log_n 时，直接返回 0 即可，证明如下：

对于玩家Alice，如果她始终在每一次操作中都在两个部分中选择较小的那一个部分（这一部分大小一定小于等于原集合总大小的一半），那么在她操作 \log_n+1 次后，集合一定会变成 \varnothing，答案为 0；同理，Bob操作 \log_n+1 次后，集合也一定会变成 \varnothing，答案为 0；综上所述，若Alice和Bob都操作 \log_n 次，即 m\ge 2\log_n 时，答案一定为 0

T3-连通块（connect）

暴力写出来了，但是空间炸了，16pts \rightarrow 0pts。长教训了，空间不能开太大，不然要炸，下次一定要计算好空间，防止再次出现这种爆零的行为，痛失暴力分（悲）

T4-公交路线（route）

我连暴力都不会打！我的天，最难的一次T4

赛后看题解发现要用十级知识点——虚树！直接放弃，这个知识点根本没学

总结：40+15+0+0=55pts，最sb的一次，吃了空间的亏。由于对自己过分自信，导致估分估高了，而教练又有个新要求：凡是估分离实际分数每差10pts，晚上多跑1圈操场，然后我高估了45pts，要多跑4圈，艹

Day 14

OI模拟赛

T1-魔法师（wizard）

看到 3\le n\le 18 的范围，盲猜是状压DP，但是不会，只好写了个爆搜，只得了15pts

后来将赛时写的subtask变成了全局解，再剪了一个枝，直接变65pts！后悔不已！

赛后看题解发现还是要用状压DP，记录每个状态所需的最少法力值和最少回合数，然后爆搜并剪枝即可

T2-二叉搜索树（bst）

这道题的代码真难调，赛时暴力调了1.5h才把样例给过了，本来可以优化的，但是时间有点紧，去写第三题了，最后得了30pts

赛后继续优化，又调了1h，终于把样例过了，优化后得了50pts

可以发现一个子树是BST当且仅当子树的中序遍历序列的点权单调不降，而每个子树的中序遍历序列是整个树中序遍历序列的区间。

可以先求出中序遍历序列 a_1,a_2,a_3,\dots a_n ，设以 u 为根的子树的中序遍历序列对应 [l,r] ，那么以 u 为根的子树是BST当且仅当 \forall i\in[l,r),a_i\le a_{i+1}

查询某个点是否合法只需要用树状数组维护区间不满足 a_i\le a_{i+1} 的个数即可

T3-枚举（enum）

我的天，这什么样例，这么水！我写了 k=2 和 k=3 的两个subtask，一分没得！样例都过了，我真的服了，辛辛苦苦推了1h的式子，各种分类讨论，你知道这有多累吗？出题人我【数据删除】

T4-树（tree）

题都没看懂，更别说暴力了

总结：15+20+0+0=35pts，别人是越学越牛逼，我是越学越傻逼，废了，离NOIP只有一个星期了，再这样下去，恐怕拿省二都吃力，哎

Day 15

今天一天都在做真题，不得不说NOIP的难题对我来说连暴力打起来都吃力，更别说正解了。有些题的正解还要用到我还没学过的知识，有的题又特别考验思维，比如双序列拓展。天天爱打卡我光是暴力就调了1h，交了3发才得了28pts（乐）

去做NOIP2022的T1——种花，本来是冲着暴力分打的，结果居然有94pts！挂的6pts还是因为结果忘记乘 c 和 f，不然都能过了

Day 16

也是全天在做真题。我的天，建造军营这道题真的难，确实配得上紫，我甚至感觉应该是道黑题（好像太夸张了），要先用tarjan缩点，缩点后求出以当前结点为根的子树的大小，然后再进行树上dp，补这道题花了我一上午；又去做了比赛，打了8pts的暴力，但是用最简单的前缀和并预处理一下就能得到20pts！我写的8pts暴力还用了线段树，太值了！

还去写了21年的报数，看到 x\le 10^7 的范围后，小心翼翼地开了个 10^7 的数组，但是跑最大的样例的时候发现什么都不输出，以为是空间炸了，于是将范围改成了 10^6。不出所料，得了70pts，RE了3个点，于是去看题解，发现题解做法跟我一模一样，只是数组空间不同，改成 10^7 后，就过了；拿这份代码再去跑大样例，还是什么都不输出！~~CCF还我30pts！~~

Day 17

没刷真题了，教练让我们刷模板，有些板子跟砍瓜切菜一样切了，有些板子因为长时间没打，已经忘了，只好重新学

Day 18

还是在刷模板

Day 19

模板写完了，在做真题，方差真难，最开始写了半天只有4pts（乐），看到讨论区和题解很多人都用了模拟退火，可惜这玩意儿我们还没学（悲），然后一波式子转化+DP；棋局没敢做，因为它是道黑题，题面又长！

接着去做20年的NOIP，第一题就给我整破防了，一道图论题还要用高精度？！不过众所周知 __int128 是个好东西

Day 20

明天就要靠NOIP了，就怕自己考不好，但只能在心里面告诉自己绝对不要这么想。

害怕战败的人一定会战败。——拿破仑·波拿巴

OI模拟赛

今天考了一场OI模拟赛，说是什么信心赛，然而我却考成了“打击信心赛”，成SB了

T1-情景剧（sitcom）

赛时我以为第一题肯定会像CF那样，是一道思维题，肯定不需要什么数据结构之类的，然后赛时就一直在朝这方面想，想了半天想不出来，心态炸了，后面考成一坨S了

一道很简单的笛卡尔树的题，建立一个小根笛卡尔树，枚举 h_i 作为区间的最小值，用笛卡尔树查找以 i 为根的子树的大小，即区间长度，然后再找区间内的最大值即可

T2-抽卡（card）

光顾着去想50pts的暴力。当然，没想出来，hhh

本来可以去打15pts的暴力的，结果因为对自己的过分自信和赛时策略的失误导致爆零（我就是个瓜皮！），明天一定要一个subtask一个subtask地打暴力，绝对不能开始就想着去打高分暴力或者正解！

考后补暴力的时候，因为多测没有初始化导致我调了4h+！艹！

T3-修改01序列（sequence）

一道弱智题，赛时心态爆炸导致没想出来一个很明显的性质！我服了呀，赛后秒过

T4-可爱的数（lovely）

没做出来，有大佬场切了这道题，这道题居然是紫题！%%%

后来有人找到原题了

总结：赛时应该先把四道题的题目全部读完后，再分别写它们的暴力，最后再来花时间死磕！不然很影响赛时心态，后面的题就只能挂掉