2025.11

• 2025/11/4

  A，61 / 100

  在思考怎么检验组成一条简单路径的时候想了很久才想到可以通过度来判断，之前的想法很复杂，导致花了大量的时间调，也没调对。

  两个小时终于把代码写对了，虽然交上去样例都能过，但不知道会不会超时，又不知道怎么优化，所以就搁置了。最后果然还是超。

  其实是被卡常了，将 multiset 改成 unordered_multiset 就能过。这就涉及到什么时候该用 unordered_multiset，不需要有序存储的时候就用 unordered_multiset。

  还要学习更优秀的做法。

  B，16 / 16

  大概十分钟想到答案是 \(cnt1\) 和 \(cnt2\) 的较大值，即有 \(0\) 的列和有 \(1\) 的行的个数的较大值。

  其实有很多性质都没想清楚，比方说一定有 \(cnt1=m\) 或 \(cnt2=n\)。

  C，0 / 0

  没看懂题。

  D，12 / 12

  暴力。

  ---

  \(11/4\) \(A\) → 100。

• 2025/11/6

  A，100 / 100

  很快想到了做法，一开始忽略了检验的时候端点两侧颜色的要求，卡了一下子。

  然而实现了很久，大样例里调对了一个数据就错下一个，调得很崩溃。

  花了两个半小时。感觉还是写复杂了，题解里检验的方法比我的简洁好多。

  B，0 / 0

  没想清楚什么时候抓不到，对它们移动的策略想得不清晰，感觉暴力都不会就跳过了。

  C，0 / 0

  不会暴力。

  D，13 / 13

  暴力。

• 2025/11/7

  CF2149\(G\)，超时还在调。

• 2025/11/8

  A，60 / ？

  一开始没有思路，也算浪费了很多时间。到最后几十分钟硬写了一个之前否过的结论，发现结论是对的。剩十几分钟的时候改成两个二分，不过还是超时。

  B，60 / 56

  写超级暴力的暴力的时候发现只会往后面跳，于是改成了 \(dp\)。加上特殊性质 \(A\)，预计 48 分。然后观察到特殊性质 \(C\)，踩到黑格子的最小次数一定是 \(0\)，所以最后全输出了 \(0\)。没去想第二个答案怎么做，所以能得 \(C\) 的 \(t=0\) 的 8 分。

  C，0 / 0

  没什么很直接的想法，换句话说就是暴力也不太会。

  D，12 / 12

  暴力。

  abc431：

  A、B、C 很快写完了。

  D 写得慢了一点，花了 30 分钟。好像是写的时候没注意只要从头向身体移零件，并且不能收集型，因为不一定要刚好移得头和身体一样重，大于需要移的总重量 \(sum\) 的状态要并到 \(sum+1\) 的状态上。贪心思路跟 s 组第一题一样，只是后面要 \(dp\) 选数。

  E 赛时想到了做法，就是走非给定的方向就要花一个代价，但是没写完。实现的过程中发现自己对 \(stl\) 用得很不熟练，比方说优先队列里面的类型是个结构体，我就不会写重载运算符。爆编的时候还不知道为啥。

  而且没看清题，它是射到 \((h,w+1)\) 结束。

• 2025/11/10

  abc431\(E\) → 100。

  abc431\(F\) → 100：

  有重复元素的情况，都可以先看作不一样的，做有序的排列，再除以重复的情况。

• 2025/11/11

  A，20 / 20

  大样例都画出来了但显然没什么用，想是想到了奇数度数的点在同侧或异侧这个方向，但是没有很清晰的做法，所以只写了特殊性质 \(A\)。

  B，0 / 0

  模数大不会处理。

  C，0 / 0

  这题感觉写了也没分。

  D，0 / 0

  放弃了。

  ---

  \(11/11\) \(A\) → 100。

• 2025/11/12

  \(10/28\) \(D\) → 100。

  \(11/11\) \(B\) 思考中。

