幻影彭的彩虹

记录青春的扇区

发表于 更新于 分类于

CSP2022

从 19 年初二第一次参加 CSP，到今年可能的最后一次，已经四年了。

停课停了也快两年（其中被半停课耽误了半年），勉强到了省队水平。

19 年的 CSP-S 很是开心，毕竟学 OI 8 个月的我和我的朋友，都顺利拿到 1=，只是可惜另一位没有过初赛。

20 年的 CSP-S 有点揪心，CE T2T3 失去了取得历史最高全国排名的机会，（这一年是真的是超水平发挥，100+0+0+95）。但是咱还是顺利 AK 普及组，第一次上了学校的宣传。

20 年发生了很多事，最初一起学 OI 的两位朋友（现在也是最好的朋友），因为各种各样的原因，离开了 OI，我以为我已经是独自一人，但我又结识了新朋友——佳馨和walk。

21 年的 CSP-S 只能说是一般般，我没有做出 T3，T4 也没有写出暴力，遗憾的以 260 画上句号。这一年发生了太多事，NOIP 因为莫名奇妙的原因变成了 0 分，自然无缘省选，高一省队的理想破灭。

22 年，我在 NOIP 碰壁后回归文化课调整心态，期末拿了一个还算行的成绩，我没想到我的文科成绩比理科还好，哈哈。这段时间我接触了软件工程，自己尝试着写工程，学会了 Python 和 JavaScript，22 年开学继续停课冲击省选，虽然我没有机会参考，但水平不能落下。省选自然是几家欢喜几家愁，高三的一位学长心态出了问题，甚至无缘 D 类，佳馨顺利进入省队， walk 以一名之差留在外面，我在 Day1Day2 的下午分别到原考场（我们学校是考点）做了题，心情很是糟糕。省选后学了 2 个月的文化，OI 的水平开始停滞。学完高一的文化课内容，去了外地集训，但是水平并没有太大提升，回学校后开始常态化考试，停滞的水平继续有了一些上涨，这个时候我还要兼顾两三个工程项目的开发，非常累，于是就把工程项目全部推了，发现好像又有点无所事事，最后还是捡回来了一个，CSP 前一周和佳馨研究 web 相关的东西，为盒武器的研发做准备，不小心把 vjudge 搞炸了，后面操作就很小心了，没再出事，事实上我周六早上还在一边写我 mirai-plugin 项目的 kotlin，一边和教练聊怎么学 Python。

终于出发了，在校车坐在前排上一路唱着歌，但是后面的学弟们都没听，我甚至还没有意识到我已经是车上年级最大的人了，还是那副嘻嘻哈哈的脸。

到考场，和转学的同学面基，还拍照留念，然后进考场的时候感叹人家是什么机房，我们是什么机房，有一说一， i7-12 的机子用起来那是一个舒服，可惜 windows 下没有高版本 g++，被迫用 c++11 语法，战斗力下跌 10%，发现有没有 Python，战斗力再下叠 5%。

发题，顺序开，T1 想都没想一个 bfs 求全起点最短路先糊上去了，然后定义了 dp 准备 dp，发现好像不太好搞，想了一下，还是得枚举，枚举策略就那几种，试试就出来了，但发现有不少细节，于是停下来认真构思代码，用了一些面向对象的思想，很顺利的一遍写过，通过所有大样例。

T2 看了一下，简单题，还是细节很多，继续停下构思代码结构，又使用了一些面向对象的方式，写出来很优美的代码，一遍过大样例。

此时还剩 3h，我尝试开 T3，比较顺利的想出 60 暴力，发现不会正解，难道要重蹈覆辙？发现数据其实挺难造的，于是考虑乱搞，写了一个放 Tag 的做法，我尝试 Hack 这个做法，没有成功，但是我确实知道这样的复杂度是假的，我从来没怀疑过自己造数据的能力，我并不认为出题人造数据的水平能比我高到哪里去，所以大胆当正解写了，我对自己的常数也很放心，大致思考了一下最坏情况，如果目标为 \(80pts\)，操作数其实可能也就 \(4\times 10^{10}\) 的样子，而且不可能卡满，但是没有高版本 g++，unordered_set 用起来还是有些提心吊胆的，如果有个 gp_hash_table，我会放心很多。大样例那么水，当然轻而易举跑过啦。

