意甲冠军

我们共收集N邮票。现在失去了2张，剩下N-2张…..原集邮收集了所有对。因此，找到什么两枚邮票是一个。它们输出。

(确定缺少邮票是不一样的)

思路

由于编号比較大，能够用hash表压缩成数组能够开的下的大小。

压缩直接取模就好。假设冲突就往下一个找。

代码

#include <cstdio>

#include <cstring>

#define MOD 1000007

const int maxn = 1000010;

struct node {

    int cnt;

    int num;

};

node s[maxn];

int main()

{

    int n;

    scanf("%d",&n);

    for(int i = 0 ; i < n-2 ; i ++) {

        int a;

        scanf("%d",&a);//??

??

int ahash = a%MOD;

        while(s[ahash].num != a && s[ahash].num != 0) {

            ahash ++;

            ahash = ahash%maxn;

        }

        s[ahash].num = a;

        s[ahash].cnt ++;

    }

    bool first = true;

    for(int i = 0 ; i < maxn ; i ++) {

        if(s[i].cnt%2) {

            if(first) {

                first = false;

                printf("%d",s[i].num);

            }else printf(" %d\n",s[i].num);

        }

    }

    return 0;

}

版权声明：本文博主原创文章，博客，未经同意不得转载。