题解：CF2014H Robin Hood Archery

CF题目传送门

题目大意

Robin 和 Sheriff 比赛，Robin 先手，每次比赛他们选择

l - r

的区间内的目标进行射击。射击编号为

i

的目标会加

a_i

分，然后这个目标被摧毁。两人初始得分均为 0。若 Sheriff 能获胜或平局输出 YES，否则输出 NO。

题目思路

由于 Robin 先手，为了获胜，当轮到 Robin 时他一定会选择当前剩余目标中最大分值的目标。所以无论如何 Sheriff 一定不会获胜，最多只能平局。

如果能平局，说明

l - r

这个区间内所有出现过的数的出现次数均为偶数（这样两人才能平均分，达到平局的效果）。此时用莫队维护区间数值出现次数。

剩下的便是板子了。

不会的去这里。

Code

附上完整代码。

CPP

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
struct node{
	int l,r,id;
}q[N];
int a[N];
int ans[N],cnt[N];
int n,m,sq;
bool cmp(node x,node y){
	if(x.l / sq != y.l / sq) return x.l / sq < y.l / sq;
	else return x.r / sq < y.r / sq; 
}
int cur = 1;
void add(int p){
	cnt[a[p]] ++;
	if(cnt[a[p]] & 1) cur ++;
	else cur --;
}
void del(int p){
	cnt[a[p]] --;
	if(cnt[a[p]] & 1) cur ++;
	else cur --;
}
void solve(){
	cur = 1;
	cin >> n >> m;
	sq = min((int)sqrt(n) + 1,n);
	for(int i = 0;i < n;i ++){
		cin >> a[i];
		cnt[a[i]] = 0;
	} 
	for(int i = 0;i < m;i ++){
		cin >> q[i].l >> q[i].r;
		q[i].l --;
		q[i].r --;
		q[i].id = i;
		ans[i] = 0;
	}
	sort(q,q + m,cmp);
	cnt[a[0]] ++;
	int L = 0,R = 0;
	for(int i = 0;i < m;i ++){
		while(R < q[i].r) add(++ R);
		while(L > q[i].l) add(-- L);
		while(L < q[i].l) del(L ++);
		while(R > q[i].r) del(R --);	
		ans[q[i].id] = cur;
	}
	for(int i = 0;i < m;i ++){
		if(ans[i]) cout << "NO\n";
		else cout << "YES\n";
	}
}
int main(){
	int T;
	cin >> T;
	while(T --) solve();
	return 0;
}

题解：CF2014H Robin Hood Archery

文章操作

CF题目传送门

题目大意

题目思路

Code

相关推荐

评论

题解：CF2014H Robin Hood Archery