RyanLi 的博客 - Ryan
type: channel
link: https://blog.ryanli.top/index.php/author/1/
description: Ryan
items: CF2244D 题解
items: CF2244C 题解
items: ICPC / CCPC 2026 游记
items: 洛谷 P16796 题解
items: 洛谷 P16799 题解
items: CF2225C 题解
items: CF2218E 题解
items: 随记 #8
items: CF2209C 题解
items: CF2194C 题解

CF2244D 题解
type: item
date: 2026-07-17T17:53:00+08:00
description: 传送门：洛谷 CF2244D Yaroslav and Productivity | Codeforces D. Yaroslav and Productivity 更佳的阅读体验：CF2244D 题解简要题意：给你两个序列 $a$ 和 $b$，每次操作可以选定一个位置 $i$，翻转 $[1, b_i]$ 上的 $a_i$ 的符号，你需要进行任意次操作来最大化 $\sum a_i$。$m \le n \le 2 \times 10^5$。这里有一个很重要的观察，就是如果我们对 $b$ 排序，把 $b_i$ 当作 $a$ 上的“分隔点”位置，那么就一定存在一种操作的方案，使得相邻两个 $b_i$ 之间对应的 $a_i$ 的符号可以独立决定。也就是说，我们对 $b$ 排序后，$a$ 就可以被分为形如$$ [1, b_1], [b_1 + 1, b_2], \cdots, [b_{m - 1} + 1, b_m], [b_m + 1, n] $$的 $m + 1$ 个区间。我们可以独立决定每个区间内是保持原来的符号，还是整体取反。此时我们发现，答案其实就是区间和的绝对值再求和。单组数据时间复杂度 $O(n + m \log m)$。#include <iostream> #include <algorithm> using namespace std; using ll = long long; const int N = 2e5 + 10; int t, n, m; ll a[N], b[N], ans; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); for (cin >> t; t; --t) { ans = 0; cin >> n >> m; for (int i = 1; i <= n; ++i) { cin >> a[i]; a[i] += a[i - 1]; } for (int i = 1; i <= m; ++i) cin >> b[i]; sort(b + 1, b + m + 1); for (int i = 1; i <= m; ++i) ans += abs(a[b[i]] - a[b[i - 1]]); cout << ans + a[n] - a[b[m]] << '\n'; } return 0; }

CF2244C 题解
type: item
date: 2026-07-17T17:23:00+08:00
description: 传送门：洛谷 CF2244C Stepan and Permutation | Codeforces C. Stepan and Permutation 更佳的阅读体验：CF2244C 题解简要题意：给你一个排列，你可以任意次交换下标差恰好为 $x$ 或 $y$ 的元素，判断是否能使得排列变为升序。$n \le 2 \times 10^5$。我们可以将每个下标看作一个节点，如果两个下标之差为 $x$ 或 $y$，就在它们之间连边。此时，一次操作就是交换图中一条边两端的元素。由此我们发现，在一个连通块内，可以沿路径不断交换，使得连通块内的元素任意排序。但任意排序仅限这个连通块内部，所以元素无法移动到其他连通块里。那我们需要判断的就变成了，对于每个元素，它在原序列中的位置和排序后应该到达的位置是否在同一连通块内。即，是否对于原序列中的任意元素都有 $p_i$ 与 $i$ 在同一连通块内。这一过程可以借助并查集来实现。单组数据时间复杂度 $O(n \alpha(n))$。#include <iostream> #include <algorithm> #include <numeric> using namespace std; const int N = 2e5 + 10; int t, n, x, y, p[N], fa[N], rk[N]; bool flag; int find(int x) { if (x == fa[x]) return x; return fa[x] = find(fa[x]); } void merge(int x, int y) { x = find(x), y = find(y); if (x == y) return; if (rk[x] < rk[y]) fa[x] = fa[y]; else if (rk[x] == rk[y]) fa[x] = fa[y], ++rk[y]; else fa[y] = fa[x]; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); for (cin >> t; t; --t) { flag = false; cin >> n >> x >> y; for (int i = 1; i <= n; ++i) cin >> p[i]; fill(rk + 1, rk + n + 1, 1); iota(fa + 1, fa + n + 1, 1); for (int i = 1; i <= x; ++i) for (int j = i; j <= n; j += x) merge(i, j); for (int i = 1; i <= y; ++i) for (int j = i; j <= n; j += y) merge(i, j); for (int i = 1; i <= n; ++i) if (find(i) != find(p[i])) { flag = true; break; } cout << (flag ? "NO\n" : "YES\n"); } return 0; }

