Pozhu's blog

11月4日闲话

在其他题解中获得了许多教益，终于看懂了这题，于是写一些其他题解中认为过于基础而略去的细节来帮助像我这样的萌新。 感谢奆佬和奆佬。 首先是这题的题意转化：在所有子矩形中找到不包含给出的任何一个特殊点且周长最大的一个，输出其周长。 这题的 $n^2$ 做法是较为容易理解的： 我们一定有一种构造方案，使得答案为 $2 \times (\max(w,h)+1)$ ，具体就是长为 $\max(w,h)$，宽为 $1$ 的细长条。 于是最优的答案矩形周长不小于这个值，那么它不可能龟缩在整个大矩形的某个四分之一的角里。 于是它一定至少经过横坐标的中位线，或纵坐标的中位线。 我们讨论这两种情况，答案取 $\max$ 即可。这里不妨只讨论经过纵坐标中位线的情况。 我们在所有的点中取两个点来限定子矩形的左右边界，设为 $i,j$ ，不妨设 $i < j$。 当 $j=i+1$ 时，这两个点相邻，那么中间没有上下界的限制，可以顶满，答案就是 $2 \times (x_j - x_i + h)$。 否则这两个点中间还有其他点，由于这两个点被钦定为左右边界，其他点就只能做横向的分割。并且这里我们讨论的是越 ...

雄关漫道真如铁，而今迈步从头越，从头越，苍山如海，残阳如血 这是一份CSP失利后的反思总结。 最大的失利并不是挂分，而是在思考一整场甚至没写对拍并完全不挂分的情况下获得了难以接受的低分。 这断绝了我所有自我安慰的借口。 不过，这次正式比赛也确实暴露出了我的许多问题，这正是我想要提升所必须纠正的。 首先是考试策略。 我的策略太过保守，对于时间安排也存在不尽合理的情况。其中T2的75分暴力我调试了1h+，而我如果把这个时间用来想正解，那么我应当能够解决掉这个问题，并且代码实现也更容易。 其次是考试心态。 我的心态是极危险的，它似乎只适合全都是难题的场，而CSP显然并不是这样。 我满足于一个高分的暴力，并对这场比赛的结果有了过于乐观的估计。 平日的训练题是更难的，大家都难以写出正解，那么这个暴力分数是不低的。然而我将这样的思想带入了CSP考场中，也就造成了一场失败。 而我当然不应将这错误的心态归咎于平日的训练。我也确实没有做到像大多数人那样一眼秒掉T2 然后是知识基础。 我的知识基础是不均衡的，它的一部分达到了足够使用的水平，但更多的地方则充满漏洞。 我不擅长图论，或者说图论只会最短路和 ...

刷杂题捋思路用的草稿纸，懒得排版所以干脆加密

国庆集训日结

9.28-9.29做题总结

今天花了一晚重打CSP-S 2021，但是最终只得到了 145pts ，比预期要低很多。 （甚至是用IOI赛制打的） 回顾这段时间的时间安排和策略，做如下反思 ： 首先在 T1 上嗑了太久，开场前 80+ 分钟都在看 T1 ，但是最终竟然也没想到正解。 { UPD 9.28 : 看了看题解，发现距离正解就差一点点……md我甚至想到了前缀和，结果死在没想到给廊桥编号每次维护最小的廊桥编号。 现在属于是经典看题解秒懂了。 } 然后再次浏览了整套卷子，觉得 T3 比较好做，于是手玩了一下样例准备找性质糊结论。 然后很顺利地发现了某性质 ： 对于每个数只出现两次，由于维护的是回文串，当第一次出现位置确定之后第二次位置随之确定。 于是我们要保证第一次取出的位置能使第二次成立。 然后发现每次只能从头尾取，而对应位置在队列中间，如果两个不同数的对应位置不再中间相邻的话，那么他们对应位置中间的数就没办法取出……可能描述不太严谨。 然后这个思路让我决定在维护队列两侧的 $l,r$ 同时维护中间的 $ql,qr$ ，表示连续的 “对应位置” 形成的子串，每次先尝试取 $l$ ， ...

9.25-9.26做题总结

9.14-9.23做题总结

Trie 树Trie树挺简单的就不介绍了，放一下代码。 一下四种写法的代码都以P2580 于是他错误的点名开始了这道经典题作为模板，记录了一些评测信息。 使用指针的递归版本1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980#include<bits/stdc++.h>// Recursive version using pointers// Using C++14(GCC9)// 576ms/63.32MB without O2// 478ms/63.35MB with O2namespace Pozhu{using namespace std;#define N 10010#define M 100010struct Trie{ Trie* son[26]; char val; int ...