A. SSeeeeiinngg DDoouubbllee

题目链接：

Problem - A - Codeforces

题面：

题意：

给定一个字符串，把这个字符串每个字符重复两遍后重新排序一定是一个回文串，问这个回文串是什么

思路：

题目是多种答案的，只要符合一个即可，那么我们可以把每个字符的数量统计重来，然后从小到大输出一遍，在从大到小输入一遍

例如：abc

变成：abccba即可

代码：

#include
using namespace std;
int mp[30];int main(){int t;cin >> t;while(t--){string s;cin >> s;memset(mp, 0, sizeof(mp));for(int i = 0; i < s.length(); i++){mp[s[i] - 'a']++;}for(int i = 0; i < 26; i++){for(int j = 0; j < mp[i]; j++){cout << char(i + 'a');}}for(int i = 25; i >= 0; i--){for(int j = 0; j < mp[i]; j++){cout << char(i + 'a');}}cout << endl;}return 0;
}

B. XOR = Average

题目链接：

Problem - B - Codeforces

题面：

题意：

构造一个长度为n的数组，这个数组的平均数和异或值相等

思路：

如果这个数组的长度为奇数，那么我们可以分成n-1和1，n-1一定是偶数，如果这n-1个数全部相同，那么这n-1个数的异或值为0，那么异或最后那个数就那个本身（0 ^ 任意数 = 任意数），所以我们只需要让这n个数相同即可

如果这个数组的长度为偶数，那么如果这n个数全相同，那么异或值为0，所以分开讨论

我们把n个数拆分成2个和n-2个，n-2一定是偶数，那么这n-2个数相同的异或值为0，n个数的异或值就是那两个数的异或值，设n-2个数都是x，那么a[0] + a[1] = 2 * x, a[0] ^ a[1] = x即可，凑一下得出a[0] = 1, a[1] = 3, x = 2

代码：

#include
using namespace std;
int mp[30];int main(){int t;cin >> t;while(t--){int n;cin >> n;if(n & 1){for(int i = 0; i < n; i++){if(i != 0){cout << " ";}cout << 1;}cout << endl;} else{cout << "1 3";for(int i = 0; i < n - 2; i++){cout << " 2";} cout << endl;}}return 0;
}

C. Almost All Multiples

题目链接：

Problem - C - Codeforces

题面：

题意：

构造一个n的排列，使得a[1] = x, a[n] = 1, a[i] % i== 0，排序的字典序尽量小，如果可以输出这个排列，不可以就输出-1

思路：

如果只有a[i] % i == 0这个条件，那么只需要把1-n输出一遍即可，但是a[1] = x, a[n] = 1，那么我们不考虑字典序最小我们只需要考虑n%x ==0?即可（我们要把n给a[x]），如果满足，那么就可以构造，如果不满足就出-1，这个时候就但是需要考虑字典树最小

如8 2

应该出2 4 3 8 5 6 7 1

而不是2 8 3 4 5 6 7 1

所以我们对于2 ~ n - 1的位置，要先考虑i是否可以，如果不可以就考虑倍数，如果满足xx % i == 0 && n % xx == 0就可以把xx填在ai，这样子就可以满足字典序最小

代码：

#include
using namespace std;
int arr[200005];
bool vis[200005];
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin >> t;while(t--){memset(vis, 0, sizeof(vis));int n, x;cin >> n >> x;arr[1] = x;arr[n] = 1;vis[1] = 1;vis[x] = 1;if(n % x != 0){cout << -1 << endl;continue;}for(int i = 2; i <= n - 1; i++){if(vis[i] == 0){arr[i] = i;vis[i] = 1;}else{for(int j = 2; j * i <= n; j++){if(n % (j * i) == 0){arr[i] = i * j;vis[i * j] = 1;break;}}}}for(int i = 1; i <= n; i++){if(i != 1){cout << " ";}cout << arr[i];}cout << endl;}return 0;
}

D. Range = √Sum

题目链接：

Problem - D - Codeforces

题面：

题意：

构造一个长度为n的数组（每个数不能重复），使得这个数组的最大值减去最小值 == 这个数组所有数字和的开根

思路：

最初的想法是让每个数等于n，那么根号n * n == n，我们只需要让max - min = n即可

设max = x,min = y, 

得到x + y = 2 * n, x - y = n

解得x = 3 * n / 2, y = n / 2.

如果n是奇数，那么x和y就不是整数,所以n为奇数不可用这个方法

如果n是偶数，那么min 就是 n / 2,max是3 * n / 2,中间n - 2个都是n，但是每个数不能重复，我们可以 n / 2 + 1. n / 2 + 2.... 3 * n / 2 - 2. 3 * n / 2 - 1这样子使得平均数为n即可

如果n是奇数，那么我们就可以把差值变成2n，那么数组和为4n^2,那么平均数为4n，那么min就是3n，max = 5n,那么数组就是3n， 3n+1，3n+2...(中间不是连续的）4n(同理)...5n-2.5n-1.5n

代码：

#include
using namespace std;
int arr[300005];
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin >> t;while(t--){int n;cin >> n;if(n & 1){arr[1] = 3 * n;arr[n] = 5 * n;int ans = (1 + n) / 2;arr[ans] = 4 * n;int cnt = 1;for(int i = 2; i < ans; i++){arr[i] = 3 * n + cnt;cnt++;}for(int i = ans + 1; i < n; i++){arr[i] = 8 * n - arr[n - i + 1];}}else{arr[1] = n / 2;arr[n] = n / 2 * 3;int ans = 1;for(int i = 2; i <= n / 2; i++){arr[i] = n / 2 + ans;ans++;}for(int i = n / 2 + 1; i < n; i++){arr[i] = 2 * n - arr[1 + n - i];}}for(int i = 1; i <= n; i++){if(i != 1){cout << " ";}cout << arr[i];}cout << endl;}return 0;
}