RyanLi 的博客 - Ryan
type: channel
link: https://blog.ryanli.top/index.php/author/1/
description: Ryan
items: CF2225C 题解
items: CF2218E 题解
items: 随记 #8
items: CF2209C 题解
items: CF2194C 题解
items: 随记 #7
items: 洛谷 P1330 题解
items: ICPC / CCPC 2025 游记
items: 随笔 #17
items: NM CSP 2025 迷惑行为大赏

CF2225C 题解
type: item
date: 2026-04-22T21:54:55+08:00

CF2218E 题解
type: item
date: 2026-04-16T17:39:00+08:00
description: 传送门：洛谷 CF2218E The 67th XOR Problem | Codeforces E. The 67th XOR Problem 更佳的阅读体验：CF2218E 题解简要题意：给你一个数组，每次操作可以选择其中一个元素，将数组内所有元素都与它进行按位异或运算，然后将该元素删除，求 $n−1$ 次操作后剩下的最后一个元素可能的最大值。$\sum n \le 3105$。诈骗题。来推个柿子吧！假如现在我们有一个 $n = 5$ 的数组 $\{ a_1, a_2, a_3, a_4, a_5 \}$，我们选中第一项进行一次操作，数组就变成了：$$ \{ a_2 \oplus a_1, a_3 \oplus a_1, a_4 \oplus a_1, a_5 \oplus a_1 \} $$那如果再对现在的第一次进行一次操作呢？现在数组就变成了：$$ \{ (a_3 \oplus a_1) \oplus (a_2 \oplus a_1), (a_4 \oplus a_1) \oplus (a_2 \oplus a_1), (a_5 \oplus a_1) \oplus (a_2 \oplus a_1) \} $$我们知道，异或运算有一个很重要的性质是 $x \oplus x = 0$，同时也满足结合律。因此，现在的每一项都异或了两次 $a_1$，其实 $a_1$ 就被消掉了，现在的数组就变成：$$ \{ a_3 \oplus a_2, a_4 \oplus a_2, a_5 \oplus a_2 \} $$我们发现第一次操作中选中的 $a_1$ 已经不存在了。如果我们一直选择序列中的第一项进行操作，最后剩下的一个元素就是 $a_5 \oplus a_4$，也就是，最后一个未被选中的数与最后一次被选中的数的异或值。因此，我们只需要确定这两个数，就可以得到最后剩下的一个数的值。因为 $n$ 非常小，我们可以直接枚举任意两个元素的异或值，求最大值即可。单组数据时间复杂度 $O(n^2)$。#include <iostream> using namespace std; const int N = 3110; int t, n, a[N], ans; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); for (cin >> t; t; --t) { ans = 0; cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; for (int i = 1; i <= n; ++i) for (int j = i + 1; j <= n; ++j) ans = max(ans, a[i] ^ a[j]); cout << ans << '\n'; } return 0; }

随记 #8
type: item
date: 2026-04-07T21:23:00+08:00
description: 我被囚禁在了一个固步自封的囚笼中。他们说，我是安全的。我沉浸在那里，沉沦在那里。我在那里挣扎着死去，在一个悄无声息的角落，偷偷地，默默地。尽管，我是安全的。$\texttt{Written on 2026.4.7.}$

CF2209C 题解
type: item
date: 2026-02-17T20:25:00+08:00
description: 传送门：洛谷 CF2209C Find the Zero | Codeforces C. Find the Zero更佳的阅读体验：CF2209C 题解简要题意：IO 交互题。有一个长度 $2n$ 的隐藏数组，其中包含 $1 \sim n$ 各一个，以及 $n$ 个 $0$。每次询问可以查询两个位置的元素是否相等，你需要在不超过 $n + 1$ 次询问中找出一个值为 $0$ 的位置。因为 $1 \sim n$ 的每个数都是出现且仅出现一次，所以如果某次询问得到了 $a_i = a_j$ 的结果，说明这两个都是 $0$，选一个输出即可。如果 $a_i \ne a_j$，说明它们最多只有一个数是 $0$。如果我们直接排除掉这两个数，继续去考虑接下来的数，我们发现还剩下至少 $n - 1$ 个 $0$。那么我们每次都对两个未询问过的位置进行询问，经过 $n - 1$ 次询问后，如果仍然没有得到 $a_i = a_j$ 的反馈，我们就剩下了最后两个数。如果这两个数也不相等呢？那就只剩下一次询问了，无法确定 $0$ 的位置。但如果将目光向前看呢？我们随便找一对之前被我们询问过的位置，加上最后剩下的两个数，我们发现这四个数里至少包含两个 $0$。现在我们剩下两次询问，此时问题就简单许多了。假设我们还没询问过的两个数是 $x, y$，从之前的询问中拿出来的两个数是 $a, b$。因为之前已经询问过 $a$ 和 $b$，所以此时就一定有 $a \ne b$。那如果我们抓住 $x$ 一个数，和 $a, b$ 分别比较，那就只有两种情况了。如果 $x = a$ 或 $x = b$，那么显然 $x$ 一定是 $0$，直接输出即可。否则，未参与比较的 $y$ 就一定是 $0$。#include <iostream> using namespace std; int t, n, stat; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); for (cin >> t; t; --t) { cin >> n; for (int i = 1; i < n; ++i) { cout << "? " << (i << 1) - 1 << ' ' << (i << 1) << '\n'; cout.flush(); cin >> stat; if (stat) { cout << "! " << (i << 1) << '\n'; cout.flush(); break; } } if (stat) continue; for (int i = 2; i <= 3; ++i) { cout << "? " << (n << 1) << ' ' << (n << 1) - i << '\n'; cout.flush(); cin >> stat; if (stat) { cout << "! " << (n << 1) << '\n'; cout.flush(); break; } } if (!stat) { cout << "! " << (n << 1) - 1 << '\n'; cout.flush(); } } return 0; }

