当前位置:首页 > 开发 > 操作系统 > 正文

zoj 3826 Hierarchical Notation(模拟)

发表于: 2014-10-13   作者:阿尔萨斯   来源:转载   浏览:
rar
摘要: 题目链接:zoj 3826 Hierarchical Notation 题目大意:给定一些结构体,结构体有value值和key值,Q次询问,输出每个key值对应的value值。 解题思路:思路很简单,写个类词法的递归函数,每次将key值映射成一个hash值,用map映射每个key的value起始终止位置,预处理完了查询就很简单了。 这题是最后10分钟出的,因为没有考虑value为{}的情

题目链接:zoj 3826 Hierarchical Notation

题目大意:给定一些结构体,结构体有value值和key值,Q次询问,输出每个key值对应的value值。

解题思路:思路很简单,写个类词法的递归函数,每次将key值映射成一个hash值,用map映射每个key的value起始终止位置,预处理完了查询就很简单了。
这题是最后10分钟出的,因为没有考虑value为{}的情况,导致RE了,但是zoj上显示的是SE,表示不理解什么意思,其实就是RE,不过还有一个地方会导致RE,就是询问的长度可能非常大。手贱瞎改了一下就给过了。PS:我做的是同步赛。

#include <cstdio>
#include <cstring>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;
typedef unsigned long long ll;
typedef pair<int,int> pii;

const int maxn = 2000000;
const ll x = 123;

int N, Q, mv;
char op[maxn], s[maxn];
map<ll, pii> G;

inline int idx(char ch) {
    if (ch >= '0' && ch <= '9')
        return ch - '0';
    else if (ch >= 'A' && ch <= 'Z')
        return ch - 'A' + 10;
    else if (ch >= 'a' && ch <= 'z')
        return ch - 'a' + 36;
    else if (ch == '.')
        return 62;
    return 63;
}

void solve (ll u) {
    ll tmp = u;

    while (s[mv] != '}') {
        mv++;
        if (s[mv] == '}')
            return;
        u = tmp;

        while (s[mv] != ':')
            u = u * x + idx(s[mv++]);

        int l = ++mv;

        if (s[mv] == '{')
            solve(u * x + 62LL);
        else
            while (s[mv+1] != ',' && s[mv+1] != '}') mv++;

        G[u] = make_pair(l, mv);
        mv++;
    }
}

int main () {
    int cas;
    scanf("%d", &cas);
    while (cas--) {
        scanf("%s", s);

        mv = 0;
        G.clear();
        solve(0);

        scanf("%d", &Q);
        for (int i = 1; i <= Q; i++) {
            scanf("%s", op);

            ll ret = 0;
            int len = strlen(op);

            for (int i = 0; i < len; i++)
                ret = ret * x + idx(op[i]);

            if (G.count(ret)) {
                pii u = G[ret];
                for (int i = u.first; i <= u.second; i++)
                    printf("%c", s[i]);
                printf("\n");
            } else
                printf("Error!\n");
        }
    }
    return 0;
}

zoj 3826 Hierarchical Notation(模拟)

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
大致题意: 如题目中给出的图片 对于这样的一个无线扩展出去的图,输入一个数n,求出数字上下左右的
Japanese Mahjong III Time Limit: 2 Seconds Memory Limit: 65536 KB Mahjong is a game of skill,
Hierarchical Path-Finding 《Near Optimal Hierarchical Path-Finding》中提出了一种层次A*算法,
函数: sys_connect_by_path(column, separator) 伪列: connect_by_isleaf connect_by_iscycle 只
1.hierarchical storage structure This notion of inserting a smaller, faster storage device (e
Cluster:Hierarchical Clustering 上次学习了K-Means算法之后,本次继续学习另外一种Clustering算
Introduction Most users at one time or another have dealt with hierarchical data in a SQL dat
JSON(JavaScript Object Notation) 是一种轻量级的数据交换格式。易于人阅读和编写。同时也易于机器
题目链接:http://www.patest.cn/contests/pat-a-practise/1073 题目: Scientific notation is the
在进行数据库设计模型时,分为概念模型设计和物理模型设计两种,概念模型主要是反映真是世界中的业
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号