Codeforces Round #735 (Div. 2) D. Diane

In the first test case, each substring of "abc" occurs exactly once.

In the third test case, each substring of "bbcaabbba" occurs an odd number of times. In particular, "b" occurs 55 times, "a" and "bb" occur 33 times each, and each of the remaining substrings occurs exactly once.

——————————————

题意：给定序列s的长度n，构造一个可能的序列满足：s的任何子列在s中出现的次数为奇数次。

思路：

①举例：对于长度为9的序列aaaaaaaaa，子序列a出现了9次，aa出现了8次，aaa出现了7次......aaaaaaaaa出现了9次。而对于长度为8的序列aaaaaaaa，子序列a出现了8次，aa出现了7次，aaa出现了6次......aaaaaaaa出现了8次。

②观察：由上两个例子，可得如下表格

 所以，按照子序列的奇偶性去看表格时，当子序列是奇/偶时，为使其次数认为奇数次，可以选择奇+偶来构造

③构造：构造时，需要两串x来满足上面的推论，一串x为奇数个，另一串为偶数个。这样x的总个数是（2*k）+(2*k+1)个。

此时x的任意长度子串必满足出现次数为奇数，前后两串x满足->（前奇后偶，前偶后奇）

若n为偶数，则需要用1个x以外的字符将两串x分隔开（例如y）。

若n为奇数，则需要2个x以外的字符将两串x分隔开。同时，若选择了2个一样的字符，则又会出现不满足奇数个的情况。故只能选用两个不同的，非x的字符（例如y,z）

④一些细节：构造时默认总长度n很大，但是不能遗漏了比如n==1的情况，n==1时只要1个任意字符串就可以。不加特判会按照奇数个的情况起码打印两个非x字符！

最后，上代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        if(n==1)
            cout<<"x"<<endl;
        else
        {
            for(int i=1;i<n/2;i++)
                cout<<"x";
            cout<<"y";
            if(n%2)
                cout<<"z";
            for(int i=0;i<n/2;i++)
                cout<<"x";
            cout<<endl; 
        }        
    }
    return 0;
}

AC代码