校OJ P1219 -- zyf的童年-CSDN博客

本文链接：https://blog.csdn.net/Elvis_code_t/article/details/79726060

最初将OJ题目P1219视为简单问题，尝试用数组解决导致TLE。了解位运算后，发现异或操作能有效解决此题。当数字出现次数为奇数时，通过不断异或，最终结果为该数字。例如，27, 23, 27经过异或运算，可得到奇数次出现的数字。" 52037096,5673585,C语言socket编程基础教程,"['c语言', 'socket']

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

去年十月份刚看到这题的时候认为这是一道水题，不就是找出出现为奇数次的那个数吗，开个100000的数组不就好了，结果TLE了，一度怀疑是OJ的问题，后来接触到位运算才知道这题的正确做法，先贴上第一次做时丑陋的代码吧

#include <stdio.h>
#include <string.h>
int main()
{
    int a[100001]={0};
    int str[100001];
    int x,i,j,n;
    scanf("%d",&n);
    while(n--)
    {
    scanf("%d",&x);
    for(i = 0;i < x;i++)
    {
        scanf("%d",&str[i]);
    }
    a[100001] = 100;
    for(i = 0;i < x;i++)
    {
        for(j = 0;j < x;j++)
        {
            if(str[i] == str[j])
            ++a[i];
        }
    }
    for(i = 0;i < x;i++)
    {
        if(a[i]%2!=0)
        {
            str[100001] = str[i];
            a[100001]=a[i];
        }
    }
    printf("%d\n",str[100001]);
    }
    return 0;
}

简直看不下去

那么下面我们就来介绍一下位运算中的异或运算(^)吧

位运算是对二进制的一种运算，两个数相反时取1，相同时取0

即0^1 = 1 0^0 = 0 1 ^ 0 = 1 1 ^ 1 = 0

根据这一特性，我们不难得到任何数与自己进行异或运算结果都为0的结论

所以显然在只有一个数出现次数为奇数的数据中，我们从第一个数据开始不断与下一个数据进行异或运算，最后出现次数为偶数的数据便会消失，我们来举个例子,有三个数字 27 23 27

11011(27) ^ 10111(23) = 01100(12)

01100(12) ^ 11011(27) = 10111(23)

那么我们根据这一特性，直接写出代码

#include <cstdio>

void input_solve() {
    int N, a, b;
    scanf("%d", &N);
    scanf("%d", &a);
    while(--N) {
        scanf("%d", &b);
        a ^= b;
    }
    printf("%d\n", a);
}

int main() {
    int T;
    scanf("%d", &T);
    while(T--)
        input_solve();
    return 0;
}