CF2194C 题解
type: item
date: 2026-02-11T20:42:00+08:00
description: 传送门：洛谷 CF2194C Secret message | Codeforces C. Secret message更佳的阅读体验：CF2194C 题解简要题意：给你 $k$ 个长度为 $n$ 的字符串，你需要构造一个新字符串，使得每个字符都与至少一个给定字符串的相同位置的字符相同，并最小化该字符串的最小循环节长度。首先来考虑如何处理循环节的长度。既然构造出来的字符串是由几个字符串循环而来的，那也就是说，最小循环节一定是 $n$ 的约数。因此，我们可以先找出 $n$ 的所有约数，从小到大挨个枚举是否合法。如何判断一个最小循环节长度 $d$ 是否合法呢？我们需要构造一个长度为 $d$ 的模式串 $t$，使得整个答案字符串由 $t$ 重复 $\dfrac{n}{d}$ 次组成。也就是说，$t$ 中的每一个位置，所选的字符都必须同时存在于给定字符串中对应的位置上。也就是说，对于一个位置 $1 \le i \le d$，所选字符必须同时存在于给定字符串的 $i, i + d, i + 2d, \cdots, i + \left ( \dfrac{n}{d} - 1 \right ) d$ 的位置上。因为给定字符串只有小写字母的 $26$ 个字符，为了方便处理，我们对字符串进行状态压缩，$mask_i$ 存储位置 $i$ 可以使用的字符集。此时，$t_i$ 可用的字符集就一定是 $mask_i, mask_{i + d}, mask_{i + 2d}, \cdots, mask_{i + \left ( \frac{n}{d} - 1 \right ) d}$ 的交集。如果这个交集为空，意味着当前的这个 $d$ 不合法，我们直接尝试枚举下一个 $d$。如果交集全都不为空，那么就可以直接构造答案。我们使用 __builtin_ctz 函数来获取一个数从最低位开始 $0$ 的个数，得到可用的字符，构造字符串即可。单组数据时间复杂度 $O \left (nk + n \cdot d(n) \right )$，其中 $d(n)$ 表示 $n$ 的约数个数。#include <iostream> using namespace std; const int N = 5e4 + 10; int t, n, k, mask[N]; string s[N], ans; vector<int> v; bool flag; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); for (cin >> t; t; --t) { v.clear(); fill(mask + 1, mask + n + 1, 0); cin >> n >> k; for (int i = 1; i <= k; ++i) { cin >> s[i]; for (int j = 1; j <= n; ++j) mask[j] |= (1 << s[i][j - 1] - 'a'); } for (int i = 1; i <= n; ++i) if (!(n % i)) v.push_back(i); for (auto d : v) { flag = false; ans.clear(); for (int i = 1; i <= d; ++i) { int tmp = mask[i]; for (int j = i + d; j <= n; j += d) tmp &= mask[j]; ans.push_back(__builtin_ctz(tmp) + 'a'); if (!tmp) { flag = true; break; } } if (!flag) { for (int i = d; i <= n; i += d) cout << ans; cout << '\n'; break; } } } return 0; }

