宝石魔阵（gemstone）题解

发表于 分类于

本人第二次给五校供题，这次题面都是我写的，这道我自己的题的题面我最满意。

宝石魔阵 (gemstone)

题目信息

时间限制：1000 ms1000 \texttt{ ms}。
空间限制：512 MiB512 \texttt{ MiB}。
本题使用文件输入输出。
输入文件名：gemstone.in。
输出文件名：gemstone.out。

题目背景

众所周知，小 R 是 R 国的著名魔法师。

四个月前，小 R 在一个荒岛上发现了神秘的巨石阵，她惊奇地发现这个巨石阵充满着魔力。于是自荒岛之旅结束后，她就一直在思考着巨石阵充满魔力的原因。她现在要开始她的魔法实验，以验证她的结论。

题目描述

由于小 R 不想花费精力取搬运巨石，她到魔法商店中购买了大量与巨石有类似魔法作用的魔法宝石，宝石也可以像巨石那样形成宝石阵。宝石一共有 2626 种，方便起见，我们按照价格从低到高将每种宝石分别标号为 a,b,c,⋯\cdots,x,y,z，我们将一个宝石阵用对应位种类的标号表示成一个小写字母字符串。

小 R 经过这四个月的思考，认为巨石阵的魔力丰盈，与一种叫图腾力量的东西有关。具体而言，对于一个长度为 nn 的巨石阵，我们可以将其抽象为一个长度为 nn 的序列 s1,s2,⋯ ,sns_1,s_2,\cdots,s_n，每存在一个 1≤i≤n−11\le i\le n-1，满足第 1∼i1\sim i 个巨石形成的巨石阵和第 n−i+1∼nn-i+1\sim n 个巨石形成的巨石阵完全一致，即 ∀1≤j≤i,sj=sn−i+j\forall 1\le j\le i,s_j=s_{n-i+j}，则这个巨石阵就会产生若干单位的图腾力量，小 R 称这个现象为 ii 的神秘化。由于每个这样的 ii 产生的图腾力量相差甚微，所以小 R 直接规定每个这样的 ii 会产生 11 个单位的图腾力量。

只不过图腾力量如果过于丰富，巨石阵会变得不稳定，小 R 认为这是不好的，所以她要在满足一些限制后让这个宝石阵的图腾力量最小，这样子这个巨石阵是最稳定的。小 R 推测这些结论在宝石阵上也是适用的。

现在小 R 要制作 TT 个宝石阵，第 ii 的宝石阵长度为 nin_i。同时还会给定一个大小为 kik_i 的序列 li,1,li,2,⋯ ,li,kil_{i,1},l_{i,2},\cdots,l_{i,k_i}，对于每个 1≤j≤ki1\le j\le k_i，小 R 要满足这个宝石阵会出现 li,jl_{i,j} 的神秘化这个现象，并且让其最稳定。为了考虑价格，小 R 还要让这个宝石阵对应的字符串字典序最小。

输入格式

从文件 gemstone.in 中读入数据。

输入的第一行包含一个正整数 TT，表示小 R 要制作的宝石阵的数量。

对于第 ii 个宝石阵：
第 2i2i 行包含两个整数 ni,kin_i,k_i，表示这个宝石阵的长度和限制集合的大小。
第 2i+12i+1 行包含 kik_i 个正整数，第 jj 个正整数为 li,jl_{i,j}，具体给出了限制。

输出格式

输出到文件 gemstone.out 中。

输出 TT 行，每行一个字符串 sis_i，表示第 ii 个宝石阵。

样例

样例输入 1

1
2
3
4
5
6
7
8
9
4
4 0

4 1
2
6 2
2 3
9 2
3 6

样例输出 1

1
2
3
4
aaab
abab
aaaaaa
aabaabaab

样例输入 2

1
2
3
4
5
6
7
3
3 1
1
7 1
2
11 1
3

样例输出 2

1
2
3
aba
abaaaab
aabaaaaaaab

样例 3

见选手目录下的 gemstone/gemstone3.in 与 gemstone/gemstone3.ans。

数据范围与提示

对于所有的数据，满足 1≤T,n≤2×1051\le T,n\le 2\times 10^5，∑n≤2×105\sum{n}\le 2\times 10^5，0≤k≤n−10\le k\le n-1，1≤l1<l2<⋯<lk≤n−11\le l_1<l_2<\cdots<l_k\le n-1（每组询问对应的下标 ii 省略，下同）。

测试点编号 nn kk TT 特殊性质
1∼31\sim 3 ≤18\le 18 <n<n ≤20\le 20 无
4∼74\sim 7 ≤18\le 18 <n<n ≤2×105\le 2\times 10^5 无
88 ≤50\le 50 <n<n ≤50\le 50 ∑n≤2500\sum{n}\le 2500
9∼109\sim 10 ≤2500\le 2500 <n<n ≤2500\le 2500 ∑n≤2500\sum{n}\le 2500
1111 ≤2×105\le 2\times 10^5 =0=0 ≤2×105\le 2\times 10^5 无
12∼1312\sim 13 ≤2×105\le 2\times 10^5 =1=1 ≤2×105\le 2\times 10^5 无
1414 ≤2×105\le 2\times 10^5 =n−1=n-1 ≤2×105\le 2\times 10^5 无
15∼1615\sim 16 ≤2×105\le 2\times 10^5 <n<n =1=1 ∀1≤j≤k,(n−lj)∣n\forall 1\le j\le k,(n-l_j)\mid n
17∼1817\sim 18 ≤2×105\le 2\times 10^5 <n<n ≤2×105\le 2\times 10^5 ∀1≤j≤k,(n−lj)∣n\forall 1\le j\le k,(n-l_j)\mid n
19∼2119\sim 21 ≤2×105\le 2\times 10^5 <n<n =1=1 无
22∼2522\sim 25 ≤2×105\le 2\times 10^5 <n<n ≤2×105\le 2\times 10^5 无

