## 【UVA-814】The Letter Carrier’s Rounds【紫书】

【UVA-814】The Letter Carrier’s Rounds【紫书】

Solution:

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <map>
#include <set>
// #define DBG

using namespace std;

map<string, int> mtaMap;
map<int, vector<string> > sendList;
set<string> personSet;
set<int> destSet;
vector<string> dest;
vector<string> message;
int gblCnt = 1;

int main(void) {
ios::sync_with_stdio(false);
// cin.tie(NULL);
string str, getter, getArea, sender, fromArea;
int n, t;
while (cin >> str && str[0] != '*') {
cin >> str;
mtaMap[str] = gblCnt++;
t = mtaMap[str];
cin >> n;
while (n--) {
cin >> str;
#ifdef DBG
cout << "crt : " << str << "\n";
#endif
}
}
while (cin >> str && str[0] != '*') {
sendList.clear();
message.clear();
dest.clear();
destSet.clear();
personSet.clear();
str[str.find("@")] = ' ';
stringstream ss;
ss << str;
ss >> sender >> fromArea;
#ifdef DBG
cout << sender << "---" << fromArea << "\n";
#endif
while (cin >> str && str[0] != '*') {
str[str.find("@")] = ' ';
stringstream ss;
ss << str;
ss >> getter >> getArea;
#ifdef DBG
cout << getter << "---" << getArea << "\n";
cout << "MAP : " << getArea << " - " << mtaMap[getArea] << "\n";
#endif
if (personSet.find(getter) == personSet.end()) {
personSet.insert(getter);
sendList[mtaMap[getArea]].push_back(getter);
}
if (destSet.find(mtaMap[getArea]) == destSet.end()) {
dest.push_back(getArea);
destSet.insert(mtaMap[getArea]);
}
}
while (getline(cin, str) && str[0] != '*') message.push_back(str);
for (int i = 0; i < dest.size(); i++) {
bool flag = false;
cout << "Connection between " << fromArea << " and " << dest[i] << "\n";
cout << "     HELO " << fromArea << "\n";
cout << "     250\n";
cout << "     MAIL FROM:<" << sender << "@" << fromArea << ">\n";
cout << "     250\n";
vector<string> &tmpList = sendList[mtaMap[dest[i]]];
for (int j = 0; j < tmpList.size(); j++) {
cout << "     RCPT TO:<" << tmpList[j] << "@" << dest[i] << ">\n";
cout << "     550\n";
} else {
cout << "     250\n";
flag = true;
}
}
if (flag) {
cout << "     DATA\n";
cout << "     354\n";
for (int j = 1; j < message.size(); j++)
cout << "     " << message[j] << "\n";
cout << "     .\n";
cout << "     250\n";
}
cout << "     QUIT\n";
cout << "     221\n";
}
}
return 0;
}


## 【UVA-1592】Database【紫书】

【UVA-1592】Database【紫书】

Solution:

#include <iostream>
#include <cstring>
#include <map>
#include <set>
// #define DBG

using namespace std;

const int SIZE = 80;
struct String {
char str[SIZE];
bool operator < (const String & s) const {
int i;
for (i = 0; str[i] && s.str[i]; i++)
if (str[i] != s.str[i]) return str[i] < s.str[i];
if (str[i] && !s.str[i]) return false;
if (!str[i] && !s.str[i]) return false;
return true;
}
} tmpStr, data[10000][10];
struct Pair {
int a, b;
bool operator < (const Pair & p) const {
if (a != p.a) return a < p.a;
return b < p.b;
}
};
map<String, int> strMap;
map<Pair, int> vis;
int gblCnt;         //global count

inline void init() {
strMap.clear();
gblCnt = 1;
}

