首页 题解 CF

# Educational Codeforces Round 157 (Rated for Div. 2)

# A Treasure Chest

连签到题都不怎么算

如果箱子是在钥匙的右边，那么答案就是钥匙的位置，走的过程中就得到了要是，没有任何力气的花费。

如果箱子是在钥匙的左边，那么答案就是先搬箱子，直到力气耗尽，然后继续走到钥匙，然后再走回来。

直接看代码吧

Code
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        int a,b,c;
        cin>>a>>b>>c;// 箱子位置，钥匙位置，力气
        if(a>=b){
            cout<<a<<endl;
        }else{
            cout<<a+min(b-a,c)+2*(b-(a+min(b-a,c)))<<endl;
        }
    }
}

# B Points and Minimum Distance

这个题目的距离是曼哈顿距离，那么总的 xx 位移就是 xmax−xminx_{max} - x_{min} 那么 yy 同理。

任何类型的最小坐标都应小于或等于至少 n−1n-1 个元素。同样，最大坐标应大于或等于至少 n−1n-1 个元素。因此，第二个最小坐标 (不是 a1a_1 的最小坐标) 最多为 an+1a_{n+1} 第二个最大坐标至少为 ana_n, 路径长度至少为 a2n−a1+an−an+1a_{2n} - a_1 + a_n - a_{n+1} , 要达到这个界限是可能的：把 aa 中的前 nn 个值当作 xx 坐标，把后 nn 个值当作 yy 坐标。

所以这道题目贪心就可以做完了。

Code
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <iomanip>
using namespace std;
const int MAXN=1e3+10;
int a[MAXN];
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=2*n;i++){
            cin>>a[i];
        }
        sort(a+1,a+2*n+1);
        int ans1=a[2*n]-a[1]+a[n]-a[n+1];
        cout<<ans1<<endl;
        for(int i=1;i<=n;i++){
            cout<<a[i]<<" "<<a[i+n]<<endl;
        }
    }
}

# C Torn Lucky Ticket

首先枚举第一部分的长度，因为字符串 ii 的长度是大于等于第一部分长度的，所以 suml−sumr=sumjsum_l - sum_r = sum_j ，那这样就可以设一个二维数组 sum[len][s]sum[len][s] 为 所需另一部分的彩票长为 ll ，其中另一部分数字和为 ss ，因为可能出现 ii 接在 jj 后或者是 jj 接在 ii 后面。

Code
p
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<queue>
#include<set>
#include<iomanip>
#define int long long
using namespace std;
const int MAXN=3e6+10;
string str[MAXN];
int sum[15],need[15][MAXN];
signed main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>str[i];
		int len=str[i].length();
		for(int j=1;j<=len;j++){
			sum[j]=sum[j-1]+((str[i][j-1])-'0');
//			cout<<str[i][j-1]<<endl;
		}
		for(int j=len/2+1;j<=len;j++){
			if((sum[j]-(sum[len]-sum[j]))<0){
				continue;
			}
			need[2*j-len][sum[j]-(sum[len]-sum[j])]++;
			// cout<<2*j-len<<" "<<sum[j]-(sum[len]-sum[j])<<endl;
		}
		for(int j=1;j<=len/2;j++){
			if(((sum[len]-sum[j])-sum[j])<0){
				continue;
			}
			need[len-2*j][(sum[len]-sum[j])-sum[j]]++;
			// cout<<len-2*j<<" "<<(sum[len]-sum[j])-sum[j]<<endl;
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		int summ=0;
		for(int j=0;j<str[i].length();j++){
			summ+=str[i][j]-'0';
		}
		ans+=need[str[i].length()][summ];
	}
	cout<<ans;
}

# D XOR Construction

根据题意你可以列出来下面的式子。

b1⊕b2=a1b2⊕b2=a2⋯bj⊕bj+1=aj然后左右异或，就得出了b1⊕bj+1=⊕i−1jai即bj+1=⊕i−1jai⊕b1b_1 \oplus b_2 = a_1 \\ b_2 \oplus b_2 = a_2 \\ \cdots b_j \oplus b_{j+1} = a_j \\ \text{然后左右异或，就得出了} b_1 \oplus b_{j+1} = \oplus_{i-1}^{j}a_i \\ \text{即} b_{j+1} = \oplus_{i-1}^{j}a_i \oplus b_1

接下来拆位就可以啦，要是某个位置上 1 的数量比 0 的数量要多，那么这位就要异或上，这样是最优的。

Code
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <iomanip>
using namespace std;
const int MAXN=1e6+10;
int a[MAXN];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<n;i++){
        cin>>a[i];
        a[i]^=a[i-1];
    }
    a[0]=0;
    int ans=0;
    for(int i=0;i<31;i++){
        int sum1=0,sum2=0;
        for(int j=0;j<n;j++){
            if(a[j]>>i&1){
                sum1++;
            }else{
                sum2++;
            }
        }
        if(sum1>sum2){
            ans|=1<<i;
        }
    }
    for(int i=0;i<n;i++){
        a[i]^=ans;
        cout<<a[i]<<" ";
    }
}