随记 #7
type: item
date: 2026-01-29T22:55:00+08:00
description: 我害怕变得冷漠。我害怕会让我身边的人，因为我哪怕一刹那的冷漠，而遭受更多的本可以因我而不必遭受的痛苦。我开始学着如何帮助更多的人。但也因此，我逐渐发现我能帮到的永远只是相比起来没那么痛苦的人。他们的痛苦太深重了，以至于我只能沉沦于无尽的共情与情绪闪回中，无法自拔。我什么都说不出来，只好生硬地重复着那些聊胜于无的安慰。我想救救他们。我想，救救过去的自己。对不起。$\texttt{Written on 2026.1.29.}$

洛谷 P1330 题解
type: item
date: 2025-12-31T12:52:00+08:00
description: 传送门：P1330 封锁阳光大学 更佳的阅读体验：洛谷 P1330 题解阅读本文前，请确保你已经对二分图有所了解。简要题意：给你一张无向图，求最少选取的节点数量，使得节点之间两两不相邻，且每条边都连接着一个选中节点。观察给出的条件，发现每个点只有“选”或“不选”两种对立的状态，并且相邻节点的状态必须是不同的。由此我们想到，本题事实上是要求我们判断给定图是否为二分图，因此可以直接染色。如果染色过程中发现了冲突，说明给定图不是二分图，不论如何也无法得到任何一种合法的方案，此时直接输出 $\texttt{Impossible}$ 并退出程序即可。染色结束后，我们取两种颜色中较少的节点数作为答案即可。你兴高采烈地写出了一份朴素的二分图染色，然后得到了 50 分的好成绩。此时你发现，题目给出的限制中，只保证了给定图是一张无向图，而非无向连通图。这样的话，我们就应当对每个连通块进行讨论了。对于每个连通块，我们仍然取两种颜色中较少的节点数，答案即为每个连通块的答案之和。时间复杂度 $O(n + m)$。#include <iostream> #include <algorithm> using namespace std; const int N = 1e4 + 10; int n, m, u, v, col[N], cnt[2], ans; basic_string<int> g[N]; void dfs(int u, int c) { col[u] = c, ++cnt[c]; for (auto v : g[u]) { if (col[v] != -1) { if (col[v] == col[u]) { cout << "Impossible\n"; exit(0); } continue; } dfs(v, c ^ 1); } } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); cin >> n >> m; for (int i = 1; i <= m; ++i) { cin >> u >> v; g[u] += v, g[v] += u; } fill(col + 1, col + n + 1, -1); for (int i = 1; i <= n; ++i) if (col[i] == -1) { cnt[0] = cnt[1] = 0; dfs(i, 0); ans += min(cnt[0], cnt[1]); } cout << ans << '\n'; return 0; }

