《算法竞赛入门经典(第2版)》第 5 章 C++与 STL 入门-代码笔记

第 5 章 C++与 STL 入门

5.1 从 C 到 C++

5.1.1 C++版框架

// C++版的“a+b 程序
#include<cstdio>
int main() {
int a, b;
while(scanf("%d%d", &a, &b) == 2) printf("%d\\n", a+b);
return 0;
}

// 展示更多的常用 C++特性
#include<iostream>
#include<algorithm>

using namespace std;
const int maxn = 100 + 10;
int A[maxn];

int main() {
long long a, b;
while(cin >> a >> b) {
cout << min(a,b) << "\\n";
}
return 0;
}

5.1.2 引用

#include<iostream>
using namespace std;

void swap2(int& a, int& b) {
int t = a; a = b; b = t;
}

int main() {
int a = 3, b = 4;
swap2(a, b);
cout << a << " " << b << "\\n";
return 0;
}

5.1.3 字符串

#include<iostream>
#include<string>
#include<sstream>
using namespace std;

int main() {
string line;
while (getline(cin, line)) {
int sum = 0, x;
stringstream ss(line);
while (ss >> x) sum += x;
cout << sum << "\\n";
}
return 0;
}

5.1.4 再谈结构体

// 引入输入输出流库，用于控制台输入输出
#include<iostream>
// 使用标准命名空间，避免每次都要写 std::
using namespace std;

// 定义一个表示二维点的结构体
struct Point {
int x, y; // 点的x和y坐标

// 构造函数，带有默认参数
// 当创建Point对象时，如果没有提供参数，则使用默认值(0,0)
Point(int x=0, int y=0):x(x),y(y) {}
// 使用初始化列表来初始化成员变量，效率更高
// :x(x), y(y) 表示将参数x赋值给成员变量x，参数y赋值给成员变量y
};

// 重载加法运算符，实现两个Point对象的相加
// 参数：两个Point对象的常引用（const & 避免拷贝，提高效率）
// 返回：一个新的Point对象，其坐标为两个点坐标之和
Point operator + (const Point& A, const Point& B) {
return Point(A.x+B.x, A.y+B.y);
// 创建临时Point对象，其x为A.x+B.x，y为A.y+B.y
}

// 重载输出运算符 <<，用于输出Point对象
// 参数：输出流引用，Point对象的常引用
// 返回：输出流引用，支持链式调用（如 cout << a << b）
ostream& operator << (ostream &out, const Point& p) {
out << "(" << p.x << "," << p.y << ")"; // 输出格式：(x,y)
return out; // 返回输出流，支持连续输出
}

// 主函数，程序入口点
int main() {
// 创建两个Point对象
Point a; // 使用默认构造函数，a的坐标为(0,0)
Point b(1,2); // 使用带参数构造函数，b的坐标为(1,2)

a.x = 3; // 修改a的x坐标为3，现在a的坐标为(3,0)

// 输出 a + b 的结果
// 等价于：operator<<(cout, operator+(a, b))
// 先计算 a+b，然后通过重载的 << 运算符输出
cout << a+b << "\\n"; // 输出 (4,2)

return 0; // 程序正常结束
}

5.2 STL 初步

例题 5-1 大理石在哪儿（Where is the Marble?, UVa 10474）

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 10000;

int main() {
int n, q, x, a[maxn], kase = 0;
while (scanf("%d%d", &n, &q) == 2 && n) {
printf("CASE# %d:\\n", ++kase);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
sort(a, a+n); //排序
while (q—) {
scanf("%d", &x);
int p = lower_bound(a, a+n, x) – a; //在已排序数组 a 中寻找 x
if (a[p] == x)
printf("%d found at %d\\n", x, p+1);
else
printf("%d not found\\n", x);
}
}
return 0;
}

例题 5-2 木块问题（The Blocks Problem, UVa 101）

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
using namespace std;

const int maxn = 30;
int n;
vector<int> pile[maxn]; // 每个 pile[i]是一个 vector

// 找木块 a 所在的 pile 和 height，以引用的形式返回调用者
void find_block(int a, int &p, int &h) {
for (p = 0; p < n; p++)
for (h = 0; h < pile[p].size(); h++)
if (pile[p][h] == a)
return;
}

// 把第 p 堆高度为 h 的木块上方的所有木块移回原位
void clear_above(int p, int h) {
for (int i = h + 1; i < pile[p].size(); i++) {
int b = pile[p][i];
pile[b].push_back(b); // 把木块 b 放回原位
}
pile[p].resize(h + 1); // pile 只应保留下标 0~h 的元素
}

