P8453 「SWTR-8」美元巨大 （位运算+贪心）

P8453 「SWTR-8」美元巨大

位运算+贪心

因为 \(a_i=2^{b_i}\)，所以每一个符号只会影响一个二进制位，也就是二进制位是独立的。

考虑经典的按位考虑，从高位到低位，我们希望高位尽可能取到 \(1\) 并且留下更好的符号让低位能更大。考虑贪心，显然 | 比 ^ 的价值更大，所以在答案不会变小的情况下尽量用 ^。

如果 \(cnt_{b_i}\) 为奇数，那么全部填 ^ 就可以取到 \(1\)，不够就补 |。

如果 \(cnt_{b_i}\) 为偶数，那么至少需要一个 | 放在最后面的 \(b_i\) 前面才能取到 \(1\)，其他都用 ^，不够只能补 |。如果没有 |，那就取不到 \(1\) 了。

注意 \(a_1\) 前面不用填符号，需要判断一下。要预处理 \(nxt_i\) 表示前一个 \(b_i\) 的位置在哪里。

复杂度 \(O(T\max(a_i))\)。

#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define mk std::make_pair
#define fi first
#define se second
#define pb push_back

using i64 = long long;
using ull = unsigned long long;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 75010;
int s, t, n, x, y;
int cnt[N], nxt[N], lst[N], b[N], f[N];
void solve() {
	std::cin >> n >> x >> y;

	int mx = 0, fi;
	std::cin >> fi;
	cnt[fi]++;
	lst[fi] = 1;
	mx = std::max(mx, fi);
	for (int i = 2; i <= n; i++) {
		int a;
		std::cin >> a;
		cnt[a]++;
		mx = std::max(mx, a);
		nxt[i] = lst[a];
		lst[a] = i;
	}

	for (int i = mx; i >= 0; i--) {
		int need;
		if(i == fi) need = cnt[i] - 1;
		else need = cnt[i];
		if(!need) {
			if(i == fi) f[i] = 1;
			continue;
		}
		if(cnt[i] & 1) {
			if(x >= need) {
				for (int j = lst[i]; j; j = nxt[j]) {
					b[j] = 0;
				} 
				x -= need;
				f[i] = 1;
			} else {
				int sum = 0;
				for (int j = lst[i]; j; j = nxt[j]) {
					if(x >= need - sum) {
						b[j] = 0;
					} else if(j != 1) b[j] = 1, sum++;
				}
				x = 0, y -= sum;
				f[i] = 1;
			}
		} else {
			if(y) {
				if(x >= need - 1) {
					b[lst[i]] = 1;
					for (int j = lst[nxt[i]]; j; j = nxt[j]) {
						b[j] = 0;
					} 
					x -= need - 1, y--;
					f[i] = 1;
				} else {
					int sum = 0;
					for (int j = lst[i]; j; j = nxt[j]) {
						if(x >= need - sum) {
							b[j] = 0;
						} else if(j != 1) b[j] = 1, sum++;
					}
					x = 0, y -= sum;
					f[i] = 1;
				}
			} else {
				for (int j = lst[i]; j; j = nxt[j]) {
					b[j] = 0;
				}
			}
		}
	}
	int lim = 0;
	for(int i = mx; i >= 0; i--) {
		if(!lim && f[i]) {
			std::cout << f[i];
			lim = 1;
		} else if(lim) std::cout << f[i];
	}
	if(!lim) std::cout << "0";
	std::cout << "\n";

	for(int i = 2; i <= n; i++) {
		std::cout << (b[i] ? "|" : "^");
	}
	std::cout << "\n";

	for(int i = 0; i <= mx; i++) f[i] = cnt[i] = lst[i] = 0;
	for(int i = 1; i <= n; i++) b[i] = nxt[i] = 0;
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::cin >> s >> t;

	while(t--) solve();

	return 0;
}