Codeforces Round #836 (Div. 2)

A

SSeeeeiinngg DDoouubbllee

题意：告诉你一个字符串。若该串上每一位上的字母都可以出现两次，求回文串 

思路：正向再反向输出s即可

#include <bits/stdc++.h>
#define lowbit(x) x&(-x)
#define ios cin.sync_with_stdio(false)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int n;
string s;
void solve()
{cin>>s;cout<<s;reverse(s.begin(),s.end());cout<<s<<'\n';
}
int main()
{//ios;int _t=1;cin>>_t;while(_t--) solve();system("pause");return 0;
}

B

XOR = Average

题意：让你构造长度为n的数组，满足

思路：n为奇数时，全为1

           n为偶数时，两个元素为1和3，其余为2

#include <bits/stdc++.h>
#define lowbit(x) x&(-x)
#define ios cin.sync_with_stdio(false)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int n;
int a[N];
void solve()
{cin>>n;if(n&1){for(int i=1;i<=n;i++) a[i]=1;}else {for(int i=3;i<=n;i++) a[i]=2;a[1]=1,a[2]=3;}for(int i=1;i<=n;i++)cout<<a[i]<<" \n"[i==n];
}
int main()
{//ios;int _t=1;cin>>_t;while(_t--) solve();system("pause");return 0;
}

C

Almost All Multiples

题意：给定n和x，构造长度为n且字典序最小的排列。满足Pn=1,P1=x, i | Pi  (1 <= i <= n-1)

思路：先不考虑字典序最小，当n%x==0时有解，让px=n，其他位置不变即可。n%x!=0时，假设我们在x的位置填k*x，那么k*x的位置要填p*k*x，若最后一个x倍数的位置不能填n就是无解的，即n%x!=0.

考虑字典序最小，x的位置我们先填2*x，要保证n是所填数的倍数且所填数未出现过，(否则到这个位置上的时候也无法用n替代那么也是不行的。)不行就填3*x，4*x...

#include <bits/stdc++.h>
#define lowbit(x) x&(-x)
#define ios cin.sync_with_stdio(false)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int n,x;
int a[N];
bool vis[N];
void solve()
{cin>>n>>x;for(int i=1;i<=n;i++) vis[i]=0;if(n%x!=0){cout<<-1<<'\n';return ;}a[1]=x;a[n]=1;vis[x]=1;vis[1]=1;for(int i=2;i<n;i++){if(vis[i]){int cnt=2;while(n%(cnt*i)!=0&&!vis[cnt*i]&&cnt*i<=n) cnt++;a[i]=cnt*i;vis[cnt*i]=1;}else{a[i]=i;vis[i]=1;}}for(int i=1;i<=n;i++)cout<<a[i]<<" \n"[i==n];
}
int main()
{//ios;int _t=1;cin>>_t;while(_t--) solve();system("pause");return 0;
}

D

Range = √Sum

题意： 给定长度n，让你构造长度为n且各元素不同，满足以下条件的数组

 思路：n为偶数时，我们让元素为n+1,n-1,n+2,n-2,....n+n/2,n-n/2.极差为n且总和为n*n

            n为奇数时，我们先让n+1变成偶数，用上述方法构造。然后删去元素n-1,再让其余n-1个元素都加一，这样极差和总和是未发生改变的。

#include <bits/stdc++.h>
#define lowbit(x) x&(-x)
#define ios cin.sync_with_stdio(false)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int n;
void solve()
{cin>>n;vector<int>a;if(n%2==0){for(int i=1;i<=n/2;i++) cout<<n+i<<' ';for(int i=1;i<=n/2;i++) cout<<n-i<<' ';cout<<'\n';}else{for(int i=1;i<=(n+1)/2;i++) a.push_back(n+1+i);for(int i=2;i<=(n+1)/2;i++) a.push_back(n+1-i);for(int i=0;i<a.size();i++) cout<<a[i]+1<<" \n"[i==n-1];}
}
int main()
{//ios;int _t=1;cin>>_t;while(_t--) solve();system("pause");return 0;
}