⚠️不要轻易预分配！

这个错误找了俩小时。。。

• 定义时声明过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;
}