ICPC / CCPC 2025 游记
type: item
date: 2025-12-14T16:07:00+08:00
description: 本文同步发表在洛谷专栏，你也可以点击这里以获得更佳的阅读体验。8.11终于联系上学校分管算法竞赛的老师了。但是他说学校的选手水平太弱，已经五六年没有搞过 ICPC / CCPC 了，只是每年打一场 NMCPC。以及表示学院不会报销。最开始刚加上的时候，老师给我发的是大长条语音，说话挺慢的，而且说话带比较重的本地口音。加上和我说的这些内容，一度让我感觉他不支持我打比赛，也完全不想管这事。甚至可能是因为这事，我一个多月没发作过的焦虑又犯了。那会正好在外面，没带抗焦虑的药物，就只能自己一个人硬扛过去了。手抖到我连手机都拿不稳，想求助也好像没有人可以求助。还是硬着头皮继续聊下去了。以及提出了自费比赛，这会他才愿意帮我报名。尝试联系了一下往届的选手，发现甚至只有两位不是开学大四。这就可以引出下一天的故事了。8.12凑不齐三个人。全剧终。哎好吧上面这个结尾是我故意这么写的。是不是叫什么，奥利奥式结尾。找不到队友确实是真，学校不给报销也确实是真，但是我真的觉得这样写很好笑啊。提出自费比赛以后，感觉老师的态度改变了点。不知道是因为我已经习惯 / 接受了还是真的有变化。至于比赛，能报的我全报了。其实也没抱着拿奖的希望去，我清楚我现在的水平离拿牌子还挺远的。但感觉还是，不打不行。哪怕是自费体验一次，我也要打。大出血了。可能还要准备一千多块钱的往返机票，以及一天的酒店。还有剩下三场网络赛的报名费。其实我也不知道自己为什么对算法竞赛有这么深的执念。曾经在 NOI 之前就是这样。哪怕明知道自己的水平已经完全没可能拿牌子，但还是坚持训练到了 NOI。甚至已经有老师建议过我，大一上学期应该把重心放在学校的课程上。我也确实清楚对于这个学期，学校的课程的成绩才是对我至关重要的。我好像，没办法说服自己，甘于平庸。哪怕只能开出一个签到题，我也想留下我的足迹。好吧，对于这么一位本来就平庸的弱者。谈这些想法和行为，是不是只会显得我很可笑？我不得而知。扯远了。其实是找到 1.5 位队友的，尽管他们都水平有限就是了。至于为什么说是 1.5 位，是因为九月一共 4 场比赛，有一位只参加后面两场。晚上 vp 了一下 JSCPC / GDCPC 2025。出于练习英语读题能力的考量，全程没看中文题面，只是偶尔查了几个不认识的词。好吧读题速度真的远低于中文题面。一个小时开出来了两道签到题，然后接下来的两个小时就没有任何进展了。这会已经凌晨一点了，不想打了。不过我罚时挺低的，看了一下榜，哪怕后面两个小时也开不出来新的题，也能铜尾了。不过如果按这个水平，哪怕是邀请赛也应该比较难拿牌子了吧。决定明天再 vp 一场邀请赛看看感觉怎么样。晚安。8.19今天下午和队友 vp 了东北邀请赛，也是我第一次完整地 vp 五个小时。说是和队友 vp，其实所有题也都是我自己开的。至于组队，有点用，但不多。1.8 小时后就没有任何进展了，也就是我自己开完了几道签到题以后。接下来的三个小时都在死磕 A，其实中间有和他有一些交流，但大部分内容都只是单纯地让我血压暴涨，包括一些错误结论和非常基础的问题，比如 long long 能不能存得下 1e15。其实我知道水平较低不是他的错，我也是从那个时候过来的，所以我始终在尝试压制一些负面的情绪。只是继续一个人闷头想题去了。今天这次 vp 以后也大概算是吃了定心丸吧，悬着的心终于死了。不过赛后看题解，发现离正解只差一点点了。但是三个小时一直没开出来，直接从上位银牌区掉到上位铁牌区。这么看来，似乎也不该向另外一位队友抱有太大希望了。不管了，先加训吧。8.20看到教练群里的消息，突然意识到网络赛是需要先缴费的。赶紧联系教练先把参赛费用缴了。余额 -= 200。以及南昌邀请赛群里的一件趣事。哪有大一省队爷。8.24突然想起来去查了一下，发现低价机票已经卖得差不多了。赶紧联系队友买票订酒店。队友预算不太够，对于酒店的态度是能住就行，于是我被迫选了一家快捷酒店。打完南昌第二天还要赶早班机回内蒙，因为下午还要打网络赛。本来有一班国航的飞机，但是好像取消了，现在只剩下一班南航的飞机了。轻薄座椅 + 早班机 + 不能进休息室，我都不敢想那天早上我的怨气得有多重。8.25CCPC 网络赛可以报名了，虽然怎么总感觉报名费在骂人。余额 -= 250。晚上发生了个挺烦的事。班级群里有个学长，说是请假需要先和他说。然后我就加他了，并且给他发了比赛的日程，我承认九月份的比赛确实有点多。问他说能不能请假去比赛，他说应该不能。军训也是修学分，时间不够我就得重修。14 天每天都去才算时间修够了。那我崩溃了啊，不是说可以临时请假吗，怎么又来这一出。之前看校历上也没写周末军训（军训那段时间的周一到周五是灰色的，周末是和其它时候一样的白色），为什么突然又变成周末也要军训了。如果我周末不军训的话，我打比赛最…

随笔 #17
type: item
date: 2025-12-12T13:57:21+08:00
description: 虚无。似乎成为了过去式，他看到了光。至少，这次已经足以让他坚信。他早已充满热情，哪怕是仍然微弱的光芒，也足以让他徜徉在喜悦中。足够明亮，也充满希望——足以让他忘却一切，那些，所谓的，阻力。他知道，顺着光，他会找到那个足够坚实，也足够可靠的港湾。对吗。他总是这样问自己。他总是可以这样骗过自己。尽管，始终沉沦在混沌的深海中。若隐若现。隐。匿。$\texttt{Written on 2025.12.11.}$

