寒假D3 A Find the Lost Sock

Alice bought a lot of pairs of socks yesterday. But when she went home, she found that she has lost one of them. Each sock has a name which contains exactly 7 charaters.

Alice wants to know which sock she has lost. Maybe you can help her.

Input

There are multiple cases. The first line containing an integer n (1 <= n <= 1000000) indicates that Alice bought n pairs of socks. For the following 2*n-1 lines, each line is a string with 7 charaters indicating the name of the socks that Alice took back.

Output

The name of the lost sock.

Sample Input

2

aabcdef

bzyxwvu

bzyxwvu

4

aqwerty

eas fgh

aqwerty

easdfgh

easdfgh

aqwerty

aqwerty

2

0x0abcd

0ABCDEF

0x0abcd

Sample Output

aabcdef

eas fgh

0ABCDEF

Hint

Because of HUGE input, scanf is recommended.

方法1：

#include<cstdio>

#include<cmath>

#include<cstring>

#include<stdlib.h>

char a[2000005][8];

//注;若用qsort对二维数组排序  应该用strcmp  若不是-

int cmp(const void *a,const void *b)

{

    return strcmp((char*)a,(char*)b);

}

int main()

{

    int i,j,k;

    int n;

    //快排，检测相邻的字符串

    while(scanf("%d",&n)!=-1)

    {

        getchar();

        for(i=0;i<2*n-1;i++)

        gets(a[i]);

        qsort(a,2*n-1,sizeof(a[0]),cmp);

        if(strcmp(a[0],a[1])!=0) {printf("%s\n",a[0]);continue;}

        for(i=0;i<2*n-1;i+=2)

        if(strcmp(a[i],a[i+1])!=0) {printf("%s\n",a[i]);break;}

    }

}

方法2：每一串都为7个字符，用数组对每一串的每一个字符计数若最后某字符的个数为奇数输出该字符（get）

巴特西