难度预估：黄，蓝，紫，紫。

A

题意：给你一堆数，选出一部分使其"中位数和众数的差的绝对值最大。这里中位数指从小到大排序后第 $\left \lfloor \frac{m}{2} \right \rfloor$ 个数。

若仅有一种或两种数，无论如何都不能使这中位数和众数不相等，答案为 $0$。

若有至少三种数，考虑怎么选数：

1.保留最小数，次大数，最大数各一个。答案为次大数减去最小数。

2.若有至少两个最大数，保留一个最小数，一个次小数，两个最大数。答案为最大数减去次小数。

无论如何都不能使答案为最大数减去最小数。所以以上两种情况取 $\max$ 即可。

时间复杂度 $O(n\log n)$ 或 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,a[N];
signed main(){
	freopen("cake.in","r",stdin);
	freopen("cake.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
	map<int,int> s;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s[a[i]]++;
	}
	int m=s.size();
	if(m<=2){
		cout<<"0\n";
		return 0;
	}
	int ans=0;
	ans=max(ans,(*prev(prev(s.end()))).first-(*s.begin()).first);
	if((*prev(s.end())).second>=2) ans=max(ans,(*prev(s.end())).first-(*next(s.begin())).first);
	cout<<ans<<"\n";
}

B

看到 $n\le 500$ 和我们要求的东西可以大概知道这是个 dp。

考虑如何处理交换操作。发现把一个数与空位置交换是不优的，所以交换两个位置后，这两个位置应该分别应用单点操作和区间操作，考虑在应用单点操作时计算其贡献。考虑在状态中记录一维 $k$ 表示当前有多少个数可以换入/换出，后者用负数表示。

再考虑区间操作的影响。如果决定执行区间操作，对于区间内的数，可以不管，也可以执行单点操作并外面换一个进来。考虑再使用一维 $s$ 表示从当前点开始还有多少位在区间操作的生效范围内。

综上，使用 $f_{i,k,s}$ 表示，前 $i$ 个数，换入 $k$ 个数，从当前位置起有 $s$ 个数在区间操作影响范围内。转移：

单点操作：

$$f_{i,k,0}+a_i\to f_{i+1,k,0}$$ $$f_{i,k,0}\to f_{i+1,k-1,0}$$

在区间操作范围内（$s>0$）：

$$f_{i,k,s}\to f_{i+1,k,s-1}$$ $$f_{i,k,s}+a_i+C\to f_{i+1,k+1,s-1}$$

执行区间操作（$len$ 表示区间操作的区间长度）：

$$f_{i,k,0}+X\to f_{i,k,len}$$

使用滚动数组。时间复杂度 $O(n^3)$。

