2022CCPC威海J. Eat, Sleep, Repeat（博弈/思维）

题目大意是给定长度为n的数组a，两个人轮流从中选一个正数将其减1。且有k个限制形如\(limit_{x_i}= y_i\)，即\(x_i\)在数组中最多出现\(y_i\)次。判负的情况为：

1. 数组全为0

2. 操作后的数组不满足某个限制。

问谁会赢。

首先可以手玩一下，设数组为 \(a = [3, 4]\)，\(limit_2=1\)，先手选3，数组变为\([2, 4]\)，此时仍然满足限制，此时第一种情况是后手选4，数组变成\([2, 3]\)，这时限制永远也不会起作用了；第二种情况是后手选2，数组变为\([1, 4]\)，原本已经卡紧的限制又放开了。这样可以观察出，如果一条限制的\(y_i\)不为0，那么不会有人傻到主动去让自己输掉，同时也没法给别人挖坑，除非有一种情况：

1
5 2
5 5 5 5 5
2 0
3 2

因为不能把数减为2，所以最多也就只能减到3，这时\(limit_3=2\)这个限制就没法绕过去了。所以可以把限制按\(y_i=0\)分段，每段中让属于这一段的数尽可能小（操作数是固定的），先把一开始连续若干个限制填满，剩下的数再尽可能小。这样算出总的操作次数，为奇则先手胜。可以额外设置\(limit_{-1}=0\)，避免冗长的特判。

#include <bits/stdc++.h>
#define int long long
#define de cout<<"fuck"<<endl;
using namespace std;
int n, k, a[100005], x[100005], y[100005], sum[100005];
void solve() {
	cin >> n >> k;
	int mx = 0;
	map<int, int> mp;//存放限制
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		mx = max(mx, a[i]);
	}
	sort(a + 1, a + n + 1);
	for(int i = 1; i <= n; i++) {
		sum[i] = sum[i - 1] + a[i];
	}
	vector<int> v, r;//v：存放y值为0的限制x r：存放所有的限制x
	v.push_back(-1);
	r.push_back(-1);
	for(int i = 1; i <= k; i++) {
		cin >> x[i] >> y[i];
		if(y[i] == 0) {
			v.push_back(x[i]);
		}
		mp[x[i]] = y[i];
		r.push_back(x[i]);
	}
	if(k == 0) {
		if(sum[n] & 1) puts("Pico");
		else puts("FuuFuu");
		return;
	}
	v.push_back(mx + 1);
	r.push_back(mx + 1);
	sort(v.begin(), v.end());
	sort(r.begin(), r.end());
	mp[-1] = 0;
	mp[mx + 1] = 0;
	int tot = 0;
	for(int i = 0; i < v.size() - 1; i++) {
		int L = v[i], R = v[i + 1] - 1;
		//找[L, R]这段区间的限制以及所有的数组的数
		int pl1 = lower_bound(r.begin(), r.end(), L) - r.begin();
		int pr1 = lower_bound(r.begin(), r.end(), R) - r.begin();//此时的r[pr1]对应的是下一个区间的起点 因此要减一
		pr1--;
		int pl2 = lower_bound(a + 1, a + n + 1, L) - a;
		int pr2 = upper_bound(a + 1, a + n + 1, R) - a - 1;
		if(!(pl2 <= pr2 && pl2 >= 1 && pl2 <= n && pr2 >= 1 && pr2 <= n)) {
			continue;//这段区间没有数
		}
		if(pl1 == pr1 || r[pl1] + 1 < r[pl1 + 1]) {
			//这段区间起作用的限制只有一开始的limit r[pl1] = 0 直接把所有数操作为 r[pl1]+1即可
			tot += (sum[pr2] - sum[pl2 - 1] - (pr2 - pl2 + 1) * (v[i] + 1));
		} else {
		 	//1
			//5 2
			//5 5 5 5 5
			//2 0
			//3 2
			//4 1
			int pos = pl1;
			int lst_consec;
			pos++;//r[pos]这个限制的y为0 跳过
			for(int j = pl2; j <= pr2; j++) {
				//a[j]是当前数
				if(pos > pr1 || (r[pos] - r[pos - 1]) > 1) {//从一开始的连续的限制已经都填满了 剩下的数都减到r[lst_consec]+1即可
					tot += (a[j] - (r[lst_consec] + 1));
					continue;
				}
				lst_consec = pos;
				if(mp[r[pos]] != 0) {//如果有空位就填
					mp[r[pos]]--;
					tot += (a[j] - r[pos]);
				}
				if(mp[r[pos]] == 0) {
					pos++;
				}
			}

		}
	}
	if(tot & 1) puts("Pico");
	else puts("FuuFuu");
}
signed main() {
	int T = 1;
	cin >> T;
	while(T--) {
		solve();
	}
	return 0;
}

原文地址：http://www.cnblogs.com/lipoicyclic/p/16876635.html