• 2025/11/13

  A，10 / 10

  赛时在往前缀后缀方面想，思考一个正数可以填哪些负数，但是发现当时想的做法不能处理一个正数填了这个负数而不能填另一个的情况。并且没有正确意识到选最近正数的贪心，所以后面没什么思路了。

  改题改了很久，主要问题出在最后答案的合并，一开始没搞清楚不只是简单的相加，而也可以从左往右刷。

  B，55 / ？

  写的 \(bfs\)，没加任何优化，不知道能过多少，实际上 \(dfs\) 加剪枝就能过。改题的时候用下标类型是 pair 的 map 存答案，从而超时。所以说对 \(stl\) 的了解还不够，不能用得很恰当。

  C，40 / 40

  先写了 \(n^3\) 枚举，之后发现可以前缀和优化，把 \(n^3\) 改成了 \(n^2\)。但没转换到求异色角上。

  D，35 / 25

  暴力。

  ---

  \(11/13\) \(B\) → 100。

  \(11/13\) \(A\) → 100。

• 2025/11/14

  \(11/13\) \(C\) → 100。

• 2025/11/15

  感冒了实在太失败了。

  abc432：

  A、B、C 写得算顺利，B 一开始有点抽风 WA 了两发。D 好像怎么没想出来就跳了，因为发现 E 是一个板子。

• 2025/11/17

  \(11/15\) \(A\) → 100：

  模数写错了看了半天没看出来还是问ai问出来的。

  \(11/15\) \(B\) → 100：

  用前缀和的时候 h[max(0, i - j - 1)] 写成 h[max(1, i - j - 1)] 了，倒是挺容易发现写错了。

  一开始对拐弯的转移不太理解，纠结于一个点被经过两次会不会被重复算，因为我当时觉得转移需要加 \(a_i\) 或者什么别的，毕竟感觉拐弯跟不拐弯还是有点区别，可能要算一个新的东西。但拐弯可以变成一个不拐弯的状态。一个食物被吃了一次就会消失，所以相当于可以把拐弯之前吃的那段食物移到拐弯后走的那段上来，就变成一段整的，会在某一次从某个点开始不拐弯走的状态里算到。然后这个转移肯定可以往前推到某个不拐弯的状态，所以拐弯的状态就这么算。当前拐弯状态走的步数 \(j1\) 比转移来的不拐弯状态的步数 \(j2\) 多的部分就是在走被走过的没有食物的位置。

• 2025/11/18

  A，20 / ？

  除了暴力想不到别的。尝试推导致前后两个数大小互换的 \(x\) 的性质，想得比较混乱就没想了。

  B，0 / 0

  C，52 / 40

  通过第一个瓶子倒，不会超过 \(2n\)，估计 40 分。考场上没有想其他方法，其实拼一拼说不定有更多的分。

  D，0 / 0

  ---

  \(11/18\) \(C\) → 100：

  把题解做法和赛时代码拼一起。

• 2025/11/20

  A，20 / 20

  想到换根，但只是想到。其实只会暴力，想了一些别的做法，但复杂度好像跟暴力差不多。思考无果就结束了。

  B，20 / 20

  也是只会写暴力，不知道从哪优化。想了一些别的做法，但复杂度似乎比暴力还高。

  C，0 / 0

  基环树没有很熟，赛时也没有清晰的想法。

  D，0 / 0

  尝试了几种贪心都错了，最后的时间大部分花在这道题上，其实可以去写别的题的特殊性质。

• 2025/11/21

  \(11/20\) \(A\) → 100。

• 2025/11/22

  A，100 / 100

  看到期望两眼一黑，先写了暴力看期望的计算方法错没错。然后想到正解，写完之后有几个小数据输出跟暴力不一样，然后发现是暴力写错了。改得一样了之后第二个样例一直错，花了很长时间瞪代码，认为思路没错，只好去了一趟厕所，回来就发现之前的代码包括暴力总方案数全写的 \(n^2\)。

  B，15 / 15

  准备先写五方，但状态设计复杂了，后面写了一半觉得太复杂就懒得写，然后就写暴力。

  C，0 / 0

  D，0 / 0

