基本过了一遍算法笔记，昨天晚上第一次刷近年的整套题。🌀台风天玩了大半天小尤非常愉快，略略略～～～
趁心情8错，选择的去年的秋季考试，据说去年的秋考比较难，一上来第一题狼人杀就被搞懵了。写的时候emmmm有心理准备，就感觉还好（考试估计心态要炸、没玩过狼人杀啊！！！
因为这次的代码对我来说算写的还不错，所以梳理一下～～～
20 25 25 30~~~
1148 Werewolf - Simple Version (20 分)
暴力穷举，第一层是任取两个为狼人，第二层是任取两个作为liar（一个从狼人里取，一个从其他里取），若推不出矛盾，则找到一组解，结束。若穷举结束还没有合理的解，No Solution。这两层分别写成了一个函数，在第一层穷举中调用第二层穷举的函数。
#include <cstdio>
using namespace std;
int claims[101][2], nn; // claims: + 1/- -1, index
bool checkLiars(int l1, int l2, int w1, int w2) {
int identity[101] = {0};
identity[w1] = identity[w2] = -1;
for (int i = 1; i <= nn; ++i) {
int flag = (i == l1 || i == l2) ? -1 : 1, obj = claims[i][1];
if (flag * claims[i][0] == -1 && obj != w1 && obj != w2) {
return false;
}
if (identity[obj] == 0)
identity[obj] = flag * claims[i][0];
else if (identity[obj] != flag * claims[i][0])
return false;
}
return true;
}
bool judgeWerewolf(int w1, int w2) {
// w1/w2 is a liar
for (int i = 1; i <= nn; ++i) {
if (i == w1 || i == w2) continue;
// i is a liar
if (checkLiars(w1, i, w1, w2)) return true;
if (checkLiars(w2, i, w1, w2)) return true;
}
return false;
}
int main() {
scanf("%d", &nn);
char ch;
for (int i = 1; i <= nn; ++i) {
scanf("\n%c%d", &ch, &claims[i][1]);
if (ch == '+') claims[i][0] = 1;
else claims[i][0] = -1;
}
for (int i = 1; i < nn; ++i) { // 2 wolves
for (int j = i + 1; j <= nn; ++j) {
if (judgeWerewolf(i, j)) {
printf("%d %d\n", i, j);
return 0;
}
}
}
puts("No Solution");
return 0;
}
1149 Dangerous Goods Packaging (25 分)
一眼看上去incompatible goods以为是POJ2492 A Bug’s Life这样二分图染色的，快写完了发现不是，立刻不知所措😢……然后就想，不管它复杂度了，就用STL暴力吧！！！map套set一上，就这么AC了。。。。。。
#include <cstdio>
#include <map>
#include <set>
using namespace std;
int npair, nlist;
map<int, set<int>> pairs;
int main() {
scanf("%d%d", &npair, &nlist);
int p1, p2;
for (int i = 0; i < npair; i++) {
scanf("%d%d", &p1, &p2);
pairs[p1].insert(p2);
pairs[p2].insert(p1);
}
for (int i = 0; i < nlist; ++i) {
int cnt, id;
bool flag = true;
set<int> list;
scanf("%d", &cnt);
for (int j = 0; j < cnt; ++j) {
scanf("%d", &id);
list.insert(id);
}
for (auto item:list) {
if (!flag) break;
if (pairs[item].empty()) continue;
for (auto item1:pairs[item]) {
if (list.find(item1) != list.end()) {
flag = false;
break;
}
}
}
printf(flag ? "Yes\n" : "No\n");
}
return 0;
}
1150 Travelling Salesman Problem (25 分)
一看这么长的题面，开始慌了。看完？？？好像就是普通的按着题里流程走。。。。。。
- 路径连通吗？
不连通则Not a TS cycle，且dist为NA，结束。
若连通，下一步。 - 路径是连通的，累加计算dist，它首尾一样吗？
不一样，Not a TS cycle。
一样，下一步。 - 每个城市都到过吗？
有的城市没到过，Not a TS cycle。
都到过，下一步。 - 每个城市仅到了一次吗？（⚠️除了首尾：2次）
是， TS simple cycle。
否，TS cycle。
找dist最小的连通路径，结束。
#include <cstdio>
#include <vector>
using namespace std;
int graph[201][201] = {0};
int main() {
int ncity, mroad, kpath;
scanf("%d%d", &ncity, &mroad);
int c1, c2, weight;
for (int i = 0; i < mroad; ++i) {
scanf("%d%d%d", &c1, &c2, &weight);
graph[c1][c2] = graph[c2][c1] = weight;
}
scanf("%d", &kpath);
int short_ts_index = -1, shortest = 0x3fffffff;
for (int i = 1; i <= kpath; ++i) {
int nc, kind = -1;
// kind 0 simple tsc, 1 tsc, 2 c not ts,
scanf("%d", &nc);
if (nc <= ncity) kind = 2;
vector<int> path;
int curr;
for (int j = 0; j < nc; ++j) {
scanf("%d", &curr);
path.emplace_back(curr);
}
if (kind == -1 && path[0] != path[nc - 1]) kind = 2;
int dist = 0;
bool visited[201] = {false}, un = false, repeat = false;
visited[path[0]] = true;
for (int k = 0; k < nc - 1; ++k) {
if (graph[path[k]][path[k + 1]]) {
dist += graph[path[k]][path[k + 1]];
if (!visited[path[k + 1]]) visited[path[k + 1]] = true;
else if (k + 1 != nc - 1) repeat = true;
} else {
un = true;
kind = 2;
break;
}
}
if (kind != 2) {
if (path[0] != path[nc - 1]) kind = 2;
else {
for (int j = 1; j <= ncity; ++j) {
if (!visited[j]) {
kind = 2;
break;
}
}
if (kind != 2) {
if (repeat) kind = 1;
else kind = 0;
}
}
}
printf("Path %d: ", i);
if (un) printf("NA ");
else {
printf("%d ", dist);
if (kind != 2 && dist < shortest) {
shortest = dist;
short_ts_index = i;
}
}
switch (kind) {
case 0:
puts("(TS simple cycle)");
break;
case 1:
puts("(TS cycle)");
break;
case 2:
puts("(Not a TS cycle)");
break;
}
}
if (short_ts_index == -1) printf("Shortest Dist(NA) = NA\n");
else
printf("Shortest Dist(%d) = %d\n", short_ts_index, shortest);
return 0;
}
1151 LCA in a Binary Tree (30 分)
这题是昨天自我感觉最好的一道题 。就是不知道如果真在考场上，还能不能写成这个亚子。
-
建树
因为需要从孩子结点找祖先结点，所以在Node中加入Node* father（双向的二叉链表），在利用先序序列、中序序列建树时，就将lchild，rchild指向孩子，father指针指向父亲。
⚠️当孩子结点存在时，才root->child->father = root。（小心空指针！！！ -
查找结点，search用了递归的写法
-
找最深的共同祖先
这里利用了栈，从当前结点一层一层将祖先入栈。
那么两个栈的栈顶一定是相同的。
若栈顶相同，则出栈，一直到栈顶不同为止。
最后一个相同的栈顶元素则为最深公共祖先。
#include <cstdio>
#include <stack>
using namespace std;
struct Node {
int key;
Node *lchild = NULL, *rchild = NULL, *father = NULL;
};
int mpair, nn, in_order[10001], pre_order[10001];
Node *createBtree(int in_st, int in_ed, int pre_st, int pre_ed) {
if (in_st > in_ed || pre_st > pre_ed) return NULL;
Node *root = new Node;
int rkey = pre_order[pre_st], pos = -1;
for (int i = in_st; i <= in_ed; ++i) {
if (in_order[i] == rkey) {
pos = i;
break;
}
}
int lsize = pos - in_st;
root->key = rkey;
root->lchild = createBtree(in_st, pos - 1, pre_st + 1, pre_st + lsize);
root->rchild = createBtree(pos + 1, in_ed, pre_st + lsize + 1, pre_ed);
if (root->lchild) root->lchild->father = root;
if (root->rchild) root->rchild->father = root;
return root;
}
Node *search(Node *root, int x) {
if (root == NULL) return NULL;
if (root->key == x) {
return root;
}
Node *res = search(root->lchild, x);
if (res != NULL) return res;
return search(root->rchild, x);
}
int main() {
scanf("%d%d", &mpair, &nn);
for (int i = 0; i < nn; ++i) {
scanf("%d", &in_order[i]);
}
for (int i = 0; i < nn; ++i) {
scanf("%d", &pre_order[i]);
}
Node *root = createBtree(0, nn - 1, 0, nn - 1);
for (int j = 0; j < mpair; ++j) {
int n1, n2;
scanf("%d%d", &n1, &n2);
Node *p1 = search(root, n1), *p2 = search(root, n2);
if (!p1 && !p2) printf("ERROR: %d and %d are not found.\n", n1, n2);
else if (!p1) printf("ERROR: %d is not found.\n", n1);
else if (!p2) printf("ERROR: %d is not found.\n", n2);
else {
if (n1 == n2) {
printf("%d is an ancestor of %d.\n", n1, n2);
continue;
}
stack<int> fathers1, fathers2;
Node *temp1 = p1, *temp2 = p2;
while (temp1 != NULL) {
fathers1.push(temp1->key);
temp1 = temp1->father;
}
while (temp2 != NULL) {
fathers2.push(temp2->key);
temp2 = temp2->father;
}
int curr_a;
while (!fathers1.empty() && !fathers2.empty()) {
if (fathers1.top() == fathers2.top()) {
curr_a = fathers1.top();
fathers1.pop();
fathers2.pop();
} else break;
}
if (curr_a == n1) {
printf("%d is an ancestor of %d.\n", n1, n2);
} else if (curr_a == n2) {
printf("%d is an ancestor of %d.\n", n2, n1);
} else printf("LCA of %d and %d is %d.\n", n1, n2, curr_a);
}
}
return 0;
}
