题解

题面描述

给定一个正整数$n$，要求构造一个只由小写英文字母 $a$ 到 $z$ 组成的字符串 $s$，其中字符串长度为$n$。
要求满足：对于 $s$ 的所有本质不同的连续子串（即去重后所有相邻字符组成的子串），其中长度为奇数的子串出现次数必须为奇数。

本质不同的连续子串指的是从字符串中提取的所有连续子串中，对内容相同的子串只保留一个。例如，对于字符串 "aa"，所有连续子串有 "a"（出现两次）和 "aa"，去重后结果为 $\{"a", "aa"\}$。

思路

1. 统计全同字符构造的字符串性质
   如果采用全由同一字母构成的字符串，比如 $s = \mathtt{a}^n$，那么所有本质不同的连续子串为
   $\{ \mathtt{a}, \mathtt{aa}, \dots, \mathtt{a}^n \}$ 数量正好为 $n$。在这些子串中，长度为奇数的子串个数为：

   • 当 $n$ 为奇数时，奇数子串个数为 $\frac{n+1}{2}$；
   • 当 $n$ 为偶数时，奇数子串个数为 $\frac{n}{2}$。
     因此，要求这些数量为奇数，则当 $n \equiv 1$ 或 $2 \ (\mod\ 4)$ 时，全$a$串满足要求。

2. 构造满足条件的字符串
   对于其他情况我们需要对全$a$串进行适当修改，使得由修改部分引入的奇数长度子串个数发生奇偶性翻转，从而满足题目要求。

   • 当 $n \equiv 0\ (\mod\ 4)$ 时，可以构造后缀为 "abca"。即令$$s = \mathtt{a}^{(n-4)} + \mathtt{"abca"}$$
   • 当 $n \equiv 3\ (\mod\ 4)$ 时，可以构造后缀为 "abacaba"（注意 $n=3$ 时单独处理，用 "aba" 即可）。即令$$s = \mathtt{a}^{(n-7)} + \mathtt{"abacaba"}$$

   这样通过不同后缀修正，全体字符串中奇数长度子串的个数即可满足奇数条件。

代码分析

下面以 $C++$ 代码为例进行分析：

• 输入部分：首先读取测试数据组数 $T$，然后对每组测试数据读取 $n$ 的值。
• 分情况构造字符串：
  • 若 $n \equiv 1$ 或 $2 \ (\mod\ 4)$，直接输出由全字符 'a' 组成的字符串。
  • 若 $n \equiv 0\ (\mod\ 4)$，则在字符串的末尾加入 "abca"，前面补上 $n-4$ 个 'a'。
  • 若 $n \equiv 3\ (\mod\ 4)$，则在字符串末尾加入 "abacaba"，前面补上 $n-7$ 个 'a'（若 $n=3$ 则直接用 "aba"）。
• 输出部分：将构造好的字符串输出。

本质上，这种构造方法利用了全$a$串在连续子串个数上的规律，在需要调整奇数子串个数时，加上特定模式的后缀，将原本偶数变化为奇数，从而满足题意。

C++

#include <iostream>
#include <string>
using namespace std;
int main(){
    int T; 
    cin >> T;  // 读入测试数据组数 T
    while(T--){
        int n; 
        cin >> n;  // 读入字符串长度 n
        string s;
        int r = n % 4;  // 求 n 对 4 取余以判断情况
        if(r == 1 || r == 2){
            // 当 n ≡ 1 或 2 (mod 4) 时，直接构造全由字符 'a' 组成的字符串
            s = string(n, 'a');
        } else if(r == 0){
            // 当 n ≡ 0 (mod 4) 时，前面填充 n-4 个 'a'，后缀为 "abca"
            s = string(n - 4, 'a') + "abca";
        } else { // r == 3
            // 当 n ≡ 3 (mod 4) 时，若 n == 3，则直接用 "aba"
            // 若 n >= 7，则前面填充 n-7 个 'a'，后缀为 "abacaba"
            if(n == 3) 
                s = "aba";
            else 
                s = string(n - 7, 'a') + "abacaba";
        }
        cout << s << "\n";  // 输出构造好的字符串
    }
    return 0;
}