这时我还有 1.5h，思考了一下，扣除了 0.2h 最终检查的时间，我放弃了 T4 正解，尽管我浏览题目时已经想出了它的正确解法，我把目标定为 68pts 的暴力，但是并不顺利，我没有通过最后一个大样例，而且无论如何都找不出问题，最后应该是 36~40 分。

出来自测，不出所料，所有民间数据都卡不掉我的 T3，目前是 100+100+100+40

发表于 更新于 分类于

A

B

首先求什么东西的和，这类题，一看到就要想是不是该开 long long。

C

多测题，特别是样例水的题，一定要认真检查清空，以及不要读入到一半 break 出去！！！

发表于 更新于 分类于

F

不算难但有坑点的题。

很容易想到可以抓鱼的时间是当且仅当某两条鱼距离为 \(A\) 时。

所以考虑左边那条鱼，分别计算右边的鱼是哪一条时可以抓到的最大重量。

我实现的时候出现了负数时间，但是不能在负数时间抓，故我忽略了负数时间的最大值贡献。

但是考虑到可能第一个正数时间的事件是某条鱼游出了范围，所以需要修正，要么弄个 \(0\)，要么在每个事件发生前取下最值。

G

有趣的题。你需要放最小数量的监视器到一个矩阵中，矩阵中有监视器不能越过的障碍，每个监视器往上下左右中一个方向看，可以看到自身位置。你需要保证所有非障碍点都被监视。

最开始想的是假定先放横着的贪心放竖着的，但是不行。

后面思考了横着和竖着的关系，发现如果将所有的横块看成一个点，竖块看成一个点，那么能构成一张二分图，二分图的每个边就是每个需要监视的点！

本质上是最小点覆盖问题，可以用网络流解决。

二维网格图的行和列，和二分图有着紧密的联系，涉及对横边和竖边分别操作时，需要求最小或者最大值，一定要考虑到网络流，数据范围如果在 \(100-500\)，那么就更应该思考网络流的方式。

发表于 更新于 分类于

D

很有意思的一道题，感觉有人一碰到这种二维平面上的图论题就只有瓜起。

首先它是一个跳棋形式的题目，我们不要考虑去移动床，考虑移动空格，容易发现相邻的两个空格一定不会是同一个空格，所以可以枚举每两个相邻的位置，计算这里有空格的最小代价。

怎么算，感觉两个东西是独立的，可以直接跑最短路。

实际上也确实是这样的，由于最短路必定不会经过同一个点两次，所以考虑某个空格在一个点时的移动方式，如果它使用了某个床两次，那么一定在第二次使用这个床时回到了原点，必定不优。

感性的考虑在两个点路径距离大于等于 \(3\) 的任意时刻，二者的路径都是互不影响的，小于 \(3\) 时已经相遇，所以两个点时独立的。

怎么说，虽然没做出来，但是这道题还是给了我们思考这类题的方向。

发表于 更新于 分类于

E

一个 \(n\times m\le 3\times 10^5\) 的网格，里面有一些 \(1\)，其余是 \(0\)，你需要填上尽可能少的 \(1\)，让网格上下不连通，并且 \(1\) 之间边不相邻。

这道题还是发现我网格图图论不扎实的问题。

首先很容易想到一定会存在一条自左到右的链，分隔了上下两部分。所以我直接从左到右 \(DP\)。

但是得到了 \(WA2\) 的好成绩。

左思右想也找不出问题，但是对拍后发现似乎是可以往回走的。

改成最短路算法就通过了。

矩阵图论的题目，不要只看到自左向右，要考虑存不存在往回的可能。

如果没有错过，确实很难意识到这种思维漏洞，所以一定要记住！

发表于 更新于 分类于

随便写写

昨天考试，模数很离谱 998244 8 53，我文件名还写错了，挂了 190。

考完在机房随口骂了出题人两句，自己也没当回事，题做不来，看错了，我本事不够，我认，文件名写错，我的问题。骂人，就是心情不好，也没多想。

上周有套题出的很离谱，考完也在机房骂了几句，想着反正已经考完了，相当于是下课时间，发泄几句也没什么。