int main(void) {
int n, m;
while (~scanf("%d%d", &n, &m)) {
while (getchar() != '\n');
init();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m - 1; j++) {
scanf("%[^,]%*c", tmpStr.str);
if (!strMap[tmpStr]) strMap[tmpStr] = gblCnt++;
data[i][j] = tmpStr;
}
scanf("%[^\n]%*c", tmpStr.str);
if (!strMap[tmpStr]) strMap[tmpStr] = gblCnt++;
data[i][m - 1] = tmpStr;
}
bool flag = true;
for (int i = 0; flag && i < m; i++) {
for (int j = i + 1; flag && j < m; j++) {
vis.clear();
for (int k = 0; flag && k < n; k++) {
Pair tmp = {strMap[data[k][i]], strMap[data[k][j]]};
#ifdef DBG
printf("%d : %s\n", strMap[data[k][i]], data[k][i].str);
printf("%d : %s\n\n", strMap[data[k][j]], data[k][j].str);
printf("%d : pair()\n", vis[tmp]);
#endif
if (vis[tmp]) {
printf("NO\n");
printf("%d %d\n", vis[tmp], k + 1);
printf("%d %d\n", i + 1, j + 1);
flag = false;
} else {
vis[tmp] = k + 1;
}
}
}
}
if (flag) printf("YES\n");
}
return 0;
}


## 【UVA-400】Unix ls【紫书】

【UVA-400】Unix ls【紫书】

Solution:

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

using namespace std;

vector<string> files;

int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
int m, n, r, numInLine;
string str;
while (cin >> n) {
files.clear();
m = 0;
for (int i = 0; i < n; i++) {
cin >> str;
files.push_back(str);
if (str.size() > m) m = str.size();
}
sort(files.begin(), files.end());
numInLine = 60 / (m + 2);
if (60 % (m + 2) >= m) numInLine++;
r = (n + numInLine - 1) / numInLine;
cout << "------------------------------------------------------------\n";
for (int i = 0; i < r; i++) {
for (int j = i; j < files.size(); j += r) {
cout << files[j];
int cnt = (j + r < files.size() ? m - files[j].size() + 2 : 0);
while (cnt--) cout << ' ';
}
cout << "\n";
}
}
return 0;
}


## 【UVA-136】Ugly Numbers【bfs+priority_queue+set】

【UVA-136】Ugly Numbers【bfs+priority_queue+set】

Solution:

#include <iostream>
#include <queue>
#include <set>
// #define DBG

using namespace std;

typedef long long LL;
struct Num {
LL num;
bool operator<(const Num & n) const { return num > n.num; }
};
const int DEST = 1500;
set<int> vis;
LL dir[] = {2, 3, 5};

void bfs() {
Num crt = {1};
int cnt = 0;
priority_queue<Num> q;
q.push(crt);
vis.insert(1);
while (!q.empty()) {
crt = q.top();
q.pop();
cnt++;
#ifdef DBG
printf("crt : %d\n", crt.num);
#endif
if (cnt == DEST) {
printf("The 1500'th ugly number is %d.\n", crt.num);
return;
}
for (int i = 0; i < 3; i++) {
LL nxt = crt.num * dir[i];
if (vis.find(nxt) == vis.end()) {
q.push({nxt});
vis.insert(nxt);
}
}
}
}

int main(void) {
bfs();
return 0;
}


## 【UVA-540】Team Queue【紫书】【队列】

【UVA-540】Team Queue【紫书】【队列】

Solution:

#include <iostream>
#include <queue>
#include <map>
#include <cstring>
#include <string>

using namespace std;

const int SIZE = 1010;
queue<int> teams[SIZE];
queue<int> teamq;
map<int, int> teamType;
int teamCnt = 1;

inline void init() {
teamCnt = 1;
teamType.clear();
for (int i = 0; i < SIZE; i++)
while (!teams[i].empty()) teams[i].pop();
while (!teamq.empty()) teamq.pop();
}

void enqueue(int num) {
int team = teamType[num];
if (teams[team].empty()) teamq.push(team);
teams[team].push(num);
}

int dequeue() {
int team = teamq.front();
int ret = teams[team].front();
teams[team].pop();
if (teams[team].empty()) teamq.pop();
return ret;
}

int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
int t, n, num;
string op;
for (int k = 1; cin >> t && t; k++) {
cout << "Scenario #" << k << "\n";
init();
while (t--) {
cin >> n;
while (n--) {
cin >> num;
teamType[num] = teamCnt;
}
teamCnt++;
}
while (cin >> op && op[0] != 'S') {
if (op[0] == 'E') {
cin >> num;
enqueue(num);
} else if (op[0] == 'D') {
cout << dequeue() << endl;
}
}
cout << '\n';
}
return 0;
}


