问题描述
p12504原题链接:UVaOJ 12504 - Updating a Dictionary
相关说明:本题为《算法竞赛入门经典(第2版)》习题 5-11
解法一:字符串解析 + 构造字典
按照题意描述构造两个前后变化的字典,根据 key 和 value 进行比较即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#include <bits/stdc++.h> using namespace std; pair<string, string> parse(string kv) { return {kv.substr(0, kv.find(':')), kv.substr(kv.find(':') + 1)}; } void build_kv(string line, map<string, string>& dict) { for (auto& ch : line) // convert other characters to blank if (ch == '{' || ch == '}' || ch == ',' || ch == ':') ch = ' '; stringstream st(line); string key, value; while (st >> key >> value) dict[key] = value; } int main() { int t; cin >> t; while (t--) { map<string, string> before, after; string line; cin >> line; build_kv(line, before); cin >> line; build_kv(line, after); string add, remove, change; for (auto it = after.begin(); it != after.end(); it++) { if (before.find(it->first) == before.end()) add += (add.size() ? "," : "") + it->first; else if (it->second != before.find(it->first)->second) change += (change.size() ? "," : "") + it->first; } for (auto it = before.begin(); it != before.end(); it++) if (after.find(it->first) == after.end()) remove += (remove.size() ? "," : "") + it->first; if (add.size() + remove.size() + change.size() == 0) cout << "No changes" << endl; else { if (add.size()) cout << "+" << add << endl; if (remove.size()) cout << "-" << remove << endl; if (change.size()) cout << "*" << change << endl; } cout << endl; } return 0; } |
1 |
#TODO |