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

第 5 章 C++与 STL 入门

5.1 从 C 到 C++

5.1.1 C++版框架

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

// 展示更多的常用 C++特性#include<iostream>#include<algorithm>usingnamespace std;constint maxn =100+10;int A[maxn];intmain(){longlong a, b;while(cin >> a >> b){ cout <<min(a,b)<<"\n";}return0;}

5.1.2 引用

#include<iostream>usingnamespace std;voidswap2(int& a,int& b){int t = a; a = b; b = t;}intmain(){int a =3, b =4;swap2(a, b); cout << a <<" "<< b <<"\n";return0;}

5.1.3 字符串

#include<iostream>#include<string>#include<sstream>usingnamespace std;intmain(){ string line;while(getline(cin, line)){int sum =0, x; stringstream ss(line);while(ss >> x) sum += x; cout << sum <<"\n";}return0;}

5.1.4 再谈结构体

// 引入输入输出流库，用于控制台输入输出#include<iostream>// 使用标准命名空间，避免每次都要写 std::usingnamespace std;// 定义一个表示二维点的结构体structPoint{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){returnPoint(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;// 返回输出流，支持连续输出}// 主函数，程序入口点intmain(){// 创建两个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)return0;// 程序正常结束}

5.2 STL 初步

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

#include<cstdio>#include<algorithm>usingnamespace std;constint maxn =10000;intmain(){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 中寻找 xif(a[p]== x)printf("%d found at %d\n", x, p+1);elseprintf("%d not found\n", x);}}return0;}

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

#include<cstdio>#include<string>#include<vector>#include<iostream>usingnamespace std;constint maxn =30;int n; vector<int> pile[maxn];// 每个 pile[i]是一个 vector// 找木块 a 所在的 pile 和 height，以引用的形式返回调用者voidfind_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 的木块上方的所有木块移回原位voidclear_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 堆的顶部voidpile_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);}voidprint(){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");}}intmain(){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();return0;}

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

#include<iostream>#include<string>#include<set>#include<sstream>usingnamespace std; set<string> dict;// string 集合intmain(){ 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";return0;}

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

#include<iostream>#include<string>#include<cctype>#include<vector>#include<map>#include<algorithm>usingnamespace 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;}intmain(){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";return0;}

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

#include<string>#include<iostream>#include<set>#include<map>#include<vector>#include<stack>#include<algorithm>usingnamespace std; map<set<int>,int> mp; vector<set<int>> v; stack<int> st;intfindId(set<int> sse){if(!mp.count(sse)){ v.push_back(sse); mp[sse]= v.size()-1;}return mp[sse];}intmain(){int t, n, i; string s; cin >> t;while(t--){ cin >> n;while(n--){ cin >> s;if(s =="PUSH"){ st.push(findId(set<int>()));}elseif(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;}return0;}

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

#include<cstdio>#include<queue>#include<map>usingnamespace std;constint maxt =1000+10;intmain(){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;elseif(cmd[0]=='D'){int t = q.front();printf("%d\n", q2[t].front()); q2[t].pop();if(q2[t].empty()) q.pop();// 团体 t 全体出队列}elseif(cmd[0]=='E'){scanf("%d",&x);int t = team[x];if(q2[t].empty()) q.push(t);// 团队 t 进入队列 q2[t].push(x);}}printf("\n");}return0;}

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

#include<iostream>#include<vector>#include<queue>#include<set>usingnamespace std;typedeflonglong LL;constint coeff[3]={2,3,5};intmain(){ 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);}}}return0;}// 答案：859963392。

5.3 应用：大整数类

5.4 竞赛题目举例

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

#include<iostream>#include<string>#include<algorithm>usingnamespace std;constint maxcol =60;constint maxn =100+5; string filenames[maxn];// 输出字符串 s，长度不足 len 时补字符 extravoidprint(const string &s,int len,char extra){ cout << s;for(int i =0; i < len - s.length(); i++) cout << extra;}intmain(){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 和行数 rowsint 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";}}return0;}