上周教练下午找我聊，说要控制情绪云云，我没当回事，说 “我就是这个性格”，骂出来被批最多难受 10min，不说两句说不定憋着难受一个星期，这件事也就这么稀里糊涂的过了，高一的老师 qq 找我聊了一下，说我 "恶意发泄情绪"，我想确实是这样，虽然我还没把所谓的 "恶意发泄情绪" 当回事，不过配合老师工作，我还是接受惩罚，20 个俯卧撑当锻炼了。

昨天考完又骂了几句，然后一起考的同学都没怎么管，晚上教练叫我和我爸打个电话，打过去披头盖脸就是一顿骂，我好好的心情被这一顿搞炸了，随即想都没想就怼了回去，也没有什么目的，就是对着干，爸叫我，自己反思错误，手写检讨，晚上 11 点前拍照发给他，否则第二天来学校接我回家。

我...

说实话我确实不知道骂几句又有什么问题，搞得这么恼火，反正一下子就哭了。

稍微冷静一下去找了 Walk，和他好好聊了一会儿，其实我能想到看到的东西真的很少。。。

回想一下，Walk 说的确实有道理，再怎么说，直接骂出来是一件很不好的事情，虽然骂出来确实很爽，不过可能我不把这件事当事，很多人也不会放在心上，甚至有共情，但总有一些居心不良的人干一些龌龊的事，骂人了确实会留下一些把柄。注意，我在这里甚至用了 "居心不良" 这个非常文艺的词，而没有用一些更加常用的，更能表达我对这些人看法的词。 所以这件事终归还是我有问题。

冷静下来和老爸回个电话，说了这一点，但是爸还是说我没有看到主要问题，我这一部分看法只是很小的一面。

他说了这些点：

  • 保护自己，别留下把柄（我说到的）

  • 这件事让身边的其他人很难办。

  • 不可避免的受到了一些网络影响。

  • 情绪控制上的问题

  • 文化素养的问题。

第一点就不再多谈。

第二点，这里的其它人并不指同学，指老师，他举了一个挺现实的例子，假定老师要写评语，那这件事情怎么办。可能平日里不会在意，但是比较正式和严肃的场合，爆粗口这件事情被提出来肯定会有很大的形象减分，所以为了咱还算行的个人形象，少骂几句。

第三点，我也不得不承认受到了整个 OI 圈某些不太好的风气的影响，走偏了，或者说没有守住 "本心"，在被不好的 "大多数" 带着走，以前完全没有意识到这一点，还是需要想想，是不是 "大多数"，就是正确的，这个 "大多数"，甚至还是片面的，是一个小圈子。所以，哪些是精华，哪些是糟粕，需要认真思考。

第四点，情绪控制，说起来容易，做起来难，人脑和电脑是一样的，CPU 寄存器就那几个，赛不了太多东西，情绪控制的数据都放进了内存了，但是情绪上来的时候，不要说内存延迟的 200 个周期了，L1 几个 CPU 周期你都等不了，会直接把寄存器里的情绪用最快捷的方式扔出来，放电脑上就是——"死机，爆炸"，所以最有效的方式还是多找找样本，多获取一些负反馈，让你的思维模型对情绪控制更敏感，遇到相似的输入能够把读取 "情绪控制" 模块的权重算的高一点，所以还是一个阅历的问题，样本不够，训练出来的 AI 就是典型的 "欠拟合"，处理基本问题都没有办法，换到人身上就是 "年轻人"。机器学习之所以叫机器学习那是因为它模仿了人的学习过程，是有道理的。

第五点，其实我不太想细谈，爸总是把文化素养和 "语文" 挂钩起来。我很讨厌以主观看法作为基础的一切。放在义务教育中，就是语文，历史，和政治。为什么我不把英语算进来？英语学习的是使用英语这个工具，而不是学习语文这种主观印象。除开义务教育，一个典例就是中医，也许我对中医有误解，但是至少到现在为止，我还认为它是一个以主观看法为基础的 Subject，所以直接告诉我。

发表于 更新于 分类于

考试

T1

套路状压题，有一些关于分支的常数优化技巧

T2

有趣的容斥原理题，但是不太适合出在考试。

首先猜想答案比较多，所以考场上直接一个随机化过掉。

