MEGChai MEGChai
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
首页 › 数据结构与算法 › 在线评测 › UVaOJ 12504 - Updating a Dictionary
AOAPC II

UVaOJ 12504 - Updating a Dictionary

Chai
2021-11-24 0:00:00在线评测阅读 501

问题描述

p12504

原题链接:UVaOJ 12504 - Updating a Dictionary

相关说明:本题为《算法竞赛入门经典(第2版)》习题 5-11

解法一:字符串解析 + 构造字典

按照题意描述构造两个前后变化的字典,根据 key 和 value 进行比较即可。

C++
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;
}
Python
1
#TODO
AOAPC II UVaOJ
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz