CF-1078-C. Secret message

题目大意

题目总结：秘密信息 (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，不能够呃循环移动的那种循环节，它是比较严格的那种循环节。

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

源代码

/**
 * 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……）