CSP-s2020初赛游记
这次初赛是我竞赛生涯里参赛感觉最好的一次，从昨天下午做完作业来到机房起，整个人处于一个松弛的状态，实在是不怎么紧张，回想起一年前那个战战兢兢的自己，心感到我一年来的进步是如此之大，不但在竞赛水平，更在心理状态。
考试的时候很淡定，阅读第三题我做了一个多小时，因为我觉得这不但是一个很有难度，要求很高的编程题，更是一道数学趣味题，虽然我最终没有完全理解，但是这个过程我很享受。
完善程序做了不到半小时，相比于去年取石子那道奇葩状压使我15分全扣光，今年的水平很稳定，直接秒杀。
去年的我只考了73.5，接下来的两周时间心态爆炸，整个人浑浑噩噩，虽然后面又滚进了复赛，但这也很说明问题。今天我虽然只考了88，但是体验比去年好很多。
简要评论一下题目
唯一一道硬件题目，看起来B最正经
出题者真是一个天才，我本来还以为这又是一道原题，结果这个栈底真的是点睛之笔
阅读第一题是在做两个数or起来的最大值
我竟然没有意识到n可以等于0，然后我错了，可惜至极
这题有数学思想，反证法。若输出为偶数，假设只有一个偶数，那么任意两个数or起来，最后一位肯定是1，那么答案就是奇数了，矛盾，所以C是正确的
阅读第二题，狂喜。前一天晚上我刚发了个求kth的博客，今天押到题了。
但是今年初赛又加了一个跟去年一样坑的出题方法，去年是把并查集的路径压缩删掉，今年把快排部分搞得乱七八糟，可以发现代码里面在交换的时候处理得很不好，所以最劣复杂度可以到
O
(
n
2
)
O(n^2)
O(n2)，我错了。
同样的，这道题目用这个代码也是
O
(
n
2
)
O(n^2)
O(n2)，我又错了。
第三题是数学小游戏。
一个字符串，选择一个点
p
p
p为轴点，可以令区间
[
1
,
k
]
[1,k]
[1,k]整体往右移动一格，
[
k
,
n
]
[k,n]
[k,n]整体往左移动一格，问最少步数是初始字符串变成目标字符串。
我还看出了他是在双向bfs
其实我觉得是对的，但答案是错的
我模拟了01234到43210的情况，答案是8
所以前后两项的差分别是4,6,6,8,8,10……
通过合情推理得到答案是68
这题我四个选项分别构造了几种情况，只有A是无解的，但是我又错了，可能是我计算错误。
完形第一题很简单，但是有一些细节
本体其实是
c
u
r
W
+
(
B
−
c
u
r
V
)
∗
w
i
v
i
curW+\frac{(B-curV)*w_i}{v_i}
curW+vi(B−curV)∗wi
不要被上面的蒙蔽，这里不用除东西，选择B
完形第二题跟去年一样的状压，所以我有经验了，很好想
x
−
l
o
w
b
i
t
(
x
)
x-lowbit(x)
x−lowbit(x)手摸一下，D
我认为四个选项其实都合理，但是硬要说的话，只有C是有意义的
今年题目比去年有水平，也比去年简单一点
后续可能会再探寻一下阅读第三题，我觉得出的很好