Codeforces Round #832 (Div. 2)——A、B、C、D

A:贪心

 题意：给定一个长度为n的数组，将所有的数分到两个背包a，b中，求|sum(a)|-|sum(b)|的最大值

 思路：一个背包放正数，一个背包放负数。这样取得的值一定是最大值

代码： 

#include
#define int long long
using namespace std;
const int N=2e5+10;
int a[N];
 
inline void solve(){
	int n;cin>>n;
	int ans1=0,ans2=0;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		if(a[i]<=0) ans1+=a[i];
		else ans2+=a[i];
	}
	cout<<abs(ans2-abs(ans1))<<"\n";
}
 
signed main(){
	int T;cin>>T;
	while(T--) solve();
}

B：构造

题意：给定长度为3n的由n个BAN组成的字符串，求出最少的交换次数使得字符串的任意子串不包含BAN。

这里特别说明一下：这里的子串并不是连续的子串

例如：AANBBNAAN是存在BAN的

思路：把所有的N放在B前面

例如：BANBANBAN ------->NANBANBAB------->NANNABBAB

代码：

#include
#define int long long
using namespace std;
const int N=2e5+10;
 
inline void solve(){
	int n;cin>>n;
	if(n==1) cout<<"1\n1 2\n";
	else{
		cout<<(n+1)/2<<"\n";
	    for(int i=1;i<=(n+1)/2;i++){
		    int x=(i-1)*3+1;
		    int y=3*n-x+1;
		    if(x>y) return;
		    cout<" "<"\n";
		}
	}
}
 
signed main(){
	int T;cin>>T;
	while(T--) solve();
}

C:博弈

题意：给定一个长度为n的数组，Alice和Bob玩博弈游戏。每次每个人选择一个大于1的位置i，先将a[1] = a[1] - 1，然后a[1]与a[i]交换。如果轮到某个人的回合开始时，出现了a[1] = 0 的情况，那么他就输了。请问游戏谁胜谁负。

分析：看样例发现，好像跟奇偶性可以扯上关系，但是交一发直接WA。所以显然是诈骗。那么我们只能手动模拟过程，找规律。

我们发现，如果a[1]是最小数，那么先手肯定输（Bob赢）

为什么呢？

因为每次操作，都会使得a[1]减1（注意：a[1]的值是变化的），那么如果一开始a[1]是最小的数，则Alice操作后，a[1]一定不会是最小的数，然后经过Bob操作，Bob选择最小的数跟a[1]=a[1]-1交换后，此时a[1]又成为了最小数，因为每次操作a[1]都会-1，所以留给先手的a[1]一定是上一轮操作中的最小数-1，每次都这样操作，那么最后留给先手的a[1]一定是等于0的，所以先手必输。

代码： 

#include
#define int long long
using namespace std;
 
inline void solve(){
	int n;cin>>n;
	vector<int>e(n+1);
	for(int i=1;i<=n;i++) cin>>e[i];
	int x=*min_element(e.begin()+1,e.end());
	if(x==e[1]) cout<<"Bob\n";
	else cout<<"Alice\n";
}
 
signed main(){
	int T;cin>>T;
	while(T--) solve();
}

D：前缀和+二分+STL

 此题题解采用的是“每日一棵splay”的题解：https://zhuanlan.zhihu.com/p/580566353

题意：

给定一个长度为n的数组，给定m个独立询问。每个询问包含[l, r]，要求每次在[l, r]范围内选择若干个奇数长度的连续区间使得这段区间内所有值变成区间异或和，求最少操作次数使得[l, r]内所有元素的值变为0.

分析：

异或运算是一种很特殊的运算，也就是不进位加法。

结论1: 如果区间内本身的异或和为不为0，那么答案为-1。

结论2: 如果区间内本身全为0，那么答案为0。

结论3: 如果区间异或和为0且区间长度为奇数，那么答案为1，也就是直接选择整段区间一次完成。

同理，假如区间长度为偶数且异或和为0，如果在区间两端存在任意一个0，那么舍弃一个0之后区间长度变成奇数，那么答案也为1。

最后一种情况，也就是操作数为2的情况。此时的限制条件是：区间长度为偶数，区间异或和为0。那么我们需要找到一个中间值将区间分为两段。对两段进行操作。

预处理

用map存奇数和偶数位置上前缀异或和为x的所有下标。比如对于奇数位置，前缀异或为3的下标有[3, 7, 9]，那么对于一个l的位置，我们可以用lowerbound快速找到第一个距离为奇数位置的区间异或和为0的右端点。查看这个端点是否在[l, r]范围内即可。

代码：

#include
#define int long long
const int N=2e5+10;
using namespace std;
int a[N],s[N],sum[N];
 
inline void solve(){
	int n,m;cin>>n>>m;
	map<int,vector<int>>v1,v2;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s[i]=s[i-1]^a[i];sum[i]=sum[i-1]+a[i];
		if(i&1) v1[s[i]].push_back(i);
		else v2[s[i]].push_back(i);
	}
	while(m--){
		int l,r;cin>>l>>r;
		int len=r-l+1;
		if(s[l-1]^s[r]){//区间l-r的前缀xor如果不为0
			cout<<"-1\n";continue;
		}
		if(sum[r]==sum[l-1]){//区间l-r中每个元素都为0
			cout<<"0\n";continue;
		}
		if(len&1){//长度为奇数
			cout<<"1\n";continue;
		}
		if(a[l]==0||a[r]==0){//区间两端任意存在一个0
			cout<<"1\n";continue;
		}
		if(!((l-1)&1)){
			auto x=lower_bound(v1[s[l-1]].begin(),v1[s[l-1]].end(),l-1);
		    if(x!=v1[s[l-1]].end()&&*x
				cout<<"2\n";continue;
			}
		}
		else{
			auto x=lower_bound(v2[s[l-1]].begin(),v2[s[l-1]].end(),l-1);
			if(x!=v2[s[l-1]].end()&&*x
				cout<<"2\n";continue;
			}
		}
		cout<<"-1\n";
	}
}
 
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	solve();
}