考虑两人集合交的大小 \(\sum|S_i\bigcap S_j|\) ，如果能算出这玩意，很容易用鸽巢原理算出答案个数的下界。

考虑每个元素对它的贡献，是 \(\binom{cnt_i}{2}\) 的，所以 \(cnt\) 的分布需要尽可能平均，不妨让它就为 \(cnt_i\)。

所以上面那个式子的下界是 \(\dfrac{n^3}{4}\) 级别的。鸽巢原理，集合总个数为 \(\dfrac{n\times(n+1)}{2}\)，每一个集合先分配 \(\lfloor\frac{n-1}{2}\rfloor\) 个，剩下的数级别是 \(O(n^2)\) 的，因此答案个数是 \(O(n)\) 的，期望随机 \(n\) 次可以找到一组合法解。

T3

能看出很多问题的题。

题目本身不难，但是坑点极多。

考虑转化问题的时候一定要搞清楚转化的前提条件，以及对应的充要条件。

第一次出错：认为选定合法的删除子序列后一定有解，实际上没有位置放 \(1/0\)

第二次出错：认为必须留位置给 \(1/0\)，但实际上有可能根本不存在 \(1/0\)，留位置是没有意义的，需要特判。

另外还有必要提的一点是，这种选择一个元素，移动到任意位置的题，往往可以考虑最终结果，也就是选择了哪些，或者是选择了哪些不动。

和求改为最长不下降子序列最小代价的题目一样，可以考虑补集转化，最多的，能不动的元素个数，就是 LIS，LCS 的长度。

多次出错的原因也就是误以为只要选择合法，那么就一定可以构造合法的方案。

T4

有趣的贪心题。

我们给矿工分级，并认为操作是放一组矿工，每个矿工只能挖一个，\(k\) 级矿工能挖掉距离小于 \(k\) 的点。

考虑有一条线从下往上扫描，我们需要尽可能把矿工往上放，这样能够到更多的点。

先考虑最深的必须放矿工的点，它一定满足，\(k\) 级儿子有一个还没有被挖的宝藏，否则可以继续往上，这一定不劣，不妨从最简单的情况开始。

假设在这个点放了矿工，那矿工必须挖掉 \(k\) 级儿子，否则上面就处理不了了。如果矿工还能挖，那么需要让他把 \(k-1\) 级儿子也尽可能挖，因为如果让父亲处理，需要付出一个 \(k\) 级矿工的代价，但是这个点的矿工上到父亲的时候降级为 \(k-1\) 级，矿工等级显然越高越好，对于等级低的儿子，在这里挖可以看成于先上去降级再挖。

所以在第一个必须放矿工的点，矿工必须挖掉 \(k\) 级儿子，尽可能挖 \(k-1\) 级儿子，意思是如果还有 \(k-1\) 级儿子没有挖完，那就没必要再放矿工，可以留给父亲处理。

接下来的点就有不同等级的矿工了，对于 \(i\) 级矿工，他会尽可能挖掉和它同级的儿子，如果还有剩余，会挖掉 \(i-1\) 级儿子，这个过程一定要从等级小的矿工到等级大的矿工考虑，否则会变劣。

剩余的矿工降级后上传，儿子升级后上传。

按照这个策略贪心即可。

发表于 更新于 分类于

代码层面

由于现在考试都开 O2，所以只讨论有 O2 的情况。

循环展开

由于 CPU 处理分支的能力很烂，所以循环展开加速的一部分原因在于减少了分支。

测试标准为 \(10^5\) 次随机区间求和，大小 \(10^5\)，以下代码用时 572ms，for 循环用时 1192ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for(int i=1;i<=m;i++){
    long long sum[4]={0,0,0,0};
    int j;
    for(j=l[i];j+3<=r[i];j+=4){
        sum[0]+=a[j+0];
        sum[1]+=a[j+1];
        sum[2]+=a[j+2];
        sum[3]+=a[j+3];
    }
    for(;j<=r[i];j++){
    	sum[0]+=a[j];
    }
    ans^=sum[0]+sum[1]+sum[2]+sum[3];
}

将 sum 数组替换为多个局部变量，效果不变。

测试了其它展开位数，开 8 位效果最佳，约 520ms。

16 位会出现寄存器溢出效率下降。