• 2025/11/24

  \(11/22\) \(B\) → 100。

  abc432\(F\) → 100：

  先想到一种一定可行的方案，也就是从大到小移，\(n-1\) 次操作能完成。

  再思考什么情况下操作次数能变少，也就是从一个挪动到另一个的时候同时满足这两个数到达平均值。

  即每出现一组数使得这组数能内部均分成最后的平均值，答案就会减少一。问题转化成怎么样分出尽可能多的这样的组。

  注意到 \(n \leq 20\)，想到状压。可以每次选一堆数进行转移，但会超时。发现没有必要，可以一个个加数，到可以成为一组的时候再加答案。对于还原方案，记录前驱即可，还原时一组一组还。

• 2025/11/25

  abc432\(D\) → 100：

  \(n\) 很小，记录每个矩形上下左右界，每次暴力枚举分割。连通块暴力判两个矩形是否连通，用并查集处理。主要是赌没有那么多矩形，因为切割一次顶多把每个矩形都分成两个，然而最终的矩形数远不会有这么多。

  abc430\(E\) → 100：

  先写的哈希，调出来的问题是到处都忘记取模。但发现又有哈希冲突，所以改成双哈希，然后试了一两个模数试对了。

  然后写了 \(KMP\) 做法，写得比哈希快。由于 \(lb\) 数组没清空调了几分钟，可能是对 \(KMP\) 没有特别熟悉。

  CF2149\(G\) → 100：

  找初选次数大于三分之一的数，由于这个数出现概率很高，所以这类的题都可以用随机化，随机几十次每次随机一个在区间内的位置判断满不满足条件。

  首先随机化这样写：std::mt19937 rnd(time(0)); rnd()。其次这个做法是基于这个数出现概率高，所以肯定是随机位置，而不是值，不然所有数随机到的概率是一样的，就很大概率随不到。

  然后不要频繁调用 \(map\)，很慢，并搞清楚离散化的作用。超时的时候思考什么东西是毫无好处的。

  abc429\(E\) → 100：

  就是算最短路和次短路，从所有安全点出发 \(bfs\) 即可，记两条路，记得区分起点。

  abc430\(F\) → 100：

  每个 \(i\) 都要算答案，所以想到每个 \(i\) 可以单独处理。

  abc429\(F\) → 100：

  线段树的一个节点存有 \(d_{i,j}\)，表示这个区间里的第一列的第 \(i\) 行到最后一列的第 \(j\) 行用的最少步数，叶子节点也就是单独列的 \(d_{i,j}\)，表示第 \(i\) 行到第 \(j\) 行用的步数。

  关键在于知道连通性可以合并，也就是说 \((x,i)\) 到 \((y,j)\) 可以通过中转点 \((z,k)\) 到达，所以左右儿子的合并可以用类似于 \(Floyd\) 的做法合并，也就是枚举头尾两列和衔接列所经过第几行。

  题目转化成线段树单点修改区间查询。注意每次要把 \(d\) 数组重新初始化成极大值，然后合并的时候衔接处要加一。

  然后其实因为如果衔接处不能走，\(d\) 肯定是 \(1e9\)，不会被算到答案，所以不需要特殊判断是不是井号。