Python

# 读入测试数据组数 T
T = int(input())
for _ in range(T):
    # 读入字符串长度 n
    n = int(input())
    # 初始化结果字符串 s
    s = ""
    r = n % 4  # 求 n 对 4 取余
    if r == 1 or r == 2:
        # 当 n ≡ 1 或 2 (mod 4) 时，构造全'a'字符串
        s = "a" * n
    elif r == 0:
        # 当 n ≡ 0 (mod 4) 时，前面填充 n-4 个 'a'，后缀为 "abca"
        s = "a" * (n - 4) + "abca"
    else:  # r == 3
        if n == 3:
            # 当 n 为 3 时，直接使用 "aba"
            s = "aba"
        else:
            # 当 n ≥ 7 且 n ≡ 3 (mod 4) 时，前面填充 n-7 个 'a'，后缀为 "abacaba"
            s = "a" * (n - 7) + "abacaba"
    print(s)  # 输出构造好的字符串

Java

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 读入测试数据组数 T
        int T = in.nextInt();
        while (T-- > 0) {
            // 读入字符串长度 n
            int n = in.nextInt();
            String s = "";
            int r = n % 4; // 求 n 对 4 取余
            if (r == 1 || r == 2) {
                // 当 n ≡ 1 或 2 (mod 4) 时，构造全'a'字符串
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < n; i++) {
                    sb.append('a');
                }
                s = sb.toString();
            } else if (r == 0) {
                // 当 n ≡ 0 (mod 4) 时，前面填充 n-4 个 'a'，后缀为 "abca"
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < n - 4; i++) {
                    sb.append('a');
                }
                sb.append("abca");
                s = sb.toString();
            } else { // r == 3
                if (n == 3) {
                    // 当 n 为 3 时，直接使用 "aba"
                    s = "aba";
                } else {
                    // 当 n ≥ 7 且 n ≡ 3 (mod 4) 时，前面填充 n-7 个 'a'，后缀为 "abacaba"
                    StringBuilder sb = new StringBuilder();
                    for (int i = 0; i < n - 7; i++) {
                        sb.append('a');
                    }
                    sb.append("abacaba");
                    s = sb.toString();
                }
            }
            System.out.println(s);  // 输出构造好的字符串
        }
        in.close();
    }
}

题目内容

小苯给了你一个正整数$n$，他希望你构造一个仅包含小写英文字母'$a$'到'$z$'的长度为$n$的字符串$s$，满足:

$s$的所有本质不同连续子串中，长度为奇数的子串恰好出现了奇数次。

请你构造一个吧。

本质不同连续子串:指的是从一个字符串中提取的所有连续子串(也就是相邻字符组成的子串)中，按照内容相同性去重后得到的集合。在这个集合中心如果两个子串在字符序列上完全相同，那么它们被视为"本质相同，只记作一个。

例如，对字符串:“$aa$”。所有可能的连续子串(包括重复的)为:

从位置$1$：“$a$",“$aa$”

从位置$2$：“$a$”

其中“$a$”出现了两次，但本质不同连续子串只记作{“$a$”,“$aa$”}两个。

因为重复的“$a$”只保留一个,

输入描述

本题有多组测试数据

输入的第一石包含一个正预数$T(1≤T≤100)$，表示数据回数,

接下来包含$T$组数据，每组数据的格式如下

在单独的一行输入一个正整数$n(1≤n≤2000)$

(保证所有更试数起中，$n$的总和不超过$2000$。)

输出描述

对于每时测试数据:

输出一行一个长度为$n$的字符串，符合题意

样例1

输入

1
4

输出

llve