// 把第 p 堆高度为 h 及其上方的木块整体移动到 p2 堆的顶部
void pile_onto(int p, int h, int p2) {
for (int i = h; i < pile[p].size(); i++)
pile[p2].push_back(pile[p][i]);
pile[p].resize(h);
}
void print() {
for (int i = 0; i < n; i++)
{
printf("%d:", i);
for (int j = 0; j < pile[i].size(); j++)
printf(" %d", pile[i][j]);
printf("\\n");
}
}

int main() {
int a, b;
cin >> n;
string s1, s2;
for (int i = 0; i < n; i++)
pile[i].push_back(i);
while (cin >> s1 >> a >> s2 >> b) {
int pa, pb, ha, hb;
find_block(a, pa, ha);
find_block(b, pb, hb);
if (pa == pb)
continue; // 非法指令
if (s2 == "onto")
clear_above(pb, hb);
if (s1 == "move")
clear_above(pa, ha);
pile_onto(pa, ha, pb);
}
print();
return 0;
}

例题 5-3 安迪的第一个字典（Andy’s First Dictionary, UVa 10815）

#include <iostream>
#include <string>
#include <set>
#include <sstream>
using namespace std;
set<string> dict; // string 集合
int main() {
string s, buf;
while (cin >> s) {
for (int i = 0; i < s.length(); i++)
if (isalpha(s[i]))
s[i] = tolower(s[i]);
else
s[i] = ' ';
stringstream ss(s);
while (ss >> buf)
dict.insert(buf);
}
for (set<string>::iterator it = dict.begin(); it != dict.end(); ++it)
cout << *it << "\\n";
return 0;
}

例题 5-4 反片语（Ananagrams, UVa 156）

#include <iostream>
#include <string>
#include <cctype>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

map<string, int> cnt;
vector<string> words;

// 将单词 s 进行“标准化”
string repr(const string &s) {
string ans = s;
for (int i = 0; i < ans.length(); i++)
ans[i] = tolower(ans[i]);
sort(ans.begin(), ans.end());
return ans;
}

int main() {
int n = 0;
string s;
while (cin >> s) {
if (s[0] == '#')
break;
words.push_back(s);
string r = repr(s);
if (!cnt.count(r))
cnt[r] = 0;
cnt[r]++;
}
vector<string> ans;
for (int i = 0; i < words.size(); i++)
if (cnt[repr(words[i])] == 1)
ans.push_back(words[i]);
sort(ans.begin(), ans.end());
for (int i = 0; i < ans.size(); i++)
cout << ans[i] << "\\n";
return 0;
}

例题 5-5 集合栈计算机（The SetStack Computer, ACM/ICPC NWERC 2006, UVa12096）

#include<string>
#include<iostream>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<algorithm>

using namespace std;

map<set<int>, int> mp;
vector<set<int>> v;
stack<int> st;

int findId(set<int> sse) {
if(!mp.count(sse)) {
v.push_back(sse);
mp[sse] = v.size() – 1;
}
return mp[sse];
}

int main() {
int t, n, i;
string s;
cin >> t;
while(t—) {
cin >> n;
while(n—) {
cin >> s;
if(s == "PUSH") {
st.push(findId(set<int>()));
} else if(s == "DUP") {
st.push(st.top());
} else {
int id1 = st.top();
st.pop();
int id2 = st.top();
st.pop();
set<int> sse;
if(s == "UNION") {
set_union(v[id1].begin(), v[id1].end(), v[id2].begin(), v[id2].end(), inserter(sse, sse.begin()));
st.push(findId(sse));
}
if(s == "INTERSECT") {
set_intersection(v[id1].begin(), v[id1].end(), v[id2].begin(), v[id2].end(), inserter(sse, sse.begin()));
st.push(findId(sse));
}
if(s == "ADD") {
sse = v[id2];
sse.insert(id1);
st.push(findId(sse));
}
}
cout << v[st.top()].size() << endl;
}
cout << "***" << endl;
}
return 0;
}

例题 5-6 团体队列（Team Queue, UVa 540）

