比赛传送门

A

Pro

传送门

Sol

考虑将前后两部分差距最大化，显然前一部分放得是前$n$小的，后一部分放的是前$n$大的，于是排序即可。

#include <bits/stdc++.h>
#define MAXN 2005
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9'){
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}
int a[MAXN];
int main(){
	int n=read();
	for (register int i=1;i<=n*2;++i){
		a[i]=read();
	}
	sort(a+1,a+1+n*2);
	int sum1=0,sum2=0;
	for (register int i=1;i<=n;++i){
		sum1+=a[i];
	}
	for (register int i=n+1;i<=n*2;++i){
		sum2+=a[i];
	}
	if (sum1!=sum2) {
		for (register int i=1;i<=2*n;++i){
			printf("%d ",a[i]);
		}
	}
	else {
		puts("-1");
	}
}

B

Pro

传送门

Sol

考虑一个数$a_i$要和$a_j$交换，如果他们两个奇偶性不同，那么直接交换即可。
如果他们两个奇偶性相同，那么假设存在一个和他们俩奇偶性不同的$a_k$，$swap(a_i,a_k),swap(a_k,a_j)$即可。

这样我们在不影响整个序列其他数的情况下交换了两个数。

再考虑选择排序，只要能交换序列中任意两个数，就可以将序列变得有序，于是这样是可以使序列从小到大排序的。

什么时候不行？序列里面只有一种奇偶性，此时输出原序列。

#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9'){
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}
int a[MAXN];
int main(){
	int n=read();
	bool flag1=true,flag2=true;
	for (register int i=1;i<=n;++i){
		a[i]=read();
		if (!(a[i]&1)) flag1=false;
		else flag2=false;
	}
	if ((!flag1)&&(!flag2)) sort(a+1,a+1+n);//两种奇偶性都有
	for (register int i=1;i<=n;++i){
		printf("%d ",a[i]);
	}
}

C

Pro

传送门

Sol

考虑一个诡异的想法，题目要求$gcd(i,j)==1$则$a_i != a_j$，不妨这么想$gcd(i,j) != 1$，我们都让$a_i,a_j$相等。
这样的话，我们只要把$2,3,5,7,11...$的倍数分别设成相同的数即可。

#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9'){
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}
int prime[MAXN],stk[MAXN],ans[MAXN],top;
int main(){
	int n=read();
	prime[0]=prime[1]=true;
	prime[2]=false;
	for (register int i=2;i<=n;++i){
		if (!prime[i]){
			stk[++top]=i;
			for (register int j=i*2;j<=n;j+=i){
				prime[j]=true;
			}
		}
	}
	int num=0;
	for (register int i=top;i>=1;--i){
		int p=stk[i];
		num++;
		for (register int j=p;j<=n;j+=p){
			if (!ans[j]) ans[j]=num;
		}
	}
	for (register int i=2;i<=n;++i){
		printf("%d ",ans[i]);
	}
}

D

Pro

传送门

Sol

首先，看到连续的异或和就要想到把他们转化为前缀和的异或，记$sum[i]=a[1] \oplus a[2] \oplus ... \oplus a[i]$，那么$a[l] \oplus ... \oplus a[r]=sum[r] \oplus a[l-1]$

转化为不存在$sum[i]=sum[j]$或者$sum[i]=x \oplus sum[j]$

这该怎么搞？

有一个很玄学的贪心，考虑记录$use[]$数组，代表$sum[i]$有没有出现，依次扫过去，如果$i$没有用，那么加入$i$，并且标记$i\oplus x$，考虑正确性，因为$a\oplus x==b \oplus x$推出$a==b$，那么肯定不会把$use[i\oplus x]$弄重复，而且$i\oplus x$一定大于$i$，如果小于的话，在$i\oplus x$的地方$i \oplus x \oplus x = i$已经被标记过了，矛盾。

use[0]=use[x]=1;
for (register int i=0;i<(1<<n);++i){
	if (!use[i]) use[i^x]=true,sum[++top]=i;
}

但是这样只能证明是合理的解，但是最优性不知道怎么证。

就当一个结论来记算了。

#include <bits/stdc++.h>
#define MAXN (1<<18)+5
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
int sum[MAXN],use[MAXN],top;
int main(){
	int n=read(),x=read();
	use[0]=use[x]=1;
	for (register int i=0;i<(1<<n);++i){
		if (!use[i]) use[i^x]=true,sum[++top]=i;
	}
	printf("%d\n",top);
	for (register int i=1;i<=top;++i){
		printf("%d ",sum[i]^sum[i-1]);
	}
}