Practice.

A. SSeeeeiinngg DDoouubbllee

题意

给定一个字符串，将字符串复制一遍后拼接在一起得到一个新的字符串，将该字符串重新组合，输出一种回文组合。

思路

倒着拼到末尾。

时间复杂度：

对应AC代码

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while(t -- > 0){
            String s = scanner.next();
            System.out.println(s + new StringBuilder(s).reverse());
        }
    }
}

过于无脑

B. XOR = Average

题意

给定一个整数 ，构造一个长度为 的无重复元素的数组 ，满足 以及所有数的异或值等于平均值，即

。

输出数组的任意一种构造。

思路

我们来考虑奇偶性：

1. 为奇数时，我们只需输出 个 ，此时恰好满足条件；

2. 为偶数时，考虑到 的平均数为 ，异或值也为 ，而偶数个相同数的异或值为 ，所以我们不妨输出 ，以及 个 ，即可满足条件。

时间复杂度：

对应AC代码

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while(t -- > 0){
            int n = scanner.nextInt();
            if(n % 2 == 1){
                for(int i=0;i<n;i++) System.out.print("1 ");
                System.out.println();
            }else{
                System.out.print("1 3 ");
                for(int i=0;i<n-2;i++) System.out.print("2 ");
                System.out.println();
            }
        }
    }
}

小的就足矣

C. Almost All Multiples

题意

给定整数 ，构建一个字典序最小的排列 ，满足下面的条件：

1. ；

2. 。

思路

显然，若不考虑条件，那么我们肯定会输出一个递增的排列。

当我们考虑条件后，我们不难发现 多余了，而 所在的原位置留空了。

但是，我们不可以直接将 的位置放上 ，因为我们需要考虑下面的两个条件：

1. ；

2. 字典序最小

对于条件 ，若不满足，输出 即可。

对于条件 ，我们不难发现，当 的因数比较多的时候，满足 的 可以有好多个，此时若 位置放上 ，所得到的字典序不一定是最小的。

我们来举一个例子：

1
12 2

此时，字典序最小的应为下述输出：

2 4 3 12 5 6 7 8 9 10 11 1

因此，我们不妨循环操作，对于 ，找出第一个满足 的 ，将 修改为 、 的值替换为 ，然后继续循环，直到 。

时间复杂度：不知道

对应AC代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t --){
        int n, x;
        cin >> n >> x;
        if(n % x != 0) cout << -1 << '\n';
        else{
            vector<int> ans(n);
            for(int i=1;i<n-1;i++) ans[i] = i + 1;
            ans[n - 1] = 1;
            ans[0] = x;
            while(x < n){
                for(int i=x*2;i<=n;i+=x) {
                    if(n % i == 0){
                        ans[x - 1] = i;
                        x = i;
                        break;
                    }
                }
            }
            for(int i=0;i<n;i++) cout << ans[i] << ' ';
            cout << '\n';
        }
    }
    return 0;
}

一开始还真想着去直接交换了（

D. Range = √Sum

题意

给定一个整数 ，构建一个无重复元素的数组 ，满足 ，以及下面的式子：

。

思路

我们来讨论 的奇偶性：

1. 当 为偶数的时候，我们只需构建一个 即可。

2. 当 为奇数的时候，我们按照上述逻辑构建一个中间值为 ，向两端递减 的数组，此时，左边为 ，右边为 。

   那么，我们希望构建一个数组，满足左右两边均为 。

   我们执行下面的操作：

   ① 整个数组 ；

   ② 左边界 ，右边界 ；

   ③ 倒数第二个数 。

时间复杂度：

对应AC代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t --){
        int n;
        cin >> n;
        if(n % 2 == 0) {
            for(int i=n/2;i<=n-1;i++) cout << i << ' ';
            for(int i=n+1;i<=3*n/2;i++) cout << i << ' ';
        }
        else {
            vector<int> ans(n);
            iota(ans.begin(), ans.end(), (n + 5) / 2);
            ans[0]--;
            ans[n - 1]++;
            ans[n - 2]++;
            for (int i = 0; i < n; i++) cout << ans[i] << ' ';
        }
        cout << '\n';
    }
    return 0;
}

好一个思维 + 构造