House_of_Fan

P9923 [POI 2023/2024 R1] Przyciski 思路 首先看到 01 矩阵，还是关于行和列的计算，考虑从每个点的行向这个点的列连边。 容易发现这是一个二分图，但是其实没什么用（行与行，列与列之间显然无法连边）。 最后我们要使每个点的度数相同。 首先考虑偶数情况，是容易的，选出一个环，环上的点均度数为 $2$，不在环上的点度数均为 $0$ 即可构造。 这一部分直接 dfs 即可。 然后是奇数情况。 首先若有环，则偶数情况成立，不会考虑，故此时图上无环，是一个森林。 我们发现叶子的度数均为 $1$，无法增加到更大的奇数，所以考虑从叶子到根枚举，若其父亲度数为偶数则断掉父亲到父亲的父亲的连边（不能断掉其与儿子的连边，否则儿子的度数会变为偶数），若父亲为根节点且度数为偶数，则不成立。 代码 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747...

CF2204B Right Maximum 思路 注意到每次都会取出最右边的 $\max$ 值，所以我们将原数组中的每个位置改为以值为第一关键字，位置为第二关键字，从大到小排序。 每次遍历到的值若在现在删除的最左边的值右边，直接跳过，否则它成为最左边且被删除的值，将删除次数加一。 代码 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include<bits/stdc++.h>#define fir first#define sec second #define int long long#define pii pair<int,int>#define fep(i,s,e) for(int i=s;i<e;i++)#define pef(i,s,e) for(int i=s;i>e;i--)#define rep(i,s,e) for(int i=s;i<=e;i++)#define per(i,s,e) f...

CF2204D Alternating Path 思路 题目要求对无向图进行二分图染色，仅合法二分图连通分量计入贡献（取该分量两颜色集合的较大点数），非二分图分量无贡献。核心思路分为三步： 通过 BFS 遍历图中所有未访问节点，拆分出每个连通分量。 对每个连通分量进行染色，若染色过程中发现相邻节点颜色相同，则判定为非二分图，返回 $-1$；若染色合法，统计两个颜色集合的点数，返回较大值。 遍历所有连通分量，将合法二分图分量的最大颜色集合点数累加，得到最终答案。 简单模拟题，但是赛时太卡，一发提交至少等 20min，然后我数组初始化出问题调了三发，幸好 CF 官方延长了时限 15min，不然就没调出来。 世界名画： 极限，尽力了。 代码 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909...

CF2204C Spring 思路 推式子题，显然利用容斥。 以下按照名字首字母简称题中的三个人。 我们发现每天的取水人共有 $7$ 种情况。 A B C AB AC BC ABC 而这就是一个很简单的容斥。 我们画一个图： 对于某人独有的部分，此人会获得 $6$ 单位的水； 对于两人共有的部分，两人都会获得 $3$ 单位的水； 对于三人共有的部分，三人都会获得 $2$ 单位的水。 所以对于 A，她能获得的水量是 $A\times6+AB\times3+AC\times3+ABC\times2$。 但是这样还是太难算了，考虑简化。 我们将某种取水的情况并入它的所有子集，此时，A 代表一整个大圆，AB 代表原来的 AB+ABC，以此类推。 此时，对于 A，她能获得的水量是 $A-AB\times3-AC\times3+ABC\times 2$。 因为 A 导致多算了六次 AB 和 AC 以及 ABC，而 AB 和 AC 只需要三次，所以减掉三次，然后又导致少算了 $3\times2=6$ 次 ABC，而 ABC 需要两次，所以还要算 $-6+6+2=2$ 次。 B 和 C 的...

P15400 [NOISG 2026 Prelim] Hungry Cats 依旧水题解。 思路 题面过于诡异，此后的描述中用单位代指猫，大小代指快乐值。 先将所有单位按照快乐值大小排序。 首先注意到每个单位只能吞一次，所以第二大的只能被最大的吞掉。 就算有和它一样大的，在吞掉更小的之后比它更大，此时也无法再次吞单位，故无法吞掉它。 所以以此类推，所有单位都只能被比它大的第一个单位吞掉。 故从小到大枚举，从第三小的开始枚举，如果有两个单位相差一（吞前一个后相等）或相等（吞前一个后更大），则输出 NO 并 return 0;，否则输出 YES。 对于第一小的，它不会吞任何其它单位，故只判断最小的两个是否相等。 代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include<bits/stdc++.h>#define fir first#define sec second #define int long long#define pii p...