• 2025/11/26

  abc428\(D\) → 100：

  发现如果后面一段长度确定，可以把 \(x\) 的范围求出来，从而求出整个拼出来的数的范围，问题变成该范围内完全平方数的个数。要知道 \(1\) 到 \(n\) 里有 \(\sqrt{n}\) 个完全平方数。

  注意 long long 可能不够，然后开根的时候使用 sqrtl。

  abc428\(E\) → 100：

  距离一个点最远的点一定是树的直径的两个端点其中之一。所以找出一条直径再判断这个点到哪边更远即可，注意要找编号尽可能大的。

  abc428\(F\) → 100：

  观察到前一个区间无论怎么动也会被后一个区间包含，所以一个数在一个区间里不存在，在它之前的区间也不会存在，所以可以二分。感觉区间修改的线段树没写很熟。

  abc427\(D\) → 100：

  步数很少所以直接记搜就可以了，状态就是当前位置和步数。博弈部分比较直接，当前先手有一种情况赢就能赢。然后这题不用考虑没路走的情况，因为这题说了每个点出度至少为 \(1\)。

  abc427\(F\) → 100：

  \(n\) 小想到折半。一开始写超时了，当然会超时，居然枚举和。直接记取模后的和就行了。

  abc427\(E\) → 100：

  其实好像直接移垃圾也没事，\(bfs\) 就可以了，以还在框里的所有垃圾的位置和步数为状态。

  abc426\(D\) → 100：

  考虑哪段不动就行了，其他的相同符号的用两次操作，不同符号的用一次操作。

  abc426\(E\) → 100：

  分成两段，一段是两个人一起走，一段是一个人停着一个人走。两段两个人相距的距离都是单峰的。所以去学习了三分这个算法🤔。

  abc426\(F\) → 100：

  线段树，倒是觉得区间修改比以前熟一点了，吧。注意开 long long。

  abc433\(E\) → 100：

  从大到小填，这个比较重要。然后想一下分讨，分为行列出现过、只有行、只有列、都没有。只用输出一个方案，还挺好的。

• 2025/11/27

  abc425\(F\) → 100：

  \(n=22\) 想到状压，一个二进制数表示出没出现过。要注意从同一个状态转移过来的情况，只算一次。

  abc425\(G\) → 100：

  先写了一个暴力，也就是枚举 \(x\) 然后在 \(trie\) 树上走。然后发现一段数里，很多数的移动轨迹长得很像，所以可以在 \(trie\) 树上分治，分为当前位为 \(0\) 为 \(1\) 来走。一定要注意从哪一位开始枚举，要统一。

  记录两个区间，一个是题目给的，一个是包含题目给的的、基于所有数的一个大区间，用来算跟题目里的交集，从而确定哪一半是 \(0\) 哪一半是 \(1\)。

  把一半强制分到另一边处理的时候会处理到很多处理过的状态，所以加上记忆化。

  abc422\(D\) → 100：

  肯定是尽量平分。考虑从上往下分，所以答案不会超过 \(1\)。注意题目里是先算一遍 \(x\)，再改数组，所以如果一开始就不能平均分，答案就不可能为 \(0\) 了。

  abc422\(E\) → 100：

  又是这种出现概率很大的题，随机两个点再对每个点判断是否在这条线上即可。emm，数学不好，求 \(a、b、c\) 是有公式的。

  abc422\(F\) → 100：

  把答案的计算换个方向看，每个点的贡献是 \(w_i\) 乘它走多少步到终点。所以状态就是当前在点 \(i\) 、还有 \(j\) 步到终点的最小代价。

  abc421\(F\) → 100：

  链表直接做就可以了，有个判断操作二中 \(x、y\) 前后关系的技巧，就是让它们同时往右边走，如果 \(x\) 走到 \(y\) 原来的位置，\(x\) 就在 \(y\) 左边，反之 \(y\) 走到 \(x\)，\(y\) 就在 \(x\) 的左边。

  abc421\(D\) → 100：

  把段再分成小段，使得两个人每次都是走直线。然后每段每段走，分类讨论。要么同一起点且同一方向，这个时候整条路上都相遇；要么不同起点，就只会有一个交点，算出交点即可。

  并且，它们要相遇就肯定是走 \((abs(x1-x2)+abs(y1-y2))/2\) 步，以此判断会不会走到同一个点即可。

  abc423\(F\) → 100：

  要用 __int128，但用了会超时，所以在最小公倍数大于 \(Y\) 的时候就不要继续算了。