e319: 小王的積木 Again!

2019-09-05

內容

給你一些數字

這些數字中只有一個只出現 1 次,其他數字則出現了 3 次

求這個只出現 1 次的數字

輸入

第一行有一個整數 N(4<=N<4*10^6)

接下來有 N 個整數,每個整數皆在 int 範圍以內

4
2 2 2 1

輸出

只出現 1 次的數字

1

解題思路

d708 的困難版，看不懂邏輯的可以先去看那題的題解。

位元操作，邏輯如下 (註解區的 t0 ~ t3 指的是所有位元的操作情況非整數)

while (readUInt(&t0))
{
    // -- 3 --
    // 當之前的 t2 和現在的 t0 都出現 1 時，將 t1 設為 1，並把剛才進位至 3 的位元清 0 (因為計算過了)
    // t1 為 1 的位元在在下一個 loop 必定會被歸 0
    // (因為 t2 和 t0 為 0，t0 為 0 時這個 loop 就不可能讓 t2 變成 1，t2 在這個 loop 為 0 時，t1 在下個 loop 就不可能為 1)
    t1 = t2 & t0;
    t2 &= ~t1;
    t0 &= ~t1;
    // -- 2 --
    // 當之前的 t1 和現在的 t0 都出現 1 時
    // 將他們 t2 設為 1
    t2 ^= t1 & t0;
    // -- 1 --
    // 之前的 t1 或現在的 t0 出現 1 的位元為 1
    // 之前的 t1 且現在的 t0 出現的則歸 0 (上面已經進位置 t2 了)
    // 都沒有則繼續維持 0
    t1 ^= t0;
}

輸入測資量極大，要做輸入優化，且優化時因記憶體限制 5MB 所以要注意 buffer 大小。

完整程式碼

AC (37ms, 108KB)

#include <stdio.h>
#define BUFSIZ 8192

inline char readChar()
{
    static char buffer[BUFSIZ], * t0 = buffer + BUFSIZ, * end = buffer + BUFSIZ;
    if (t0 == end)
    {
        if (end < buffer + BUFSIZ)
            return EOF;
        end = (buffer + fread(buffer, 1, BUFSIZ, stdin));
        t0 = buffer;
    }
    return *t0++;
}

inline char readUInt(unsigned int* dst)
{
    register char ch;
    while ((ch = readChar()) < '0')
        if (ch == EOF) return 0;
    *dst = ch ^ '0';
    while ((ch = readChar()) >= '0')
        * dst = (*dst << 3) + (*dst << 1) + (ch ^ '0');
    return 1;
}

int main()
{
    unsigned int t0, t1 = 0, t2 = 0, t3 = 0;
    scanf(" %*d");
    while (readUInt(&t0))
    {
        t3 = t2 & t0;
        t2 &= ~t3;
        t0 &= ~t3;
        t2 ^= t1 & t0;
        t1 ^= t0;
    }
    printf("%d", t1);
    return 0;
}