ICPC / CCPC 2026 游记
type: item
date: 2026-06-20T13:00:00+08:00
description: 本文同步发表在洛谷专栏，你也可以点击这里以获得更佳的阅读体验。前段时间一直在忙转专业的事情，最近刚刚有空了点，是时候开启新赛季的游记了！4.30 - ICPC 西安邀请赛西安邀请赛正好放在了五一假期前两天，所以正好提前去玩一天！其实是因为明天机票太贵了。早上六点钟就要起来赶早班机，困死我了。不过确实是我和新队友一起打的第一场比赛，其实还是有点期待的。在机场走的时候发现停着一架没见过的彩绘机，发现是天骄航空的新涂装，记录一下。内蒙本土的航空公司，唉有点难评。飞机上睡了会，下飞机买了杯咖啡就去酒店了。我一直在喷，西工大怎么直接把校区建在山里了，从机场打车过去都要七十公里。我的钱包在天上失望地看着我。下午收到了三重喜报！首先是，下午去找了 XDU 的朋友，好久没见了真的很开心。其次是，大概下午三点多的时候，虽然邀请函上写着的是英文题面，但是突然在西安群里看到了有中文题面！让我们感谢 cfz 出题组。然后是，大概下午五点多，通过我的神秘人脉得知到了 NMCPC 目前初步确定的时间！之前一直在担心会不会撞贵州，或是其他比赛。现在正好在贵州缴费截止的前一天得到了，大道消息（？）。NMCPC 不会撞任何比赛了！接下来可以放心缴费了。西工大这个地方，从市里过去还没有快速路或者高速，往返一趟市区二十多公里，以及五十个红绿灯，走一下停一下真挺心烦的吧。晚上回酒店打 CF，大概十二点出头的时候，一转头发现地上有一只爬得飞快的巨大的虫子。大概起码三厘米长，不过我没带眼镜看不清它长啥样，还好没带眼镜。然后把它踩死了并且捏起来扔到垃圾桶，太痛苦了。事后思考了下可能是蟑螂什么的，太恐怖了。煮波超级怕虫子。5.1今天是报到日，当然我不清楚为什么热身赛和正赛都放在了明天，也就是说今天只有一个签到和领物资。所以我就一觉睡到中午十二点了。中午吃了饭就和队友去报到了，我还是要骂为什么要在这么一个鸟不拉屎的山里办比赛。确实是五一，学校里没什么人。我和队友走了大概十多分钟，一路上只能看到同样来报到的其他队伍。这场的物资还挺好看的，包括袋子和衣服和胸牌的设计我都很喜欢。当然，我也确实第一次见到这种，邀请赛级别的比赛，胸牌上只写着「队员」「教练」字样的。去年的辽宁省赛好歹还有个学校名字的。接下来去拍照。一个小趣闻是，拍完照我们报学校名字的时候，摄像老师突然抬头，感觉语言里带着点惊喜地说，他也是我校毕业的。太巧了。签到流程就结束了，然后我就找朋友去玩了，以及买一点明天赛时吃的东西。今天西安下雨了，到我晚上回酒店的时候，出了城区就开始下得很大。是不是叫什么，倾盆大瓢。5.2今天是比赛日！热身赛八点开始，虽然不急，但是还是想早点去，标记一下领地。另外早上七八点，酒店附近根本点不到咖啡，看了下校内的瑞幸早上七点开门，那还是早点去学校里买吧。到了已经七点五十多分了，索性还是先去场地里看看吧。西安是机房竞赛，每个机房都挺小的，大概就只能容得下十几个队，或者更少，反正总体的感觉是略显压抑的，可能和窗外没有太阳也有点关系。机房的 DOMjudge 也很老，具体什么版本我忘了，但反正是有一种上世纪的美感（x）。先去热身赛签了一道题，发现居然有三份中文题面，这波给到夯。然后调了一些配置以及测了一下评测机速度，就下楼买咖啡了。我打开地图认真看了下，居然这么远，已经在整个校区最角落的地方了，还是骑个车去吧。西安的雨还在零星地落着。我骑着车，姑且算是悠闲地，在校内的小路上慢慢往前晃。风一阵一阵地吹过来，带着没散干净的凉意，偶尔还有几滴雨点砸在脸上。空气里混着雨后的潮气和泥土味，倒也让人清醒了不少。骑了一会儿，前面忽然像是进了施工区域。我停下来翻了几次地图，确认自己确实没走错，只好继续往前骑。假期里的校园本来就安静，路上几乎看不到什么人，偏偏远处又时不时传来泥头车的轰隆声。那种空旷和吵闹混在一起，反而显得更冷清了。风再一吹，整个人都不由得打了几个寒战。我回去的时候，热身赛刚好结束，中间有半个小时的开幕式，我懒得看，于是就在楼上转悠，突然发现楼道栏杆上挂的标语很有趣。接下来就是比赛时间了。这场的签到是 E，发现比去年西安站的签到简单多了，三四分钟写出来，然后就提交，然后喜提 TLE，何意味。我看了两三分钟确定程序逻辑不太可能出问题，然后把 umap 改成 map，过了。喜提 29 分钟罚时。我再也不用 umap 了！接下来就去开 D。口胡了一个贪心，交了一发发现 WA 了。然后过了一会按照队友给的思路，将信将疑地写了一份代码。其实没抱有多大希望的，但是居然过了？很惊喜，虽然我也不知道这是咋过的。赛后发现我最开始口胡的那个做法是对的，但是不知道什么地方挂了。接下来去开 J 了。看到 Convex（笑），想到了去年西安站的签到也是 Convex，非常相似啊！最开始想到一个非常接近正解的做法，然后觉得，同一个…

