⚠️不要轻易预分配！
这个错误找了俩小时。。。
- 定义时声明过vector大小，之后直接给vec[i]赋值就好！！
- 没有预先分配，用emplace_back （push_back）!!!
对string等c++容器也适用。。。
❌❌❌❌❌❌
改正
1140 Look-and-say Sequence (20 分)
写这题时有个大胆的想法💡：应该只有0 - 9输入，第二个数二分一波……直接输出答案……
😝直接写也是简单的，两个string♻️用，注意最后一种数字和它的个数，并没有在for遍历内加到新字串中，遍历完后记得加上它～
#include <string>
#include <iostream>
using namespace std;
int main() {
int nn;
string str, desc_str;
cin >> str >> nn;
while (--nn) {
char curr_ch = str[0];
int cnt = 1;
for (int i = 1; i < int(str.length()); ++i) {
if (str[i] != curr_ch) {
desc_str += curr_ch;
desc_str += char(cnt + '0');
curr_ch = str[i];
cnt = 1;
} else cnt++;
}
desc_str += curr_ch;
desc_str += char(cnt + '0');
str = desc_str;
desc_str = "";
}
cout << str << endl;
return 0;
}
1141 PAT Ranking of Institutions (25 分)
-
再次强调，vector预分配空间和push_back/emplace_back不能混用，干脆就别预分配空间啦！预分配和直接按下标赋值是一路的。。。
- TWS is the total weighted score which is defined to be the integer part of ScoreB/1.5 + ScoreA + ScoreT*1.5, where ScoreX is the total score of the testees belong to this institution on level X; and Ns is the total number of testees who belong to this institution.
取integer part对浮点数进行强转就好，或者只输出整数位（如果还按浮点数存记得排序时强转。。。所以还是先强转为int再排序好。
-
若要浮点数四舍五入，➕0.5再强转为int
另外，严格按题目对score的定义，应该是⬇️这样，（下午不知道写了几版
-
先算各校A、B、T分级别的总分，在✖️系数取整
#include <cstdio>
#include <string>
#include <cstring>
#include <unordered_map>
#include <cctype>
#include <vector>
#include <algorithm>
using namespace std;
unordered_map<string, pair<double, int>> summary;
struct Institution {
string name;
int score, num;
bool operator<(const Institution &i2) const {
if (score != i2.score) return score > i2.score;
if (num != i2.num) return num < i2.num;
return name < i2.name;
}
};
int main() {
int nn;
scanf("%d", &nn);
char temp_id[10], temp_inst[10];
int temp_score;
for (int i = 0; i < nn; ++i) {
scanf("%s%d%s", temp_id, &temp_score, temp_inst);
for (int j = 0; j < strlen(temp_inst); ++j) {
if (isupper(temp_inst[j])) temp_inst[j] += ('a' - 'A');
}
double rate;
switch (temp_id[0]) {
case 'A':
rate = 1.0;
break;
case 'T':
rate = 1.5;
break;
case 'B':
rate = 1 / 1.5;
break;
}
summary[temp_inst].first += temp_score * rate;
summary[temp_inst].second++;
}
int n_inst = summary.size();
vector<Institution> res;
for (auto &item: summary) {
res.emplace_back(Institution{item.first, int(item.second.first), item.second.second});
}
sort(res.begin(), res.end());
printf("%d\n", n_inst);
int rank = 0, score = 0x3fffffff;
for (int i = 0; i < n_inst; ++i) {
if (res[i].score < score) {
rank = i + 1;
score = res[i].score;
}
printf("%d %s %d %d\n", rank, res[i].name.data(), score, res[i].num);
}
return 0;
}
1142 Maximal Clique (25 分)
严格照定义来就好！
- 思路：
- 先判断给的这一组是不是一个clique（bool flag）。
- 若是，继续判断有没有clique之外的点和clique内所有点都直接相连（bool more），有则不是最大团，无则是最大团。
- 复杂度挺高的，为了稍微快一点，用vector和bool in_clique[]存了clique成员，sort一波，避免两次check一对点是否相连。（不知有没有快emmmmm
判断有无更多点可以放入clique：只要找出一个点和clique内所有点都直接相连就能说明不是最大团了。
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
bool graph[201][201] = {false};
int main() {
int nn, mm, nq, t1, t2;
scanf("%d%d", &nn, &mm);
for (int i = 0; i < mm; ++i) {
scanf("%d%d", &t1, &t2);
graph[t1][t2] = graph[t2][t1] = true;
}
scanf("%d", &nq);
for (int i = 0; i < nq; ++i) {
bool in_clique[201] = {false};
vector<int> clique;
int cnt, v;
scanf("%d", &cnt);
for (int j = 0; j < cnt; ++j) {
scanf("%d", &v);
clique.emplace_back(v);
in_clique[v] = true;
}
sort(clique.begin(), clique.end());
bool flag = true;
for (int k = 0; flag && k < cnt; k++) {
for (int j = k + 1; j < cnt; ++j) {
if (!graph[clique[k]][clique[j]]) {
flag = false;
break;
}
}
}
if (!flag) {
puts("Not a Clique");
continue;
}
bool more = false;
for (int r = 1; !more && r <= nn; ++r) {
if (!in_clique[r]) {
int count = 0;
for (auto item: clique) {
if (graph[r][item])
count++;
}
if (cnt == count) more = true;
}
}
puts(more ? "Not Maximal" : "Yes");
}
return 0;
}
1143 Lowest Common Ancestor (30 分)
- 首先建树，这次突然意识到，一路搜索BST某结点的时候经过的就是这个结点的所有祖先了（祖先也包括它自身），所以建树的时候没必要存father指针域，反正都还要search的……
- 递归search的时候用vector记录下一路搜索走过的结点。搜索后，若都存在，比较u和v经过的路就好，“分叉”前面的一个就是LCA。
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct Node {
int key;
Node *lchild = NULL, *rchild = NULL;
};
int _pre[10001], _in[10001], nn, mm;
Node *createTree(int pst, int ped, int ist, int ied) {
if (pst > ped || ist > ied) return NULL;
if (pst == ped && ist == ied)
return new Node{_pre[pst], NULL, NULL};
int rk = _pre[pst], pos = ist, lsize;
while (_in[pos] != rk) pos++;
lsize = pos - ist;
Node *root = new Node;
root->key = rk;
root->lchild = createTree(pst + 1, pst + lsize, ist, pos - 1);
root->rchild = createTree(pst + lsize + 1, ped, pos + 1, ied);
return root;
}
vector<int> path;
Node *search_path(Node *root, int xx) {
if (root == NULL) return NULL;
if (root->key == xx) {
path.emplace_back(xx);
return root;
}
path.emplace_back(root->key);
if (xx < root->key) {
return search_path(root->lchild, xx);
} else {
return search_path(root->rchild, xx);
}
}
int main() {
scanf("%d%d", &mm, &nn);
int v, uu, vv;
for (int i = 0; i < nn; ++i) {
scanf("%d", &_pre[i]);
_in[i] = _pre[i];
}
sort(_in, _in + nn);
Node *root = createTree(0, nn - 1, 0, nn - 1);
for (int i = 0; i < mm; ++i) {
scanf("%d%d", &uu, &vv);
Node *U_pointer = search_path(root, uu);
vector<int> pu = path;
path.clear();
Node *V_pointer = search_path(root, vv);
vector<int> pv = path;
path.clear();
if (!U_pointer || !V_pointer) {
printf("ERROR: ");
if (!U_pointer && !V_pointer)
printf("%d and %d are not found.\n", uu, vv);
else printf("%d is not found.\n", (U_pointer ? vv : uu));
continue;
}
int ii = 0, _min = min(pu.size(), pv.size());
while (ii < _min) {
if (pu[ii] != pv[ii]) break;
ii++;
}
int aa = pu[ii - 1];
if (aa != uu && aa != vv) {
printf("LCA of %d and %d is %d.\n", uu, vv, aa);
} else if (uu == aa)
printf("%d is an ancestor of %d.\n", uu, vv);
else printf("%d is an ancestor of %d.\n", vv, uu);
}
return 0;
}
网友评论