例题 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>usingnamespace std;voidparse_address(const string &s, string &user, string &mta){int k = s.find('@'); user = s.substr(0, k); mta = s.substr(k +1);}intmain(){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";}}return0;}

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

#include<cstdio>#include<algorithm>usingnamespace std;constint maxn =100+5;structBuilding{int id;double x, y, w, d, h;booloperator<(const Building &rhs)const{return x < rhs.x ||(x == rhs.x && y < rhs.y);}} b[maxn];int n;double x[maxn *2];boolcover(int i,double mx){return b[i].x <= mx && b[i].x + b[i].w >= mx;}// 判断建筑物 i 在 x=mx 处是否可见boolvisible(int i,double mx){if(!cover(i, mx))returnfalse;for(int k =0; k < n; k++)if(b[k].y < b[i].y && b[k].h >= b[i].h &&cover(k, mx))returnfalse;returntrue;}intmain(){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");}return0;}

5.5 习题

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

#include<iostream>#include<sstream>#include<vector>#include<string.h>usingnamespace std;intmain(){ 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;}return0;}

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

#include<iostream>#include<math.h>#include<string.h>usingnamespace std;int arr[1005][2005];int n;intjudge(int i){int j, k;for(j =0; j < n;++j){if(arr[i][j]!=0){break;}}if(j == n){return1;}for(k =0; k < i;++k){for(j =0; j < n;++j){if(arr[i][j]!= arr[k][j]){break;}}if(j == n){return2;}}return0;}intmain(){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>usingnamespace std;intmain(){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;}return0;}

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

#include<stdio.h>#include<vector>#include<algorithm>usingnamespace std;intmain(){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");}}return0;}

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

#include<set>#include<iostream>#include<string>usingnamespace std;intmain(){ 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;}}return0;}

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

#include<iostream>#include<vector>#include<algorithm>usingnamespace std;structpoint{int x, y;};boolcmp1(const point &lhs,const point &rhs){if(lhs.x != rhs.x){return lhs.x < rhs.x;}return lhs.y < rhs.y;}boolcmp2(const point &lhs,const point &rhs){if(lhs.x != rhs.x){return lhs.x < rhs.x;}return lhs.y > rhs.y;}intmain(){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;}}return0;}

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

#include<stdio.h>#include<queue>usingnamespace std;int m;intfindTime(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;}}}}intmain(){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));}return0;}

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

#include<iostream>#include<vector>#include<map>#include<string>#include<algorithm>usingnamespace std;structbook{ string title; string author;int has;booloperator<(const book &rhs){if(this->author != rhs.author){returnthis->author < rhs.author;}else{returnthis->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;}voidshelve(){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;}intmain(){ 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;}}return0;}

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

#include<iostream>#include<string>#include<map>#include<vector>#include<stdlib.h>#include<stack>#defineMAX60usingnamespace std;structArray{int size; map<int,int> mp;}; Array arr[MAX];int bug;intgetValue(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;return0;} av = arr[a].mp[av]; st.pop();}return av;}voidhandleDecl(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;}voidhandlAssi(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;}voidhandleLine(string line){int pos = line.find("=");if(pos <0){handleDecl(line);}else{handlAssi(line);}}intmain(){ 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;}return0;}

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

#include<iostream>#include<map>#include<vector>#include<sstream>#include<set>#include<algorithm>usingnamespace std;structDID{int doci;int linei;bool hole;booloperator==(const DID &rhs){if(this->doci != rhs.doci){returnfalse;}if(this->hole && rhs.hole){returntrue;}returnthis->linei == rhs.linei;}}; vector<vector<string>> docs; map<string, vector<DID>> mp; set<string> se ={"a","the","to","and","or","not"};voidgetDocs(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];}}voidputMPV(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;}}voidgetNOT(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);}voidgetAND(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]);}}}boolcmp(const DID &lhs,const DID &rhs){if(lhs.doci != rhs.doci){return lhs.doci < rhs.doci;}return lhs.linei < rhs.linei;}voidhandleQuery(){ 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]);}elseif(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{//andgetAND(mpv, mpv1, mpv2);}}sort(mpv.begin(), mpv.end(), cmp); mpv.erase(unique(mpv.begin(), mpv.end()), mpv.end());putMPV(mpv);}intmain(){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;}return0;}

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

#include<iostream>#include<string>#include<map>#include<sstream>usingnamespace std;voidgetMap(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;}}intmain(){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;}return0;}

习题 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>usingnamespace std;structLOC{double x, y;};structMAP{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;doublecompDis(MAP &m,int x,int y){return(m.cenx - x)*(m.cenx - x)+(m.ceny - y)*(m.ceny - y);}doublecompDisRC(MAP &m,int x,int y){return(m.x2 - x)*(m.x2 - x)+(m.y2 - y)*(m.y2 - y);}boolcmp(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;}intmain(){ string line, word;double x1, x2, y1, y2;int i, j, t;getline(cin ,line);while(cin >> word && word !="LOCATIONS"){ MAP m; m.name = word; cin >> x1 >> y1 >> x2 >> y2;if(x1 > x2){ m.x1 = x2; m.x2 = x1;}else{ m.x2 = x2; m.x1 = x1;}if(y1 > y2){ m.y1 = y2; m.y2 = y1;}else{ m.y2 = y2; m.y1 = y1;} m.cenx =(m.x1 + m.x2)/2; m.ceny =(m.y1 + m.y2)/2; m.radio =(m.x2 - m.x1)/(m.y2 - m.y1); m.radio = m.radio -0.75;if(m.radio <0){ m.radio =-m.radio;} m.area =(m.x2 - m.x1)*(m.y2 - m.y1); vm.push_back(m);}while(cin >> word && word !="REQUESTS"){ cin >> xt >> yt; vector<int> v;for(i =0; i < vm.size();++i){if(vm[i].x1 <= xt && vm[i].x2 >= xt && vm[i].y1 <= yt && vm[i].y2 >= yt){ v.push_back(i);}}sort(v.begin(), v.end(), cmp); vector<int> vt;for(i =0; i < v.size();++i){if(i ==0){ vt.push_back(v[0]);continue;}if(vm[vt[vt.size()-1]].area == vm[v[i]].area){continue;} vt.push_back(v[i]);} mp[word]= vt;}while(cin >> word && word !="END"){ cin >> t; cout << word <<" at detail level "<< t <<' ';if(!mp.count(word)){ cout <<"unknown location";}elseif(mp[word].size()==0){ cout <<"no map contains that location";}elseif(mp[word].size()>= t){ cout <<"using "<< vm[mp[word][t-1]].name;}else{ cout <<"no map at that detail level; using "<< vm[mp[word][mp[word].size()-1]].name;} cout << endl;}return0;}

习题 5-13 客户中心模拟（Queue and A, ACM/ICPC World Finals 2000, UVa822）

#include<iostream>#include<vector>#include<queue>#include<algorithm>usingnamespace std;structREQ{int id, num, elap, serv, btwe;}; vector<REQ> reqs;structPER{int id; vector<int> v;int eart, endt;}; vector<PER> pers;int MAXTOPLEN;structTIME{int t;int flag;int i;booloperator==(const TIME & rhs)const{if(this->t == rhs.t &&this->i == rhs.i &&this->flag == rhs.flag){returntrue;}returnfalse;}booloperator<(const TIME & rhs)const{if(this->t != rhs.t){returnthis->t < rhs.t;}if(this->flag != rhs.flag)returnthis->flag < rhs.flag;returnthis->i< rhs.i;}booloperator>(const TIME & rhs)const{if(*this== rhs ||*this< rhs){returnfalse;}returntrue;}};boolcmp(const TIME & lhs,const TIME & rhs){if(lhs.t != rhs.t){return lhs.t < rhs.t;}return lhs.i < rhs.i;}intjudgePer(int i,int j){if(pers[i].eart > pers[j].eart){return j;}if(pers[i].eart < pers[j].eart){return i;}if(pers[i].id > pers[j].id){return j;}if(pers[i].id < pers[j].id){return i;}}intchoosePerson(int r,int t){int i, j, k;bool flag;int choose;for(i =0; i < MAXTOPLEN;++i){ flag =false;for(j =0; j < pers.size();++j){if(pers[j].v.size()<= i || pers[j].endt > t){continue;}if(pers[j].v[i]== reqs[r].id){if(flag ==false){ flag =true; choose = j;}else{ choose =judgePer(j, choose);}}}if(flag ==true){return choose;}}return-1;}intsimulate(){int t =0, i, j, k; TIME ti, tt; priority_queue<TIME, vector<TIME>, greater<TIME>> pq; queue<int> qth;for(i =0; i < reqs.size();++i){for(j =0; j < reqs[i].num;++j){ TIME tim; tim.t = reqs[i].elap + reqs[i].btwe * j; tim.i = i; tim.flag =1; pq.push(tim);}}while(pq.size()|| qth.size()){if(pq.size()){ ti = pq.top(); pq.pop();if(ti.flag >0){ qth.push(ti.i);} t = ti.t;while(pq.size()){ tt = pq.top();if(tt.t == t){if(tt.flag >0){ qth.push(tt.i);} pq.pop();}else{break;}}} k = qth.size();for(i =0; i < k;++i){ j = qth.front(); qth.pop();int perCho =choosePerson(j, t);if(perCho <0){ qth.push(j);continue;} pers[perCho].eart = t; pers[perCho].endt = t + reqs[j].serv; TIME tim; tim.t = pers[perCho].endt; tim.flag =-1; pq.push(tim);}}return t;}intmain(){int m, n, i, j, k, t =0;while(cin >> m && m !=0){ reqs.clear(); pers.clear(); MAXTOPLEN =0;while(m--){ REQ r; cin >> r.id >> r.num >> r.elap >> r.serv >> r.btwe; reqs.push_back(r);} cin >> n;while(n--){ PER p; cin >> p.id >> i;if(i > MAXTOPLEN){ MAXTOPLEN = i;}while(i--){ cin >> j; p.v.push_back(j);} p.eart =0; p.endt =0; pers.push_back(p);} k =simulate(); cout <<"Scenario "<<++t <<": All requests are serviced within "<< k <<" minutes."<< endl;}return0;}

习题 5-14 交易所（Exchange, ACM/ICPC NEERC 2006, UVa1598）

12333#include<iostream>#include<string>#include<queue>#include<map>usingnamespace std;structMES{int id;int size;int price;int bs;booloperator<(const MES &rhs)const{if(this->price != rhs.price){returnthis->price < rhs.price;}returnthis->id > rhs.id;}booloperator>(const MES &rhs)const{if(this->price != rhs.price){returnthis->price > rhs.price;}returnthis->id > rhs.id;}}; vector<MES> vmes; priority_queue<MES, vector<MES>, less<MES>> buys; priority_queue<MES, vector<MES>, greater<MES>> sells; map<int,int> mpBuy, mpSell;voiddeleteMes(int id){if(id >= vmes.size()||!vmes[id].size){return;}if(vmes[id].bs >0){ mpBuy[vmes[id].price]-= vmes[id].size;}else{ mpSell[vmes[id].price]-= vmes[id].size;} vmes[id].size =0;}voidbuyMes(MES &m){ MES m1, m2;int size, price;while(!sells.empty()&& m.size){ m1 = sells.top();if(vmes[m1.id].size ==0){ sells.pop();continue;}if(vmes[m1.id].price > m.price){break;} price = vmes[m1.id].price;if(m.size >= vmes[m1.id].size){ size = vmes[m1.id].size; sells.pop();}else{ size = m.size;} mpSell[price]-= size; m.size -= size; vmes[m1.id].size -= size; cout <<"TRADE "<< size <<" "<< price << endl;}}voidsellMes(MES &m){ MES m1, m2;int size, price;while(!buys.empty()&& m.size){ m1 = buys.top();if(vmes[m1.id].size ==0){ buys.pop();continue;}if(vmes[m1.id].price < m.price){break;} price = vmes[m1.id].price;if(m.size >= vmes[m1.id].size){ size = vmes[m1.id].size; buys.pop();}else{ size = m.size;} mpBuy[price]-= size; m.size -= size; vmes[m1.id].size -= size; cout <<"TRADE "<< size <<" "<< price << endl;}}intmain(){int n, i, j, k;int id; string s; MES m1, m2;int size, price;bool flag =false;while(cin >> n && n !=0){if(flag ==false){ flag =true;}else{ cout << endl;} priority_queue<MES, vector<MES>, less<MES>> buysT; priority_queue<MES, vector<MES>, greater<MES>> sellsT; buys = buysT; sells = sellsT; mpBuy.clear(); mpSell.clear(); vmes.clear();for(i =0; i < n;++i){ MES m; m.id = i; cin >> s;if(s =="CANCEL"){ cin >> id; id = id -1;deleteMes(id); m.price =0; m.size =0;}else{ cin >> m.size >> m.price;if(s =="BUY"){ m.bs =1;buyMes(m);if(m.size >0){if(!mpBuy.count(m.price)){ mpBuy[m.price]=0;} mpBuy[m.price]+= m.size; buys.push(m);}}else{//sell m.bs =-1;sellMes(m);if(m.size >0){if(!mpSell.count(m.price)){ mpSell[m.price]=0;} mpSell[m.price]+= m.size; sells.push(m);}}} vmes.push_back(m); cout <<"QUOTE "; size =0; price =0;while(!buys.empty()){ m1 = buys.top();if(vmes[m1.id].size ==0){ buys.pop();continue;} price = vmes[m1.id].price; size = mpBuy[vmes[m1.id].price];break;} cout << size <<" "<< price; cout <<" - "; size =0; price =99999;while(!sells.empty()){ m1 = sells.top();if(vmes[m1.id].size ==0){ sells.pop();continue;} price = vmes[m1.id].price; size = mpSell[vmes[m1.id].price];break;} cout << size <<" "<< price; cout << endl;}}return0;}

习题 5-15 Fibonacci 的复仇（Revenge of Fibonacci, ACM/ICPC Shanghai 2011, UVa12333）

#include<stdio.h>#include<string.h>#include<vector>#include<string>#include<algorithm>usingnamespace std;structBigInt{staticconstlonglong BASE =1000000000000000000;staticconstint WIDTH =18;staticconstint LEN =4; vector<longlong> s;BigInt(longlong num =0){*this= num;} BigInt operator=(longlong num){ s.clear();do{ s.push_back(num % BASE); num /= BASE;}while(num >0);return*this;} BigInt operator+(const BigInt &b){ BigInt c; c.s.clear();longlong g =0, x;int ssize = s.size(), bssize = b.s.size();for(int i =0;; i++){if(g ==0&& i >= ssize && i >= bssize)break; x = g;if(i < ssize) x += s[i];if(i < bssize) x += b.s[i]; c.s.push_back(x % BASE); g = x / BASE;}return c;} string outN(){ string str, st;int i = s.size()-1, j = LEN;while(i >=0&& j >0){ st =to_string(s[i]);while(i != s.size()-1&& st.length()< WIDTH){ st ="0"+ st;} str += st;--i;--j;}return str.substr(0,40);}};structNode{int id;int num; Node* childs[10]={NULL};}; vector<string> v; Node*createTree(){int i, j, n, num; Node * tree =new Node; tree->id =-1; tree->num =-1;for(i =0; i < v.size();++i){ n = v[i].size(); Node *p = tree;for(j =0; j < n;++j){ num = v[i][j]-'0';if(!p->childs[num]){ p->childs[num]=new Node; p->childs[num]->id = i; p->childs[num]->num = num;} p = p->childs[num];}}return tree;}intmain(){char s[45];int i, j, T, n, num, res; BigInt bv[3]; bv[0]=1; bv[1]=1; v.push_back("1"); v.push_back("1");for(i =2; i <100000;++i){ bv[i %3]= bv[(i-1)%3]+ bv[(i-2)%3]; v.push_back(bv[i %3].outN());}scanf("%d",&T); Node * tree =createTree();for(i =0; i < T;++i){scanf("%s", s); n =strlen(s); Node * p = tree;for(j =0; j < n;++j){ num = s[j]-'0';if(!p->childs[num]){break;} p = p->childs[num];}if(j == n){ res = p->id;}else{ res =-1;}printf("Case #%d: %d\n", i+1, res);}return0;}

习题 5-16 医院设备利用（Use of Hospital Facilities, ACM/ICPC World Finals 1991, UVa212）

#include<stdio.h>#include<vector>#include<queue>usingnamespace std;int oproomNum, reroomNum, startTime, transTime, preop, prere, patiNum;structPatient{char name[105];int opTime, reTime;int opNum, opBeg, opEnd, reNum, reBeg, reEnd;}; vector<Patient> v;structRoom{int useTime;bool use;int endTime;}; vector<Room> opV; vector<Room> reV;// type˵��// 1 �뿪oproom// -1 ׼���� oproomstructPrioItem{int time;int type;int pai;int roomi;booloperator<(const PrioItem &rhs)const{if(time != rhs.time){return time > rhs.time;}if(type != rhs.type){return type > rhs.type;}return roomi > rhs.roomi;}};int pai, timeNow, endTime; priority_queue<PrioItem> pq;// ���˿�ʼ����voiduseOpNum(int pai,int roomi){ PrioItem pi; opV[roomi].use =true; opV[roomi].useTime += v[pai].opTime; opV[roomi].endTime = timeNow + v[pai].opTime + preop; v[pai].opNum = roomi; v[pai].opBeg = timeNow; v[pai].opEnd = timeNow + v[pai].opTime; pi.time = v[pai].opEnd; pi.type =1; pi.pai = pai; pi.roomi = roomi; pq.push(pi);}voidhandleN1(PrioItem pi){if(pai >= patiNum){return;}for(int i =0; i < opV.size();++i){if(opV[i].endTime <= timeNow){useOpNum(pai++, i);}}}voidhandle1(PrioItem pi){// ת�˲���// ת�˵�ʱ���Ҫѡ��ָ���int i, j, k;for(i =0; i < reroomNum;++i){if(reV[i].endTime <= timeNow){break;}}if(i == reroomNum){//printf("��ô�����û�лָ��ҵ������\n");return;} reV[i].useTime += v[pi.pai].reTime; v[pi.pai].reNum = i; v[pi.pai].reBeg = timeNow + transTime; v[pi.pai].reEnd = v[pi.pai].reBeg + v[pi.pai].reTime;if(v[pi.pai].reEnd > endTime){ endTime = v[pi.pai].reEnd;} reV[i].endTime = v[pi.pai].reEnd + prere;// �����������¼�  PrioItem piNew2; piNew2.type =-1; piNew2.roomi = pi.roomi; piNew2.time = timeNow + preop; pq.push(piNew2);}voidoper(){int i, j, k; timeNow = startTime; PrioItem pi;for(pai =0; pai < oproomNum && pai < patiNum;++pai){useOpNum(pai, pai);}while(pq.size()){ pi = pq.top(); pq.pop(); timeNow = pi.time;switch(pi.type){case-1:handleN1(pi);break;case1:handle1(pi);break;}}if(pai != patiNum){// printf("��ô�����û���������������\n");return;}}voidoutTime(int t){int hour = t /60;int min = t %60;printf("%2d:%02d", hour, min);}voidoutPatient(){printf(" Patient Operating Room Recovery Room\n");printf(" # Name Room# Begin End Bed# Begin End\n");printf(" ------------------------------------------------------\n");int i;for(i =0; i < v.size();++i){printf("%2d %-9s %2d ", i+1, v[i].name, v[i].opNum +1);outTime(v[i].opBeg);printf(" ");outTime(v[i].opEnd);printf(" %2d ", v[i].reNum +1);outTime(v[i].reBeg);printf(" ");outTime(v[i].reEnd);printf("\n");}}doubleoutUsed(int i,int type){if(endTime == startTime){return0.0;}if(type ==0){return(double)opV[i].useTime /(endTime-startTime)*100;}if(type ==1){return(double)reV[i].useTime /(endTime-startTime)*100;}}voidoutFac(){printf("Facility Utilization\n");printf("Type # Minutes %% Used\n");printf("-------------------------\n");int i;for(i =0; i < opV.size();++i){printf("Room %2d %7d %7.2lf\n",i+1, opV[i].useTime,outUsed(i,0));}for(i =0; i < reV.size();++i){printf("Bed %2d %7d %7.2lf\n",i+1, reV[i].useTime,outUsed(i,1));}}intmain(){int i, j;while(scanf("%d%d%d%d%d%d%d",&oproomNum,&reroomNum,&startTime,&transTime,&preop,&prere,&patiNum)==7){ v.clear(); opV.clear(); reV.clear(); pq =priority_queue<PrioItem>(); startTime = startTime *60; endTime = startTime;for(i =0; i < oproomNum;++i){ Room m; m.use =false; m.useTime =0; opV.push_back(m);}for(i =0; i < reroomNum;++i){ Room m; m.use =false; m.useTime =0; m.endTime =0; reV.push_back(m);}for(i =0; i < patiNum;++i){ Patient p;scanf("%s", p.name);scanf("%d%d",&p.opTime,&p.reTime); v.push_back(p);}oper();outPatient();printf("\n");outFac();printf("\n");}return0;}