d708: 小王的積木

2019-09-05

內容

自從小涵去商店買了那麼多的積木，小王也去買了一大堆。
不過小王比較喜歡數學，所以他買的積木上寫的只有數字；因為他認為偶數比較吉利，於是他買的積木是全是偶數快的。
聽說小涵少了一個積木，他便整理了一下他的，可是他發現他也少了一塊積木…（很無語吧…）
上次他見你已經幫小涵找到了積木，於是就請你來幫他找找，而且他還告訴你：“我的積木比小涵的好找很多。”
半信半疑的你決定幫幫他。

輸入

只有一筆測資。測資末尾會有多餘信息，忽略就好。//感謝 asas 提醒。2015/8/6

輸入數據的第一行，是小王告訴你他的積木個數 N（N 一定是一個正偶數，而且 2<=N<=1000000，你看他的積木可沒有小涵的多）。
接下來每行有（N-1）個數字，表示小王每個積木上的數字（可以用 longint 存儲）。

8
1
2
3
2
3
4
4

輸出

對於每組測資，輸出小王缺少的那塊積木的數字。

1

解題思路

e319 的簡易版。

利用兩相同數經 XOR 運算後因為偶一為零會變成 0 的特性，將一個整數 0 和每個數字都 XOR 一遍，最後的值就會是只出現一次的那個 (出現偶數次的都互相抵銷掉了)

本題不用做輸入優化也能輕鬆過。

完整程式碼

AC (10ms, 1.1MB)

#include <stdio.h>
#define BUFSIZ 1048576

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 n, ans = 0, tmp;
    scanf(" %d", &n);
    while (--n)
    {
        readUInt(&tmp);
        ans ^= tmp;
    }
    printf("%d", ans);
    return 0;
}