涉及知识
- 1125 贪心
- 1126 DFS判连通（并查集、BFS也可）
- 1127 二叉树BFS（zig-zag）
- 1129 利用set排序（避免n次重排）
1130 二叉树建树、中序遍历、string（erase、pop_back）
1124 Raffle for Weibo Followers (20 分)
利用set不重复的性质、find函数。
#include <cstdio>
#include <set>
#include <string>
#include <vector>
using namespace std;
set<string> winners;
vector<string> res;
char forwards[1010][21];
int main() {
int mm, n_skip, win1;
scanf("%d%d%d", &mm, &n_skip, &win1);
for (int i = 1; i <= mm; ++i)
scanf("%s", forwards[i]);
int curr = win1;
while (curr <= mm) {
while (winners.find(forwards[curr]) != winners.end())
curr++;
winners.insert(forwards[curr]);
res.emplace_back(forwards[curr]);
curr += n_skip;
}
if (winners.empty()) {
printf("Keep going...\n");
} else {
for (auto item: res) {
puts(item.data());
}
}
return 0;
}
1125 Chain the Ropes (25 分)
两段绳子每次连结，它们的长度都要折半。越早选中的绳子，折半次数越多。
因此，要让最后绳长最长，就要让长绳子少折半（两个较短绳连接折半后，一定还是剩余绳子中最短的！）。
策略：从小到大排序，按序连结。
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int nn;
scanf("%d", &nn);
vector<double> ropes;
double temp;
for (int i = 0; i < nn; ++i) {
scanf("%lf", &temp);
ropes.emplace_back(temp);
}
sort(ropes.begin(), ropes.end());
double res = ropes[0];
int ii = 1;
while (ii < nn) {
res = (res + ropes[ii++]) / 2;
}
printf("%d\n", int(res));
return 0;
}
1126 Eulerian Path (25 分)
- 输入时，建图并计算各结点的度。
- 判连通。（DFS、并查集、BFS均可）
- 按照定义判断即可。
#include <cstdio>
using namespace std;
bool graph[501][501] = {false}, visited[501] = {false};
int deg[501] = {0}, nn, mm;
void DFS(int src) {
visited[src] = true;
for (int i = 1; i <= nn; ++i) {
if (!visited[i] && graph[src][i])
DFS(i);
}
}
int main() {
int v1, v2;
scanf("%d%d", &nn, &mm);
for (int i = 0; i < mm; ++i) {
scanf("%d%d", &v1, &v2);
graph[v1][v2] = graph[v2][v1] = true;
deg[v1]++, deg[v2]++;
}
DFS(1);
bool connected = true;
for (int i = 1; i <= nn; ++i) {
if (!visited[i]) {
connected = false;
break;
}
}
int cntOdd = 0;
for (int i = 1; i <= nn; ++i) {
printf("%d", deg[i]);
printf(i == nn ? "\n" : " ");
if (deg[i] % 2) cntOdd++;
}
if (!connected) puts("Non-Eulerian");
else if (cntOdd == 0) puts("Eulerian");
else if (cntOdd == 2) puts("Semi-Eulerian");
else puts("Non-Eulerian");
return 0;
}
1127 ZigZagging on a Tree (30 分)
- 由中序、后序序列建树，记录各深度结点数量。
- 层序遍历，保存层序序列。
- 按照结点深度 （奇、偶），顺序/逆序的输出层序序列中的该层。
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
struct Node {
int key, depth;
Node *lchild, *rchild;
};
int in_order[31], post_order[31], level_cnt[31] = {0};
vector<int> zz_order;
Node *createBTree(int in_st, int in_ed, int post_st, int post_ed, int depth) {
if (in_st > in_ed || post_st > post_ed) return NULL;
if (in_st == in_ed || post_st == post_ed) {
level_cnt[depth]++;
return new Node{in_order[in_st], depth, NULL, NULL};
}
Node *root = new Node;
int rkey = post_order[post_ed], 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->depth = depth;
root->lchild = createBTree(in_st, pos - 1, post_st, post_st + lsize - 1, depth + 1);
root->rchild = createBTree(pos + 1, in_ed, post_st + lsize, post_ed - 1, depth + 1);
level_cnt[depth]++;
return root;
}
void LevelOrder(Node *root) {
queue<Node *> mq;
mq.push(root);
zz_order.emplace_back(root->key);
while (!mq.empty()) {
Node *curr = mq.front();
mq.pop();
if (curr->lchild) {
mq.push(curr->lchild);
zz_order.emplace_back(curr->lchild->key);
}
if (curr->rchild) {
mq.push(curr->rchild);
zz_order.emplace_back(curr->rchild->key);
}
}
}
int main() {
int nn;
scanf("%d", &nn);
for (int i = 0; i < nn; ++i) scanf("%d", &in_order[i]);
for (int i = 0; i < nn; ++i) scanf("%d", &post_order[i]);
Node *root = createBTree(0, nn - 1, 0, nn - 1, 1);
LevelOrder(root);
int curr = 0;
for (int i = 1; level_cnt[i]; ++i) {
if (i % 2 == 0) { // l->r
for (int j = 0; j < level_cnt[i]; ++j) {
printf("%d", zz_order[curr]);
printf(curr < nn - 1 ? " " : "\n");
curr++;
}
} else { //r->l
int t = curr;
for (int j = level_cnt[i] - 1; j >= 0; --j) {
printf("%d", zz_order[t + j]);
printf(curr < nn - 1 ? " " : "\n");
curr++;
}
}
}
return 0;
}
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
1128 N Queens Puzzle (20 分)
用不着保存整个棋盘！！！
对角线上位置的表示（diagonal）：行号差的绝对值 == 列号差的绝对值
⚠️Nov. 1st二刷：若用abs函数，头文件用cstdlib，而不是cmath。
#include <cstdio>
#include <cmath>
void judgeSolution() {
int nn;
scanf("%d", &nn);
int board[1001];
bool res = true;
for (int i = 0; i < nn; ++i) {
scanf("%d", &board[i]);
if (res)
for (int j = 0; j < i; ++j) {
if (board[j] == board[i] || (fabs(i - j) == fabs(board[i] - board[j]))) {
res = false;
break;
}
}
}
puts(res ? "YES" : "NO");
}
int main() {
int tt;
scanf("%d", &tt);
for (int i = 0; i < tt; ++i) {
judgeSolution();
}
return 0;
}
1129 Recommendation System (25 分)
- 每次加入新元素就重排，复杂度将达到O(n^2 log n)，由于超时，仅16分！！！
- 应该利用set的插入、删除仅O(n log n)的特性，重载Item的小于号，注意另外保存当前的cnts数组，供
res.find(Item{temp, cnts[temp]})使用，删除再插入 来更新set中记录（set中元素不可修改）！！！
#include <cstdio>
#include <set>
using namespace std;
struct Item {
int id, cnt;
bool operator<(const Item &i2) const {
if (cnt != i2.cnt) return cnt > i2.cnt;
return id < i2.id;
}
};
int cnts[50001] = {0};
set<Item> res;
int main() {
int nquery, max_k, temp;
scanf("%d%d", &nquery, &max_k);
scanf("%d", &temp);
cnts[temp]++;
res.insert(Item{temp, cnts[temp]});
for (int i = 1; i < nquery; ++i) {
scanf("%d", &temp);
printf("%d:", temp);
int kk = 0;
for (auto item:res) {
printf(" %d", item.id);
kk++;
if (kk == max_k) {
printf("\n");
break;
}
}
if (kk < max_k) printf("\n");
auto _find_ = res.find(Item{temp, cnts[temp]});
if (_find_ != res.end()) {
res.erase(_find_);
}
cnts[temp]++;
res.insert(Item{temp, cnts[temp]});
}
return 0;
}
- NOV 3 update: set的erase可以直接erase（key）
#include <cstdio>
#include <set>
using namespace std;
struct Commodity {
int id, cnt = 1;
bool operator<(const Commodity &c2) const {
return cnt != c2.cnt ? cnt > c2.cnt : id < c2.id;
}
};
int main() {
int nq, max_rec, cnts[50001] = {0}, temp;
scanf("%d%d", &nq, &max_rec);
set<Commodity> rec_list;
for (int i = 0; i < nq; ++i) {
scanf("%d", &temp);
if(i > 0) {
printf("%d:", temp);
int j = 0;
for(auto &item: rec_list) {
printf(" %d", item.id);
if(++j == max_rec) break;
}
puts("");
}
rec_list.erase(Commodity{temp, cnts[temp]});
cnts[temp]++;
rec_list.insert(Commodity{temp, cnts[temp]});
}
return 0;
}
1130 Infix Expression (25 分)
中缀表达式
- 二叉树建树、中序遍历（给孩子不为空的结点加括号）
- string（字符/字符串连结 +=）
- string erase（0）、pop_back（）去除最外面一层括号
- ⚠️去括号要特判树仅有一个结点的情况
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;
struct Node {
string data;
int lchild, rchild;
} btree[21];
int nn;
string res;
void inorder(int root) {
if (root == -1) return;
bool _embrace = (btree[root].lchild != -1 || btree[root].rchild != -1);
if (_embrace) res += '(';
if (btree[root].lchild != -1) {
inorder(btree[root].lchild);
}
res += btree[root].data;
if (btree[root].rchild != -1) {
inorder(btree[root].rchild);
}
if (_embrace) res += ')';
}
int main() {
int nn, v1, v2;
char temp_data[12];
bool isRoot[21];
fill(isRoot, isRoot + 21, true);
scanf("%d", &nn);
for (int i = 1; i <= nn; ++i) {
scanf("%s%d%d", temp_data, &v1, &v2);
btree[i] = Node{temp_data, v1, v2};
if (v1 != -1) isRoot[v1] = false;
if (v2 != -1) isRoot[v2] = false;
}
int root = -1;
for (int i = 1; i <= nn; ++i) {
if (isRoot[i]) {
root = i;
break;
}
}
inorder(root);
if (nn >= 2) {
res.erase(0, 1); //注意
res.pop_back();
}
puts(res.data());
return 0;
}
- NOV 3 update 原来写的太麻烦了 醉了
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;
struct Node {
string data;
int lc, rc;
} btree[21];
int root = 1;
void in_traverse(int curr) {
if (root != curr && btree[curr].rc != -1) printf("(");
if (btree[curr].lc != -1) in_traverse(btree[curr].lc);
printf("%s", btree[curr].data.data());
if (btree[curr].rc != -1) in_traverse(btree[curr].rc);
if (root != curr && btree[curr].rc != -1) printf(")");
}
int main() {
int nn;
bool isRoot[21];
fill(isRoot, isRoot + 21, true);
scanf("%d", &nn);
char str[12];
int lc, rc;
for (int i = 1; i <= nn; ++i) {
scanf("%s%d%d", str, &lc, &rc);
btree[i].data = str, btree[i].lc = lc, btree[i].rc = rc;
isRoot[lc] = isRoot[rc] = false;
}
while (!isRoot[root]) root++;
in_traverse(root);
return 0;
}
