{"id":11,"date":"2019-02-22T22:24:41","date_gmt":"2019-02-22T14:24:41","guid":{"rendered":"https:\/\/blog.kaaass.net\/acm\/?p=11"},"modified":"2019-02-22T22:24:41","modified_gmt":"2019-02-22T14:24:41","slug":"uva-1596-bug-hunt","status":"publish","type":"post","link":"https:\/\/blog.kaaass.net\/acm\/2019\/02\/uva-1596-bug-hunt\/","title":{"rendered":"UVA 1596 Bug Hunt"},"content":{"rendered":"

\u7b2c\u4e00\u6b21\u89c1\u5230\u9898\u76ee\u91cc\u5e26\u4e86\u4e2aBNF\uff0c\u6709\u610f\u601d\u3002\u57fa\u672c\u5c31\u662fSTL\u7684map\u3001stack\u5e94\u7528\u3002\u89e3\u6790\u6c42\u503c\u5c31\u6309\u7740\u7f16\u8bd1\u5668\u7684\u6765\u3002\u8d4b\u503c\u8bed\u53e5\u7684\u53f3\u503c\u3001\u5de6\u503c\u7684\u53c2\u6570\u3001\u58f0\u660e\u8bed\u53e5\u7684\u53c2\u6570\u9700\u8981\u6c42\u503c\u5230\u5e95\uff0c\u5176\u4f59\u8bed\u53e5\u4fdd\u7559\u3002\u6808arr\u7528\u4e8e\u5b58\u50a8\u5f53\u524d\u64cd\u4f5c\u7684\u6570\u7ec4\u540d\uff0c\u4e0d\u8fc7\u5176\u5b9e\u4e5f\u53ef\u4ee5\u4e0d\u7528\u6808\u3002\u5224\u65ad\u7684\u51fd\u6570\u53ef\u4ee5\u5185\u8054\uff0c\u4f46\u662f\u76f4\u63a5\u5199\u51fa\u6765\u66f4\u52a0\u6e05\u6670\u3002<\/p>\n

<\/p>\n

#include <iostream>\r\n#include <map>\r\n#include <string>\r\n#include <stack>\r\n\r\nusing namespace std;\r\n\r\nbool isArrayName(char c) {\r\n    return 'a' <= c && c <= 'z' || 'A' <= c && c <= 'Z';\r\n}\r\n\r\nbool isNum(char c) {\r\n    return '0' <= c && c <= '9';\r\n}\r\n\r\nstring line;\r\nmap<char, map<int, int>> env;\r\nmap<char, int> sizes;\r\nstack<char> arr; int num;\r\n\r\nbool validInd() {\r\n    char n = arr.top();\r\n    return env.count(n) > 0 && 0 <= num && num < sizes[n];\r\n}\r\n\r\nbool parse(int st, int ed, bool rt) {\r\n    int pEnd = st; bool bug;\r\n    if (isArrayName(line[st])) {\r\n        arr.push(line[st]);\r\n        if (bug = parse(st + 2, ed - 1, true)) return true;\r\n        if (rt) { \/\/ Query\r\n            if (!validInd() || env[arr.top()].count(num) == 0)\r\n                return true;\r\n            num = env[arr.top()][num];\r\n            arr.pop();\r\n        }\r\n    } else {\r\n        \/\/ num\r\n        while (++pEnd < ed && isNum(line[pEnd]));\r\n        num = stoi(line.substr(st, pEnd));\r\n    }\r\n    return false;\r\n}\r\n\r\nint main() {\r\n    int posEq, lineCnt = 0, rValue; bool flag = false, bug = false;\r\n    while (cin >> line) {\r\n        if (line[0] == '.') {\r\n            if (flag) break;\r\n            env.clear();\r\n            sizes.clear();\r\n            if (!bug) cout << 0 << endl;\r\n            else if (lineCnt) cout << lineCnt << endl;\r\n            lineCnt = 0;\r\n            flag = true; bug = false;\r\n            continue;\r\n        }\r\n        flag = false;\r\n        if (bug) continue;\r\n        \/\/ Read\r\n        posEq = 0; lineCnt++;\r\n        while (++posEq < line.size() && line[posEq] != '=');\r\n        if (posEq == line.size()) {\r\n            \/\/ declaration\r\n            if (bug = parse(0, line.size() - 1, false))\r\n                continue;\r\n            sizes[arr.top()] = num;\r\n            env[arr.top()] = map<int, int>();\r\n            arr.pop();\r\n        } else {\r\n            \/\/ rt\r\n            if (bug = parse(posEq + 1, line.size() - 1, true))\r\n                continue;\r\n            rValue = num;\r\n            if (bug = parse(0, posEq, false)) continue;\r\n            if (bug = !validInd()) continue;\r\n            env[arr.top()][num] = rValue;\r\n            arr.pop();\r\n        }\r\n    }\r\n    return 0;\r\n}<\/pre>","protected":false},"excerpt":{"rendered":"
\u7b2c\u4e00\u6b21\u89c1\u5230\u9898\u76ee\u91cc\u5e26\u4e86\u4e2aBNF\uff0c\u6709\u610f\u601d\u3002\u57fa\u672c\u5c31\u662fSTL\u7684map\u3001stack\u5e94\u7528\u3002\u89e3\u6790\u6c42\u503c\u5c31\u6309\u7740\u7f16\u8bd1\u5668\u7684\u6765\u3002\u8d4b\u503c\u8bed … <\/p>\n
\u7ee7\u7eed\u9605\u8bfb\u201cUVA 1596 Bug Hunt\u201d<\/span><\/a><\/p>","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[],"class_list":["post-11","post","type-post","status-publish","format-standard","hentry","category-3","entry"],"_links":{"self":[{"href":"https:\/\/blog.kaaass.net\/acm\/wp-json\/wp\/v2\/posts\/11","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.kaaass.net\/acm\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.kaaass.net\/acm\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.kaaass.net\/acm\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.kaaass.net\/acm\/wp-json\/wp\/v2\/comments?post=11"}],"version-history":[{"count":0,"href":"https:\/\/blog.kaaass.net\/acm\/wp-json\/wp\/v2\/posts\/11\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.kaaass.net\/acm\/wp-json\/wp\/v2\/media?parent=11"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.kaaass.net\/acm\/wp-json\/wp\/v2\/categories?post=11"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.kaaass.net\/acm\/wp-json\/wp\/v2\/tags?post=11"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}