题解

简要题意

有 TT 组询问，每组询问给定一个正整数 nin_i 和一个长度为 kik_i 的序列 li,1,li,2,⋯ ,li,kil_{i,1},l_{i,2},\cdots,l_{i,k_i}，求一个长度为 nin_i 的小写字母字符串，满足：

  • 字典序最小；
  • border 数量最小；
  • 对于任意的 1≤j≤ki1 \le j \le k_i，存在长度为 li,jl_{i,j} 的 border。

算法一

直接爆搜，考虑如果我们已经求出了序列为 SS 时的答案是什么，则当序列为 S∪{x}S \cup \{x\} 时答案是什么，这只要将 SS 的答案扫一遍调整一下即可，时间复杂为 O(∑2nn)O(\sum{2^nn})，期望得分 1212 分。

对于第 3∼73 \sim 7 个测试点，TT 很大，每组都暴力搜索会导致复杂度爆炸。于是我们考虑打表算出 n=1∼18n = 1 \sim 18 的所有答案，这只有 218−12^{18}-1 种情况。期望得分 2828 分。

算法二

对于 k=0k = 0 的情况，若 n=1n = 1 则字符串 a 满足条件；若 n>1n > 1 则字符串 aa⋯\cdotsab 满足条件。对于 k=n−1k = n − 1 则字符串 aa⋯\cdotsaa 满足条件。对于 k=1k = 1 则我们将第 l1l_1 和 nn 位设为 bb 其他位设为 aa 即可满足条件。综合前面算法，期望总得分 4444 分。

算法三

显然的，如果一个字符串有长度为 mm 的 border，则这个字符串有长度为 n−mn − m 的周期。

对于第 15∼1815 \sim 18 个测试点，所有周期均整除长度。所以我们只需要求出所有周期的 gcd⁡\gcd，在周期内像 k=0k = 0 那样填 a 或者 aa⋯\cdotsab，然后不断重复下去即可。综合前面算法，期望得分 6060 分。

算法四

弱周期引理：若一个字符串有长度为 aa 和 bb 的周期，且满足 a+b≤na + b \le n，则这个字符串有长度 gcd⁡(a,b)\gcd(a, b) 的周期。

我们考虑缩减 border 集合，如果当前集合中的最长 border 的长度 BB 大等于 TT，则有 n−B+T≤nn − B + T \le n，所以由弱周期引理可以得到不会更长的周期 gcd⁡(T,𝑛−B)\gcd (T, 𝑛 − B)，然后这个 border 就没用了。

缩减到没法缩减后，即当前的 B<TB < T，我们考虑两种情况：

  • 2T≥n2T \ge n ，则 border 长度 B≤⌊n/2⌋B ≤ \lfloor n/2\rfloor，于是我们可以得到下图：

pic

对于前后 BB 个，我们递归构造，对于中间的部分，我们先全部填 a，然后 KMP 一边判断一下当前串的最长 border 是不是 BB，如果不是，那么把最后一个 a 改成 b 即可让所有多余的 border 消失。

  • 2T<n2T < n，则一个周期至少完整出现两次，于是我们可以得到下图：

pic

我们考虑把周期缩至一倍，因为后面只是单纯的重复，该有的都会有，所以又有下图：

pic

我们将 border 集合并上 xx，递归构造前面 TT 个，再将其不断重复即可。

时间复杂度为 O(nlog⁡2n)O(n\log^2{n})，空间复杂度为 O(n)O(n)，期望得分 100100 分。

标程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
#define il inline
#define S std::string
#define V std::vector<int>
#define H(x) (x).back()
#define pb push_back
#define qb pop_back
const int N=2e5+5;

int tt,n,m,p[N]; V B; V::iterator I;

il int gcd(int a,int b){return b?gcd(b,a%b):a;}

il int KMP(const S &s)
{
    int i,j=-1,n=s.size();
    for (p[0]=-1,i=0; i<n; p[++i]=++j) for ( ; ~j&&s[j]!=s[i]; j=p[j]);
    return p[n];
}

il S sol(int n,V &B)
{
    if (!B.size()) return n<2?"a":S(n-1,'a')+"b"; int i,m=B.size(),X=H(B),T=n-X; S r;
    for (i=m-1; ~i&&H(B)>=T; i--,B.qb()) T=gcd(T,n-H(B));
    if (X=n-T,T<=X)
    {
        if (i=n%T)
        {
            I=std::lower_bound(B.begin(),B.end(),i);
            if (I==B.end()||*I!=i) B.insert(I,i);
        }
        for (r=sol(i+=T,B); i<n; i+=T) r+=r.substr(i-T);
    }
    else
    {
		B.qb(),r=sol(X,B)+S(T-X,'a');
		if (KMP(r+=r.substr(0,X))!=X) r[T-1]='b';
	}
	return r;
}

int main()
{
    freopen("gemstone.in","r",stdin),freopen("gemstone.out","w",stdout);

    std::ios::sync_with_stdio(0),std::cin.tie(NULL);
    std::cin>>tt; int i,x;
    while (tt--)
    {
        std::cin>>n>>m,B.clear();
        while (m--) std::cin>>x,B.pb(x);
        std::cout<<sol(n,B)<<'\n';
    }
	
    return 0;
}