#include <cstdio>
#include <queue>
#include <map>
using namespace std;
const int maxt = 1000 + 10;
int main() {
int t, kase = 0;
while (scanf("%d", &t) == 1 && t) {
printf("Scenario #%d\\n", ++kase);
// 记录所有人的团队编号
map<int, int> team; // team[x]表示编号为 x 的人所在的团队编号
for (int i = 0; i < t; i++) {
int n, x;
scanf("%d", &n);
while (n—) {
scanf("%d", &x);
team[x] = i;
}
}
// 模拟
queue<int> q, q2[maxt]; // q 是团队的队列，而 q2[i]是团队 i 成员的队列
for (;;) {
int x;
char cmd[10];
scanf("%s", cmd);
if (cmd[0] == 'S')
break;
else if (cmd[0] == 'D') {
int t = q.front();
printf("%d\\n", q2[t].front());
q2[t].pop();
if (q2[t].empty())
q.pop(); // 团体 t 全体出队列
}
else if (cmd[0] == 'E') {
scanf("%d", &x);
int t = team[x];
if (q2[t].empty())
q.push(t); // 团队 t 进入队列
q2[t].push(x);
}
}
printf("\\n");
}
return 0;
}

例题 5-7 丑数（Ugly Numbers, UVa 136）

#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;
typedef long long LL;
const int coeff[3] = {2, 3, 5};
int main() {
priority_queue<LL, vector<LL>, greater<LL>> pq;
set<LL> s;
pq.push(1);
s.insert(1);
for (int i = 1;; i++) {
LL x = pq.top();
pq.pop();
if (i == 1500) {
cout << "The 1500'th ugly number is " << x << ".\\n";
break;
}
for (int j = 0; j < 3; j++) {
LL x2 = x * coeff[j];
if (!s.count(x2)) {
s.insert(x2);
pq.push(x2);
}
}
}
return 0;
}
// 答案：859963392。

5.3 应用：大整数类

5.4 竞赛题目举例

例题 5-8 Unix ls 命令（Unix ls, UVa 400）

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int maxcol = 60;
const int maxn = 100 + 5;
string filenames[maxn];

// 输出字符串 s，长度不足 len 时补字符 extra
void print(const string &s, int len, char extra) {
cout << s;
for (int i = 0; i < len – s.length(); i++)
cout << extra;
}

int main() {
int n;
while (cin >> n) {
int M = 0;
for (int i = 0; i < n; i++) {
cin >> filenames[i];
M = max(M, (int)filenames[i].length()); // STL 的 max
}
// 计算列数 cols 和行数 rows
int cols = (maxcol – M) / (M + 2) + 1, rows = (n – 1) / cols + 1;
print("", 60, '-');
cout << "\\n";
sort(filenames, filenames + n); // 排序
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
int idx = c * rows + r;
if (idx < n)
print(filenames[idx], c == cols – 1 ? M : M + 2, ' ');
}
cout << "\\n";
}
}
return 0;
}

例题 5-9 数据库（Database, ACM/ICPC NEERC 2009, UVa1592）

例题 5-10 PGA 巡回赛的奖金（PGA Tour Prize Money, ACM/ICPC World Finals 1990,

UVa207）

例题 5-11 邮件传输代理的交互（The Letter Carrier’s Rounds, ACM/ICPC World Finals

1999, UVa814）

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
using namespace std;
void parse_address(const string &s, string &user, string &mta)
{
int k = s.find('@');
user = s.substr(0, k);
mta = s.substr(k + 1);
}
int main()
{
int k;
string s, t, user1, mta1, user2, mta2;
set<string> addr;
// 输入所有 MTA，转化为地址列表
while (cin >> s && s != "*")
{
cin >> s >> k;
while (k—)
{
cin >> t;
addr.insert(t + "@" + s);
}
}
while (cin >> s && s != "*")
{
parse_address(s, user1, mta1); // 处理发件人地址
vector<string> mta; // 所有需要连接的 mta，按照输入顺序
map<string, vector<string>> dest; // 每个 MTA 需要发送的用户
set<string> vis;
while (cin >> t && t != "*")
{
parse_address(t, user2, mta2); // 处理收件人地址
if (vis.count(t))
continue; // 重复的收件人
vis.insert(t);
if (!dest.count(mta2))
{
mta.push_back(mta2);
dest[mta2] = vector<string>();
}
dest[mta2].push_back(t);
}
getline(cin, t); // 把“*”这一行的回车吃掉
// 输入邮件正文
string data;
while (getline(cin, t) && t[0] != '*')
data += " " + t + "\\n";
for (int i = 0; i < mta.size(); i++)
{
string mta2 = mta[i];
vector<string> users = dest[mta2];
cout << "Connection between " << mta1 << " and " << mta2 << endl;
cout << " HELO " << mta1 << "\\n";
cout << " 250\\n";
cout << " MAIL FROM:<" << s << ">\\n";
cout << " 250\\n";
bool ok = false;
for (int i = 0; i < users.size(); i++)
{
cout << " RCPT TO:<" << users[i] << ">\\n";
if (addr.count(users[i]))
{
ok = true;
cout << " 250\\n";
}
else
cout << " 550\\n";
}
if (ok)
{
cout << " DATA\\n";
cout << " 354\\n";
cout << data;
cout << ".\\n";
cout << " 250\\n";
}
cout << " QUIT\\n";
cout << " 221\\n";
}
}
return 0;
}

