CF-1078-C. Secret message · znzryb
## 题目大意
## 题目总结：秘密信息 (Secret message)
给定 $k$ 条长度均为 $n$ 的字符串（纸条）。你需要构造一个长度为 $n$ 的目标字符串 $S$，满足以下要求：
- **字符来源限制**：对于 $S$ 中的每一个位置 $i$（$0 \le i < n$），该位置的字符必须是 $k$ 条纸条中第 $i$ 个位置出现的某一个字符。
- **最小化信息度**：字符串 $S$ 的“信息度” $d$ 必须尽可能小。
- **信息度 **$d$** 的定义**：最小的正整数 $d$，使得 $S$ 可以由一个长度为 $d$ 的字符串 $t$ 连续重复多次构成（即 $S = t + t + \dots + t$）。这意味着 $d$ 必须是 $n$ 的约数。
---
### 样例解释
**样例 1**
输入：$n=3, k=2$，纸条为 `abc` 和 `baa`
- 位置 0 可选字符：{a, b}
- 位置 1 可选字符：{b, a}
- 位置 2 可选字符：{c, a}
- 目标：尝试最小信息度 $d=1$（即 $S$ 是由同一个字符重复 3 次）。
- 检查：若 $S = \text{"aaa"}$，第 0 位 'a'（在第一条纸条）、第 1 位 'a'（在第二条纸条）、第 2 位 'a'（在第二条纸条）均存在。因此 $d=1$ 可行。
- 输出：`aaa`
**样例 2**
输入：$n=9, k=2$，纸条为 `iiinnnfff` 和 `nnfiffinn`
- 尝试 $d=1$：无法找到一个字符在所有 9 个位置都出现。
- 尝试 $d=3$：寻找长度为 3 的字符串 $t$，使得 $S = t + t + t$ 满足条件。
- 检查：若 $t = \text{"inf"}$，则 $S = \text{"infinfinf"}$。
- 第 0, 3, 6 位：'i' 分别在纸条 1, 2, 2 中出现。
- 第 1, 4, 7 位：'n' 分别在纸条 1, 1, 1 中出现。
- 第 2, 5, 8 位：'f' 分别在纸条 2, 1, 2 中出现。
- 输出：`infinfinf`
**样例 3**
输入：$n=4, k=2$，纸条为 `acbd` 和 `bdac`
- 尝试 $d=1$：不满足。
- 尝试 $d=2$：寻找长度为 2 的字符串 $t$，使得 $S = t + t$ 满足条件。
- 检查：若 $t = \text{"ac"}$，则 $S = \text{"acac"}$。
- 位置 0 ('a')：在第一条。
- 位置 1 ('c')：在第二条。
- 位置 2 ('a')：在第二条。
- 位置 3 ('c')：在第一条。
- 输出：`acac`
## 思路讲解
其实说白了这道题目就是想让你找一个字符串，一个字符串集的这个最小循环子串。啊，也就是找其最小循环节，但是其最小循环节呢是严格的这个**最小循环节长度（即题目中的信息度）**，就是它不能够呃就是它不能够比如说呃roate，不能够呃循环移动的那种循环节，它是比较严格的那种循环节。
```cpp
auto check=[&](ll len,bool gen_ans=false) -> bool {
// 先生成一个长度为 len 的，每一位他能够所选的这个字符的集合(可以使用 Vector 套 bitset 表示.)。
vector<vector<int>> bi=gen_bi(0,len);
// 然后这里是不断的生成，就是继续生成这样子的集合，进行与运算的操作。
for (ll i=len;i<N;i+=len) {
bi=fac_and(bi,gen_bi(i,len));
}
for (int i=0;i<len;++i) {
bool ok=false;
for (int j=0;j<26;++j) {
if (bi[i][j]) {
if (gen_ans) {
ans.push_back('a'+j);
}
ok=true;
break;
}
}
if (!ok) {
return false;
}
}
if (gen_ans) {
string back_up=ans;
for (int i=2;i<=N/len;++i) {
ans+=back_up;
}
}
return true;
};
```
## AC代码
[https://codeforces.com/contest/2194/submission/361977470](https://codeforces.com/contest/2194/submission/361977470)
::: 源代码
```cpp
/**
* Problem: C. Secret message
* Contest: Codeforces Round 1078 (Div. 2)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2194/problem/C
* Created: 2026-02-08 17:13:24
* Author: Gospel_rock
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
void Solve() {
ll N,K;
cin >> N >> K;
vector<string> A(K);
vector<vector<int>> i_ch_has(N,vector<int>(26));
for (int i=0;i<K;++i) {
cin>>A[i];
for (int j=0;j<N;++j) {
i_ch_has[j][A[i][j]-'a']=1;
}
}
vector<ll> factor_n;
for (int i=1;i<=N;++i) {
if (N%i==0) {
factor_n.push_back(i);
}
}
string ans;
auto gen_bi=[&](ll idx,ll len) -> vector<vector<int>> {
vector<vector<int>> res(len,vector<int>(26));
for (ll i=idx;i<idx+len;++i) {
for (int j=0;j<26;++j) {
res[i-idx][j]|=i_ch_has[i][j];
}
}
return res;
};
auto fac_and=[](vector<vector<int>> a, const vector<vector<int>> &b)->vector<vector<int>> {
for (int i=0;i<a.size();++i) {
for (int j=0;j<a[i].size();++j) {
a[i][j]&=b[i][j];
}
}
return a;
};
auto check=[&](ll len,bool gen_ans=false) -> bool {
vector<vector<int>> bi=gen_bi(0,len);
for (ll i=len;i<N;i+=len) {
bi=fac_and(bi,gen_bi(i,len));
}
for (int i=0;i<len;++i) {
bool ok=false;
for (int j=0;j<26;++j) {
if (bi[i][j]) {
if (gen_ans) {
ans.push_back('a'+j);
}
ok=true;
break;
}
}
if (!ok) {
return false;
}
}
if (gen_ans) {
string back_up=ans;
for (int i=2;i<=N/len;++i) {
ans+=back_up;
}
}
return true;
};
for (auto fac:factor_n) {
if (check(fac)) {
check(fac,true);
break;
}
}
cout<<ans<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
cin >> lT;
for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
1
9 2
iiinnnfff
nnfiffinn
*/
```
:::
## 心路历程（WA，TLE，MLE……）