【2017ACM-ICPC广西邀请赛】CS Course

【2017ACM-ICPC广西邀请赛】CS Course

【前后缀/位数统计+异或的运算性质】

问题链接:https://vjudge.net/problem/HDU-6186

Solution 1:

Core concept:

1. 对于一串数\(a_1, a_2 … a_n\),要求去掉\(a_p (p \in [1, n])\)后,求剩下全部数的与、或、异或的值,为了方便表述,我们将这里的运算用符号\(\oplus\)表示,则当前问题是求:

\(a_1 \oplus … a_{p – 1} \oplus a_{p + 1}… \oplus a_n = ?\).

显然上式等于:

\((a_1 \oplus … a_{p – 1}) \oplus (a_{p + 1} … \oplus a_n)\)

特殊的,对于\(p = 1 or n\),可通过去掉上式左侧圆括号内容或右侧圆括号内容使得等式成立。因此,我们可以开两个数组:

前缀数组pre(\(pre[i] = a_1 \oplus … \oplus a_{p – 1}\))

后缀数组suf(\(suf[i] = a_{p + 1} \oplus … \oplus a_n\)).

2.对于异或运算,我们也可以采用上边的办法,但是,由于有更好的办法(即利用异或运算性质),我们采用另一种办法。

关键:

b ^ b = 0(^表示异或),即一个数总是其自身的异或逆元。

a ^ b = b ^ a,即交换律。

所以我们将a_1 ^ … ^ a_n放到一个变量中(取名为xorans),则除去\(a_k\)后,答案应是:xorans ^ \(a_p\).

#include <iostream>

using namespace std;

const int LIM = 1e5 + 10;
struct node {
    int av, ov;     // "and value" and "or value"
};

int a[LIM];
node pre[LIM], suf[LIM];

int main(void) {
    int n, q;
    int xorans;
    while (~scanf("%d%d", &n, &q)) {
        xorans = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", a + i);
            xorans ^= a[i];
            pre[i].av = pre[i].ov = suf[i].av = suf[i].ov = a[i];
            if (i != 1) {
                pre[i].av &= pre[i - 1].av;
                pre[i].ov |= pre[i - 1].ov;
            }
        }
        for (int i = n - 1; i >= 1; i--){
            suf[i].av &= suf[i + 1].av;
            suf[i].ov |= suf[i + 1].ov;
        }
        int p;
        while (q--) {
            scanf("%d", &p);
            if (p == 1) printf("%d %d %d\n", suf[2].av, suf[2].ov, xorans ^ a[1]);
            else if (p == n) printf("%d %d %d\n", pre[n - 1].av, pre[n - 1].ov, xorans ^ a[n]);
            else printf("%d %d %d\n", pre[p - 1].av & suf[p + 1].av, pre[p - 1].ov | suf[p + 1].ov, xorans ^ a[p]);

        }
    }
    return 0;
}

 

Solution 2:

统计所有数各二进制位的1的个数,如果去掉a[k]后,某位上1的个数为n – 1,则与运算后该位是1;如果某位上1的个数大于0,则或运算后该位是1。

#include <iostream>
#include <cstring>
using namespace std;

const int LIM = 1e5 + 10;
const int BITS = 32;
int a[LIM];
int cnt[BITS];
int cnttmp[BITS];

int main(void) {
    int n, q;
    int xorans;
    while (~scanf("%d%d", &n, &q)) {
        memset(cnt, 0, sizeof cnt);
        xorans = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", a + i);
            xorans ^= a[i];
            int tmp = a[i];
            for (int i = 0; tmp; i++, tmp >>= 1)
                if (tmp & 1) cnt[i]++;
        }
        int p, andans, orans;
        while (q--) {
            andans = orans = 0;
            scanf("%d", &p);
            memcpy(cnttmp, cnt, sizeof cnt);
            int tmp = a[p];
            // 使用cnttmp数组来存储去掉a_p后,各位的1的个数
            for (int i = 0; tmp; i++, tmp >>= 1) {
                if (tmp & 1) cnttmp[i]--;
            }
            for (int i = BITS - 1; i >= 0; i--, tmp >>= 1) {
                andans <<= 1;
                orans <<= 1;
                if (cnttmp[i] == n - 1) andans |= 1;
                if (cnttmp[i] > 0) orans |= 1;
            }
            printf("%d %d %d\n", andans, orans, xorans ^ a[p]);
        }
    }
    return 0;
}