例题 5-12 城市正视图（Urban Elevations, ACM/ICPC World Finals 1992, UVa221）

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100 + 5;
struct Building
{
int id;
double x, y, w, d, h;
bool operator<(const Building &rhs) const
{
return x < rhs.x || (x == rhs.x && y < rhs.y);
}
} b[maxn];
int n;
double x[maxn * 2];
bool cover(int i, double mx)
{
return b[i].x <= mx && b[i].x + b[i].w >= mx;
}
// 判断建筑物 i 在 x=mx 处是否可见
bool visible(int i, double mx)
{
if (!cover(i, mx))
return false;
for (int k = 0; k < n; k++)
if (b[k].y < b[i].y && b[k].h >= b[i].h && cover(k, mx))
return false;
return true;
}
int main()
{
int kase = 0;
while (scanf("%d", &n) == 1 && n)
{
for (int i = 0; i < n; i++)
{
scanf("%lf%lf%lf%lf%lf", &b[i].x, &b[i].y, &b[i].w, &b[i].d, &b[i].h);
x[i * 2] = b[i].x;
x[i * 2 + 1] = b[i].x + b[i].w;
b[i].id = i + 1;
}
sort(b, b + n);
sort(x, x + n * 2);
int m = unique(x, x + n * 2) – x; // x 坐标排序后去重，得到 m 个坐标
if (kase++)
printf("\\n");
printf("For map #%d, the visible buildings are numbered as follows:\\n%d",
kase, b[0].id);
for (int i = 1; i < n; i++)
{
bool vis = false;
for (int j = 0; j < m – 1; j++)
if (visible(i, (x[j] + x[j + 1]) / 2))
{
vis = true;
break;
}
if (vis)
printf(" %d", b[i].id);
}
printf("\\n");
}
return 0;
}

5.5 习题

习题 5-1 代码对齐（Alignment of Code, ACM/ICPC NEERC 2010, UVa1593）

#include<iostream>
#include<sstream>
#include<vector>
#include<string.h>
using namespace std;

int main() {
vector<vector<string> > v;
string line, word;
int i, j, k;
int vlen[200];
while(getline(cin, line)) {
stringstream ss(line);
vector<string> vs;
while(ss >> word) {
vs.push_back(word);
}
v.push_back(vs);
}
memset(vlen, 0, 200);
for(i = 0; i < v.size(); ++i) {
for(j = 0; j < v[i].size(); ++j) {
vlen[j] = v[i][j].length() > vlen[j] ? v[i][j].length() : vlen[j];
}
}
for(i = 0; i < v.size(); ++i) {
// if(i != 0) cout << endl;
for(j = 0; j < v[i].size(); ++j) {
cout << v[i][j];
if(j != v[i].size() – 1) {
for(k = vlen[j] – v[i][j].size(); k > 0; —k) {
cout << ' ';
}
cout << ' ';
}
}
cout << endl;
}
return 0;
}

习题 5-2 Ducci 序列（Ducci Sequence, ACM/ICPC Seoul 2009, UVa1594）

#include<iostream>
#include<math.h>
#include<string.h>
using namespace std;

int arr[1005][2005];
int n;

int judge(int i) {
int j, k;
for(j = 0; j < n; ++j) {
if(arr[i][j] != 0) {
break;
}
}
if(j == n) {
return 1;
}
for(k = 0; k < i; ++k) {
for(j = 0; j < n; ++j) {
if(arr[i][j] != arr[k][j]) {
break;
}
}
if(j == n) {
return 2;
}
}
return 0;
}