洛谷 P16796 题解
type: item
date: 2026-06-11T13:26:45+08:00
description: 传送门：P16796 [蓝桥杯 2026 国 B] 灯带修补 更佳的阅读体验：洛谷 P16796 题解简要题意：给你一个环，你需要求出环上最长的连续子段，使得该字段中相邻元素之差的绝对值 $> k$ 的位置数量 $\le m$。$n \le 2 \times 10^5$。看到环，我们应该就有一个直觉是需要把整个序列在数组末尾再复制一次，这样环上问题就被转化成线性的序列问题了。我们发现，最后的答案其实只和相邻元素之差的绝对值有关，而与 $a_i$ 本身的值无关。此时，如果我们将 $|a_i - a_{i + 1}| > k$ 视作 $1$，否则为 $0$，那我们就可以得到一个新的序列，即 $d_i = \left [|a_i - a_{i + 1}| > k \right ]$，其中 $[P]$ 为条件表达式，命题 $P$ 为真时值为 $1$，否则为 $0$。这时，我们对序列 $d$ 再做一次前缀和，我们就可以很简单地求出来每个区间有多少个位置符合条件了。那反过来想，其实只需要遍历一次序列 $d$，查找最后一个不超过 $d_i + m$ 的位置即可。时间复杂度 $O(n \log n)$。#include <iostream> #include <algorithm> #include <cmath> using namespace std; using ll = long long; const int N = 4e5 + 10; int n, m, ans; ll k, a[N], d[N]; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); cin >> n >> m >> k; for (int i = 1; i <= n; ++i) cin >> a[i]; copy(a + 1, a + n + 1, a + n + 1); for (int i = 1; i < (n << 1); ++i) d[i] = d[i - 1] + (abs(a[i] - a[i + 1]) > k); for (int i = 1; i <= n; ++i) ans = max(ans, min(n, int(upper_bound(d + 1, d + (n << 1) + 1, d[i] + m) - d - i))); cout << ans << '\n'; return 0; }

