比赛链接：Dashboard - Codeforces Round #836 (Div. 2) - Codeforces

A： 构造

 题意：给定一个字符串，每个字符可以出现两次，要求通过重新排列构造一个回文串。

 方法：回想回文串的性质。我们只需要把一个字符放在前面和后面即可。

代码：

#include<iostream>#include<string>#define int long long#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);using namespace std;const int N=2e5+10;typedef pair<int,int>PII;char ans[N];inline void solve(){string s;cin>>s;int n=s.size();s="*"+s;for(int i=1;i<=n;i++){ans[i]=s[i];ans[2*n-i+1]=s[i];}for(int i=1;i<=2*n;i++) cout<<ans[i];cout<<"\n";}signed main(){int T;cin>>T;while(T--) solve();}

B:构造

 题意：给定一个长度为N的数组，输出一个序列，使得它的xor和等于这个序列的平均值。

方法：当长度为奇数的时候，直接输出奇数个相同的数即可。当长度为偶数的时候，我们选择前n-2个数为2，最后两个数分别为1和3即可。

代码：

#include<iostream>#include<string>#define int long long#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);using namespace std;const int N=2e5+10;typedef pair<int,int>PII;int a[N];inline void solve(){int n;cin>>n;if(n&1){for(int i=1;i<=n;i++) cout<<"1 ";cout<<'\n';}else{for(int i=1;i<=n-2;i++) cout<<"2 ";cout<<"1 3\n";}}signed main(){int T;cin>>T;while(T--) solve();}

 C：构造

 题意：给定一个n和x，要求构造一个数组，使得a[1]=x,a[n]=1。并且对于i（1-n），ai%i==0，且1-n中的数只能出现一次。输出字典序最小的数组

ps：这里的i同时表示位置和数字

分析：我们发现：

如果n%x！=0。那么肯定是-1。（自己用手模拟一下下啦）

如果n==x，则可以直接输出答案

常规情况：

要使字典序最小，那么n一定要尽可能在后面。仔细观察可以知道，i位置上的数对应数字i，则一定是最小的。那么，不对应的地方一定是从位置x开始。

我们考虑最坏的情况，即：n在位置x上。ans[x]=n。现在需要做的就是，把n尽可能满足条件往后面的位置调。

cur表示n找到新位置后的原始位置（初始值为x）。从不对应位置x开始往后调整。可以满足的条件（i%cur==0&&n%i==0）。解释：第一个条件表示，数字i（也可以说是位置i）可以换到新的位置，第二个条件表示：n可以在位置i放下。那么，经过正向调整一遍，我们使得n尽可能的放在了后面，其余位置保持不变，字典序仍然是最小的。

代码：

#include<iostream>#include<string>#define int long long#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);using namespace std;const int N=2e5+10;typedef pair<int,int>PII;int ans[N];inline void solve(){int n,x;cin>>n>>x;if(n==x){cout<<x<<" ";for(int i=2;i<n;i++) cout<<i<<" ";cout<<"1\n";return;}if(n%x){cout<<"-1\n";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<<"\n";}signed main(){int T;cin>>T;while(T--) solve();}

D：构造

题意：构造一个长度为n的整数数组，使得数组的最大值和最小值的差等于数组之和的二次方根。

ps：此题构造方法很难解释的通，读者自行理解吧

分析： 如何够构造呢？

我们发现，当n为偶数时：

构造   [,n-1]U(n+1,n+]

n为奇数怎么办？

我们可以将n转变为偶数：

构造   [+1,n-1]U[n+1,n++1]

代码：

#include<iostream>#include<string>#define int long long#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);using namespace std;const int N=2e5+10;typedef pair<int,int>PII;int ans[N];inline void solve(){int n;cin>>n;if(n%2==0){for(int i=n/2;i<n;i++) cout<<i<<" ";for(int i=n+1;i<=n+n/2;i++) cout<<i<<" ";}else{n++;//变为偶数for(int i=n/2+1;i<n;i++) cout<<i<<" ";for(int i=n+2;i<=n+n/2+1;i++) cout<<i<<" ";}cout<<"\n";}signed main(){int T;cin>>T;while(T--) solve();}