In this problem, a dictionary is collection of key-value pairs, where keys are lower-case letters, and values are non-negative integers. Given an old dictionary and a new dictionary, find out what were changed.
Each dictionary is formatting as follows:
{key:value,key:value,...,key:value}
Each key is a string of lower-case letters, and each value is a non-negative integer without leading zeros or prefix ‘+’. (i.e. -4, 03 and +77 are illegal). Each key will appear at most once, but keys can appear in any order.
Input
The first line contains the number of test cases T (T ≤ 1000). Each test case contains two lines. The first line contains the old dictionary, and the second line contains the new dictionary. Each line will contain at most 100 characters and will not contain any whitespace characters. Both dictionaries could be empty.
WARNING: there are no restrictions on the lengths of each key and value in the dictionary. That means keys could be really long and values could be really large.
Output
For each test case, print the changes, formatted as follows:
• First, if there are any new keys, print ‘+’ and then the new keys in increasing order (lexicographically), separated by commas.
• Second, if there are any removed keys, print ‘-’ and then the removed keys in increasing order (lexicographically), separated by commas.
• Last, if there are any keys with changed value, print ‘*’ and then these keys in increasing order (lexicographically), separated by commas.
If the two dictionaries are identical, print ‘No changes’ (without quotes) instead. Print a blank line after each test case.
Sample Input
3
{a:3,b:4,c:10,f:6}
{a:3,c:5,d:10,ee:4}
{x:1,xyz:123456789123456789123456789}
{xyz:123456789123456789123456789,x:1}
{first:1,second:2,third:3}
{third:3,second:2}
Sample Output
+d,ee
-b,f
*c
No changes
-first
题目类型：简单字符处理+二分搜索
算法分析：使用map<string, string>ma[2]分别表示旧和新字典，然后直接循环判断。注意解析字符串的方法和字典可能是空的
|
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 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 |
/************************************************** filename :k.cpp author :maksyuki created time :2018/1/24 22:09:24 last modified :2018/1/24 23:00:24 file location :C:\Users\abcd\Desktop\TheEternalPoet ***************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("in", "r", stdin) #define CFO freopen ("out", "w", stdout) #define CPPFF ifstream cin ("in") #define CPPFO ofstream cout ("out") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC) #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; map<string, string> ma[6]; void ParseString(string s, int pp) { string ss, ssa, ssb; if(s == "{}") return; do { if(s.find_first_of(',') != string::npos) ss = s.substr(1, s.find_first_of(',') - 1); else ss = s.substr(1, s.find_first_of('}') - 1); ssa = ss.substr(0, ss.find(':')); ssb = ss.substr(ss.find(':') + 1); //DB(ssa),DB(ssb); ma[pp][ssa] = ssb; if(s.find_first_of(',') != string::npos) { s = s.substr(s.find_first_of(',')); s[0] = '{'; } else break; }while(1); } int main() { #ifdef LOCAL CFF; //CFO; #endif int t; cin >> t; while(t--) { for(int i = 0; i < 6; i++) ma[i].clear(); string sa, sb; cin >> sa >> sb; ParseString(sa, 1); ParseString(sb, 2); bool is_change = false, is_first = true; bool is_change_a = false; for(map<string, string>:: iterator it = ma[2].begin(); it != ma[2].end(); it++) { if(!ma[1].count(it->first)) { is_change = is_change_a = true; if(is_first) { is_first = false; cout << "+" << it->first; } else cout << "," << it->first; } } if(is_change_a) cout << endl; bool is_change_b = false; is_first = true; for(map<string, string>:: iterator it = ma[1].begin(); it != ma[1].end(); it++) { if(!ma[2].count(it->first)) { is_change = is_change_b = true; if(is_first) { is_first = false; cout << "-" << it->first; } else cout << "," << it->first; } } if(is_change_b) cout << endl; bool is_change_c = false; is_first = true; for(map<string, string>:: iterator it = ma[1].begin(); it != ma[1].end(); it++) { if(ma[2].count(it->first) && ma[2][it->first] != it->second) { is_change = is_change_c = true; if(is_first) { is_first = false; cout << "*" << it->first; } else cout << "," << it->first; } } if(is_change_c) cout << endl; if(!is_change) cout << "No changes" << endl; cout << endl; } return 0; } |
- « 上一篇：uva1597
- uva514：下一篇 »