2010-1091

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题目大意：寻找丢失的袜子，告知2*n-1只袜子的名字（保证名字长度为7），名字一样的可以计作一双，这样最后只需要找出多出的那只袜子（也就是丢失袜子的另外一只了），输出这只袜子的名字。[[BR]]
这里列举了三种不同的方法：法1最快且编程复杂度最小，其次法2，再次法3。[[BR]]

法1：位运算，利用异或操作，凡是偶数袜子的异或操作没有影响，而奇数袜子则记录下来，所以方法很不错的说，即快又省[[BR]]
法2：算是异或运算的手写版吧，统计名字每位各个字母出现的次数，出现奇数次的那个字母必定是此为上的答案。[[BR]]
法3：最模拟的办法，（直接读入近600000个名字，排序后遍历一次即可找出出现奇数次的名字，但是排序string的名字超时）把长为7的字符串看作26进制数，转换为数字（要long long)存储，再排序，排序后遍历找出现奇数次的数字，再转换为字符串输出，这个方法不推荐，又慢，又占空间。

{{{
#!cpp
#include<cstdio>
char t[10],f[10];
int main()
{
    int j,k,i,n;
    while(scanf("%d",&n)!=EOF)
    {
        scanf("%s",f);
        for (j=2;j<=2*n-1;++j)
        {
            scanf("%s",t);
            for (k=0;k<7;++k) f[k]^=t[k];
        }
        printf("%s\n",f);
    }
    return 0;
}            
}}}
{{{
#!cpp
#include<cstdio>
#include<cstring>
int main()
{
    int f[8][27];
    int n,j,k,i;
    char t[10];
    while(scanf("%d",&n)!=EOF)
    {
        memset(f,0,sizeof(f));
        for (j=1;j<=2*n-1;++j)
        {
            scanf("%s",t);
            for (k=0;k<7;++k) f[k][t[k]-'a']++;
        }
        for (j=0;j<7;++j)
            for (k=0;k<26;++k)
            if (f[j][k]%2==1)
            {
                printf("%c",k+'a');
                break;
            }
        printf("\n");
    }
    return 0;
}            
}}}
{{{
#!cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long f[600001];
int main()
{   
    long n,ans,j,k,i;
    long long cc;
    char t[10];
    while(scanf("%ld",&n)!=EOF)
    {
        for (j=1;j<=2*n-1;++j)
        {
            scanf("%s",t);
            cc=1;
            f[j]=0;
            for (k=0;k<7;++k)
            {
                f[j]+= (t[k]-'a')*cc;
                cc=cc*26LL;
            }
        }
        sort(f+1,f+2*n);
        f[2*n]=-1;
        i=1;
        j=1;
        while(j<=2*n-1)
        {
            while(f[j]==f[i]) ++j;
            k=j-i;
            if (k%2!=0) break;
            i=j;
        }
        cc=f[i];
        i=0;
        while(cc!=0LL)
        {
            printf("%c",cc%26+'a');
            cc=cc/26LL;
            ++i;
        }
        for (j=i;j<=6;++j) printf("a");
        printf("\n");
    }
    return 0;
}
}}}

------------------------------------------------------------------------------------

题目大意：寻找丢失的袜子，告知2*n-1只袜子的名字（保证名字长度为7），名字一样的可以计作一双，这样最后只需要找出多出的那只袜子（也就是丢失袜子的另外一只了），输出这只袜子的名字。

这里列举了三种不同的方法：法1最快且编程复杂度最小，其次法2，再次法3。

法1：位运算，利用异或操作，凡是偶数袜子的异或操作没有影响，而奇数袜子则记录下来，所以方法很不错的说，即快又省

法2：算是异或运算的手写版吧，统计名字每位各个字母出现的次数，出现奇数次的那个字母必定是此为上的答案。

法3：最模拟的办法，（直接读入近600000个名字，排序后遍历一次即可找出出现奇数次的名字，但是排序string的名字超时）把长为7的字符串看作26进制数，转换为数字（要long long)存储，再排序，排序后遍历找出现奇数次的数字，再转换为字符串输出，这个方法不推荐，又慢，又占空间。

#include<cstdio>
char t[10],f[10];
int main()
{
    int j,k,i,n;
    while(scanf("%d",&n)!=EOF)
    {
        scanf("%s",f);
        for (j=2;j<=2*n-1;++j)
        {
            scanf("%s",t);
            for (k=0;k<7;++k) f[k]^=t[k];
        }
        printf("%s\n",f);
    }
    return 0;
}            

#include<cstdio>
#include<cstring>
int main()
{
    int f[8][27];
    int n,j,k,i;
    char t[10];
    while(scanf("%d",&n)!=EOF)
    {
        memset(f,0,sizeof(f));
        for (j=1;j<=2*n-1;++j)
        {
            scanf("%s",t);
            for (k=0;k<7;++k) f[k][t[k]-'a']++;
        }
        for (j=0;j<7;++j)
            for (k=0;k<26;++k)
            if (f[j][k]%2==1)
            {
                printf("%c",k+'a');
                break;
            }
        printf("\n");
    }
    return 0;
}            

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long f[600001];
int main()
{   
    long n,ans,j,k,i;
    long long cc;
    char t[10];
    while(scanf("%ld",&n)!=EOF)
    {
        for (j=1;j<=2*n-1;++j)
        {
            scanf("%s",t);
            cc=1;
            f[j]=0;
            for (k=0;k<7;++k)
            {
                f[j]+= (t[k]-'a')*cc;
                cc=cc*26LL;
            }
        }
        sort(f+1,f+2*n);
        f[2*n]=-1;
        i=1;
        j=1;
        while(j<=2*n-1)
        {
            while(f[j]==f[i]) ++j;
            k=j-i;
            if (k%2!=0) break;
            i=j;
        }
        cc=f[i];
        i=0;
        while(cc!=0LL)
        {
            printf("%c",cc%26+'a');
            cc=cc/26LL;
            ++i;
        }
        for (j=i;j<=6;++j) printf("a");
        printf("\n");
    }
    return 0;
}

---