NM CSP 2025 迷惑行为大赏
type: item
date: 2025-11-14T21:05:00+08:00
description: 本文同步发表在洛谷专栏，你也可以点击这里以获得更佳的阅读体验。下面是往期的迷惑行为大赏：NM 2023 NOI 春寄测试 迷惑行为大赏NMOI 2023 迷惑行为大赏NM CSP 2023 迷惑行为大赏喜报，今年已经是内蒙古（NM）连续第三年举办 CSP-J/S 第二轮认证了！本次认证中，共有 $543$ 位选手参加了 CSP-J，有 $431$ 位选手参加了 CSP-S。今年的参赛人数变化十分耐人寻味，CSP-S 的参赛人数一如既往地疯狂增长，涨幅达到了 $59 \%$，但CSP-J 的参赛人数竟然有所减少，较去年降低了 $18 \%$，笔者推测这种现象或许与今年禁止低龄选手参赛的政策有关。今年也是 CCF 第一次禁止低龄选手参赛，在这样的政策下，内蒙古的选手们在本次认证中的抱铃比例降低到了惊人的 $43 \%$，也就是说，有超过 $57 \%$ 的选手取得了不低于 $1$ 分的好成绩！这样的飞速进步无时无刻不在昭示着世人：内蒙古的 OI 事业正在蒸蒸日上！这无疑证明了在世界经济下行的大背景下，我国民间仍然存在大量的慈善家，愿意为伟大的慈善事业贡献一份属于自己的力量。很遗憾的是，我们已经无法在今年的赛场上见到他们了，让我们期待他们长大后继续作出的伟大贡献吧！笔者在撰写本文时，尚未得到 CCF 作出的有关选手准考证号与姓名、身份证号、手机号、洛谷账号等传统个人信息的相关性论证的调研报告。因此，我们将在下文中直接使用选手的准考证号，作为识别他们的唯一标识。另一个原因是笔者目前暂时未掌握盒武器的相关核心技术。但笔者相信，随着科学技术的研究进一步深入，我们对相关技术的掌握会变得越来越深刻！此外，在 AI 技术正在迅猛发展的当下，内蒙古的选手们也选择了紧跟时代的脚步，尝试以极具创新意义的方式拓宽“人机边界”的可能性，在算法竞赛的舞台上展开了一场极具前瞻性的实验性探索，新颖的研究结果实属令人叹为观止！我们将在下文中进一步讲述。来自内蒙古的 $974$ 位选手中，在三个半（或四个（或七个半））小时的时间内，在 $3446$ 份扩展名为 .cpp（包括 .cpp.cpp）的文件（或文件夹）下，写下了：$6147$ 个 freopen（包括 $119$ 个 //freopen 或 // freopen）。$4737$ 个 return。$3743$ 个 include（包括 $4$ 个 includes）。$3734$ 个 stdin（和 $3$ 个 sdtin）。$3689$ 个 stdout（和 $1$ 个 stfout）（虽然笔者并不清楚为什么与 stdin 的数量不相同）。$3333$ 个 main（和 $6$ 个 mian）。$2973$ 个 bits/stdc++.h。$1240$ 个 fclose（虽然笔者并不理解为什么有这么多人写这个）。$346$ 个 iostream。$136$ 个 cstdio。$168$ 个 define。除此之外，一个令人哀叹的事实是，在本次认证的代码中，笔者还发现了 $7$ 个 fuck、$4$ 个 cnm 和 $3$ 个 tmd，这是否成为暴戾语言势力重新入侵 OI 的表现，我们不得而知。但不得不承认的是，CCF 曾发表的《关于个别选手在NOIP 2021中使用暴戾语言的处罚公告》的含金量仍在上升。但冰冷的数据总是无趣的，或许只有认真鉴赏过各位选手的代码后，我们才能领略其中的精髓。NM-J00012 同学在他的每份代码末尾都编写了一段注释，似乎在传达着美好的期许。让我们恭喜这位同学在民间数据的测试中取得了 $163$ 分的好成绩！NM-J00014 同学在 polygon 文件夹下创建了一份名为 palygon.cpp 的文件，并尝试读取和写入 palygon.in 和 palygon.out 文件。同时，我们有理由怀疑这位同学赛时所使用的键盘的拥有着 $\texttt{F}$ 在 $\texttt{D}$ 左侧的奇妙布局。NM-J00021 同学在选手文件夹下创建了名为 number.cpp 的文件夹，并在 Untitled1 文件中写下了一份疑似受到宇宙射线影响的文字。同理，家长也会用付费对宇宙射线表示支持。NM-J00023 同学试图使用语言的力量感化评测姬。为了防止无法清晰地辨识代码的语言，NM-J00028 同学贴心地向评测姬反复重申了这一要点。哪怕是在我国最北方的内蒙古，这份温暖也足以让内蒙古的冬天变得不再寒冷！为了可以顺畅地使用 sort 函数，NM-J00044 同学在 polydon.cpp 中引入了 sort 头文件，并使用 frepone 函数完成了文件读写操作！NM-J00052 在注释中写下了一串疑似祈愿的语句。但我们仍然要重申，盲目迷信是不可取的。NM-J00087 同…