## 【UVA-12096】The SetStack Computer【紫书】

【UVA-12096】The SetStack Computer【紫书】

Solution：

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

using namespace std;

map<set<int>, int> idmap;
stack<set<int> > sets;
set<int> stop, ssec;
int gblid;

inline void check(const set<int> &s) {
if (!idmap[s]) idmap[s] = gblid++;
}

inline void init() {
idmap.clear();
while (!sets.empty()) sets.pop();
gblid = 1;
}

void popTwo() {
stop = sets.top();
sets.pop();
ssec = sets.top();
sets.pop();
}

int push() {
set<int> s;
check(s);
sets.push(s);
return 0;
}

int dup() {
set<int> s = sets.top();
sets.push(s);
return s.size();
}

int unionOp() {
popTwo();
for (set<int>::iterator ite = ssec.begin(); ite != ssec.end(); ite++)
stop.insert(*ite);
check(stop);
sets.push(stop);
return stop.size();
}

int interOp() {
popTwo();
set<int> s;
for (set<int>::iterator ite = ssec.begin(); ite != ssec.end(); ite++)
if (stop.find(*ite) != stop.end()) s.insert(*ite);
check(s);
sets.push(s);
return s.size();
}

popTwo();
set<int> s = ssec;
s.insert(idmap[stop]);
check(s);
sets.push(s);
return s.size();
}

int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
int t, n;
string op;
cin >> t;
while (t--) {
init();
cin >> n;
while (n--) {
cin >> op;
if (op == "PUSH") cout << push() << "\n";
else if (op == "DUP") cout << dup() << "\n";
else if (op == "UNION") cout << unionOp() << "\n";
else if (op == "INTERSECT") cout << interOp() << "\n";
}
cout << "***\n";
}
return 0;
}


## 【UVA-815】Flooded!【紫书】【浮点误差处理】

【UVA-815】Flooded!【紫书】【浮点误差处理】

Solution:

#include <iostream>
#include <algorithm>
#include <cmath>
// #define DBG

using namespace std;

const int LIM = 30 * 30 + 10;
const double AREA = 100;
const double EPS = 1e-6;
int data[LIM];

int main(void) {
int n, m, len, i;
double height, v;
for (int k = 1; ~scanf("%d%d", &n, &m) && n && m; k++) {
printf("Region %d\n", k);
len = n * m;
for (i = 0; i < len; i++) scanf("%d", data + i);
scanf("%lf", &v);
v = v / AREA + EPS;
sort(data, data + len);
for (i = 1; i < len; i++) {
v += data[i - 1];
height = v / i + (height < EPS ? -EPS : EPS);
#ifdef DBG
printf("height : %f\n", height);
#endif
if (height - data[i] <= EPS) break;
}
if (i == len) height = (v + data[i - 1]) / i + (height < EPS ? -EPS : EPS);
printf("Water level is %.2f meters.\n"
"%.2f percent of the region is under water.\n\n", height, i * 100.0 / len + (height < EPS ? -EPS : EPS));
}
return 0;
}


## 【UVA-12108】Extraordinarily Tired Students【紫书】

【UVA-12108】Extraordinarily Tired Students【紫书】

Solution:

#include <iostream>
#include <set>

using namespace std;

typedef unsigned long long ULL;
const int LIM = 11;
bool state[LIM];        // true is sleep
int minut[LIM], period[LIM], a[LIM], b[LIM], n, cnt;
set<ULL> vis;

inline ULL getHash(void) {
ULL ret = 0;
for (int i = 0; i < n; i++)
ret = ret * 100 + minut[i] * 10 + (state[i] ? 1 : 0);
return ret;
}

