中考前最后一场 CF（指的是我回归文化课以前的最后一场）的好题。 拖得也有个半年了。 ------- 首先不难发现 $a$ 和 $b$ 肯定都是有循环的。设循环节为 $k$ 则 $a_1$ 一定等于 $a_{k+1}$，因为 $a_{[2,k]}$ 都相等且 $a_{[1,k]}$ 和 $a_{[2,k+1]}$ 在重…

## 省流 $60+0+10+36$。 又忘记清空导致自己成为了全机房唯一 T1 $80-$ 的人。 [NOI2021 轻重边](https://www.luogu.com.cn/problem/P7735)也是一样的问题。 ---- :::info[Hint 1] 考虑哪些数是有用的。 ::: :::success[…

本题相当于要对这样的序列进行计数： - $\sum_{i=1}^{n}a_i=3\times m$ - $\max\left\{ a_i\right \}\le 2\times m$ - $\sum_{i=1}^{n} a_i\pmod2\le m$ 看到这种题可以往容斥的角度上面去思考。本题考虑对第二个限制进行容斥。…

看到删除操作就可以往这么一个方向上去想了： > 设 $nxt_i$ 代表如果从 $i$ 开始插入，之后环形插入，第一次出现删空**之后**再往 $s$ 里面加数，加入的第一个数的位置。 > > （这里的位置可能会 $>n$，因为我们在记录位置的同时要记录是第几次走到这里，这样才能应对 $k$ 轮的变化） 之后直接暴力跳…

# $2023/10/28$ 在南山中学打 CSP-S。 半小时速通 T1 后在 T2、T3、T4 之间横跳。 T2：写完 $O(n^3)$ 区间 dp 然后不知道该怎么做了。打完特殊性质 A 就紧急下播了。 T3：大模拟。场上打完 A 性质就摆烂了。 T4：不想写。感觉写了还有些分的。 估分：$100+45+15+0…

