Practice.

A. SSeeeeiinngg DDoouubbllee

题意

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

思路

倒着拼到末尾。

时间复杂度：\(O(n)\)

对应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

题意

给定一个整数 \(n\)，构造一个长度为 \(n\) 的无重复元素的数组 \(a\)，满足 \(1 \leq a \leq 10 ^ 9\) 以及所有数的异或值等于平均值，即

\(a_1 \oplus a_2 \oplus \dots \oplus a_n = \frac{a_1 + a_2 + \dots + a_n}{n}\)。

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

思路

我们来考虑奇偶性：

\(n\) 为奇数时，我们只需输出 \(n\) 个 \(1\)，此时恰好满足条件；
\(n\) 为偶数时，考虑到 \(1, 3\) 的平均数为 \(2\)，异或值也为 \(2\)，而偶数个相同数的异或值为 \(0\)，所以我们不妨输出 \(1,3\)，以及 \(n - 2\) 个 \(2\)，即可满足条件。

时间复杂度：\(O(n)\)

对应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

题意

给定整数 \(n, x\)，构建一个字典序最小的排列 \(p\)，满足下面的条件：

\(p_1 = x, p_n = 1\)；
\(p_i \% i = 0\)。

思路

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

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

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

\(p_x = n \rightarrow n \% x\)；
字典序最小

对于条件 \(1\)，若不满足，输出 \(NO\) 即可。

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

我们来举一个例子：

1
12 2

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

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

因此，我们不妨循环操作，对于 \(x\)，找出第一个满足 \(n \% kx, k \geq 2\) 的 \(k\)，将 \(p_i\) 修改为 \(kx\)、\(x\) 的值替换为 \(kx\) ，然后继续循环，直到 \(x \geq x\)。

时间复杂度：不知道

对应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

题意

给定一个整数 \(n\)，构建一个无重复元素的数组 \(a\)，满足 \(1 \leq a_i \leq 10 ^ 9\)，以及下面的式子：

\(\max(a_1, a_2, \dots, a_n) - \min(a_1, a_2, \dots, a_n)= \sqrt{a_1 + a_2 + \dots + a_n}\)。

思路

我们来讨论 \(n\) 的奇偶性：

当 \(n\) 为偶数的时候，我们只需构建一个 \([n / 2, n / 2 + 1, \ldots, n - 1, n + 1, n + 2, \ldots, 3n / 2]\) 即可。
当 \(n\) 为奇数的时候，我们按照上述逻辑构建一个中间值为 \(n\)，向两端递减 \(1\) 的数组，此时，左边为 \(n\)，右边为 \(\sqrt {n (n + 1)}\)。那么，我们希望构建一个数组，满足左右两边均为 \(n + 1\)。我们执行下面的操作： ① 整个数组 \(+1\)； ② 左边界 \(-1\)，右边界 \(+1\)； ③ 倒数第二个数 \(+1\)。

时间复杂度：\(O(n)\)

对应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;
}

好一个思维 + 构造