int main(void) {
int ans;
for (int k = 1; ~scanf("%d", &n) && n; k++) {
printf("Case %d: ", k);
ans = 1;
cnt = 0;
vis.clear();
for (int i = 0; i < n; i++) {
scanf("%d%d%d", a + i, b + i, minut + i);
period[i] = a[i] + b[i];
minut[i] %= period[i];
if (period[i] > a[i] || !minut[i]) {
state[i] = true;
cnt++;
}
}
vis.insert(getHash());
for (; cnt; ans++) {
int tmpcnt = 0;
for (int i = 0; i < n; i++) {
minut[i] = (minut[i] + 1) % period[i];
if ((minut[i] > a[i] || !minut[i]) && cnt > (n / 2)) state[i] = true;
else if (minut[i] && minut[i] <= a[i]) state[i] = false;
if (state[i]) tmpcnt++;
}
cnt = tmpcnt;
ULL tmp = getHash();
if (vis.find(tmp) != vis.end()) {
printf("-1\n");
break;
} else {
vis.insert(tmp);
}
}
if (!cnt) printf("%d\n", ans);
}
return 0;
}


## 【UVA-12412】A Typical Homework (a.k.a Shi Xiong Bang Bang Mang)

【UVA-12412】A Typical Homework (a.k.a Shi Xiong Bang Bang Mang)

Solution:

1）我下面的代码使用了链表的数据结构，使用数组来实现，让0号结点的下一个结点将是链表的开头，同时规定最后一个结点的下一个结点是0号结点，使用一个变量【我把它叫做last】表示尾结点在数组中的位置，使用另外一个变量【我叫做pos】表示目前最大使用到的数组位置，如果移除某个结点后，就把那个结点的位置加到一个vector或者queue里，表示数组中前面有位置已经失效，可以被新的数据覆盖了，每次插入结点先判断vector或queue里是否存放有已经失效的结点位置，如果有就优先放到数组中那个位置，如果没有则放在pos处，并将pos增加。这样链表实现方法在实际项目中不建议使用，由于是竞赛题目，为了减少不必要的申请内存时间消耗，可以这样实现。

2）这道题在精度上有坑点，数据会有浮点误差，将那几个浮点数加上一个精度值【经测设1e-4、 1e-5、 1e-6都是可行的】后就可以通过了。

3）Fast I/O，对于这道问题并不需要的，从最后结果来看，它的数据很水，0ms跑完，在有些竞赛程序中十分重要，特别是题目明确说明输入会很大的时候，这个时候可以通过：

ios::sync_with_stdio(false);

cin.tie(NULL);

C++实现：

#include <iostream>
#include <queue>
#include <string>
#include <set>
#include <cstring>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

const int LIM = 120;
const int SIZE = 4;
const int CLASSCNT = 20 + 1;
const double EPS = 1e-6;
struct Student {
string sid, name;
int cid;
int score[SIZE];
int rank, tot;
int nxt, pre;
};
struct Rank {
int idx, score;
bool operator < (const Rank & r) const { return score > r.score; }
};
Student list[LIM];
Rank val[LIM];
queue<int> emptyIdx;
set<string> exists;
vector<Student> ret;
enum {CH, MATH, EN, PRO, ALL};
int pos = 1, last = 0, rankLen, passedCnt[CLASSCNT][SIZE], overCnt[CLASSCNT][SIZE + 1], num[CLASSCNT] = {0}, sum[CLASSCNT][SIZE];

bool isSid(const string &str) {
return isdigit(str[0]);
}

bool add(const Student & stu) {
if (exists.find(stu.sid) != exists.end()) return false;
int p;
if (!emptyIdx.empty()) {
p = emptyIdx.front();
emptyIdx.pop();
} else {
p = pos++;
}
list[p] = stu;
for (int i = 0; i < SIZE; i++) list[p].tot += list[p].score[i];
list[last].nxt = p;
list[p].pre = last;
list[p].nxt = 0;
last = p;
exists.insert(stu.sid);
num[list[p].cid]++, num[0]++;
return true;
}

