P8453 「SWTR-8」美元巨大 题解

· · 题解

题目简述

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

思路

根据贪心的思想以及位运算的相关知识，对于出现奇数次的 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;
}