如果用的求和变量较多，最好开 4 位。

顺便一提，开 Ofast/O3 后会帮你展开。

如果你写了假的循环展开，那么效率提升只有约 \(50\%\)，这是假的循环展开，但是开了 O3 就是真的了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
long long calc(int* begin, int* end) {
	long long res = 0;
	if ((size_t)begin & 4) res = *begin++;
    unsigned long long sum[4];
	while (begin + 7 <= end) {
        auto addr = (unsigned long long*)begin;
        sum[0] += addr[0];
        sum[1] += addr[1];
        sum[2] += addr[2];
        sum[3] += addr[3];
        begin += 8;
    }
    for (int i = 0; i < 4; i++) res += (sum[i] >> 32) + unsigned(sum[i]);
    while (begin < end) res += *begin++;
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
for(int i=1;i<=m;i++){
    long long sum=0;
    int j;
    for(j=l[i];j+3<=r[i];j+=4){
        sum+=a[j+0];
        sum+=a[j+1];
        sum+=a[j+2];
        sum+=a[j+3];
    }
    for(;j<=r[i];j++){
    	sum+=a[j];
    }
    ans^=sum;
}

用时 832ms。

减少分支

这个减少分支主要指减少内层循环的分支，尤其是理论预测成功率很低的分支。

CPU 的分支预测，可以视为一种很智能的找规律，在几乎不执行，几乎执行的情况下，或者是否成功具有循环节之类的情况，具有极高的预测效率。

当分支预测失败时，有较大可能会从内存中重新读取对应代码块，

一般可以采用乘法等算术方式。

不建议写偏向条件赋值的代码，因为高版本编译器可能会弄成条件执行，它以认为它读懂了你的代码，但是它就是个蠢逼。

在一些比较极端的情况，甚至能带来 \(5\) 倍的效率差异！

这里的 \(k=10\)。

例子：

1
2
3
4
5
6
for(int mask=0;mask<1<<(k+1);mask++){
    int final=0;
    for(j=0;j<k;j++)if(bool((1<<j)&mask))
        final^=stat[mask>>k][j];
    dp[(i+1)&1][final]+=dp[i&1][mask&((1<<k)-1)];
}

可以换成：

1
2
3
4
5
for(int mask=0;mask<1<<(k+1);mask++){
    int final=0;
    for(j=0;j<k;j++)final^=bool((1<<j)&mask)*stat[mask>>k][j];
    dp[(i+1)&1][final]+=dp[i&1][mask&((1<<k)-1)];
}

或者更理想的：

1
2
3
4
5
for(int mask=0;mask<1<<(k+1);mask++){
    int final=0;
    for(int w=mask;w;w-=w&(-w))final^=stat[mask>>k][__builtin_ctz(w)];
    dp[(i+1)&1][final]+=dp[i&1][mask&((1<<k)-1)];
}

__builtin_clz() 返回一个数二进制下前导 0 的个数，对于负数，返回值是 0

__builtin_ctz() 返回二进制末尾连续 0 的个数。

三份代码的运行时间分别为 1200ms 213ms 150ms。

高速缓存

一般情况

用一句话来说，能滚动的数组要滚动。

可以看看这两个提交，效率改进因子为 1.6。

无滚动数组，390ms。

滚动数组，150ms。

互踢缓存

如果遍历数组的顺序和数组的大小都不太理想，很容易出现互踢缓存的特殊情况，在一些极端情况可能会带来 10 倍甚至 20 倍的常数差距。

缓存存储的基本单位是 cacheline，大小为 64Byte，将一个数据物理地址的末六位抹掉，可以得到它的缓存行编号，缓存行编号视高速缓存大小和分组策略取末 \(k\) 位，作为高速缓存使用区域编号。同一高速缓存使用区一般可以存储 16 个 cacheline，如果超出，则踢出最早进入的。

举例来说，如果以 256Byte 作为步长遍历数组，那么由于抹掉 \(6\) 位后末 \(2\) 位是一样的，所以实际被利用的高速缓存仅有 \(\frac{1}{4}\)，会出现非常阴间的情况，需要避免。

访问连续

访问连续有两个层面，缓存行连续访问，页的访问连续。

一般强调前者。

算法层面

0%