int del(const string &str) {
int cnt = 0, p;
if (isSid(str)) {
for (p = list[0].nxt; p; p = list[p].nxt)
if (list[p].sid == str) {
list[list[p].pre].nxt = list[p].nxt;
list[list[p].nxt].pre = list[p].pre;
if (p == last) last = list[p].pre;
emptyIdx.push(p);
exists.erase(list[p].sid);
num[list[p].cid]--, num[0]--;
return 1;
}
} else {
last = 0;
for (p = list[0].nxt; p; p = list[p].nxt)
if (list[p].name == str) {
list[list[p].pre].nxt = list[p].nxt;
list[list[p].nxt].pre = list[p].pre;
emptyIdx.push(p);
exists.erase(list[p].sid);
num[list[p].cid]--, num[0]--;
cnt++;
} else {
last = p;
}
}
return cnt;
}

void calRank(void) {
int rank = 1;
memset(passedCnt, 0, sizeof passedCnt);
memset(overCnt, 0, sizeof overCnt);
memset(sum, 0, sizeof sum);
rankLen = 0;
for (int p = list[0].nxt; p; p = list[p].nxt, rankLen++) {
val[rankLen].score = 0;
val[rankLen].idx = p;
int tmp = SIZE;
for (int i = 0; i < SIZE; i++) {
val[rankLen].score += list[p].score[i];
if (list[p].score[i] >= 60) passedCnt[0][i]++, passedCnt[list[p].cid][i]++;
else tmp--;
sum[0][i] += list[p].score[i];
sum[list[p].cid][i] += list[p].score[i];
}
overCnt[0][tmp]++, overCnt[list[p].cid][tmp]++;
}
sort(val, val + rankLen);
for (int i = 0; i < rankLen; i++) {
if (i && val[i].score != val[i - 1].score) rank = i + 1;
list[val[i].idx].rank = rank;
}
}
}

void query(const string &str) {
int p;
ret.clear();
if (isSid(str)) {
for (p = list[0].nxt; p; p = list[p].nxt) {
if (list[p].sid == str) {
ret.push_back(list[p]);
return;
}
}
} else {
for (p = list[0].nxt; p; p = list[p].nxt)
if (list[p].name == str) ret.push_back(list[p]);
}
}

inline void statics(void) {
}

cout << "Welcome to Student Performance Management System (SPMS).\n\n"
<< "2 - Remove\n"
<< "3 - Query\n"
<< "4 - Show ranking\n"
<< "5 - Show Statistics\n"
<< "0 - Exit\n\n";
}

int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.setf(ios::fixed);
cout.precision(2);
int op = 0;
Student tmp;
string str;
tmp.tot = 0;
while (cin >> op && op) {
if (op == 1) {
while (true) {
cout << "Please enter the SID, CID, name and four scores. Enter 0 to finish.\n";
cin >> tmp.sid;
if (tmp.sid == "0") break;
cin >> tmp.cid >> tmp.name;
for (int i = 0; i < SIZE; i++) cin >> tmp.score[i];
if (!add(tmp)) cout << "Duplicated SID.\n";
}
} else if (op == 2) {
while (true) {
cout << "Please enter SID or name. Enter 0 to finish.\n";
cin >> str;
if (str == "0") break;
int cnt = del(str);
cout << cnt << " student(s) removed.\n";
}
} else if (op == 3) {
while (true) {
cout << "Please enter SID or name. Enter 0 to finish.\n";
cin >> str;
if (str == "0") break;
query(str);
for (int i = 0; i < ret.size(); i++) {
cout << ret[i].rank << " "
<< ret[i].sid << " "
<< ret[i].cid << " "
<< ret[i].name;
for (int j = 0; j < SIZE; j++) cout << " " << ret[i].score[j];
cout << " " << ret[i].tot
<< " " << 1.0 * ret[i].tot / SIZE + EPS << "\n";
}
}
} else if (op == 4) {
cout << "Showing the ranklist hurts students' self-esteem. Don't do that.\n";
} else if (op == 5) {
cout << "Please enter class ID, 0 for the whole statistics.\n";
statics();
cin >> op;
cout << "Chinese\n"
<< "Average Score: " << 1.0 * sum[op][CH] / num[op] + EPS << "\n"
<< "Number of passed students: " << passedCnt[op][CH] << "\n"
<< "Number of failed students: " << num[op] - passedCnt[op][CH] << "\n\n"
<< "Mathematics" << "\n"
<< "Average Score: " << 1.0 * sum[op][MATH] / num[op] + EPS << "\n"
<< "Number of passed students: " << passedCnt[op][MATH] << "\n"
<< "Number of failed students: " << num[op] - passedCnt[op][MATH] << "\n\n"
<< "English\n"
<< "Average Score: " << 1.0 * sum[op][EN] / num[op] + EPS << "\n"
<< "Number of passed students: " << passedCnt[op][EN] << "\n"
<< "Number of failed students: " << num[op] - passedCnt[op][EN] << "\n\n"
<< "Programming\n"
<< "Average Score: " << 1.0 * sum[op][PRO] / num[op] + EPS << "\n"
<< "Number of passed students: " << passedCnt[op][PRO] << "\n"
<< "Number of failed students: " << num[op] - passedCnt[op][PRO] << "\n\n"
<< "Overall:\n"
<< "Number of students who passed all subjects: " << overCnt[op][4] << "\n"
<< "Number of students who passed 3 or more subjects: " << overCnt[op][3] + overCnt[op][4] << "\n"
<< "Number of students who passed 2 or more subjects: " << overCnt[op][2] + overCnt[op][3] + overCnt[op][4] << "\n"
<< "Number of students who passed 1 or more subjects: " << overCnt[op][1] + overCnt[op][2] + overCnt[op][3] + overCnt[op][4] << "\n"
<< "Number of students who failed all subjects: " << overCnt[op][0] << "\n\n";
}
}
}


