Codeforces Round #836 (Div. 2)

A. SSeeeeiinngg DDoouubbllee

题意：给定一个字符串，让这个字符串的每个位置重复出现一次。然后输出它的回文子串。

思路：就瞎搞搞

void solve() {
    string s; cin >> s;
    string be, ed;
    map<char, int> mp;
    for (auto x : s) mp[x] += 2;
    for (auto [x, v] : mp) {
        int k = v / 2;
        for (int i = 0; i < k; i ++ ) be += x, ed += x;
    }
    reverse(all(ed));
    cout << be + ed << endl;
}

 B. XOR = Average

题意：n个数的异或值=n个数的平均值，要求你构造一个序列出来

思路：首先对于奇数n来说，我们只需要任意输出1个数即可。因为对于任意的x，偶数个x起来是0，0异或最后一个x就是x。对于偶数来说，我们有1^3=2,我们我们前面再补（n-2)个2， 就满足了。

void solve() {
    int n; cin >> n;
    if(n % 2)   for (int i = 1; i <= n; i ++ )  cout << 1 << ' ';
    else {
        for (int i = 1; i <= n - 2; i ++ )
            cout << 2 << ' ';
        cout << 1 << ' ' << 3;
    }
    cout << endl;
}

     

C. Almost All Multiples 

题意：一个序列从1~n，现在固定a1为x，an为1，要求其他位置(2~n-1)的数能整除i，请构造这个序列， 字典序最小。

思路：其实我们只需要去考虑n这个数就可以了。加入a1=x=n，那么显然后面直接输出就可以了。那么如果a1=x != n, 那么说明我们的n是得派上用场的。一个最直观的理解， 如果n % x != 0, 那么n就不能对x这个位置完成操作， 就失败了。 那么如果n % x = 0，说明n满足条件，下面只需要去找字典序最小就行了。 如何寻找呢， 显然比如说2, 4, 6这种位置， 如果说n一开始是弥补了2， 但是4和6都可以整除2， 那么我们就可以把n换到6的位置了(同时要满足n能整除6)。

void solve()
{   
    cin >> n >> x;     
    if(n == x) {
        cout << x << " ";
        for (int i = 2; i < n; i++ ) {
            cout << i << " ";
        }
        cout << 1 << endl;
        return ;
    }
    if(n % x) {cout << -1 << endl; return ;}
 
    ans[1] = x, ans[n] = 1;
    for (int i = 2; i < n; i++ ) ans[i] = i;
    ans[x] = n;
    int cur = x;
    for (int i = x; i < n; i++ ) {
        if(i % cur == 0 && n % i == 0) {
            swap(ans[cur], ans[i]);
            cur = i;
        }
    }
 
    for (int i = 1; i <= n; i++ ) cout << ans[i] << ' ';
    cout << endl;
 
}

D. Range = √Sum

题意：max-min = 根号sum。要求构造一个不含重复数的序列。

思路：呃其实偶数挺想的。奇数有点难，我不会证明我的n+3为什么对，但是一发过了hh。

 

 

好像有点抽象~~

void solve() {
    int n; cin >> n;
    if(n % 2 == 0) {
        for (int i = 0; i < n / 2; i ++ ) {
            cout << (n / 2) + i << ' ';
        }
        for (int i = 0; i < n / 2; i ++ )
            cout << 3 * n / 2 - i << ' ';
    }
    else {
        for (int i = 0; i < n / 2; i ++ ) {
            cout << (n + 1) / 2 + i + 1 << ' ';
        }   
        for (int i = 0; i < n / 2; i ++ )
            cout << (3 * n + 3) / 2 - i + 1 << ' ';
        cout << n + 3;
    }
    
    cout << endl;
}