洛谷 P16799 题解
type: item
date: 2026-06-10T22:08:49+08:00
description: 传送门：P16799 [蓝桥杯 2026 国 B] 实验数据 更佳的阅读体验：洛谷 P16799 题解没错笔者去参赛了，虽然赛时做到这种题确实有点难绷，猜你想找 P1471 方差、P5142 区间方差。这篇题解主要写给初学线段树的同学，如果你有一定基础，想必你已经做过上面两题了。简要题意：给你一个序列，你需要支持单点修改和查询区间和、区间方差。$n \le 10^5$。如果你做过洛谷的线段树板子，那么此时你已经会了最基础的区间和查询。但题目还要求你求出区间方差，此时你已经推了一百页公式，发现无论如何也推不出来只用区间和求解的方案。怎么办呢？来推一下式子吧。$$ \begin{align} \text{Var} = & \sum_{i = l}^r \left (a_i - \overline{a} \right )^2 \\ = & \sum_{i = l}^r a_i^2 + \sum_{i = l}^r \overline{a}^2 - 2 \cdot \sum_{i = l}^r \left ( a_i \cdot \overline{a} \right ) \\ = & \sum_{i = l}^r a_i^2 + (r - l + 1) \cdot \overline{a}^2 - 2 \cdot (r - l + 1) \cdot \overline{a}^2 \\ = & \sum_{i = l}^r a_i^2 - (r - l + 1) \cdot \overline{a}^2 \\ = & \sum_{i = l}^r a_i^2 - (r - l + 1) \cdot \left ( \dfrac{\sum \limits_{i = l}^r a_i}{r - l + 1} \right )^2 \\ = & \sum_{i = 1}^r a_i^2 - \dfrac{\left ( \sum \limits_{i = l}^r a_i \right )^2}{r - l + 1} \end{align} $$好像推不下去了，但至少已经出现了一个我们熟悉的区间求和。但还有一个求平方和，是否有办法处理这个呢？答案是肯定的。我们考虑线段树本身的结构，似乎只要是可以支持 push up 和 push down 操作的数据，就都可以拿线段树来维护，那平方和当然也满足。因此，我们只需要让这一棵线段树多维护一个区间平方和即可。因为本题只需要支持单点修改，所以甚至不需要 lazy tag 和 push down。当然，你还需要注意模意义下的除法需要通过乘它的乘法逆元来实现。时间复杂度 $O(n \log n)$。#include <iostream> #define ls(p) t[p].lson #define rs(p) t[p].rson #define mid (l + r >> 1) using namespace std; using ll = long long; const int N = 3e5 + 10; const ll MOD = 998244353; int n, m, op, l, r, k; ll a[N], x; struct seg_tree { int rt[N << 1], tot; struct node { int lson, rson; ll sum, sqsum; } t[N << 1]; void pushup(int p) { t[p].sum = (t[ls(p)].sum + t[rs(p)].sum) % MOD; t[p].sqsum = (t[ls(p)].sqsum + t[rs(p)].sqsum) % MOD; } void build(int &p, int l, int r) { p = ++tot; if (l == r) return t[p].sum = a[l] % MOD, t[p].sqsum = a[l] * a[l] % MOD, void(); build(ls(p), l, mid); build(rs(p), mid + 1, r); pushup(p); } void update(int p, int l, int r, int k, ll x) { if (l > k || r < k) return; if (l == r) return t[p].sum = x % MOD, t[p].sqsum = x * x % MOD, void(); update(ls(p), l, mid, k, x); update(rs(p), mid + 1, r, k, x); pushup(p); } ll query_sum(i…

CF2225C 题解
type: item
date: 2026-04-22T21:54:00+08:00
description: 传送门：洛谷 CF2225C Red-Black Pairs | Codeforces C. Red-Black Pairs 更佳的阅读体验：CF2225C 题解简要题意：给你一个 $2 \times n$ 的网格，每个格子涂成红色或黑色，要求重新涂色最少数量的格子，使得所有格子能分成 $n$ 对，每对格子颜色相同且相邻，求这个最小重新涂色数。$\sum n \le 2 \times 10^5$。只有两行，所以所有可能的匹配方式就只有两种，也就是横着或者竖着的两格。匹配时如果这两格的颜色不相同，就产生 $1$ 的代价，否则匹配的代价为 $0$。此时问题变成了，我们需要找到一种匹配方式，使得所有格子都被匹配且代价最小。考虑 DP。我们定义 $f_i$ 表示匹配完前 $i$ 列的最小总代价。转移时就只需要考虑，如果竖着匹配一次，那就匹配当前的这一列。或者横着匹配两次，匹配当前一列和前面的一列。我们可以提前预处理出竖着匹配和横着匹配的代价 $cost_1$ 和 $cost_2$：$$ \begin{cases} \text{cost}_{1, i} = [a_{1, i} \ne a_{2, i}] \\ \text{cost}_{2, i} = [a_{1, i} \ne a_{1, i + 1}] + [a_{2, i} \ne a_{2, i + 1}] \end{cases} $$其中 $[P]$ 表示命题 $P$ 为真时值为 $1$，否则为 $0$。于是我们就得到了转移方程。$$ f_i = \min \{ f_{i - 1} + \text{cost}_{1, i}, f_{i - 2} + \text{cost}_{2, i - 1} \} $$时间复杂度 $O(n)$。#include <iostream> #include <algorithm> using namespace std; const int N = 2e5 + 10, M = 5; int t, n, f[N], cost[M][N]; char c[M][N]; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); for (cin >> t; t; --t) { fill(f + 1, f + n + 1, 0); fill(cost[1] + 1, cost[1] + n + 1, 0); fill(cost[2] + 1, cost[2] + n + 1, 0); cin >> n >> c[1] + 1 >> c[2] + 1; for (int i = 1; i <= n; ++i) { cost[1][i] = c[1][i] != c[2][i]; cost[2][i] = (c[1][i] != c[1][i + 1]) + (c[2][i] != c[2][i + 1]); } f[1] = cost[1][1]; for (int i = 2; i <= n; ++i) f[i] = min(f[i - 1] + cost[1][i], f[i - 2] + cost[2][i - 1]); cout << f[n] << '\n'; } return 0; }

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; }