Solution:

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int LIM = 10;
const int NIL = -1;
enum {EX, DC, DR, IC, IR};
struct Operation {
int t, val[LIM];
};
struct Node {
int r, c;
};
vector<Operation> ops;

int main(void) {
Operation tmp;
Node tnode;
char op[3];
int n, R, C, a;
for (int k = 1; ~scanf("%d%d", &R, &C) && R && C; k++) {
if (k - 1) putchar('\n');
ops.clear();
scanf("%d", &n);
while (n--) {
memset(tmp.val, NIL, sizeof(int) * LIM);
scanf("%s", op);
if (!strcmp(op, "EX")) tmp.t = EX;
else if (!strcmp(op, "DC")) tmp.t = DC;
else if (!strcmp(op, "DR")) tmp.t = DR;
else if (!strcmp(op, "IC")) tmp.t = IC;
else if (!strcmp(op, "IR")) tmp.t = IR;
if (tmp.t != EX) scanf("%d", &a);
else a = 4;
for (int i = 0; i < a; i++) scanf("%d", tmp.val + i);
ops.push_back(tmp);
}
scanf("%d", &n);
while (n--) {
scanf("%d%d", &tnode.r, &tnode.c);
Node bak = tnode;
bool flag = true;
int cnt;
for (int i = 0; i < ops.size(); i++) {
cnt = 0;
if (ops[i].t == EX) {
if (ops[i].val[0] == tnode.r && ops[i].val[1] == tnode.c)
tnode.r = ops[i].val[2], tnode.c = ops[i].val[3];
else if (ops[i].val[2] == tnode.r && ops[i].val[3] == tnode.c)
tnode.r = ops[i].val[0], tnode.c = ops[i].val[1];
} else {
for (int j = 0; j < LIM; j++) {
if (ops[i].val[j] == NIL) break;
if (ops[i].t == DC && ops[i].val[j] == tnode.c) {
flag = false;
break;
}
if (ops[i].t == DR && ops[i].val[j] == tnode.r) {
flag = false;
break;
}
if ((ops[i].t == DC || ops[i].t == IC) && ops[i].val[j] <= tnode.c) cnt++;
if ((ops[i].t == DR || ops[i].t == IR) && ops[i].val[j] <= tnode.r) cnt++;
}
if (!flag) {
printf("Cell data in (%d,%d) GONE\n", bak.r, bak.c);
break;
}
if (ops[i].t == DR) tnode.r -= cnt;
else if (ops[i].t == DC) tnode.c -= cnt;
else if (ops[i].t == IR) tnode.r += cnt;
else tnode.c += cnt;
}
}
if (flag) printf("Cell data in (%d,%d) moved to (%d,%d)\n", bak.r, bak.c, tnode.r, tnode.c);
}
}
return 0;
}