自动搬运

查看原文

来自洛谷，原作者为

	Dregen_Yor 那时，我开始使用名叫数学的武器。但是，那种武器往往过于巨大，很多时候不能灵活操控。这种感觉正如我很难操控自己年轻时的青涩，很难控制对他们的思念一样。

搬运于2025-08-24 22:39:12，当前版本为作者最后更新于2022-07-31 17:18:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目简述

• 给定 $n$ 个 $2$ 的幂 $a_1, a_2, \cdots, a_n$，$a_i=2^{b_i}$。

• 在这 $n$ 个数中插入 $x$ 个异或运算符和 $y$ 个或运算符，组成一个表达式。保证 $x + y = n - 1$。求这个表达式的最大值。

不会位运算的请点击这里。

思路

根据贪心的思想以及位运算的相关知识，对于出现奇数次的 $b_i$，我们可以一直加入异或运算符，异或运算符数量不够了再用或运算符，如果是偶数个，可以先一直进行异或操作，在最后一个相等的 $b_i$ 前插入或运算符。

如何保证最大

我们可以使用一个结构体记录每个 $b_i$ 以及它对应的下标 $i$，根据 $b_i$ 从大到小排序，对于相等的 $b_i$ 根据 $i$ 的大小从小到大排序，这样就可以保证最大的值可以加入答案中并保证偶数情况下的或运算符插在最后一个位置上。

具体实现

把 $b_1$ 单独拿出来，排序的时候从第二个开始，因为 $b_1$ 一开始的时候一定会被加入到答案中，使用一个数组记录下每个 $b_i$ 出现的次数，再用一个字符数组记录构造方案。遍历时看做在每个数前面加入运算符。对于出现奇数次的数，直接插入异或运算符即可，异或运算符不足的情况下再补或运算符。对于出现偶数次的情况，只要不是最后一个出现的就插入异或运算符，异或运算符不足的情况下再补或运算符。如果是最后一个出现的，就插入或运算符，如果或运算符不足就补或运算符，同时把这个数从答案中移除即可。

更多细节见注释。

代码

#include <bits/stdc++.h>
using namespace std;
int t, n, x, y, s[65537], sum[65537];//s记录出现次数，sum记录答案
char ans[65537];//记录构造方案

struct node {
	int pos, add;//pos对应bi，add对应下标
} b[50000];

bool cmp(node a, node b) {
	if (a.pos == b.pos) {
		return a.add < b.add;//根据下标从小到大排序
	}
	return a.pos > b.pos;//根据bi从大到小排序

}

int main() {
	scanf("%d", &t);
	scanf("%d", &t);
	while (t--) {
		int maxn = 0;//记录最大位置
		memset(s, 0, sizeof(s));
		memset(sum, 0, sizeof(sum));
		scanf("%d%d%d", &n, &x, &y);
		for (int i = 1; i <= n; i++) {
			scanf("%d", &b[i].pos);
			maxn = max(maxn, b[i].pos);
			s[b[i].pos]++;
			b[i].add = i;
		}
		sum[b[1].pos] = 1;
		if (n != 1) {
			sort(b + 2, b + 1 + n, cmp);
		}
		for (int i = 2; i <= n; i++) {
			if (s[b[i].pos] & 1) {
				if (x) {
					ans[b[i].add] = '^';
					x--;
					sum[b[i].pos] = 1;
				} else {
					ans[b[i].add] = '|';
					y--;
					sum[b[i].pos] = 1;
				}
			} else {
				if (b[i + 1].pos != b[i].pos) {//最后一个如果y>0插入|，否则插入^
					if (y) {
						ans[b[i].add] = '|';
						y--;
						sum[b[i].pos] = 1;
					} else {
						ans[b[i].add] = '^';
						x--;
						sum[b[i].pos] = 0;
					}
				} else {//不是最后一个就插入^
					if (x) {
						ans[b[i].add] = '^';
						x--;
					} else {
						ans[b[i].add] = '|';
						y--;
						sum[b[i].pos] = 1;
					}
				}
			}
		}

		while (sum[maxn] == 0 && maxn >= 0) {
			maxn--;
		}//清除前导零
		for (int i = maxn; i >= 0; i--) {
			printf("%d", sum[i]);
		}
		if (maxn == -1) {
			printf("0");
		}
		putchar('\n');
		for (int i = 2; i <= n; i++) {
			putchar(ans[i]);//输出方案
		}
		putchar('\n');
	}
	return 0;
}