A. Ehab Fails to Be Thanos
题目链接:https://codeforc.es/contest/1174/problem/A
题意: 给你2n个数的数组,重新排列,使得前n和不等于后n项和.
题解:
- 如果元素都相等,不可能,输出"-1"
- 否则sort后输出
#include <bits/stdc++.h>
#define P pair<int,int>
#define fir first
#define sec second
using namespace std;
typedef long long ll;
const int N=2e5+5;
const int mod=998244353;
int a[N];
int main(){
int n;
cin>>n;
int f=0;
for(int i=1;i<=2*n;i++){
cin>>a[i];
if(a[1]!=a[i]) f=1;
}
if(!f){
puts("-1");
return 0;
}
sort(a+1,a+1+2*n);
for(int i=1;i<=2*n;i++) printf("%d ",a[i]);
return 0;
}
B. Ehab Is an Odd Person
题目链接:https://codeforc.es/contest/1174/problem/B
题意:给你有n个数的数组,你可以对此进行此操作任意次:如果ai+aj是奇数,你可以选择交换这两个数.输出字典序最小的数列.
题解:
显然如果数列中既有奇数又有偶数,可以得到最小的序列.
- 如果所有元素全是奇数或者全是偶数.输出原数列
- 否则sort后输出数列.
#include <bits/stdc++.h>
#define P pair<int,int>
#define fir first
#define sec second
using namespace std;
typedef long long ll;
const int N=1e5+5;
const int mod=998244353;
int a[N];
int main(){
int n;
cin>>n;
int x=0,y=0;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]%2) x=1;
else y=1;
}
if(x&&y) sort(a+1,a+1+n);
for(int i=1;i<=n;i++) printf("%d ",a[i]);
return 0;
}
C. Ehab and a Special Coloring Problem
题目链接:https://codeforc.es/contest/1174/problem/C
题意:构造一个数列a[],使得i从2到n满足,当i,j互质时,a[i]!=a[j];且数列的最大值要最小.
题解:质数与质数肯定都是互质的,先筛出素数,依次编号,非素数找到一个质因子,输出质因子的编号.
6/5 emmm,好像写复杂了,其实可以在筛数时直接记录非质数的质因子,对.
#include <bits/stdc++.h>
#define P pair<int,int>
#define fir first
#define sec second
using namespace std;
typedef long long ll;
const int N=1e5+5;
const int mod=998244353;
int pri[N];
int b[N];
int cnt;
int op(int x){
for(int i=1;i<=cnt;i++)
if(x%b[i]==0) return pri[b[i]];
}
void init(){
for(int i=2;i<=N-5;i++){
if(pri[i]==-1){
pri[i]=++cnt;
b[cnt]=i;
int j=i;
while(1ll*i*j<=N-5){
pri[i*j]=0;
j++;
}
}
}
}
int main(){
memset(pri,-1,sizeof(pri));
init();
int n;
cin>>n;
for(int i=2;i<=n;i++){
if(pri[i]>0) printf("%d ",pri[i]);
else printf("%d ",op(i));
}
return 0;
}
D. Ehab and the Expected XOR Problem[前缀亦或]
题目链接:https://codeforc.es/contest/1174/problem/D
题意:给一个n和x,构造一个数组.
-
使得每个元素
1<=ai<2^n, -
子段的亦或结果不等于0或x
-
长度要最大.
题解:数组a[]存储前缀亦或和,对于任意一个子段a[l]-a[r],如果a[l]^a[r]不等于0或x,即满足条件.
所以我们从前到后构造,对a[i],标记a[i]和a[i]^x.对于已经标记的数,下次就不使用.直到没有数可用为止.
输出a[i]^a[i-1].
tips:请忽略毒瘤while(1).
#include <bits/stdc++.h>
using namespace std;
const int N=(1<<18)+5;
int a[N],cnt;
map<int,int> mp;
int main(){
int n,x;
cin>>n>>x;
int now=0;
mp[0]=1;
mp[x]=1;
while(1){
int f=0;
for(int i=1;i<(1<<n);i++) if(mp[now^i]==0){
now^=i;
f=1;
break;
}
if(!f) break;
a[++cnt]=now;
mp[now]=1;
mp[now^x]=1;
}
printf("%d
",cnt);
for(int i=1;i<=cnt;i++) printf("%d ",a[i]^a[i-1]);
return 0;
}