NEFU-643 Teacher Li

Description

This time,suddenly,teacher Li wants to find out who have missed interesting DP lesson to have fun.The students who are found out will get strictly punishment.Because,teacher Li wants all the students master the DP algorithm.

However,Li doesn't want to waste the class time to call over the names of students.So he let the students to write down their names in one paper.To his satisfaction,this time, only one student has not come. He can get the name who has not come to class,but,it is troublesome,and,teacher always have many things to think about,so,teacher Li wants you, who is in the ACM team, to pick out the name.

Input

There are several test cases.The first line of each case have one positive integer N.N is the number of the students,and N will not greater than 500,000.

Then,following N lines,each line contains one name of students who have attended class.The N-1 lines are presented after N lines.These N-1 lines indicates the names of students who have come to class this time,one name in one line.

The length of student's name is not greater than 30.

Process to the end of file.

Output

For each test case, first print a line saying "Scenario #k", where k is the number of the test case.Then output the name of the student who have not come to class.One case per line.Print a blank line after each test case, even after the last one.

题目翻译

第一行输入一个整数n

其后n行每行输入一个姓名，代表该班学生姓名

其后n-1行每行输入一个姓名，代表到班的学生姓名

要求按格式输出未到的那名学生的姓名

如样例

Sample Input

8
ALPHA
BRAVO
CHARLIE
DELTA
ECHO
FOXTROT
GOLF
INDIA 
ALPHA
BRAVO
CHARLIE
DELTA
ECHO
GOLF
INDIA 
3
A
B
C
A
C 

Sample Output

Scenario #1
FOXTROT

Scenario #2
B

哦！简单！这我不就来了么

Unaccepted Code

#include <bits/stdc++.h>
using namespace std;
struct $
{
    char name[35];
    int x;
};
$ a[500005];
int main()
{
    int n, q = 0;
    while (scanf("%d", &n) != EOF)
    {
        memset(a, 0, sizeof(a));
        int num = 0;
        for (int i = 0; i < n; i++)
        {
            scanf("%s", a[i].name);
            a[i].x = i + 1;
            num = num ^ a[i].x;
        }
        for (int i = 0; i < n - 1; i++)
        {
            char tmp[35];
            scanf("%s", tmp);
            for (int m = 0; m < n; m++)
            {
                if (a[m].x)
                {
                    if (strcmp(tmp, a[m].name) == 0)   //可以二分查找优化
                    {
                        num = num ^ a[m].x;
                        a[m].x = -1;
                        break;
                    }
                }
            }
        }
        cout << "Scenario #" << q + 1 << endl;
        cout << a[num - 1].name << endl<<endl;
        ++q;
    }
    return 0;
}

显然，这个做法他虽然有效，但是在往复查找的过程中复杂度较高，在较大的数据量面前，TLE自然在所难免

那么没有办法去对代号操作的时候，我们能不能对名字进行操作呢，当然可以

既然异或两次，变化重置的性质在数字中存在，那么在所有以ascii码存储的内容当中自然也存在，我们这里将名字保存到字符串中去，对字符串每位进行异或操作即可

当然，需要注意好读入的时候的格式位置问题就可以顺利ac了

Accepted Code

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, q = 0;
    char name[35];
    char tmp[35];
    while (scanf("%d", &n) != EOF)
    {
        getchar();
        memset(name, 0, sizeof(name));
        for (int i = 0; i < 2*n-1; i++)
        {
            memset(tmp, 0, sizeof(tmp));
            for (int i = 34;tmp[i+1]!='\n' ; i--)
            {
                scanf("%c",&tmp[i]);
            }
            for (int i = 0; i < 35; i++)
            {
                name[i]=name[i]^tmp[i];
            }
        }
        cout << "Scenario #" << q + 1 << endl;
        for (int i = 34; i >=0; i--)
        {
            cout<<name[i];
            if(!name[i-1])
            break;
        }
        cout<<endl;
        ++q;
    }
    return 0;
}

解后反思

能自己做的事不要转借他人。