int main() {
int m,i,j,k;
int flag;
cin >> m;
while(m—) {
memset(arr, 0, 1005*2005);
cin >> n;
for(i = 0; i < n; ++i) {
cin >> arr[0][i];
}
i = 0;
while(1) {
flag = judge(i);
if(flag != 0) {
break;
}
++i;
arr[i][n–1] = abs(arr[i–1][0] – arr[i–1][n–1]);
for(j = 1; j < n; ++j) {
arr[i][j–1] = abs(arr[i–1][j] – arr[i–1][j–1]);
}
}
if(flag == 1) {
cout << "ZERO" << endl;
} else {
cout << "LOOP" << endl;
}
}
}

习题 5-3 卡片游戏（Throwing cards away I, UVa 10935）

#include<queue>
#include<iostream>
using namespace std;

int main() {
int n, i, j, k;
while(cin >> n && n) {
queue<int> qu;
for(i = 1; i <= n; ++i) {
qu.push(i);
}
cout << "Discarded cards:";
while(qu.size() > 1) {
cout << " " << qu.front();
if(qu.size() > 2) {
cout << ",";
}
qu.pop();
j = qu.front();
qu.pop();
qu.push(j);
}
cout << endl;
cout << "Remaining card: " << qu.front() << endl;
}
return 0;
}

习题 5-4 交换学生（Foreign Exchange, UVa 10763）

#include<stdio.h>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
int n, a, b, i, j, k;
while(scanf("%d", &n) && n) {
vector<int> lv, rv;
for(i = 0; i < n; ++i) {
scanf("%d %d", &a, &b);
lv.push_back(a);
rv.push_back(b);
}
sort(lv.begin(), lv.end());
sort(rv.begin(), rv.end());
for(i = 0; i < n; ++i) {
if(lv[i] != rv[i]) {
break;
}
}
if(i != n) {
puts("NO");
} else {
puts("YES");
}
}
return 0;
}

习题 5-5 复合词（Compound Words, UVa 10391）

#include<set>
#include<iostream>
#include<string>
using namespace std;

int main() {
set<string> se;
string s;
int size, i;
bool flag;
while(cin >> s) {
se.insert(s);
}
for(auto ip = se.begin(); ip != se.end(); ++ip) {
size = ip->length() – 1;
// cout << size << " " << *ip << endl;
flag = false;
for(i = 1; i < size; ++i) {
string s1 = ip->substr(0, i);
string s2 = ip->substr(i);
if(se.count(s1) && se.count(s2)) {
flag = true;
break;
}
}
if(flag == true) {
cout << *ip << endl;
}
}
return 0;
}

习题 5-6 对称轴（Symmetry, ACM/ICPC Seoul 2004, UVa1595）

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

struct point {
int x, y;
};

bool cmp1(const point &lhs, const point &rhs) {
if(lhs.x != rhs.x) {
return lhs.x < rhs.x;
}
return lhs.y < rhs.y;
}

bool cmp2(const point &lhs, const point &rhs) {
if(lhs.x != rhs.x) {
return lhs.x < rhs.x;
}
return lhs.y > rhs.y;
}

