首页 > ACM题库 > HDU-杭电 > HDU 3150-Robot Roll Call-Cambot…Servo…Gypsy…Croooow[解题报告]HOJ
2014
03-06

HDU 3150-Robot Roll Call-Cambot…Servo…Gypsy…Croooow[解题报告]HOJ

Robot Roll Call � Cambot…Servo…Gypsy…Croooow

问题描述 :


Tetrahedral Stacks of Cannonballs

Mystery Science Theater 3000 is about to start, which means it’s time for "Robot Roll Call", where the name of each robot is called out, as per the list received from Earth. The expectation is that if a robot is there, it will respond by adding its name to a data stream which is then sent back to Earth. Unfortunately today, once the roll is received, communication with Earth is temporarily lost. In the meantime, the robots that are present for roll call have saved their names to the data stream. However, lots of other things are also being saved to this same stream. To help extract data later, any data placed in the stream is separated by whitespace. Once the communication problems are resolved, the contents of this stream are relayed to Earth.

Your task is as follows. Given a list of names for roll call, you must scan the accompanying data stream and determine if a given name is there. For each name that is in the roll call, report whether or not that name was in the data stream. For a name to be a match, it must appear EXACTLY as shown in the roll. This means a match is case-sensitive and sub-string matches are not allowed.

输入:

The first entry in the file will be an integer value t (t > 0) that represents the number of test data sets the file contains. Following this entry, will be t test sets. Each test set will start with an integer n (0 < n < 26) representing the number of names in the roll. On the lines that follow will be n entries, one per line, containing the individual names in the roll. No name will have more than 25 characters. Names will only contain the characters A-Z, a-z, and 0-9. Names will be unique.

Following the names will be an integer d (0 < d < 100) representing the number of lines in the data stream. On each subsequent line will be the characters that make up the data stream. Each line of the data stream will contain at least one character and at most 100. Furthermore, the data on a given line will be separated by whitespace (space, tab, or combination of the two). Finally, any names from the roll that might occur as part of the data stream will be found on one line (a name will not be split across lines).

输出:

The first entry in the file will be an integer value t (t > 0) that represents the number of test data sets the file contains. Following this entry, will be t test sets. Each test set will start with an integer n (0 < n < 26) representing the number of names in the roll. On the lines that follow will be n entries, one per line, containing the individual names in the roll. No name will have more than 25 characters. Names will only contain the characters A-Z, a-z, and 0-9. Names will be unique.

Following the names will be an integer d (0 < d < 100) representing the number of lines in the data stream. On each subsequent line will be the characters that make up the data stream. Each line of the data stream will contain at least one character and at most 100. Furthermore, the data on a given line will be separated by whitespace (space, tab, or combination of the two). Finally, any names from the roll that might occur as part of the data stream will be found on one line (a name will not be split across lines).

样例输入:

2
4
Gypsy
TomServo
CrowTRobot
Cambot
2
Manos Torgo Joel 101010 Gypsy tomservo
Fugitive Alien Time of the Apes crowTrobot Cambot
2
R2D2
C3PO
1
Boba Fett c3Po R2D22 Jar Jar Binks Luke give in to the dark side

样例输出:

Test set 1:
Gypsy is present
TomServo is absent
CrowTRobot is absent
Cambot is present
Test set 2:
R2D2 is absent
C3PO is absent

/**
 * ID: ping128
 * LANG: C++
 */

#include <stdio.h>
#include <iostream>
#include <sstream>
#include <stdlib.h>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <math.h>
#include <algorithm>
#include <map>
#include <string.h>

using namespace std;

typedef long long LL;
typedef pair<int, int>PII;
typedef pair<PII, int>PII2;

string name[30];
int n, m;
set<string>S;
class Solve
{
 public:
 void main2()
 {
 cin >> n;
 for(int i = 0; i < n; i++ ) cin >> name[i];
 cin >> m;
 string s;
 S.clear();
 getline(cin, s);
 for(int i = 0; i < m; i++ ) 
 {
 getline(cin, s);
 istringstream iss(s);
 while(iss >> s)
 {
 S.insert(s);
 }
 }
 
 for(int i = 0; i < n; i++ )
 {
 cout << name[i] << " is "; 
 if(S.find(name[i]) != S.end()) 
 {
 cout << "present" << endl;
 }
 else
 {
 cout << "absent" << endl;
 }
 }
 
 }
};

int main()
{
 // freopen("b.in", "r", stdin);
 // freopen(".out", "w", stdout);

 int Test;
 scanf("%d", &Test);
 for(int t = 1; t <= Test; t++ )
 {
 Solve ___test;
 printf("Test set %d:\n", t);
 ___test.main2();
 
 printf("\n");
 
 }
//while(1);
return 0;
}

  1. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c