P15406 [NOISG 2026 Prelim] 摩天大楼 思路 首先我们发现若 $k\le 2$，则一定有解。 我们现将所有高度的大楼数量按照高度为关键字排序。 考虑从上到下，从左到右填数字。 这时所有位置的上面和左边一定不存在比它高的大楼。 然后若 $k=4$，显然当且仅当所有大楼都一样高时成立。 这时便只剩下 $k=3$ 的情况需要讨论。 我们考虑从小到大填，从外往内覆盖整个矩形。 发现当且仅当用同样高度填充整行或整列才能合法地填入最小高度的大楼。 用完了一种高度的大楼就用大于它的最小高度的大楼。 若当前剩余的最小大楼数量不足填充任何一条整边，这种填充方法不合法。 考虑进行 DFS，传参还需要填充的行数和列数，现在用到了哪个高度以及用了多少。 但这样还无法通过，考虑进行记忆化，用一个 map 存下哪些行列数量已经遍历过了（因为从小到大填，所以填的顺序没有影响）。 所有的行数和列数都只会被考虑到一次，总时间复杂度为 $O(n^2\cdot \log n)$，$n$ 最大仅有 $1000$，足以通过。 代码 123456789101112131415161718192021...

CF2208B Cyclists 思路 首先考虑若要选的那个胜利条件最开始就在最后面，该怎么选。 显然是找前面 $k-1$ 个花费最大的卡牌，将它们保留，然后将其它的卡牌挪到最后面，最后胜利条件就会位于第 $k$ 个位置，直接挪动它。 此时就回到了跟原情况等价的一种局面，可以花费一定的代价稳定地获取一次胜利条件，用剩余的花费除以一定的代价得到答案。 那如果胜利条件最开始不在最后面呢？ 那就想办法将它挪动到最后面。 若开始时它在前 $k$ 个，直接挪动。 否则，留下在它前面且最大的 $k-1$ 个，挪动其它卡牌，再挪动胜利条件。 最后所有情况都到了它开始就在最后的局面，按照前面提到的方法计算次数即可。 代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include<bits/stdc++.h>#define fir first#define sec second #define ...

CF2208C Stamina and Tasks 思路 若选择完成一个任务，则后面的所有收入将会乘以 $\frac{100-p_i}{100}$。 而无论后面如何选择，都不会对前面有影响。 所以我们考虑从后往前枚举，并将第 $i$ 位以及它后面的最大收入设为 $s_i$。 假设当前枚举到了第 $i$ 位，若选择完成这个任务，则 $s_i$ 会变为 $c_i+s_{i+1}\times\frac{100-p_i}{100}$，若不完成，则是继承 $s_{i+1}$。 将这两个值比较后取更大的一个就可以了。 代码 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include<bits/stdc++.h>#define fir first#define sec second #define int long long#define double long double#define pii pair<int,int>#define fe...

CF2203B Beautiful Numbers 思路 首先满足 $F(x)=F(F(x))$ 的数所有数位之和一定 $<10$。 我们设 $dp_{i,j}$ 表示处理完前 $i$ 位数字，各位和为 $j$ 时的最少修改次数。 初始设为一个极大值表示不可达。 枚举最后的总数位和 $1$ 到 $9$。 遍历每一位数字 $i$。 遍历总数位和 $j$。 枚举当前位要修改成什么数 $k$。 如果当前要修改成的数字 $k$ 不等于原数字，则修改次数增加。 核心转移方程为 $dp_{i+1,j+k}=\min(dp_{i+1,j+k},dp_{i,j}+(k\neq d));$ 最后再看是否存在可达的状态即可，更新答案为这些最终数位和对应的最小值。 代码 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include<bits/stdc++.h>#define fir...

我也要打省选吗？ 我也要尝试做出 D1T1 吗？ 我也要参与赛后讨论吗？ 我也要 D2 再去坐牢吗？ 我也要学会用 NOI Linux 吗？ 我也要做两道交互题吗？ 我也要尝试读懂题面滚木比大小吗？ 总结：rand+0+eps+[0,40]+0+eps。 就这样吧，反正初三。 我居然能打省选。 我居然能连续思考尝试同一道题目 5h。 我居然能参与赛后讨论并且被难绷微信视频号拍到。 我居然能且有心情继续参加 D2。 我居然只用 2h 就过了 D2T1 的编译。 我居然阅读了两道交互题题面。 我居然读懂了滚木该如何比大小。 以及，我和 SC 的 $13$ 个正式队爷和一个 JMR，我们 $15$ 个真厉害。 贵州省队爷对此文章评价：好诡异啊。 以及无力吐槽，毕竟还是我太菜了，但是我往出题人家里丢了一颗震撼弹，怎么没有声纹？ 哎我说 CCF，我已急哭，那你没急吧。 AI 使用声明：本文第三部分使用了 @Song_stok_SZH 进行润色。