#include<bits/stdc++.h>
using namespace std;
const int N=505;
int n,len,X,C,a[N];
int f[N*2][N],g[N*2][N];
void upd(int &x,int y){
	x=min(x,y);
}
signed main(){
	freopen("apple.in","r",stdin);
	freopen("apple.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>len>>X>>C;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	memset(f,0x3f,sizeof(f));
	memset(g,0x3f,sizeof(g));
	f[n][0]=0;
	for(int i=0;i<n;i++){
		for(int k=0;k<=2*n;k++){
			upd(f[k][len],f[k][0]+X);
		}
		for(int k=0;k<=2*n;k++){
			upd(g[k][0],f[k][0]+a[i+1]);
			if(k>0) upd(g[k-1][0],f[k][0]);
		}
		for(int k=0;k<=2*n;k++){
			for(int s=1;s<=len;s++){
				upd(g[k][s-1],f[k][s]);
				upd(g[k+1][s-1],f[k][s]+a[i+1]+C);
			}
		}
		memcpy(f,g,sizeof(f));
		memset(g,0x3f,sizeof(g));
	}
	int ans=1e9;
	for(int s=0;s<=len;s++){
		ans=min(ans,f[n][s]);
	}
	cout<<ans<<"\n";
}

C

记每个点连的所有边的异或和为 $a_i$。对一条路径异或 $x$，只会使两个端点的 $a$ 值异或 $x$，其余 $a$ 值不变。最终我们要使所有 $a$ 值为 $0$。所以问题转化为，给定数组 $a$，每次选两个数分别异或 $x$，最小化将 $a$ 全部变为 $0$ 的操作次数。

如果 $a$ 中存在相同的数，那么直接对它们操作一次令这两个数变为 $0$ 肯定是最优的。所以令 $a$ 中不存在相同的数。再转化一下问题的形式：给定若干个 $[1,31]$ 中不同的数，分成若干个集合使每个集合的异或和为 $0$，最大化集合数。

预处理出仅存在 $[1,15]$ 中的数时的答案。令 $[16,31]$（即最高位为 $1$ 的数）必须先两两配对把最高位的 $1$ 消除。共有 $\frac{16!}{(2!)^8\times 8!} =2027025$ 中配对方式。暴搜所有配对方式，配对并异或后仅剩 $[1,15]$ 中的数，调用预处理的值即可。

暴搜需要剪枝，不然可能过不去。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=32,C=1<<16;
int f[C],vis[C];
int n,val[N],cnt[M],res;
int stk[M],top;
bool use[M];
void cl(){
	memset(use,0,sizeof(use));
	memset(stk,0,sizeof(stk));
	top=0;
	memset(cnt,0,sizeof(cnt));
	res=0;
	fill(val,val+n+5,0);
}
void dfs(int u){
	if(vis[u]) return;
	vis[u]=1;
	for(int i=15;i>=1;i--){
		for(int j=i-1;j>=1;j--){
			if(((u>>i)&1)&&((u>>j)&1)){
				int v=u^(1<<i)^(1<<j)^(1<<(i^j));
				int w=1;
				if(!((v>>(i^j))&1)) w=2;
				dfs(v);
				f[u]=min(f[u],f[v]+w);
			}
		}
	}
}
void init(){
	memset(f,0x3f,sizeof(f));
	f[0]=0;
	for(int i=2;i<C;i+=2){
		dfs(i);
	}
}
void dfs0(int i,int prs,int cnt,int las){
	int min_cost=cnt+(__builtin_popcount(prs)*2+las)/3;
	if(min_cost>=res) return;
	if(i==top+1){
		res=min(res,f[prs]+cnt);
		return;
	}
	if(use[i]){
		dfs0(i+1,prs,cnt,las);
		return;
	}
	use[i]=1;
	for(int j=i+1;j<=top;j++){
		if(use[j]) continue;
		use[j]=1;
		int w=0;
		if((prs>>(stk[i]^stk[j]))&1) w=1;
		dfs0(i+1,prs^(1<<(stk[i]^stk[j])),cnt+w,las-1);
		use[j]=0;
	}
	use[i]=0;
}
void sol(){
	cin>>n;
	for(int i=1;i<n;i++){
		int x,y,w;
		cin>>x>>y>>w;
		val[x]^=w;
		val[y]^=w;
	}
	for(int i=1;i<=n;i++){
		cnt[val[i]]++;
	}
	int ans=0;
	for(int i=1;i<32;i++){
		ans+=cnt[i]/2;
		cnt[i]=cnt[i]%2;
	}
	int w=0;
	for(int i=1;i<16;i++){
		if(cnt[i]){
			w|=(1<<i);
		}
	}
	for(int i=16;i<32;i++){
		if(cnt[i]){
			stk[++top]=i;
		}
	}
	res=1e9;
	dfs0(1,w,0,top/2);
	cout<<(ans+top/2+res)<<"\n";
}
signed main(){
	freopen("snow.in","r",stdin);
	freopen("snow.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	init();
	int ct;
	cin>>ct;
	while(ct--){
		sol();
		cl();
	}
}

D

发现我们需要根据 $[0,n-1]$ 中的值，将 $n$ 位取反，然后复原其余部分。

发现，除非我们在操作 $n$ 后再进行跟 $n$ 的取值有关的操作（我们应该也没有这样做的动机，因为这样除了污染一个点以外没有任何好处），所有操作都可以在不改变 $n$ 的值的情况下复原（倒序执行相同的操作就是复原了）。所以我们先不考虑复原的问题，只考虑如何恰好在 $[0,n-1]$ 中的值均为 $1$ 时反转 $n$ 的值。

观察样例得到：记 $f(S,p)$ 表示仅在 $S$ 为 $1$ 时对 $p$ 取反的操作序列。记 $x$ 为 $S$ 中的一个数，$S'=S\setminus \{x\}$。$f(S,p)$ 可以表示为：

$$\operatorname{opt}(x,k,p),f(S',p),\operatorname{opt}(x,k,p)$$

其中 $\operatorname{opt}$ 表示操作，$k$ 表示辅助位置。考虑到辅助位置可能不充足，如果需要还原辅助位置，再执行一次 $f(S',p)$ 即可（甚至不需要倒着执行，因为除 $p$ 外的位置都没变，正着执行效果相同）。

考虑如何解决问题。因为辅助位置不足，而执行 $f$ 的递归需要一定数量的辅助位置，所以将原数组分成两半，记为 $L,R$，使用类似的思想进行操作：第一步执行 $f(R\cup \{m-1\},n)$ 并将 $L$ 作为其辅助位（需要还原）。第二步执行 $f(L,m-1)$ 并将 $R$ 作为其辅助位（同样需要还原）。第三步重复第一步操作，第四步重复第二步操作用于还原。

时间复杂度 $O(n)$，执行次数 $8n-eps$。

SPJ 疑似是坏的，下发的 checker 好像也是坏的，所以代码正确性可能无法验证，但是做法是对的。

#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> ans;
int n,m,q,cs;
void opt(int x,int y=-1,int z=-1){
	int cnt=1+(y!=-1)+(z!=-1);
	vector<int> res={cnt,x};
	if(y!=-1) res.push_back(y);
	if(z!=-1) res.push_back(z);
	ans.push_back(res);
}
void sol(vector<int> a,vector<int> b,int goal,bool ret){
	if((int)a.size()==0) return opt(goal);
	if((int)a.size()==1) return opt(a[0],goal);
	if((int)a.size()==2) return opt(a[0],a[1],goal);
	int x=a.back(),y=b.back();
	a.pop_back(),b.pop_back();
	opt(x,y,goal);
	sol(a,b,y,0);
	opt(x,y,goal);
	if(ret) sol(a,b,y,0);
}
auto get_vec(int l,int r){
	vector<int> res;
	for(int i=l;i<=r;i++){
		res.push_back(i);
	}
	return res;
}
signed main(){
	freopen("signal.in","r",stdin);
	freopen("signal.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m>>q>>cs;
	int l=0,r=n-1,mid=(l+r)/2;
	auto L=get_vec(l,mid);
	auto R=get_vec(mid+1,r);
	auto w=R;
	w.push_back(m-1);
	for(int i=0;i<=1;i++){
		sol(w,L,n,1);
		sol(L,R,m-1,1);
	}
	cout<<(int)ans.size()<<"\n";
	for(auto vec:ans){
		for(int i:vec){
			cout<<i<<" ";
		}
		cout<<"\n";
	}
}