Diane

Created by LXC on Wed Apr 24 17:08:12 2024

https://codeforces.com/problemset/problem/1554/D

ranting: 1800

tag: constructive algorithms, greedy, strings

problem

题意简述

要求您构造一个长度为 $n$ 的由小写字母构成的字符串，使得字符串内每个字串出现奇数次。

输入格式

第一行输入一个整数 $t$ 表示数据组数。

对于每组数据输入一个整数 $n$ 表示字符串长度。

输出格式

对于每组数据，输出一行长度为 $n$ 的满足题意的字符串。若有多组解任意输出一组即可。

说明/提示

在第一组数据里， $\texttt{abc}$ 的每个子串都恰好只出现一次。

在第三组数据里，$\texttt{bbcaabbba}$ 的每个子串出现奇数次，其中 $\texttt{b}$ 出现 $5$ 次，$\texttt{a}$ 和 $\texttt{bb}$ 各出现 $3$ 次，其它子串各出现 $1$ 次。

数据范围及约定

对于 $100%$ 的数据，$1\le t\le 500$，$1\le n \le 10^5$，$1\le \sum n\le 3\times 10^5$。

solution

对于一个长度为n以及n-1的全为同一种字符的字符串，两个串的所有同种子串出现个数只和是奇数。

因此构造一个串全为同种字符的串，只需要在正中心放一两个不同字符即可。

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

random_device seed;
ranlux48 engine(seed());
int random(int l, int r) {
    uniform_int_distribution<> distrib(l, r);
    return distrib(engine);
}
template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    int n;
    cin >> n;
    if (n<=26) {
        for (int i=0; i<n; i++) {
            cout << char('a'+i);
        }
        cout << "\n";
    } else if (n%2) {
        cout << string(n/2, 'a') << "bc" << string(n/2-1, 'a') << "\n";
    } else {
        cout << string(n/2, 'a') << "b" << string(n/2-1, 'a') << "\n";
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}