比赛地址：https://codeforces.com/contest/1895

A：大意是给出宝箱和钥匙的坐标，可以向前或向后走，花费1秒。抱起宝箱最多可以走k秒。

宝箱在右，x

宝箱在左，考虑x+k>=y，y ； x+k<y，y+(y-(x+k))

code：

void solve()
{
	ll x,y,k;
	cin>>x>>y>>k;
	if(x>=y){
		cout<<x<<endl;
	}else if(x+k>=y){
		cout<<y<<endl;
	}else{
		cout<<y+(y-x-k)<<endl;
	}
}

B：大意是给出2n个数字，凑n个点，求走过的路径最短和点对。

排序，由外到内一次组合得到最优解。

code：

void solve()
{
	int n;
	cin>>n;
	for(int i=1;i<=2*n;i++){
		cin>>a[i];
	}
	sort(a+1,a+2*n+1);
	ll ans = 0;
	if(n%2==0){
		int l =1, r =2*n;
		while(r-l>1){
			ans+=a[l+1]-a[l];
			ans+=a[r]-a[r-1];
			l++,r--;
		}
		cout<<ans<<endl;
		for(int i=1;i<=n;i++){
			cout<<a[i]<<' '<<a[2*n-i+1]<<endl;
		}
	}else{
		int l =1, r =2*n;
		while(r-l>1){
			ans+=a[l+1]-a[l];
			ans+=a[r]-a[r-1];
			l++,r--;
		}
		cout<<ans<<endl;
		for(int i=1;i<=n;i++){
			cout<<a[i]<<' '<<a[2*n-i+1]<<endl;
		}
	}
}

C：大意是给出n个纸票，纸票上有不超过5位的数字，两个纸票（同一个也可以）可以组合。
前半和与后半和相同的是幸运纸票。求数量。

mp[i][j][k][l] 表示，纸票被分为了前i份，i个数的和，后k份，k个数的和。

预处理每个纸票可以产生的可能性，然后暴力位数。
考虑当前纸票位数多，分裂情况。考虑当前纸票位数少，借位情况。
时间复杂度n*50*5.

code：

void solve()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s[i];
		ll sum = 0;
		ll tsum = 0;
		for(auto c:s[i]) sum+=c-'0';
		mp[0][0][s[i].size()][sum]++;
		for(int j=0;j<s[i].size();j++){
			tsum+=s[i][j]-'0';
			mp[j+1][tsum][s[i].size()-(j+1)][sum-tsum]++;
		}
	}
	// cout<<mp[0][0][1][2]<<"!"<<endl;
	ll ans = 0;
	for(int i=1;i<=n;i++){
		ll sum = 0;
		ll zong = 0;
		for(auto c:s[i]) zong+=c-'0';
		
		for(int j=0;j<s[i].size();j++){
			sum+=s[i][j]-'0';
			if((j+1)>s[i].size()/2){
				int l = j+1;
				int r = s[i].size()-(j+1);
				int w = j+1;
				if(sum*2-zong>=0){
					ans+=mp[0][0][w-r][sum*2-zong];
				}
			}
		}
		for(int j=s[i].size()+1;j<=5;j++){
			for(int k=zong;k<=j*9;k++){
				if(k-zong>=0){
					ans+=mp[j-s[i].size()][k-zong][j][k];
				}
			}
		}
	}//1111sum 1  111
	cout<<ans<<endl;
}

D：大意是给n-1个数字，你需要从0-n-1这n个数组合出b[i]^b[i+1] = a[i]。

预处理前缀异或可以得到a[1]^ 其他各个数。
总共我们需要异或n-1次，遍历每一位，记录一下1的数量。看首位是否需要这一位的1.

code：

void solve()
{
	int n;
	cin>>n;
	for(int i=1;i<n;i++){
		cin>>a[i];
	}
	for(int i=2;i<n;i++){
		a[i]^=a[i-1];
	}
	int x = 0;
	for(int i=0;i<20;i++){
		int cnt[2]={},mb[2]={};
		for(int j=0;j<n;j++){
			mb[j>>i&1]++;
		}
		for(int j=1;j<n;j++){
			cnt[a[j]>>i&1]++;
		}
		if(cnt[1]!=mb[1]){
			x|=1<<i;
		}
	}
	cout<<x<<" ";
	for(int i=1;i<n;i++){
		cout<<(a[i]^x)<<' ';
	}
	cout<<endl;
}