不朽的思维题！ **本题解会使用 CF Hint 的风格。** ---------------- ::::info[Hint 1] 如果把 $\frac{1}{n}$ 换成 $\frac{1}{n-1}$ 应该怎么做？ :::success[答案] 对于任意树，$f(t)=1$。 ::: :::warning[证明思路…

做过 [CF489F](https://www.luogu.com.cn/problem/AT_abc273_g) 但做不出这题的蒟蒻这辈子有了。 再怎么说也不该有 $2400+$ 啊！ ---------- 设 $dp_{cnt1,cnt2}$ 代表**抵达还剩 $cnt1$ 列为 $1$、$cnt2$ 列为 $2$…

## 题面 给定 $c,x$，构造 $n\oplus c\mod n=x$。 ## 解法 参考了[官方题解](https://atcoder.jp/contests/arc208/editorial/14209)和[这篇题解](https://www.luogu.com.cn/article/2p9rb6z2)的做法。…

葬送整场比赛的题。看不懂直径的做法，来一个**子树合并+换根**的做法。 首先考虑处理出每一个子树 $u$ 内深度前两大的点，要求它们分别属于子树 $v_1$ 和 $v_2$ 内（$v_1$ 和 $v_2$ 均为 $u$ 的直接儿子，且 $v_1\neq v_2$）。记录它们所在的子树、它们本身的编号、距离。 定义 $…

如此费解的题目，我拖了半年才终于搞了出来…… ---- 以下设 $dp_i$ 代表把 $[i,n]$ 区间排列整齐的最多可保留的书的数目。通过暴力搜索和肉眼观察可得：**每一本书最多移动一次！** 转移分为 $3$ 类： - 移动这本书：$dp_i=dp_{i+1}$。 - 将所有某种颜色的书之间的其他颜色的书移走：设…

来不及写就被我妈要求回去睡觉了。 ----- 考虑对称图形的性质： - 有 $\ge 3$ 条边。 - 边两两配对，只剩下 $0/1/2$ 条边。 只剩下 $0$ 条边是好处理的，但是要注意必须至少有两对相等边。 剩下 $1$ 条边需要使其小于其他边的总和。 剩下 $2$ 条边要求较长边小于其他边的总和（包括另外一条剩…

近期的 CF 补累了回来做杂题！ 这道题我走了不少弯路，尝试了很多错误的解法，最终才找到正解的。 --- 看到题目之后首先想到的是连通块数等于点数减边数，于是写了一个这样的代码： ```cpp #include #define mp(a,b) make_pair(a,b) using namespace std; in…

哈哈，橙题没场切。 令 $b_i$ 为 $a_i$ 的前缀和。倒序操作，每一次可以选 $C_{b_i}^{a_i}$ 个答案，最终答案即可 $\prod_{i=1}^{n}C_{b_i}^{a_i}$。 用杨辉三角处理组合数即可。 ```cpp #include #define int long long #defin…

CF 做不进去的蒟蒻先把这题题解写了。 这是把我送进水名的题目。也是我切过的 kenkoooo 分最高的 AtCoder 题。 --- 首先考虑 $x$ 一定在 $y$ 前面的做法。 因为加入的数不重，所以一定可以记录每一个数的前驱后继。每一个数都只会被删除一次，所以一定是 $O(n)$ 的。 回到原问题，需要记录 $…

看起来就在觉得它和 NOI2024 的[树的定向](https://www.luogu.com.cn/problem/P10787)（其实我压根儿都没有做过这题）有啥关联，其实一点没有，这是个我上了高一都不会的普及组题。 --- 运用 [NOI2024 树的定向](https://www.luogu.com.cn/pr…

怎么有人这题写了 $221$ 行？ 第一个要考虑的问题是**答案的上限**。根据小学奥数，要把一个数拆成若干个等于它的数，应当尽最大努力拆 $3$，最多拆两个 $2$，绝不拆 $1$。 将 $70$ 这样拆分能够得到的最大答案上限 $\le 2\times 10^{11}$，所以 $k$ 的实际范围是 $1\sim 2…

q1uple 随手切了，膜拜。 --- 推式子： $$m=\sqrt{n^2+n+x}$$ 去根号： $$m^2=n^2+n+x$$ $$(2m)^2=(2n)^2+4n+4x$$ $$(2m)^2=(2n+1)^2+4x-1$$ $$(2m)^2-(2n+1)^2=4x-1$$ 把左边写成 $(a+b)(a-b)$…

什么时候全机房都能切 E 了？我不是成废物了？（机房 $13$ 个人有 $12$ 个场切 E，但只有 $8$ 个场切 D） --- 并查集维护所有的连通块，用 $ans_i$ 代表以 $i$ 为根的连通块的黑色点数目。 因为要知道所有点的颜色，再开 $col_i$ 代表每一个点的颜色。 一个要注意的细节是在合并时，要把…

第一次实现 ABC 切掉 ABCDEF，也是第一次 Performance $2000+$，纪念一下。 看来集训了那么久起到效果了啊。 --- 看到**所有的串都是子串**就可以往 AC 自动机上状压 dp 想了。 设 $dp_{i,j,k}$ 代表已确定了 $[1,i]$ 位，在 AC 自动机的第 $j$ 个位置，包…

这题评紫纯属虚高，建议降绿。 前置知识：【5】深度优先搜索、【6】搜索的剪枝优化。 对于一个位置，如果它所对应的字符还没有匹配，就枚举所有合法的结果。如果已有匹配，也要判断其合法性。 另外一个要剪枝的地方就是如果一组数据已经找到解了，就立即退出。 具体来说，所有的位置都要维护它有没有在上下边界。类似于数位 dp 的转移…

@[DaiRuiChen007](luogu://user/539618) 无敌了！ --- 唐氏区间 dp 拖了一年。 首先按照区间 dp 的基本思路：设 $dp_{l,r}$ 代表 $[l,r]$ 区间的答案。考虑到我们要**通过删除前面的数给删除后面的数机会**，不妨设 $dp_{l,r}$ 代表删除完 $[l,…

放在 ABC 的 G 的位置上的网络流题目里面最水的。估计是 ABC 用网络流题目作为压轴题的时代的落幕吧…… 这题的 kenkoooo 分也比其他几题低了好几个档次。 --- 首先对网格黑白染色，然后源向每一个黑格连流量为 $1$、费用为 $0$ 的边，白格向汇连相同流量、费用的边。 流量为 $1$ 代表每一个格子最…

纯粹的手玩题，不知道为什么能有水色的难度。 本人首先手玩的是 $2$ 个 $1$ 和 $1$ 个 $0$ 的情况。 比如说：$(1,1,0)$ 可以把区间 $[1,1]$ 和区间 $[2,3]$ 互换得到 $(1,0,1)$，再把区间 $[1,1]$ 和区间 $[2,3]$ 互换得到 $(0,1,1)$，就有了所有的情…

很厉害的题，硬控我一天，让我又补完一场 ABC。 前置知识：[P6192 【模板】最小斯坦纳树](https://www.luogu.com.cn/problem/P6192) 因为是要加入两个点，所以考虑把第一个点放入集合，作为第 $k+1$ 个集合中的点。 接下来就转化成了 [ABC364G](https://ww…

成战犯了，我很晚才把这个题做出来。 前置知识：[P6192 【模板】最小斯坦纳树](https://www.luogu.com.cn/problem/P6192) 没有在板子的基础上有多少加强，但是**必须使用优化最短路转移后的最小斯坦纳树算法。**（如果你写的是 $O(nm\log n+3^knk+3^kn\log…

我居然独立做出了这题？这题真的不是紫的难度啊。 暑假集训第一场考试 T1，洛谷上过了但校测 TLE 了。 一种不用 ddp 的做法，感觉比 ddp 强。 --- 朴素线段树做法。 考虑在线段树上每一个节点开 $16$ 个答案统计。形如 $ans_{l,r}$，代表左边有 $l$ 个被选的位置，右边的 $r$ 个被选的位…

~~偶然看到这题还能提交题解来水一发~~ 之前 ABC 的 G 题经常出这个啊，但我不会就白搭了吗。 令 $dp_{i,|S|}$ 代表一个包含子集为 $|S|$ 且包含 $i$ 点的最小斯坦纳树。有两种转移，其一是将 $dp_{i,|S|}$ 转移到 $dp_{j,|S|}$，代价为 $(i,j)$ 之间的最短路，另…

本文同步于我的[ABC251~300 板刷记录](https://www.luogu.com.cn/article/p46znyv5)。 考虑**没有前向边**的搜索树。 全部非树边均为祖先关系，即为返祖边，无横叉边，使用任意一棵 dfs 树即可。 均非祖先关系，即为横叉边，无返祖边，即可使用图的 bfs 树。 注意两…

~~置顶公告：因为现在 kenkoooo 出了一些问题待修复，板刷暂停。~~ ~~置顶公告：因为我很忙，板刷暂停。~~ # ABC251~300 板刷记录 不是所有的题我都做出来或者补出来了，因为我就是个废物，我就是个废物，我就是个废物啊！ ## [ABC251 2022/05/14 (1)](https://atco…

一道很水的 ABC 压轴题，正好让我从刚刚离开初中的感觉回到了才来初中的感觉。 感觉区分了做过 [Ivan and Burgers](https://www.luogu.com.cn/problem/CF1100F) 和没做过的人。 ## 前缀线性基 就是针对于求静态区间 $[l,r]$ 线性基的一种利器。 前缀线性基…