int main() {
int t, n, i, j, k, a, b;
cin >> t;
bool cut2, flag;
while(t—) {
vector<point> v;
cin >> n;
for(i = 0; i < n; ++i) {
point p;
cin >> p.x >> p.y;
v.push_back(p);
}
sort(v.begin(), v.end(), cmp1);
int beg1 = 0, end1, beg2, end2 = n – 1, xcut;
cut2 = false;
if(n % 2 == 0) {
end1 = n/2 – 1;
beg2 = n/2;
int sum = v[beg2].x + v[end1].x;
xcut = sum / 2;
if(sum % 2 != 0) {
cut2 = true;
}
// xcut = (v[n/2].x + v[n/2 – 1].x) / 2;
} else {
xcut = v[n/2].x;
end1 = n/2 – 1;
beg2 = n/2 + 1;
}
sort(v.begin() + beg2, v.end(), cmp2);
flag = true;
for(i = beg1; i <= end1; ++i) {
a = i;
b = end2 – i;
if(v[a].x == xcut && v[b].x == xcut) {
continue;
}
if(v[a].y != v[b].y) {
flag = false;
break;
}
if(!cut2) {
if((xcut – v[a].x) != (v[b].x – xcut)) {
flag = false;
break;
}
}
if(cut2) {
if((xcut – v[a].x) != (v[b].x – xcut – 1)) {
flag = false;
break;
}
}
}
if(flag) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
return 0;
}

习题 5-7 打印队列（Printer Queue, ACM/ICPC NWERC 2006, UVa12100）

#include<stdio.h>
#include<queue>
using namespace std;

int m;

int findTime(queue<int> &qu, priority_queue<int> &qup) {
int time = 0;
int k, kt;
while(1) {
k = qu.front();
kt = qup.top();
qu.pop();
—m;
if(k == kt) {
++time;
qup.pop();
if(m == –1) {
return time;
}
} else {
qu.push(k);
if(m == –1) {
m = qu.size() – 1;
}
}
}
}

int main() {
int t, n, i, k;
scanf("%d", &t);
while(t—) {
scanf("%d %d", &n, &m);
queue<int> qu;
priority_queue<int> qup;
for(i=0; i<n; ++i) {
scanf("%d", &k);
qu.push(k);
qup.push(k);
}
printf("%d\\n", findTime(qu, qup));
}
return 0;
}

习题 5-8 图书管理系统（Borrowers, ACM/ICPC World Finals 1994, UVa230）

#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<algorithm>

using namespace std;

struct book {
string title;
string author;
int has;
bool operator < (const book &rhs) {
if(this->author != rhs.author) {
return this->author < rhs.author;
} else {
return this->title < rhs.title;
}
}
};

vector<book> v;
map<string, int> mp;

book getBook(string s) {
book b;
s = s.substr(1);
int pos = s.find("\\"");
b.title = s.substr(0, pos);
b.author = s.substr(pos + 5);
b.has = 0;
return b;
}

void shelve() {
int i;
string fore = "";
for(i = 0; i < v.size(); ++i) {
if(v[i].has == 0) {
fore = v[i].title;
}
if(v[i].has == 2) {
cout << "Put \\"" << v[i].title << "\\" ";
if(fore == "") {
cout << "first";
} else {
cout << "after \\"" << fore << "\\"";
}
cout << endl;
v[i].has = 0;
fore = v[i].title;
}
}
cout << "END" << endl;
}

int main() {
string s, out;
book b;
int i;
while(getline(cin, s) && s != "END") {
b = getBook(s);
v.push_back(b);
}
sort(v.begin(), v.end());
for(i = 0; i < v.size(); ++i) {
mp[v[i].title] = i;
}
while(getline(cin, s) && s != "END") {
string st = s.substr(0, 6);
if(st == "SHELVE") {
shelve();
continue;
}
string name = s.substr(8, s.length() – 9);
if(st == "BORROW") {
v[mp[name]].has = 1;
}
if(st == "RETURN") {
v[mp[name]].has = 2;
}
}
return 0;
}

习题 5-9 找 bug（Bug Hunt, ACM/ICPC Tokyo 2007, UVa1596）

#include<iostream>
#include<string>
#include<map>
#include<vector>
#include<stdlib.h>
#include<stack>
#define MAX 60
using namespace std;

struct Array {
int size;
map<int, int> mp;
};

Array arr[MAX];
int bug;

int getValue(string s) {
stack<int> st;
int a = 0, av = 0;
while(s.length()) {
if(s[0] >= 'A' && s[0] <= 'z') {
st.push(s[0] – 'A');
s = s.substr(2, s.length() – 3);
} else {
av = atoi(s.c_str());
break;
}
}
while(st.size()) {
a = st.top();
if(av >= arr[a].size || !arr[a].mp.count(av)) {
bug = 1;
return 0;
}
av = arr[a].mp[av];
st.pop();
}
return av;
}

void handleDecl(string line) {
Array a;
int i = line[0] – 'A';
if(i < 0 || i > MAX) {
bug = 1;
return;
}
line = line.substr(2, line.length() – 3);
int num = atoi(line.c_str());
a.size = num;
arr[i] = a;
}

void handlAssi(string line) {
int cut = line.find("=");
string front, after;
front = line.substr(0, cut);
after = line.substr(cut + 1);
int a1, v1, v2;
a1 = front[0] – 'A';
if(a1 < 0 || a1 > MAX) {
bug = 1;
return;
}
v1 = getValue(front.substr(2, front.length() – 3));
if(bug) {
return;
}
if(v1 >= arr[a1].size) {
bug = 1;
return;
}
v2 = getValue(after);
if(bug) {
return;
}
arr[a1].mp[v1] = v2;
}

void handleLine(string line) {
int pos = line.find("=");
if(pos < 0) {
handleDecl(line);
} else {
handlAssi(line);
}
}

int main() {
string line;
int i, j, k, lineNum;
while(getline(cin, line) && line != ".") {
for(i = 0; i < MAX; ++i) {
arr[i].size = 0;
arr[i].mp.clear();
}
bug = 0;
lineNum = 1;
handleLine(line);
while(getline(cin, line) && line != ".") {
if(!bug) {
++lineNum;
handleLine(line);
}
}
if(!bug) {
lineNum = 0;
}
cout << lineNum << endl;
}
return 0;
}

习题 5-10 在 Web 中搜索（Searching the Web, ACM/ICPC Beijing 2004, UVa1597）

#include<iostream>
#include<map>
#include<vector>
#include<sstream>
#include<set>
#include <algorithm>

using namespace std;

struct DID {
int doci;
int linei;
bool hole;
bool operator== (const DID &rhs) {
if (this->doci != rhs.doci) {
return false;
}
if(this->hole && rhs.hole) {
return true;
}
return this->linei == rhs.linei;
}
};
vector<vector<string> > docs;
map<string, vector<DID>> mp;
set<string> se = {
"a", "the", "to", "and", "or", "not"
};

void getDocs(int i) {
vector<string> doc;
string line, word;
int j, k = 0;

while(getline(cin, line) && line != "**********") {
doc.push_back(line);
for(j = 0; j < line.length(); ++j) {
if(line[j] >= 'A' && line[j] <= 'Z') {
line[j] = (line[j] – 'A') + 'a';
}
if(line[j] < 'a' || line[j] > 'z') {
line[j] = ' ';
}
}
stringstream ss(line);
while(ss >> word) {
if(!se.count(word)) {
DID d;
d.doci = i;
d.linei = k;
d.hole = false;
if(!mp.count(word)) {
mp[word] = vector<DID>();
}
mp[word].push_back(d);
}
}
++k;
}
docs.push_back(doc);
}
vector<DID> EMPTYVEC;
vector<DID> & getWordVec(string word) {
if(!mp.count(word)) {
return EMPTYVEC;
} else {
return mp[word];
}
}

void putMPV(const vector<DID> &mpv) {
if(!mpv.size()) {
cout << "Sorry, I found nothing." << endl;
return;
}
int i, j, k;
for(i = 0; i < mpv.size(); ++i) {
if(i != 0 && mpv[i].doci != mpv[i–1].doci) {
cout << "———-" << endl;
}
if(mpv[i].hole) {
k = mpv[i].doci;
for(j = 0; j < docs[k].size(); ++j) {
cout << docs[k][j] << endl;
}
continue;
}
cout << docs[mpv[i].doci][mpv[i].linei] << endl;
}
}

void getNOT(string word) {
set<int> vse;
int i;
vector<DID> & v = getWordVec(word);
for(i = 0; i < v.size(); ++i) {
vse.insert(v[i].doci);
}
vector<DID> ve;
for(i = 0; i < docs.size(); ++i) {
if(!vse.count(i)) {
DID d;
d.doci = i;
d.linei = 0;
d.hole = true;
ve.push_back(d);
}
}
putMPV(ve);
}

void getAND(vector<DID> &mpv, vector<DID> &mpv1, vector<DID> &mpv2) {
set<int> vse1, vse2;
int i;
for(i = 0; i < mpv1.size(); ++i) {
vse1.insert(mpv1[i].doci);
}
for(i = 0; i < mpv2.size(); ++i) {
vse2.insert(mpv2[i].doci);
}
for(i = 0; i < mpv1.size(); ++i) {
if(vse2.count(mpv1[i].doci)) {
mpv.push_back(mpv1[i]);
}
}
for(i = 0; i < mpv2.size(); ++i) {
if(vse1.count(mpv2[i].doci)) {
mpv.push_back(mpv2[i]);
}
}
}

bool cmp(const DID &lhs, const DID &rhs) {
if(lhs.doci != rhs.doci) {
return lhs.doci < rhs.doci;
}
return lhs.linei < rhs.linei;
}

void handleQuery() {
string query, word;
int i;
getline(cin, query);
stringstream ss(query);
vector<string> v;
while(ss >> word) {
v.push_back(word);
}

vector<DID> mpv;
if(v.size() == 1) {
mpv = getWordVec(v[0]);
} else if(v.size() == 2) {
getNOT(v[1]);
return;
} else {
vector<DID> & mpv1 = getWordVec(v[0]), & mpv2 = getWordVec(v[2]);
if(v[1] == "OR") {
mpv = mpv1;
for(i = 0; i < mpv2.size(); ++i) {
mpv.push_back(mpv2[i]);
}
} else { //and
getAND(mpv, mpv1, mpv2);
}
}
sort(mpv.begin(), mpv.end(), cmp);
mpv.erase(unique(mpv.begin(), mpv.end()), mpv.end());
putMPV(mpv);
}

int main() {
int N, M;
int i, j, k;
string s;
cin >> N;
getline(cin, s);
for(i = 0; i < N; ++i) {
getDocs(i);
}
/*
for(auto bi = mp.begin(); bi !=mp.end(); ++bi) {
vector<DID> & vt = bi->second;
sort(vt.begin(), vt.end(), cmp);
vt.erase(unique(vt.begin(), vt.end()), vt.end());
}
*/

cin >> M;
getline(cin, s);
while(M—) {
handleQuery();
cout << "==========" << endl;
}
return 0;
}

习题 5-11 更新字典（Updating a Dictionary, UVa12504）

#include<iostream>
#include<string>
#include<map>
#include<sstream>
using namespace std;

void getMap(map<string, string> & mp, string &line) {
int i, j, k;
for(i = 0; i < line.length(); ++i) {
if((line[i] < 'a' || line[i] > 'z') && (line[i] < '0' || line[i] > '9')) {
line[i] = ' ';
}
}
stringstream ss(line);
string word1, word2;
while(ss >> word1 >> word2) {
mp[word1] = word2;
}
}

int main() {
int n;
bool flag[3];
cin >> n;
string line1, line2;
getline(cin, line1);
while(n—) {
getline(cin, line1);
getline(cin, line2);
map<string, string> mp1, mp2;
getMap(mp1, line1);
getMap(mp2, line2);
flag[0] = false;
flag[1] = false;
flag[2] = false;
for(auto i = mp2.begin(); i !=mp2.end(); ++i) {
if(!mp1.count(i->first)) {
if(flag[0] == false) {
flag[0] = true;
cout << "+" << i->first;
} else {
cout << ',' << i->first;
}
}
}
if(flag[0] == true) {
cout << endl;
}
for(auto i = mp1.begin(); i !=mp1.end(); ++i) {
if(!mp2.count(i->first)) {
if(flag[1] == false) {
flag[1] = true;
cout << "-" << i->first;
} else {
cout << ',' << i->first;
}
}
}
if(flag[1] == true) {
cout << endl;
}
for(auto i = mp2.begin(); i !=mp2.end(); ++i) {
if(mp1.count(i->first) && i->second != mp1[i->first]) {
if(flag[2] == false) {
flag[2] = true;
cout << "*" << i->first;
} else {
cout << ',' << i->first;
}
}
}
if(flag[2] == true) {
cout << endl;
}
if(!flag[0] && !flag[1] && !flag[2]) {
cout << "No changes" << endl;
}
cout << endl;
}
return 0;
}

习题 5-12 地图查询（Do You Know The Way to San Jose?, ACM/ICPC World Finals

1997, UVa511）

#include<iostream>
#include<map>
#include<string>
#include<algorithm>
#include<vector>

using namespace std;

struct LOC {
double x, y;
};

struct MAP {
double x1, x2, y1, y2;
double cenx, ceny;
double radio;
double area;
string name;
};

vector<MAP> vm;
map<string, vector<int>> mp;
double xt, yt;

double compDis(MAP &m, int x, int y) {
return (m.cenx – x) * (m.cenx – x) + (m.ceny – y) * (m.ceny – y);
}

double compDisRC(MAP &m, int x, int y) {
return (m.x2 – x) * (m.x2 – x) + (m.y2 – y) * (m.y2 – y);
}

bool cmp(int l, int r) {
MAP &m1 = vm[l], &m2 = vm[r];
if(m1.area != m2.area) {
return m1.area > m2.area;
}
double dis1 = compDis(m1, xt ,yt), dis2 = compDis(m2, xt ,yt);
if(dis1 != dis2) {
return dis1 < dis2;
}
if(m1.radio != m2.radio) {
return m1.radio < m2.radio;
}
dis1 = compDisRC(m1, xt ,yt);
dis2 = compDisRC(m2, xt ,yt);
if(dis1 != dis2) {
return dis1 > dis2;
}
return m1.x1 < m2.x1;
}