ZOJ 3826 Herarchical Notation（2014牡丹江H、文字列シミュレーション）

4601 ワード

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5380
Herarchical Notation
Time Limit: 2 Seconds
メモリLimit: 131313072 KB
In Marjar University、students in Collage of Computer Science will learn EON（Edward Object Notation）、which is a hierarchical data format to trans to transmint data daoject of wastine。
The EON formas is a list of key-value pairs separated by commma「」、enclosed by couble of braaces「{and]」.Each key-value pair has the form of「":"is a string consists of alphabers thegines.the。
To retrieve the data from an EON text，we can search it by using a key.Of course，the key can be in ness ted form because the value may be still an En.In this case，we will use dot".to separaketer differement。
For example、here is an EON text:
｛「headmaster」：「Edward」、「students」：｛student 01”：「Alice」、「student 02」：「Bob」｝

For the key「headmaster」，the value is「Edward」。

For the key“students”、the value is｛student 01”：“Alice”、“student 02”：“Bob”｝、

For the key「students」、「student 01」、the value is「Alice」、

As a student in Marjar University，you are dong your homework now.Please write a program to parse a line of EON and repond to several queries on the EON.
Input
The re are multiple test cases.The first line of input contains an integer T indicating the number of test cases.For each test case:
The first line contains an EON text.The number of colons:"in the string will not exced 10000 and the length of each key and non-EON value will not exceed 20.
The nextラインcontains an integer Q (0<= Q <= 1000）indicating the number of queries.The n follo wed by Q LINE，each line is a key for query.The querying keys are in corect format，but some of them may not exist in the EON text.
The length of each hierarchy of the querying keys will not exceed 20,while the total length of each querying key is not specified.It is Garanted that the total size of input data will not exceed 10 MB.
Output
For each test case，output Q LINE of values cores ponding to the queries.If a key does not exist in the EON text，output「Eror！」instead.
Sample Input

1
{"hm":"Edward","stu":{"stu01":"Alice","stu02":"Bob"}}
4
"hm"
"stu"
"stu"."stu01"
"students"

Sample Output

"Edward"
{"stu01":"Alice","stu02":"Bob"}
"Alice"
Error!

Author: LU，Yi
件名:
pythonを模した辞書。辞書を与えて、1000個のクエリーがあり、対応するキー値を出力します。
分析:
簡単で粗暴な文字列の神煩は模擬します。ネットの同時試合を打つために、メモリの制限がきつくて、オフライン操作を採用しました。
これらのキーシンボルをつかんで、'''''、':'を操作します。具体的にコードとコメントを見て、データはとても吐き気がしません。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define maxn 400007

char buff[maxn];

map > MAP;

char buf[maxn];

void print(int pos)
{
    int rest=0;
    while ((buff[pos]!=','&& buff[pos]!='}' || rest>0) && buff[pos]!='\0')
    {
        if (buff[pos]=='{')
            rest++;
        if (buff[pos]=='}')
            rest--;

        putchar(buff[pos++]);
    }
    putchar('
');
}

int ans[1007];

void analyse(const char *s)
{
    int j=0;

    for (int i=0;s[i]!='\0';i++)
    {
        if (s[i]=='{')
        {
            while (j>0 && buf[j-1]!='|') buf[j--]='\0'; //       
            if (j>0 && buf[j-1]=='|') j--;
            buf[j]='\0';
            buf[j++]='.';
            buf[j]='\0';
            continue;
        }

        if (s[i]=='}')  //    
        {
            while (j>0 &&buf[j-1]!='.') buf[j--]='\0';
            buf[j--]='\0';
            while (j>0 &&buf[j-1]!='.') buf[j--]='\0';
            buf[j]='\0';

            continue;
        }
        if (s[i]==':')
        {
            buf[j]='\0';
            if (MAP.count(string(buf))==1)  //       ，       
            {
                for (int k=0;k

HashMapのindexFor方法

google protobuf学習ノート2：使用と原理