发布于：2024-08-30更新于：2024-10-03

PAT 甲级

1001 A+B Format

#include <iostream>
#include <string>
using namespace std;
int main() {
    int a, b;
    cin >> a >> b;
    int c = a + b;
    if (c < 0) {
        cout << '-';
        c = -c;
    }
    if (c >= 1000) {
        string t = to_string(c);
        int d = t.size() % 3;
        if(d) cout << t.substr(0, d) << ",";
        for (int i = d; i < t.size(); i += 3) {
            cout << t.substr(i, 3);
            if (i + 3 < t.size()) cout << ",";
        }
    } else cout << c;
    return 0;
}

柳婼的

#include <iostream>
#include <string>
using namespace std;
int main() {
    int a, b;
    cin >> a >> b;
    string s = to_string(a + b);
    int len = s.length();
    for (int i = 0; i < len; i++) {
        cout << s[i];
        if (s[i] == '-') continue;
        if ((i + 1) % 3 == len % 3 && i != len - 1) cout << ',';
    }
    return 0;
}

1002 A+B for Polynomials

#include <iostream>
using namespace std;
const int N = 1001;
double nums[N];
int main() {
    int n, a;
    double b;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a >> b;
        nums[a] = b;
    }
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a >> b;
        nums[a] += b;
    }
    int cnt = 0;
    for (int i = 1000; i >= 0; i--) {
        if (nums[i]) cnt++;
    }
    cout << cnt;
    for (int i = 1000; i >= 0; i--) {
        if (nums[i]) {
            printf(" %d %.1f", i, nums[i]);
        }
    }
    return 0;
}

1003 Emergency

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 501;
const int INF = 0x3f3f3f3f;
int vals[N], d[N], num[N], val[N];
bool visit[N];
vector<PII> g[N];
void djkstra(int s, int n) {
    fill(d, d + N, INF);
    d[s] = 0;
    val[s] = vals[s];
    num[s] = 1;
    for (int i = 0; i < n; i++) {
        int u = -1, mind = INF;
        for (int j = 0; j < n; j++) {
            if (!visit[j] && mind > d[j]) {
                u = j;
                mind = d[j];
            }
        }
        if (u == -1) return;
        visit[u] = true;
        for (int j = 0; j < g[u].size(); j++) {
            int v = g[u][j].first;
            int dis = g[u][j].second;
            if (!visit[v]) {
                if (d[u] + dis < d[v]) {
                    d[v] = d[u] + dis;
                    num[v] = num[u];
                    val[v] = val[u] + vals[v];
                } else if (d[u] + dis == d[v]) {
                    num[v] = num[v] + num[u];
                    val[v] = max(val[v], val[u] + vals[v]);
                }
            }
        }
    }
}

int main() {
    int n, m, c1, c2, u, v, w;
    cin >> n >> m >> c1 >> c2;
    for (int i = 0; i < n; i++) {
        cin >> vals[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    djkstra(c1, n);
    cout << num[c2] << " " << val[c2];
    return 0;
}

1004 Counting Leaves

bfs

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<int> trees[101];
void bfs(int u) {
    queue<int> q;
    q.push(u);
    while (!q.empty()) {
        int len = q.size();
        int t = 0;
        while (len--) {
            u = q.front();
            q.pop();
            for (int i = 0; i < trees[u].size(); i++) {
                q.push(trees[u][i]);
            }
            if (trees[u].empty()) t++;
        }
        cout << t;
        if (!q.empty()) cout << " ";
    } 
}
int main() {
    int n, m, id1, k, id2;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> id1 >> k;
        for (int j = 0; j < k; j++) {
            cin >> id2;
            trees[id1].push_back(id2);
        }
    }
    bfs(1);
    return 0;
}

dfs

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> trees[101];
int res[101], maxdepth;
void dfs(int u, int depth) {
    if (trees[u].size() == 0) {
        res[depth]++;
        maxdepth = max(maxdepth, depth);
    }
    for (int i = 0; i < trees[u].size(); i++) {
        dfs(trees[u][i], depth + 1);
    }
}
int main() {
    int n, m, id1, k, id2;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> id1 >> k;
        for (int j = 0; j < k; j++) {
            cin >> id2;
            trees[id1].push_back(id2);
        }
    }
    dfs(1, 0);
    for (int i = 0; i <= maxdepth; i++) {
        cout << res[i];
        if (i < maxdepth) cout << " ";
    }
    return 0;
}

1005 Spell It Right

#include <iostream>
#include <string>
using namespace std;
int main() {
    string str;
    cin >> str;
    string words[10] = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
    int res = 0;
    for (int i = 0; i < str.length(); i++) {
        res += str[i] - '0';
    }
    string res2 = to_string(res);
    for (int i = 0; i < res2.length(); i++) {
        cout << words[res2[i] - '0'];
        if (i < res2.length() - 1) cout << " ";
    }
    return 0;
}

#include <iostream>
#include <string>
using namespace std;
int main() {
    int n;
    cin >> n;
    string name, start, end, res1_name, res1_start = "23:59:59", res2_name, res2_end = "00:00:00";
    for (int i = 0; i < n; i++) {
        cin >> name >> start >> end;
        if (start < res1_start) {
            res1_name = name;
            res1_start = start;
        }
        if (end > res2_end) {
            res2_name = name;
            res2_end = end;
        }
    }
    cout << res1_name << " " << res2_name;
    return 0;
}

1007 Maximum Subsequence Sum

#include <iostream>
using namespace std;
const int INF = 0x3f3f3f3f;
int nums[10001], dp[10001];
int main() {
    int n;
    cin >> n;
    fill(dp, dp + n, -INF);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    dp[0] = nums[0];
    for (int i = 1; i < n; i++) {
        dp[i] = max(dp[i - 1] + nums[i], nums[i]);
    }
    int res = -INF, start = 0, end = n - 1, t = 0;
    for (int i = 0; i < n; i++) {
        if (res < dp[i]) {
            res = dp[i];
            end = i;
        }
    }
    if (res == 0) start = end;
    else if (res > 0) {
        for (int i = end; i >= 0; i--) {
            if (t < res) {
                t += nums[i];
                start = i;
            }
        }
    } else {
        res = 0;
        start = 0;
        end = n - 1;
    }
    cout << res << " " << nums[start] << " " << nums[end];
    return 0;
}

柳婼的

#include <iostream>
using namespace std;
int nums[100001];
int main() {
    int n;
    cin >> n;
    int left = 0, right = n - 1, res = -1, temp = 0, tempindex = 0;
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
        temp = temp + nums[i];
        if (temp < 0) {
            temp = 0;
            tempindex = i + 1;
        } else if (temp > res) {
            res = temp;
            left = tempindex;
            right = i;
        }
    }
    if (res < 0) res = 0;
    cout << res << " " << nums[left] << " " << nums[right];
    return 0;
}

1008 Elevator

#include <iostream>
using namespace std;
int main() {
    int n, pre = 0, now, res = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> now;
        if (now > pre) res += (now - pre) * 6 + 5;
        else res += (pre - now) * 4 + 5;
        pre = now;
    }
    cout << res;
    return 0;
}

1009 Product of Polynomials

#include <iostream>
using namespace std;
const int N = 1001;
double nums[N], res[N * N];
int main() {
    int k, a, cnt = 0;
    double b;
    cin >> k;
    for (int i = 0; i < k; i++) {
        cin >> a >> b;
        nums[a] = b;
    }
    cin >> k;
    for (int i = 0; i < k; i++) {
        cin >> a >> b;
        for (int j = 0; j < N; j++) {
            res[a + j] += b * nums[j];
        }
    }
    for (int i = 0; i < N * N; i++)
        if (res[i]) cnt++;
    cout << cnt;
    for (int i = N * N - 1; i >= 0; i--)
        if (res[i]) printf(" %d %.1f", i, res[i]);
    return 0;
}

1010 Radix

#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
LL convert(string s, int k) {
    LL sum = 0, idx = 0;
    for (int i = s.length() - 1; i >= 0; i--) {
        int t = isdigit(s[i]) ? s[i] - '0' : s[i] - 'a' + 10;
        sum += t * pow(k, idx++);
    }
    return sum;
}
LL find(string s, LL num) {
    char maxt = *max_element(s.begin(), s.end());
    LL low = isdigit(maxt) ? maxt - '0' + 1 : maxt - 'a' + 11;
    LL high = max(low, num);
    while (low <= high) {
        LL mid = low + high >> 1;
        LL t = convert(s, mid);
        if (t < 0 | t > num) high = mid - 1;
        else if (t == num) return mid;
        else low = mid + 1;
    }
    return -1;
}
int main() {
    string n1, n2;
    int tag, radix, res;
    cin >> n1 >> n2 >> tag >> radix;
    if (tag == 1) res = find(n2, convert(n1, radix));
    else res = find(n1, convert(n2, radix));
    if (res == -1) cout << "Impossible";
    else cout << res;
    return 0;
}

1011 World Cup Betting

#include <iostream>
using namespace std;
double fun(double a, double b, double c) {
    double res = 1;
    if (b >= a && b >= c) {
        cout << "T ";
        res *= b;
    } else if (a >= b && a >= c) {
        cout << "W ";
        res *= a;
    } else {
        cout << "L ";
        res *= c;
    }
    return res;
}
int main() {
    double a, b, c;
    double res = 1;
    for (int i = 0; i < 3; i++) {
        cin >> a >> b >> c;
        res *= fun(a * 0.65, b, c);
    }
    printf("%.2f", 2 * (res - 1));
    return 0;
}

1012 The Best Rank

#include <iostream>
#include <algorithm>
using namespace std;
struct student {
    int num, c, m, e;
    double a;
    student(int _num, int _c, int _m, int _e, double _a) {
        num = _num, c = _c, m = _m, e = _e, a = _a;
    }
    student(){};
} nums[2000];
bool cmp_a(student a, student b) {
    return a.a > b.a;
}
bool cmp_c(student a, student b) {
    return a.c > b.c;
}
bool cmp_m(student a, student b) {
    return a.m > b.m;
}
bool cmp_e(student a, student b) {
    return a.e > b.e;
}
int A[1000000], C[1000000], M[1000000], E[1000000];
bool isin[1000000];
int main() {
    int n, m, num, c1, m1, e1;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> num >> c1 >> m1 >> e1;
        double a1 = (c1 + m1 + e1) / 3.0;
        nums[i] = student(num, c1, m1, e1, a1);
        isin[num] = true;
    }
    int idx = 1;
    sort(nums, nums + 2000, cmp_a);
    A[nums[0].num] = idx;
    for (int i = 1; i < n; i++) {
        if (nums[i].a == nums[i - 1].a) {
            A[nums[i].num] = idx;
        } else {
            A[nums[i].num] = i + 1;
            idx = i + 1;
        }
    }
    idx = 1;
    sort(nums, nums + 2000, cmp_c);
    C[nums[0].num] = idx;
    for (int i = 1; i < n; i++) {
        if (nums[i].c == nums[i - 1].c) {
            C[nums[i].num] = idx;
        } else {
            C[nums[i].num] = i + 1;
            idx = i + 1;
        }
    }
    idx = 1;
    sort(nums, nums + 2000, cmp_m);
    M[nums[0].num] = idx;
    for (int i = 1; i < n; i++) {
        if (nums[i].m == nums[i - 1].m) {
            M[nums[i].num] = idx;
        } else {
            M[nums[i].num] = i + 1;
            idx = i + 1;
        }
    }
    idx = 1;
    sort(nums, nums + 2000, cmp_e);
    E[nums[0].num] = idx;
    for (int i = 0; i < n; i++) {
        if (nums[i].e == nums[i - 1].e) {
            E[nums[i].num] = idx;
        } else {
            E[nums[i].num] = i + 1;
            idx = i + 1;
        }
    }
    for (int i = 0; i < m; i++) {
        cin >> num;
        if (isin[num]) {
            int res_rank = n, res_sub;
            if (res_rank > A[num]) {
                res_rank = A[num];
                res_sub = 'A';
            }
            if (res_rank > C[num]) {
                res_rank = C[num];
                res_sub = 'C';
            }
            if (res_rank > M[num]) {
                res_rank = M[num];
                res_sub = 'M';
            }
            if (res_rank > E[num]) {
                res_rank = E[num];
                res_sub = 'E';
            }
            printf("%d %c\n", res_rank, res_sub);
        } else {
            cout << "N/A" << endl;
        }
    }
    return 0;
}

柳婼的

#include <iostream>
#include <algorithm>
using namespace std;
struct node {
    int id, best;
    int score[4], rank[4];
} stu[2001];
int hashtable[1000000], flag;
bool cmp(node a, node b) {
    return a.score[flag] > b.score[flag];
}
int main() {
    int n, m, id;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> stu[i].id >> stu[i].score[1] >> stu[i].score[2] >> stu[i].score[3];
        stu[i].score[0] = (stu[i].score[1] + stu[i].score[2] + stu[i].score[3]) / 3.0 + 0.5;
    }
    for (flag = 0; flag <= 3; flag++) {
        sort(stu, stu + n, cmp);
        stu[0].rank[flag] = 1;
        for (int i = 1; i < n; i++) {
            stu[i].rank[flag] = i + 1;
            if (stu[i].score[flag] == stu[i - 1].score[flag])
                stu[i].rank[flag] = stu[i - 1].rank[flag];
        }
    }
    for (int i = 0; i < n; i++) {
        hashtable[stu[i].id] = i + 1;
        stu[i].best = 0;
        int minn = stu[i].rank[0];
        for (int j = 1; j <= 3; j++) {
            if (stu[i].rank[j] < minn) {
                minn = stu[i].rank[j];
                stu[i].best = j;
            }
        }
    }
    char c[5] = {"ACME"};
    for (int i = 0; i < m; i++) {
        cin >> id;
        if (hashtable[id]) {
            int best = stu[hashtable[id] - 1].best;
            printf("%d %c\n", stu[hashtable[id] - 1].rank[best], c[best]);
        } else {
            cout << "N/A\n";
        }
    }
    return 0;
}

1013 Battle Over Cities

并查集

#include <iostream>
#include <set>
using namespace std;
const int N = 1001;
int g[N][N], fa[N];
int find(int x) {
    if (fa[x] != x) {
        fa[x] = find(fa[x]);
    }
    return fa[x];
}
int main() {
    int n, m, k, u, v, x;
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++) {
        cin >> u >> v;
        g[u][v] = g[v][u] = 1;
    }
    for (int i = 0; i < k; i++) {
        cin >> x;
        for (int j = 1; j <= n; j++) {
            fa[j] = j;
        }
        for (int j = 1; j <= n; j++) {
            for (int k = j + 1; k <= n; k++) {
                if (j == x || k == x) continue;
                if (g[j][k] == 1 && find(j) != find(k)) {
                    fa[find(j)] = find(k);
                }
            }
        }
        set<int> res;
        for (int j = 1; j <= n; j++) {
            res.insert(find(j));
        }
        cout << res.size() - 2 << endl;
    }
    return 0;
}

柳婼的（dfs）

#include <iostream>
#include <set>
using namespace std;
const int N = 1001;
int g[N][N], n;
bool visit[N];
void dfs(int x) {
    visit[x] = true;
    for (int i = 1; i <= n; i++) {
        if (g[i][x] && !visit[i]) {
            dfs(i);
        }
    }
}
int main() {
    int m, k, u, v, x;
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++) {
        cin >> u >> v;
        g[u][v] = g[v][u] = 1;
    }
    for (int i = 0; i < k; i++) {
        fill(visit, visit + N, false);
        cin >> x;
        visit[x] = true;
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (!visit[i]) {
                dfs(i);
                cnt++;
            }
        }
        cout << cnt - 1 << endl;
    }
    return 0;
}

1014 Waiting in Line

大模拟（queue）

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct node {
    int poptime, endtime;
    queue<int> q;
};
int main() {
    int n, m, k, q, idx = 1;
    cin >> n >> m >> k >> q;
    vector<int> time(k + 1), res(k + 1);
    for (int i = 1; i <= k; i++) {
        cin >> time[i];
    }
    vector<node> win(n + 1);
    vector<bool> sorry(k + 1, false);
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (idx <= k) {
                win[j].q.push(time[idx]);
                if (win[j].endtime >= 540) 
                    sorry[idx] = true;
                win[j].endtime += time[idx];
                if (i == 1)
                    win[j].poptime = win[j].endtime;
                res[idx] = win[j].endtime;
                idx++;
            }
        }
    }
    while (idx <= k) {
        int tmin = win[1].poptime, twin = 1;
        for (int i = 2; i <= n; i++) {
            if (win[i].poptime < tmin) {
                twin = i;
                tmin = win[i].poptime;
            }
        }
        win[twin].q.pop();
        win[twin].q.push(time[idx]);
        win[twin].poptime += win[twin].q.front();
        if (win[twin].endtime >= 540)
            sorry[idx] = true;
        win[twin].endtime += time[idx];
        res[idx] = win[twin].endtime;
        idx++;
    }
    for (int i = 1; i <= q; i++) {
        int query, minute;
        cin >> query;
        minute = res[query];
        if (sorry[query]) cout << "Sorry" << endl;
        else printf("%02d:%02d\n", (minute + 480) / 60, minute % 60);
    }
    return 0;
}

1015 Reversible Primes

#include <iostream>
#include <string>
#include <cmath>
using namespace std;
const int N = 100001;
bool st[N];
int convert1(string s, int k) {
    int sum = 0, idx = 0;
    for (int i = s.size() - 1; i >= 0; i--) {
        sum += (s[i] - '0') * pow(k, idx++);
    }
    return sum;
}
string convert2(int n, int k) {
    string res;
    while (n) {
        res.push_back(n % k + '0');
        n /= k;
    }
    return res;
}
int main() {
    for (int i = 2; i < N; i++) {
        if (!st[i]) {
            for (int j = i + i; j < N; j += i) {
                st[j] = true;
            }
        }
    }
    st[0] = st[1] = true;
    int a, b;
    while (cin >> a) {
        if (a < 0) break;
        cin >> b;
        int t = convert1(convert2(a, b), b);
        if (!st[t] && !st[a]) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

柳婼的

#include <iostream>
#include <cmath>
using namespace std;
bool isprime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i <= int(sqrt(n * 1.0)); i++) {
        if (n % i == 0) return false;
    }
    return true;
}
int main() {
    int a, b;
    while (cin >> a) {
        if (a < 0) break;
        cin >> b;
        if (!isprime(a)) {
            cout << "No" << endl;
            continue;
        }
        int len = 0, arr[100];
        do {
            arr[len++] = a % b;
            a /= b;
        } while(a != 0);
        for (int i = 0; i < len; i++) 
            a = a * b + arr[i];
        if (isprime(a)) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

1016 Phone Bills

大模拟

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
struct node {
    string time, tag;
    node (string _time, string _tag) {
        time = _time, tag = _tag;
    }
};
map<string, vector<node>> mp;
bool cmp(node a, node b) {
    return a.time < b.time;
}
int price[25] = {0}, n;
double count2(string time) {
    int res = 0, day = stoi(time.substr(0,2)), hour = stoi(time.substr(3, 2)), min = stoi(time.substr(6, 2));
    res = price[hour] * min + price[24] * 60 * day;
    for (int i = 0; i < hour; i++) {
        res += price[i] * 60;
    }
    return res / 100.0;
}
int count1(string time) {
    int res = 0, day = stoi(time.substr(0,2)), hour = stoi(time.substr(3, 2)), min = stoi(time.substr(6, 2));
    res = day * 24 * 60 + hour * 60 + min;
    return res;
}
int main() {
    for (int i = 0; i < 24; i++) {
        cin >> price[i];
        price[24] += price[i];
    }
    cin >> n;
    string name, time, tag, month;
    for (int i = 0; i < n; i++) {
        cin >> name >> time >> tag;
        month = time.substr(0, 2);
        mp[name].push_back(node(time.substr(3, 8), tag));
    }
    for (auto i = mp.begin(); i != mp.end(); i++) {
        vector<node> nodes = i->second;
        sort(nodes.begin(), nodes.end(), cmp);
        double money = 0;
        int idx = 0, minute;
        string start, end;
        vector<string> times;
        for (int i = 0; i < nodes.size() - 1; i++) {
            if (nodes[i].tag == "on-line" && nodes[i + 1].tag == "off-line") {
                times.push_back(nodes[i].time);
                times.push_back(nodes[i + 1].time);
            }
        }
        if (times.size() > 0) {
            cout << i->first << " " << month << endl;
            for (int i = 0; i < times.size(); i += 2) {
                string start = times[i], end = times[i + 1];
                minute = count1(end) - count1(start);
                double t = count2(end) - count2(start);
                money += t;
                printf("%s %s %d $%.2f\n", start.c_str(), end.c_str(), minute, t);
            }
            printf("Total amount: $%.2f\n", money);
        } 
    }
    return 0;
}

柳婼的

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
struct node {
    string name;
    int status, month, time, day, hour, minute;
};
bool cmp(node a, node b) {
    return a.name != b.name ? a.name < b.name : a.time < b.time;
}
int rate[25], n;
double count(node a) {
    double res = rate[a.hour] * a.minute + rate[24] * 60 * a.day;
    for (int i = 0; i < a.hour; i++) {
        res += rate[i] * 60;
    }
    return res / 100.0;
}
int main() {
    for (int i = 0; i < 24; i++) {
        cin >> rate[i];
        rate[24] += rate[i];
    }
    cin >> n;
    vector<node> data(n);
    for (int i = 0; i < n; i++) {
        cin >> data[i].name;
        scanf("%d:%d:%d:%d", &data[i].month, &data[i].day, &data[i].hour, &data[i].minute);
        string tmp;
        cin >> tmp;
        data[i].status = (tmp == "on-line") ? 1 : 0;
        data[i].time = data[i].day * 24 * 60 + data[i].hour * 60 + data[i].minute;
    }
    sort(data.begin(), data.end(), cmp);
    map<string, vector<node> > custom;
    for (int i = 1; i < n; i++) {
        if (data[i].name == data[i - 1].name && data[i - 1].status == 1 && data[i].status == 0) {
            custom[data[i - 1].name].push_back(data[i - 1]);
            custom[data[i].name].push_back(data[i]);
        }
    }
    for (auto it: custom) {
        vector<node> tmp = it.second;
        printf("%s %02d\n", it.first.c_str(), tmp[0].month);
        double res = 0;
        for (int i = 1; i < tmp.size(); i += 2) {
            double t = count(tmp[i]) - count(tmp[i - 1]);
            printf("%02d:%02d:%02d %02d:%02d:%02d %d $%.2f\n", tmp[i - 1].day, tmp[i - 1].hour, tmp[i - 1].minute, tmp[i].day, tmp[i].hour, tmp[i].minute, tmp[i].time - tmp[i - 1].time, t);
            res += t;
        }
        printf("Total amount: $%.2f\n", res);
    }
    return 0;
}

1017 Queueing at Bank

#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
int main() {
    int n, k, p, hour, minute, second, idx = 0, res = 0;
    cin >> n >> k;
    vector<PII> nums;
    vector<int> v(k);
    for (int i = 0; i < n; i++) {
        scanf("%d:%d:%d %d", &hour, &minute, &second, &p);
        int t = hour * 3600 + minute * 60 + second;
        if (t > 61200) continue;
        nums.push_back({t, p * 60});
    }
    sort(nums.begin(), nums.end());
    n = nums.size();
    for (int j = 0; j < min(n, k); j++) {
        if (nums[idx].first < 28800) {
            v[j] = 28800;
            res += 28800 - nums[idx].first;
        } else {
            v[j] = nums[idx].first;
        }
        v[j] += nums[idx].second;
        idx++;
    }
    while (idx < n) {
        int tmin = v[0], twin = 0;
        for (int i = 1; i < k; i++) {
            if (tmin > v[i]) {
                tmin = v[i];
                twin = i;
            }
        }
        if (v[twin] > nums[idx].first) {
            res += v[twin] - nums[idx].first;
        } else {
            v[twin] = nums[idx].first;
        }
        v[twin] += nums[idx].second;
        idx++;
    }
    printf("%.1f", res / 60.0 / n);
    return 0;
}

柳婼的

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 10005;
struct person {
    int come, time;
} p[maxn];
int cmp(person p1, person p2) {
    return p1.come < p2.come;
}
int n, k, cnt, total;
int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        int hh, ss, mm, tt;
        scanf("%d:%d:%d %d", &hh, &mm, &ss, &tt);
        int sum = hh * 3600 + mm * 60 + ss;
        if (sum > 61200) continue;
        p[++cnt].time = tt * 60;
        p[cnt].come = sum;
    }
    sort(p + 1, p + 1 + cnt, cmp);
    priority_queue<int, vector<int>, greater<int> > q;
    for (int i = 1; i <= k; i++) 
        q.push(28800);
    for (int i = 1; i <= cnt; i++) {
        cout << i << endl;
        if (q.top() <= p[i].come) {
            q.push(p[i].come + p[i].time);
        } else {
            total += q.top() - p[i].come;
            q.push(q.top() + p[i].time);
        }
        q.pop();
    }
    if (!cnt) cout << "0.0" << endl;
    else printf("%.1f", total / 60.0 / cnt);
    return 0;
}

1018 Public Bike Management

dijkstra

#include <iostream>
#include <vector>
#include <map>
#include <iostream>
using namespace std;
typedef pair<int, int> PII;
const int N = 501;
const int INF = 0x3f3f3f3f;
bool visit[N];
int d[N], weight[N], n, minNeed = INF, minBack = INF;
vector<PII> g[N];
vector<int> pre[N], path, tmppath;
void dijkstra(int x) {
    fill(d, d + N, INF);
    d[x] = 0;
    for (int i = 0; i <= n; i++) {
        int u = -1, mind = INF;
        for (int j = 0; j <= n; j++) {
            if (!visit[j] && mind > d[j]) {
                mind = d[j];
                u = j;
            }
        }
        if (u == -1) return;
        visit[u] = true;
        for (int j = 0; j < g[u].size(); j++) {
            int v = g[u][j].first;
            int dis = g[u][j].second;
            if (!visit[v]) {
                if (d[u] + dis < d[v]) {
                    d[v] = d[u] + dis;
                    pre[v].clear();
                    pre[v].push_back(u);
                } else if(d[u] + dis == d[v]) {
                    pre[v].push_back(u);
                }
            }
        }
    }
}
void dfs(int v) {
    tmppath.push_back(v);
    if (v == 0) {
        int need = 0, back = 0;
        for (int i = tmppath.size() - 1; i >= 0; i--) {
            int idx = tmppath[i];
            if (weight[idx] > 0) {
                back += weight[idx];
            } else {
                if (back > -weight[idx]) {
                    back += weight[idx];
                } else {
                    need += (-weight[idx] - back);
                    back = 0;
                }
            }
        }
        if (need < minNeed) {
            minNeed = need;
            minBack = back;
            path = tmppath;
        } else if (need == minNeed && back < minBack) {
            minBack = back;
            path = tmppath;
        }
        tmppath.pop_back();
        return;
    }
    for (int i = 0; i < pre[v].size(); i++) 
        dfs(pre[v][i]);
    tmppath.pop_back();
}
int main() {
    int c, s, m, u, v, w;
    cin >> c >> n >> s >> m;
    for (int i = 1; i <= n; i++) {
        cin >> weight[i];
        weight[i] = weight[i] - c / 2;
    }
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    dijkstra(0);
    dfs(s);
    cout << minNeed << " 0";
    for (int i = path.size() - 2; i >= 0; i--) {
        cout << "->" << path[i];
    }
    cout << " " << minBack;
    return 0;
}

1019 General Palindromic Number

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    vector<int> str;
    while (n) {
        str.push_back(n % k);
        n /= k;
    }
    vector<int> str2(str.rbegin(), str.rend());
    if (str == str2) cout << "Yes" << endl;
    else cout << "No" << endl;
    for (int i = 0; i < str2.size(); i++) {
        cout << str2[i];
        if (i < str2.size() - 1) cout << " ";
    }
    return 0;
}

1020 Tree Traversals

#include <iostream>
#include <queue>
using namespace std;
const int N = 31;
int post[N], in[N];
struct node {
    int l, r;
} trees[N];
int build(int postl, int postr, int inl, int inr) {
    if (postl > postr) return -1;
    int root = post[postr], idx;
    for (int i = inl; i <= inr; i++) {
        if (root == in[i]) {
            idx = i;
            break;
        }
    }
    int cntl = idx - inl;
    trees[root].l = build(postl, postl + cntl - 1, inl, idx - 1);
    trees[root].r = build(postl + cntl, postr - 1, idx + 1, inr);
    return root;
}
void bfs(int u) {
    queue<int> q;
    q.push(u);
    while (!q.empty()) {
        u = q.front();
        q.pop();
        cout << u;
        if (trees[u].l != -1) q.push(trees[u].l);
        if (trees[u].r != -1) q.push(trees[u].r);
        if (!q.empty()) cout << " ";
    }
}
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> post[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> in[i];
    }
    int root = build(0, n - 1, 0, n - 1);
    bfs(root);
    return 0;
}

柳婼的

#include <iostream>
#include <map>
using namespace std;
const int N = 31;
int post[N], in[N];
map<int, int> level;
void pre(int root, int start, int end, int idx) {
    if (start > end) return;
    int i = start;
    while (i < end && in[i] != post[root]) i++;
    level[idx] = post[root];
    pre(root - 1 - end + i, start, i - 1, 2 * idx + 1);
    pre(root - 1, i + 1, end, 2 * idx + 2);
}
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> post[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> in[i];
    }
    pre(n - 1, 0, n - 1, 0);
    for (auto i = level.begin(); i != level.end(); i++) {
        cout << i->second;
        if (next(i) != level.end()) cout << " ";
    }
    return 0;
}

1021 Deepest Root

#include <iostream>
#include <vector>
#include <set>
using namespace std;
int n, maxh = 0;
vector<int> g[10010], tmp;
bool visit[10010];
set<int> s;
void dfs(int node, int height) {
    if (maxh < height) {
        maxh = height;
        tmp.clear();
        tmp.push_back(node);
    } else if (maxh == height) {
        tmp.push_back(node);
    }
    visit[node] = true;
    for (int i = 0; i < g[node].size(); i++) {
        if (!visit[g[node][i]]) {
            dfs(g[node][i], height + 1);
        }
    }
}
int main() {
    int n, u, v, cnt = 0, s1 = 0;
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        if (!visit[i]) {
            dfs(i, 1);
            if (i == 1) {
                if (!tmp.empty()) s1 = tmp[0];
                for (int j = 0; j < tmp.size(); j++) {
                    s.insert(tmp[j]);
                }
            }
            cnt++;
        }
    }
    if (cnt > 1) cout << "Error: " << cnt << " components";
    else {
        tmp.clear();
        fill(visit, visit + 10010, false);
        maxh = 0;
        dfs(s1, 1);
        for (int i = 0; i < tmp.size(); i++)
            s.insert(tmp[i]);
        for (auto it = s.begin(); it != s.end(); it++) {
            cout << *it << endl;
        }
    }
    return 0;
}

1022 Digital Library

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
struct book {
    string num, title, auther, publisher, year;
    vector<string> keys;
} books[10001];
bool cmp(book a, book b) {
    return a.num < b.num;
}
int main() {
    int n, m, q;
    string key, query;
    scanf("%d\n", &n);
    for (int i = 0; i < n; i++) {
        getline(cin, books[i].num);
        getline(cin, books[i].title);
        getline(cin, books[i].auther);
        while (cin >> key) {
            books[i].keys.push_back(key);
            char c = getchar();
            if (c == '\n') break;
        }
        getline(cin, books[i].publisher);
        getline(cin, books[i].year);
    }
    sort(books, books + n, cmp);
    cin >> m;
    for (int i = 0; i < m; i++) {
        bool flag = false;
        scanf("%d: ", &q);
        getline(cin, query);
        cout << q << ": " << query << endl;
        for (int i = 0; i < n; i++) {
            if (q == 1 && books[i].title == query) {
                cout << books[i].num << endl;
                flag = true;
            } else if (q == 2 && books[i].auther == query) {
                cout << books[i].num << endl;
                flag = true;
            } else if (q == 3) {
                for (int j = 0; j < books[i].keys.size(); j++) {
                    if (query == books[i].keys[j]) {
                        cout << books[i].num << endl;
                        flag = true;
                    }
                }
            } else if (q == 4 && books[i].publisher == query) {
                cout << books[i].num << endl;
                flag = true;
            } else if (q == 5 && books[i].year == query) {
                cout << books[i].num << endl;
                flag = true;
            }
        }
        if (!flag) cout << "Not Found" << endl;
    }
    return 0;
}

柳婼的

#include <iostream>
#include <map>
#include <set>
using namespace std;
map<string, set<int> > title, author, key, pub, year;
void query(map<string, set<int> > &m, string &str) {
    if(m.find(str) != m.end()) {
        for(auto it = m[str].begin(); it != m[str].end(); it++)
            printf("%07d\n", *it);
    } else
        cout << "Not Found\n";
}
int main() {
    int n, m, id, num;
    scanf("%d", &n);
    string ttitle, tauthor, tkey, tpub, tyear;
    for(int i = 0; i < n; i++) {
        scanf("%d\n", &id);
        getline(cin, ttitle);
        title[ttitle].insert(id);
        getline(cin, tauthor);
        author[tauthor].insert(id);
        while(cin >> tkey) {
            key[tkey].insert(id);
            char c = getchar();
            if(c == '\n') break;
        }
        getline(cin, tpub);
        pub[tpub].insert(id);
        getline(cin, tyear);
        year[tyear].insert(id);
    }
    scanf("%d", &m);
    for(int i = 0; i < m; i++) {
        scanf("%d: ", &num);
        string temp;
        getline(cin, temp);
        cout << num << ": " << temp << "\n";
        if(num == 1) query(title, temp);
        else if(num == 2) query(author, temp);
        else if(num == 3) query(key, temp);
        else if(num == 4) query(pub,temp);
        else if(num ==5) query(year, temp);
    }
    return 0;
}

1023 Have Fun with Numbers

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int nums[10];
int main() {
    string a, b = "";
    cin >> a;
    int t = 0;
    for (int i = a.size() - 1; i >= 0; i--) {
        b += ((a[i] - '0') * 2 + t) % 10 + '0';
        t = ((a[i] - '0') * 2 + t) / 10;
    }
    if (t) b += t + '0';
    reverse(b.begin(), b.end());
    for (int i = 0; i < a.size(); i++) {
        nums[a[i]]++;
    }
    bool flag = true;
    for (int i = 0; i < b.size(); i++) {
        nums[b[i]]--;
        if (nums[b[i]] < 0) {
            flag = false;
            break;
        }
    }
    if (flag) cout << "Yes" << endl;
    else cout << "No" << endl;
    cout << b;
    return 0;
}

1024 Palindromic Number

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string add(string a) {
    string b(a.rbegin(), a.rend()), c = "";
    int t = 0;
    for (int i = a.size() - 1; i >= 0; i--) {
        int sum = a[i] - '0' + b[i] - '0' + t;
        c += sum % 10 + '0';
        t = sum / 10;
    }
    if (t) c += t + '0';
    reverse(c.begin(), c.end());
    return c;
}
bool ispal(string a) {
    string b(a.rbegin(), a.rend());
    return a == b;
}
int main() {
    string n;
    int k;
    cin >> n >> k;
    for (int i = 0; i < k; i++) {
        if (ispal(n)) {
            cout << n << endl;
            cout << i;
            return 0;
        }
        n = add(n);
    }
    cout << n << endl;
    cout << k;
    return 0;
}

1025 PAT Ranking

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
struct node1 {
    string num;
    int score, locnum, locrank;
};
bool cmp1(node1 &a, node1 &b) {
    if (a.score == b.score) {
        return a.num < b.num;
    } else {
        return a.score > b.score;
    }
}
int main() {
    int n, k, score;
    string num;
    vector<node1> nums;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> k;
        vector<node1> tmp(k);
        for (int j = 0; j < k; j++) {
            cin >> tmp[j].num >> tmp[j].score;
            tmp[j].locnum = i;
        }
        sort(tmp.begin(), tmp.end(), cmp1);
        tmp[0].locrank = 1;
        nums.push_back(tmp[0]);
        for (int j = 1; j < k; j++) {
            if (tmp[j].score != tmp[j - 1].score) tmp[j].locrank = j + 1;
            else tmp[j].locrank = tmp[j - 1].locrank;
            nums.push_back(tmp[j]);
        }
    }
    sort(nums.begin(), nums.end(), cmp1);
    int rank = 1;
    cout << nums.size() << endl;
    cout << nums[0].num << " " << rank << " " << nums[0].locnum << " " << nums[0].locrank << endl;
    for (int i = 1; i < nums.size(); i++) {
        if (nums[i].score != nums[i - 1].score) rank = i + 1;
        cout << nums[i].num << " " << rank << " " << nums[i].locnum << " " << nums[i].locrank << endl;
    }
    return 0;
}

1026 Table Tennis

最恶心的大模拟

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long ll;
struct table {
    int endtime, num;
    bool vip;
};
struct play {
    int arrive, use, start; // 到达时间，使用时间，开始时间
    bool served, vip;       // 是否服务，vip?
};
int cmp1(play a, play b) {
    return a.arrive < b.arrive; // 先对数据进行排序，按到达的时间升序
}
int cmp2(play a, play b) {
    return a.start < b.start; // 最后输出的时候为什么是8:12:00在8:10:00的前面呢？就是因为是按开始使用的时间升序的
}
vector<play> p;
vector<table> t;

// 找到personid及之后的，并且到达（arrive）时间不晚于before的，未服务的，且为vip的 person-id. 如果没找到,则返回-1
int findvip(int personId, int minendtime) {
    for (int i = personId; i < p.size() && p[i].arrive <= minendtime; i++) {
        if (!p[i].served && p[i].vip)
            return i;
    }
    return -1;
}
// 更新以personId的玩家对，和tableId的桌子的信息
// 1、将该玩家对的开始时间赋值为到达时间和可用桌子结束时间中的较大值
// 2、将该玩家对的服务状态赋值为以服务过
// 3、将桌子的结束时间信息更新为该玩家对的开始时间加该玩家的使用时间
// 4、将该桌子服务的玩家数量加一
void update(int personid, int tableid) {
    p[personid].start = max(p[personid].arrive, t[tableid].endtime);
    p[personid].served = 1;
    t[tableid].endtime = p[personid].start + p[personid].use;
    t[tableid].num++;
}

int main() {
    int n, m, k, vipnum;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int h, m, s, use, vip, arrive;
        scanf("%d:%d:%d %d %d", &h, &m, &s, &use, &vip);
        arrive = h * 3600 + m * 60 + s;
        use = use > 120 ? 7200 : use * 60;
        p.push_back({arrive, use, 0, 0, vip > 0});
    }
    sort(p.begin(), p.end(), cmp1);
    scanf("%d %d", &k, &m);
    for (int i = 0; i < k; i++)
        t.push_back({28800, 0, 0});
    for (int i = 0; i < m; i++) {
        scanf("%d", &vipnum);
        t[vipnum - 1].vip = 1;
    }
    for (int i = 0; i < p.size();) {
        // 找到最先空闲的桌子,如果多个桌子同时空闲，则返回桌子号最小的那个
        int minendtime = INF, minendid;
        for (int j = 0; j < k; j++) {
            if (minendtime > t[j].endtime) {
                minendtime = t[j].endtime;
                minendid = j;
            }
        }
        // 如果最先空闲的桌子空闲的太晚了，或者当前序列中的第一位玩家对达到的时间太晚了，就退出循环
        if (minendtime >= 75600 || p[i].arrive >= 75600)
            break;
        // 声明新的变量，personId为经过调整选择后最终的开始使用桌子的玩家对索引，tableId为为经过调整选择后最终的开始被使用的桌子
        int personid = i, tableid = minendid;
        // 如果当前的最早空闲且号最小的桌子空闲时，存在玩家对已经在等待了
        if (minendtime >= p[i].arrive) {
            // 并且当前的最早空闲且号最小的桌子是vip，寻找是vip的且未服务过的，玩家对到达时间不晚于minEndTime的玩家对索引
            if (t[tableid].vip) {
                int vipid = findvip(personid, minendtime);
                personid = vipid != -1 ? vipid : personid;
            }
            else if (p[i].vip) { 
                // 虽然当前的最早空闲且号最小的桌子不是vip，但是还可能存在同时空闲，桌号更大的桌子是vip
                for (int j = 0; j < k; j++) {
                    if (t[j].vip && t[j].endtime <= p[personid].arrive) {
                        tableid = j;
                        break;
                    }
                }
            } // 如果当前的桌子非vip，且当前的序列的第一个玩家对非vip，顺序选择即可，换句话说，personId和tableId无需调整
        } else {
            /*
            如果当前的最早空闲的桌子空闲时，没有玩家在等待序列中，即当一个玩家到达时，应该是至少有一个桌子是空闲的
            我们总是希望选择空闲中的桌子中桌子号最小的，如果到达了一个vip玩家对，并且存在空闲的vip桌子，我们选择空闲中的vip桌中号最小的
            在这里，我们不管是否是vip，先得到空闲中的桌子中桌子号最小的，如果当前到达的玩家对未vip，并且存在空闲的vip桌子，
            我们用空闲中的vip桌中号最小的那个桌子覆盖之前得到的tableId
           */
            for (int j = 0; j < k; j++) {
                if (t[j].endtime <= p[personid].arrive) {
                    tableid = j;
                    break;
                }
            }
            if (p[personid].vip) {
                for (int j = 0; j < k; j++) { 
                    // 尝试寻找空闲的vip桌子并调整tableId，顺序找到即退出得到的就是号码最小的
                    if (t[j].vip && t[j].endtime <= p[personid].arrive) {
                        tableid = j;
                        break;
                    }
                }
            }
        }
        update(personid, tableid);
        while (i < p.size() && p[i].served)
            i++;
    }
    sort(p.begin(), p.end(), cmp2);
    for (int i = 0; i < p.size(); i++) {
        if (p[i].served) {
            int wait = p[i].start - p[i].arrive;
            printf("%02d:%02d:%02d %02d:%02d:%02d %d\n", p[i].arrive / 3600,
                   p[i].arrive % 3600 / 60, p[i].arrive % 60, p[i].start / 3600,
                   p[i].start % 3600 / 60, p[i].start % 60, (int)(1.0 * wait / 60 + 0.5));
        }
    }
    for (int i = 0; i < k; i++) {
        if (i != 0)
            printf(" ");
        printf("%d", t[i].num);
    }
    return 0;
}

柳婼的

#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;
int n, m, k, H, M, S, t, table, vtable, cnt, now, nowt, T[100000], V[100000], num[10001], AnsI[10001], AnsO[10001], vip[10001];
map<int, int> Table;
queue<int> Wait, vWait;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d:%d:%d", &H, &M, &S);
        t = H * 3600 + M * 60 + S;
        scanf("%d %d", &T[t], &V[t]);
        T[t] = min(T[t], 120) * 60;
    }
    scanf("%d %d", &m, &k);
    for (int i = 0; i < k; i++) {
        scanf("%d", &t);
        vip[t] = 1;
    }
    for (int Time = 28800; Time < 75600; Time++, table = vtable = now = 0) {
        if (T[Time] && V[Time]) vWait.push(Time);
        else if (T[Time]) Wait.push(Time);
        for (int i = 1; i <= m; i++) {
            if (Table[i] > 0) Table[i]--;
            if (Table[i] == 0 && vip[i] && vtable == 0) vtable = i;
            if (Table [i] == 0 && table == 0) table = i;
        }
        if (!vWait.empty() && (table || vtable)) {
            now = vWait.front();
            nowt = vtable;
            if (vtable != 0) vWait.pop();
            else {
                nowt = table;
                if (!Wait.empty() && Wait.front() < vWait.front()) {
                    now = Wait.front();
                    Wait.pop();
                } else vWait.pop();
            }
        } else if (!Wait.empty() && (table || vtable)) {
            if (table != 0) nowt = table;
            else nowt = vtable;
            now = Wait.front();
            Wait.pop();
        }
        if (now == 0) continue;
        Table[nowt] = T[now];
        AnsI[cnt] = now;
        AnsO[cnt++] = Time;
        num[nowt]++;
    }
    for (int i = 0; i < cnt; i++)
        printf("%02d:%02d:%02d %02d:%02d:%02d %d\n", AnsI[i] / 3600, AnsI[i] % 3600 / 60, AnsI[i] % 60, AnsO[i] / 3600, AnsO[i] % 3600 / 60, AnsO[i] % 60, (AnsO[i] - AnsI[i] + 30) / 60);
    for (int i = 1; i <= m; i++) {
        if (i != 1) printf(" ");
        printf("%d", num[i]);
    }
    return 0;
}

1027 Colors in Mars

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string convert(int n) {
    string res = "";
    while (n) {
        if (n % 13 > 9) res += n % 13 + 'A' - 10;
        else res += n % 13 + '0';
        n /= 13;
    }
    while (res.size() < 2) res += '0';
    reverse(res.begin(), res.end());
    return res;
}
int main() {
    int red, green, blue;
    cin >> red >> green >> blue;
    cout << "#" << convert(red) << convert(green) << convert(blue);
    return 0;
}

柳婼的

#include <iostream>
using namespace std;
int main() {
    char c[14] = {"0123456789ABC"};
    cout << "#";
    for (int i = 0; i < 3; i++) {
        int num;
        cin >> num;
        cout << c[num / 13] << c[num % 13];
    }
    return 0;
}

1028 List Sorting

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
struct node {
    string num, name;
    int score;
} nums[100001];
bool cmp1 (node a, node b) {
    return a.num < b.num;
}
bool cmp2 (node a, node b) {
    if (a.name == b.name) return a.num < b.num;
    else return a.name < b.name;
}
bool cmp3 (node a, node b) {
    if (a.score == b.score) return a.num < b.num;
    else return a.score < b.score;
}
int main() {
    int n, c, score;
    string num, name;
    cin >> n >> c;
    for (int i = 0; i < n; i++) {
        cin >> nums[i].num >> nums[i].name >> nums[i].score;
    }
    if (c == 1) {
        sort(nums, nums + n, cmp1);
    } else if (c == 2) {
        sort(nums, nums + n, cmp2);
    } else if (c == 3) {
        sort(nums, nums + n, cmp3);
    }
    for (int i = 0; i < n; i++) {
        cout << nums[i].num << " " << nums[i].name << " " << nums[i].score << endl;
    }
}

1029 Median

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
vector<LL> nums;
int main() {
    LL n, x;
    scanf("%lld", &n);
    for (int i = 0; i < n; i++) {
        scanf(" %lld", &x);
        nums.push_back(x);
    }
    scanf("%lld", &n);
    for (int i = 0; i < n; i++) {
        scanf(" %lld", &x);
        nums.push_back(x);
    }
    sort(nums.begin(), nums.end());
        cout << nums[(nums.size() - 1) / 2];
    return 0;
}

柳婼的

#include <iostream>
using namespace std;
const int N = 200005;
int n, m, a1[N], a2[N];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a1[i]);
    }
    cin >> m;
    for (int i = 1; i <= m; i++) {
        scanf("%d", &a2[i]);
    }
    int target = (n + m + 1) / 2;
    int i = 1, j = 1, cnt = 0, res;
    while (i <= n && j <= m) {
        res = a1[i] <= a2[j] ? a1[i++] : a2[j++];
        if (++cnt == target) break;
    }
    if (i <= n && cnt < target) 
        res = a1[i + target - cnt - 1];
    else if (j <= m && cnt < target)
        res = a2[j + target - cnt - 1];
    cout << res;
    return 0;
}

1030 Travel Plan

dijkstra

#include <iostream>
#include <vector>
using namespace std;
const int N = 501;
const int INF = 0x3f3f3f3f;
struct node {
    int v, dis;
    node (int _v, int _dis) {
        v = _v, dis = _dis;
    }
};
vector<node> g[N];
vector<int> pre[N];
int n, s, d[N], cost[N][N], mincost = INF;
bool visit[N];
void dijkstra(int s) {
    fill(d, d + N, INF);
    d[s] = 0;
    for (int i = 0; i < n; i++) {
        int u = -1, mind = INF;
        for (int j = 0; j < n; j++) {
            if (!visit[j] && mind > d[j]) {
                u = j;
                mind = d[j];
            }
        }
        if (u == -1) return;
        visit[u] = true;
        for (int j = 0; j < g[u].size(); j++) {
            int v = g[u][j].v;
            int dis = g[u][j].dis;
            if (!visit[v]) {
                if (d[u] + dis < d[v]) {
                    d[v] = d[u] + dis;
                    pre[v].clear();
                    pre[v].push_back(u);
                } else if (d[u] + dis == d[v]) {
                    pre[v].push_back(u);
                }
            }
        }
    }
}
vector<int> tmp, res;
void dfs(int t) {
    tmp.push_back(t);
    if (s == t) {
        int minc = 0;
        for (int i = 0; i < tmp.size() - 1; i++) {
            int id = tmp[i], nexti = tmp[i + 1];
            minc += cost[id][nexti];
        }
        if (minc < mincost) {
            mincost = minc;
            res = tmp;
        }
        tmp.pop_back();
        return;
    }
    for (int i = 0; i < pre[t].size(); i++) {
        dfs(pre[t][i]);
    }
    tmp.pop_back();
}
int main() {
    int m, t, u, v, w, c;
    cin >> n >> m >> s >> t;
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> w >> c;
        cost[u][v] = cost[v][u] = c;
        g[u].push_back(node(v, w));
        g[v].push_back(node(u, w));
    }
    dijkstra(s);
    dfs(t);
    for (int i = res.size() - 1; i >= 0; i--) {
        cout << res[i] << " ";
    }
    cout << d[t] << " " << mincost;
    return 0;
}

1031 Hello World for U

#include <iostream>
#include <string>
using namespace std;
int main() {
    string str;
    cin >> str;
    int len = str.size() + 2;
    int n = len / 3;
    int n2 = len - n * 3 + n - 2;
    for (int i = 0; i < n - 1; i++) {
        cout << str[i];
        for (int j = 0; j < n2; j++) {
            cout << " ";
        }
        cout << str[str.size() - 1 - i] << endl;
    }
    for (int i = n - 1; i < n + n2 + 1; i++) {
        cout << str[i];
    }
    return 0;
}

#include <iostream>
using namespace std;
const int N = 100001;
struct node {
    int next;
    char data;
    bool flag;
} nodes[N];
int main() {
    int s1, s2, n, add, next;
    char data;
    cin >> s1 >> s2 >> n;
    for (int i = 0; i < n; i++) {
        cin >> add >> data >> next;
       nodes[add] = {next, data, false};
    }
    for (int i = s1; i != -1; i = nodes[i].next) {
        nodes[i].flag = true;
    }
    for (int i = s2; i != -1; i = nodes[i].next) {
        if (nodes[i].flag) {
            printf("%05d", i);
            return 0;
        }
    }
    cout << -1;
    return 0;
}

1033 To Fill or Not to Fill

错误答案（没有考虑到油箱上限）

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<double, double> PII;
vector<PII> sites;
int main() {
    double c_max, d_max, d_avg, n,price, dis;
    cin >> c_max >> d_max >> d_avg >> n;
    for (int i = 0; i < n; i++) {
        cin >> price >> dis;
        if (dis >= d_max) continue;
        sites.push_back({dis, price});
    }
    sort(sites.begin(), sites.end());
    int cur_site = 0;
    double res = 0, cur_dis = 0, diff = 0;
    priority_queue<PII, vector<PII>, greater<PII> > q;
    if (sites[0].first != 0) {
        cout << "The maximum travel distance = 0.00";
        return 0;
    }
    while (cur_dis < d_max && cur_site < sites.size()) {
        if (cur_site == sites.size() - 1) 
            diff = d_max - cur_dis;
        else
            diff = sites[cur_site + 1].first - cur_dis;
        q.push({sites[cur_site++].second, c_max});
        while (!q.empty()) {
            PII t = q.top();
            q.pop();
            if (d_avg * t.second <= diff) {
                res += t.first * t.second;
                diff -= d_avg * t.second;
                cur_dis += d_avg * t.second;
            } else {
                res += diff * t.first / d_avg;
                cur_dis += diff;
                q.push({t.first, t.second - diff / d_avg});
                diff = 0;
                break;
            }
        }
        if (diff > 0) break;
    }
    if (cur_dis == d_max) printf("%.2f", res);
    else printf("The maximum travel distance = %.2f", cur_dis);
    return 0;
}

柳婼的（贪心）

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef pair<double, double> PII;
int main() {
    double c_max, d_max, d_avg, n;
    cin >> c_max >> d_max >> d_avg >> n;
    vector<PII> sta(n + 1);
    sta[0] = {d_max, 0};
    for (int i = 1; i <= n; i++) {
        cin >> sta[i].second >> sta[i].first;
    }
    sort(sta.begin(), sta.end());
    double cur_dis = 0, max_dis = 0, cur_price = 0, total_price = 0, left_dis = 0;
    if (sta[0].first != 0) {
        cout << "The maximum travel distance = 0.00";
        return 0;
    } else {
        cur_price = sta[0].second;
    }
    while (cur_dis < d_max) {
        max_dis = cur_dis + c_max * d_avg;
        double min_price_dis = 0, min_price = INF;
        int flag = 0;
        for (int i = 1; i <= n && sta[i].first <= max_dis; i++) {
            if (sta[i].first <= cur_dis) continue;
            if (sta[i].second <= cur_price) {
                total_price += (sta[i].first - cur_dis - left_dis) * cur_price / d_avg;
                left_dis = 0;
                cur_price = sta[i].second;
                cur_dis = sta[i].first;
                flag = 1;
                break;
            }
            if (sta[i].second < min_price) {
                min_price = sta[i].second;
                min_price_dis = sta[i].first;
            }
        }
        if (flag == 0 && min_price != INF) {
            total_price += (cur_price * (c_max - left_dis / d_avg));
            left_dis = c_max * d_avg - (min_price_dis - cur_dis);
            cur_price = min_price;
            cur_dis = min_price_dis;
        }
        if (flag == 0 && min_price == INF) {
            cur_dis += c_max * d_avg;
            printf("The maximum travel distance = %.2f", cur_dis);
            return 0;
        }
    }
    printf("%.2f", total_price);
    return 0;
}

1034 Head of a Gang

并查集（写复杂了）

#include <iostream>
#include <set>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef pair<string, int> PII;
const int N = 20000;
int fa[N], sum[N], maxs[N];
int find(int x) {
    if (fa[x] != x) {
        fa[x] = find(fa[x]);
    }
    return fa[x];
}
int convert1(string x) {
    return (x[0] - 'A') * 26 * 26 + (x[1] - 'A') * 26 + x[2] - 'A';
}
string convert2(int x) {
    string res = "";
    res += x / (26 * 26) + 'A';
    res += x % (26 * 26) / 26 + 'A';
    res += x % 26 + 'A';
    return res;
}
set<int> nums;
struct node {
    int a, b, time;
};
vector<node> relations;
int main() {
    int n, k, time;
    cin >> n >> k;
    string a, b;
    for (int i = 0; i < n; i++) {
        cin >> a >> b >> time;
        nums.insert(convert1(a));
        nums.insert(convert1(b));
        relations.push_back({convert1(a), convert1(b), time});
    }
    for (auto i = nums.begin(); i != nums.end(); i++) {
        fa[*i] = *i;
    }
    for (int i = 0; i < relations.size(); i++) {
        int a = relations[i].a, b = relations[i].b, time = relations[i].time;
        if (fa[a] != fa[b]) {
            sum[find(b)] = max(sum[find(a)], sum[find(b)]);
            fa[find(a)] = find(b);
        }
        sum[find(b)] += time;
        maxs[a] += time;
        maxs[b] += time;
    }
    set<int> bangs;
    for (auto i = nums.begin(); i != nums.end(); i++) {
        if (sum[find(*i)] > k) bangs.insert(find(*i));
    }
    vector<PII> res;
    for (auto i = bangs.begin(); i != bangs.end(); i++) {
        set<int> tmp;
        int m = 0, r;
        for (int j = 0; j < relations.size(); j++) {
            if (find(*i) == find(relations[j].a)) {
                tmp.insert(relations[j].a);
                tmp.insert(relations[j].b);
                if (m < maxs[relations[j].a]) {
                    m = maxs[relations[j].a];
                    r = relations[j].a;
                }
                if (m < maxs[relations[j].b]) {
                    m = maxs[relations[j].b];
                    r = relations[j].b;
                }
            }
        }
        if (tmp.size() > 2) res.push_back({convert2(r), tmp.size()});
    }
    cout << res.size() << endl;
    sort(res.begin(), res.end());
    for (int i = 0; i < res.size(); i++) {
        cout << res[i].first << " " << res[i].second << endl;
    }
    return 0;
}

柳婼的（dfs）

#include <iostream>
#include <map>
#include <string>
#include <algorithm>
using namespace std;
map<string, int> stringToInt;
map<int, string> intToString;
map<string, int> res;
int id = 1, k;
int stoifun(string s) {
    if (stringToInt[s] == 0) {
        stringToInt[s] = id;
        intToString[id] = s;
        return id++;
    } else {
        return stringToInt[s];
    }
}
int g[2010][2010], weight[2010];
bool vis[2010];
void dfs(int u, int &head, int &numMember, int &totalweight) {
    vis[u] = true;
    numMember++;
    if (weight[u] > weight[head])
        head = u;
    for (int v = 1; v < id; v++) {
        if (g[u][v] > 0) {
            totalweight += g[u][v];
            g[u][v] = g[v][u] = 0;
            if (!vis[v]) 
                dfs(v, head, numMember, totalweight);
        }
    }
}
void dfsTrave() {
    for (int i = 1; i < id; i++) {
        if (!vis[i]) {
            int head = i, numMember = 0, totalweight = 0;
            dfs(i, head, numMember, totalweight);
            if (numMember > 2 && totalweight > k) 
                res[intToString[head]] = numMember;
        }
    }
}
int main() {
    int n, w;
    cin >> n >> k;
    string s1, s2;
    for (int i = 0; i < n; i++) {
        cin >> s1 >> s2 >> w;
        int id1 = stoifun(s1);
        int id2 = stoifun(s2);
        weight[id1] += w;
        weight[id2] += w;
        g[id1][id2] += w;
        g[id2][id1] += w;
    }
    dfsTrave();
    cout << res.size() << endl;
    for (auto it = res.begin(); it != res.end(); it++) {
        cout << it->first << " " << it-> second << endl;
    }
    return 0;
}

1035 Password

#include <iostream>
#include <vector>
#include <map>
#include <string>
using namespace std;
string convert(string a) {
    string b = "";
    for (int i = 0; i < a.size(); i++) {
        if (a[i] == '1') b += '@';
        else if (a[i] == '0') b += '%';
        else if (a[i] == 'l') b += 'L';
        else if (a[i] == 'O') b += 'o';
        else b += a[i];
    }
    return b;
}
int main() {
    int n;
    cin >> n;
    string name, password;
    vector<pair<string, string> > res;
    for (int i = 0; i < n; i++) {
        cin >> name >> password;
        if (password != convert(password)) {
            res.push_back({name, convert(password)});
        }
    }
    if (res.size() > 1) {
        cout << res.size() << endl;
        for (int i = 0; i < res.size(); i++) {
            cout << res[i].first << " " << res[i].second << endl;
        }
    } else if (n == 1) {
        cout << "There is 1 account and no account is modified";
    } else {
        cout << "There are " << n << " accounts and no account is modified";
    }
    return 0;
}

1036 Boys vs Girls

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
struct node {
    string name, id;
    int grade;
};
bool cmp(node a, node b) {
    return a.grade < b.grade;
}
vector<node> males, famales;
int main() {
    int n;
    cin >> n;
    string name, gender, id;
    int grade;
    for (int i = 0; i < n; i++) {
        cin >> name >> gender >> id >> grade;
        if (gender == "M") {
            males.push_back({name, id, grade});
        } else {
            famales.push_back({name, id, grade});
        }
    }
    bool flag = false;
    int diff;
    sort(males.begin(), males.end(), cmp);
    sort(famales.begin(), famales.end(), cmp);
    if (famales.size() > 0) {
        cout << famales[famales.size() - 1].name << " " << famales[famales.size() - 1].id << endl;
        diff = famales[famales.size() - 1].grade;
    } else {
        cout << "Absent" << endl;
        flag = true;
    }
    if (males.size() > 0) {
        cout << males[0].name << " " << males[0].id << endl;
        diff += -males[0].grade;
    } else {
        cout << "Absent" << endl;
        flag = true;
    }
    if (flag) cout << "NA";
    else cout << diff;
    return 0;
}

柳婼的

#include <iostream>
using namespace std;
int main() {
    int n;
    scanf("%d", &n);
    string female, male;
    int femalescore = -1, malescore = 101;
    for(int i = 0; i < n; i++) {
        string name, sex, num;
        int score;
        cin >> name >> sex >> num;
        scanf("%d", &score);
        if(sex == "F") {
            if(femalescore < score) {
                femalescore = score;
                female = name + " " + num;
            }
        } else if(malescore > score) {
                malescore = score;
                male = name + " " + num;
            }
    }
    if(femalescore != -1)
        cout << female << endl;
    else
        printf("Absent\n");
    if(malescore != 101)
        cout << male << endl;
    else
        printf("Absent\n");
    if(femalescore != -1 && malescore != 101)
        printf("%d", femalescore - malescore);
    else
        printf("NA");
    return 0;
}

1037 Magic Coupon

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100001;
int a[N], b[N];
int main() {
    int n, m;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> b[i];
    }
    sort(a, a + n);
    sort(b, b + m);
    int al = 0, bl = 0, ar = n - 1, br = m - 1, res = 0;
    while(al < n && bl < n && a[al] < 0 && b[bl] < 0) {
        res += a[al++] * b[bl++];
    }
    while (ar >= 0 && br >= 0 && a[ar] > 0 && b[br] > 0) {
        res += a[ar--] * b[br--];
    }
    cout << res;
    return 0;
}

1038 Recover the Smallest Number

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(string a, string b) {
    return a + b < b + a;
}
typedef long long LL;
int main() {
    int n;
    string x;
    cin >> n;
    vector<string> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    sort(nums.begin(), nums.end(), cmp);
    bool flag = true, first = true;
    for (int i = 0; i < (LL)nums.size(); i++) {
        if (first) {
            int j = 0;
            for (; j < (LL)nums[i].size(); j++) {
                if (nums[i][j] != '0') break;
            }
            if (j < (LL)nums[i].size()) first = false;
            for (; j < (LL)nums[i].size(); j++) {
                cout << nums[i][j];
                flag = false;
            }
        } else {
            cout << nums[i];
        }
    }
    if (flag) cout << 0;
    return 0;
}

柳婼的

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(string a, string b) {
    return a + b < b + a;
}
string str[10010];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) 
        cin >> str[i];
    sort(str, str + n, cmp);
    string s;
    for (int i = 0; i < n; i++) 
        s += str[i];
    while (s.size() != 0 && s[0] == '0') 
        s.erase(s.begin());
    if (s.size() == 0) cout << 0;
    cout << s;
    return 0;
}

1039 Course List for Student

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
map<string, vector<int> > students;
int main() {
    int n, k, courseId, m;
    string name;
    cin >> n >> k;
    for (int i = 0; i < k; i++) {
        cin >> courseId >> m;
        for (int j = 0; j < m; j++) {
            cin >> name;
            students[name].push_back(courseId);
        }
    }
    for (int i = 0; i < n; i++) {
        cin >> name;
        cout << name << " " << students[name].size();
        sort(students[name].begin(), students[name].end());
        for (int j = 0; j < students[name].size(); j++) {
            cout << " " << students[name][j];
        }
        cout << endl;
    }
    return 0;
}

柳婼的

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int getid(char *name) {
    int id = 0;
    for(int i = 0; i < 3; i++)
        id = 26 * id + (name[i] - 'A');
    id = id * 10 + (name[3] - '0');
    return id;
}
const int maxn = 26 * 26 * 26 * 10 + 10;
vector<int> v[maxn];

int main() {
    int n, k, no, num, id = 0;
    char name[5];
    scanf("%d %d", &n, &k);
    for(int i = 0; i < k; i++) {
        scanf("%d %d", &no, &num);
        for(int j = 0; j < num; j++) {
            scanf("%s", name);
            id = getid(name);
            v[id].push_back(no);
        }
    }
    for(int i = 0; i < n; i++) {
        scanf("%s", name);
        id = getid(name);
        sort(v[id].begin(), v[id].end());
        printf("%s %lu", name, v[id].size());
        for(int j = 0; j < v[id].size(); j++)
            printf(" %d", v[id][j]);
        printf("\n");
    }
    return 0;
}

1040 Longest Symmetric String

#include <iostream>
#include <string>
using namespace std;
const int N = 1005;
bool dp[N][N];
int main() {
    string str;
    getline(cin, str);
    int n = str.size(), res = 1;
    for (int i = 1; i < n; i++) {
        dp[i][i] = true;
        if (i < n - 1 && str[i] == str[i + 1]) {
            dp[i][i + 1] = true;
            res = 2;
        }
    }
    for (int len = 3; len <= n; len++) {
        for (int l = 0; l < n - len + 1; l++) {
            int r = l + len - 1;
            if (str[l] == str[r] && dp[l + 1][r - 1]) {
                dp[l][r] = true;
                res = len;
            }
        }
    }
    cout << res;
    return 0;
}

1041 Be Unique

#include <iostream>
using namespace std;
const int N = 100005;
int nums[N], cnt[N];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
        cnt[nums[i]] ++;
    }
    for (int i = 0; i < n; i++) {
        if (cnt[nums[i]] == 1) {
            cout << nums[i];
            return 0;
        }
    }
    cout << "None";
    return 0;
}

1042 Shuffling Machine

#include <iostream>
#include <string>
using namespace std;
string nums[55] = {" ","S1","S2","S3","S4","S5","S6","S7","S8","S9","S10","S11","S12","S13","H1","H2","H3","H4","H5","H6","H7","H8","H9","H10","H11","H12","H13","C1","C2","C3","C4","C5","C6","C7","C8","C9","C10","C11","C12","C13","D1","D2","D3","D4","D5","D6","D7","D8","D9","D10","D11","D12","D13","J1", "J2"};
int shuff[55];
int main () {
    int n;
    cin >> n;
    for (int i = 1; i < 55; i++) {
        cin >> shuff[i];
    }
    for (int i = 0; i < n; i++) {
        string tmps[55];
        for (int j = 1; j < 55; j++) {
            tmps[shuff[j]] = nums[j];
        }
        copy(begin(tmps), end(tmps), begin(nums));
    }
    for (int i = 1; i < 55; i++) {
        cout << nums[i];
        if (i < 54) cout << " ";
    }
    return 0;
}

柳婼的

#include <iostream>
using namespace std;
int main () {
    int cnt;
    cin >> cnt;
    int start[55], end[55], scan[55];
    for (int i = 1; i < 55; i++) {
        cin >> scan[i];
        end[i] = i;
    }
    for (int i = 0; i < cnt; i++) {
        for (int j = 1; j < 55; j++) 
            start[j] = end[j];
        for (int k = 1; k < 55; k++) 
            end[scan[k]] = start[k];
    }
    char c[6] = {"SHCDJ"};
    for (int i = 1; i < 55; i++) {
        end[i] = end[i] - 1;
        cout << c[end[i] / 13] << end[i] % 13 + 1;
        if (i != 54) cout << " ";
    }
    return 0;
}

1043 Is It a Binary Search Tree

#include <iostream>
#include <vector>
using namespace std;
bool isMirror;
vector<int> pre, post;
void getpost(int root, int tail) {
    if (root> tail) return;
    int i = root + 1, j = tail;
    if (!isMirror) {
        while (i <= tail && pre[root] > pre[i]) i++;
        while (j > root && pre[root] <= pre[j]) j--;
    } else {
        while (i <= tail && pre[root] <= pre[i]) i++;
        while (j > root && pre[root] > pre[j]) j--;
    }
    if (i - j != 1) return;
    getpost(root + 1, j);
    getpost(i, tail);
    post.push_back(pre[root]);
}
int main() {
    int n;
    cin >> n;
    pre.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> pre[i];
    }
    getpost(0, n - 1);
    if (post.size() != n) {
        isMirror = true;
        post.clear();
        getpost(0, n - 1);
    }
    if (post.size() == n) {
        cout << "YES" << endl;
        for (int i = 0; i < n; i++) {
            cout << post[i];
            if (i < n - 1) cout << " ";
        }
    } else {
        cout << "NO";
    }
    return 0;
}

1044 Shopping in Mars

滑动窗口

#include <iostream>
#include <vector>
#include <map>
using namespace std;
const int N = 100005;
vector<pair<int, int> > res;
int nums[N];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    int tmp = 0, maxn = 0x3f3f3f3f;
    int l = 0, r = 0;
    while (r < n) {
        tmp += nums[r];
        if (tmp >= m && tmp < maxn) maxn = tmp;
        if (tmp == maxn) res.push_back({l + 1, r + 1});
        while (l < r && tmp >= m) {
            if (maxn > tmp) {
                maxn = tmp;
                res.clear();
                if (tmp == maxn) res.push_back({l + 1, r + 1});
            }
            tmp -= nums[l++];
            if (tmp == maxn) res.push_back({l + 1, r + 1});
        }
        r++;
    }
    for (int i = 0; i < res.size(); i++) {
        cout << res[i].first << "-" << res[i].second << endl;
    }
    return 0;
}

柳婼的（二分）

#include <iostream>
#include <vector>
using namespace std;
vector<int> sum, res;
int n, m;
void search(int i, int &j, int &tmp) {
    int l = i, r = n;
    while (l < r) {
        int mid = (l + r) / 2;
        if (sum[mid] - sum[i - 1] >= m)
            r = mid;
        else
            l = mid + 1;
    }
    j = r;
    tmp = sum[j] - sum[i - 1];
}
int main() {
    cin >> n >> m;
    sum.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> sum[i];
        sum[i] += sum[i - 1];
    }
    int minres = sum[n];
    for (int i = 1; i <= n; i++) {
        int j, tmpsum;
        search(i, j, tmpsum);
        if (tmpsum > minres) continue;
        if (tmpsum >= m) {
            if (tmpsum < minres) {
                res.clear();
                minres = tmpsum;
            }
            res.push_back(i);
            res.push_back(j);
        }
    }
    for (int i = 0; i < res.size(); i += 2)
        cout << res[i] << "-" << res[i + 1] << endl;
    return 0;
}

1045 Favorite Color Stripe

动态规划

#include <iostream>
#include <algorithm>
using namespace std;
int dp[10001], b[201], a[10001];
int main() {
    int n, m, x, l, num = 0, res = 0;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> x;
        b[x] = i;
    }
    cin >> l;
    for (int i = 0; i < l; i++) {
        cin >> x;
        if (b[x] >= 1)
            a[num++] = b[x];
    }
    for (int i = 0; i < num; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (a[i] >= a[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        res = max(dp[i], res);
    }
    cout << res;
    return 0;
}

1046 Shortest Distance

前缀和

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 200001;
int nums[N], sums[N];
int main() {
    int n, m, a, b;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> nums[i];
        nums[i + n] = nums[i];
        sums[i] = sums[i - 1] + nums[i];
    }
    for (int i = n + 1; i < n + n; i++) {
        sums[i] = sums[i - 1] + nums[i];
    }
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        if (a > b) swap(a, b);
        cout << min(sums[b - 1] - sums[a - 1], sums[a + n - 1] - sums[b - 1]) << endl;
    }
    return 0;
}

1047 Student List for Course

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
vector<string> course[2501];
int main() {
    int n, k, c, x;
    string name;
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> name >> c;
        for (int j = 0; j < c; j++) {
            cin >> x;
            course[x].push_back(name);
        }
    }
    for (int i = 1; i <= k; i++) {
        cout << i << " " << course[i].size() << endl;
        sort(course[i].begin(), course[i].end());
        for (int j = 0; j < course[i].size(); j++) {
            printf("%s\n", course[i][j].c_str());
        }
    }
    return 0;
}

1048 Find Coins

双指针

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100005;
int nums[N];
int main() {
    int n, m, cnt = 0, x;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> x;
        if (x < m) nums[cnt++] = x;
    }
    sort(nums, nums + cnt);
    int l = 0, r = cnt - 1, tmp = nums[l] + nums[r];
    while (l < r) {
        if (tmp == m) {
            cout << nums[l] << " " << nums[r];
            return 0;
        } else if (tmp > m) {
            r--;
        } else {
            l++;
        }
        tmp = nums[l] + nums[r];
    }
    cout << "No Solution";
    return 0;
}

柳婼的

#include <iostream>
using namespace std;
int nums[1001];
int main() {
    int n, m, cnt = 0, x;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> x;
        nums[x] ++;
    }
    for (int i = 0; i < 1001; i++) {
        if (nums[i]) {
            nums[i]--;
            if (m > i && nums[m - i]) {
                cout << i << " " << m - i;
                return 0;
            }
        }
    }
    cout << "No Solution";
    return 0;
}

1049 Counting Ones

暴力（超时）

#include <iostream>
using namespace std;
int main() {
    int n, cnt = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int a = i;
        while (a) {
            if (a % 10 == 1) cnt++;
            a /= 10;
        }
    }
    cout << cnt;
    return 0;
}

柳婼的

#include <iostream>
using namespace std;
int main() {
    int n, left = 0, right = 0, a = 1, now = 1, res = 0;
    cin >> n;
    while (n / a) {
        left = n / (a * 10), now = n / a % 10, right = n % a;
        if (now == 0) res += left * a;
        else if (now == 1) res += left * a + right + 1;
        else res += (left + 1) * a;
        a = a * 10;
    }
    cout << res;
    return 0;
}

1050 String Subtraction

#include <iostream>
#include <string>
#include <set>
using namespace std;
string s1, s2;
bool nums[129];
int main() {
    getline(cin, s1);
    getline(cin, s2);
    for (auto i: s2) {
        nums[i] = true;
    }
    for (auto i: s1) {
        if (!nums[i]) cout << i;
    }
    return 0;
}

1051 Pop Sequence

#include <iostream>
#include <stack>
using namespace std;
int main() {
    int m, n, k, x;
    cin >> m >> n >> k;
    for (int i = 0; i < k; i++) {
        int cnt = 1;
        stack<int> st;
        bool flag = true;
        for (int j = 0; j < n; j++) {
            cin >> x;
            while (x >= cnt && st.size() < m && cnt <= n) {
                st.push(cnt);
                cnt++;
            }
            if (st.top() != x) {
                flag = false;
                while (j++ < n - 1) cin >> x;
                break;
            }
            st.pop();
        }
        cout << (flag ? "YES" : "NO") << endl;
    }
    return 0;
}

1052 Linked List Sorting

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
typedef pair<int, int> PII;
struct node {
    int add, key, next;
};
bool cmp(PII a, PII b) {
    return a.second < b.second;
}
const int INF = 0x3f3f3f3f;
const int N = 100001;
node nums[N];
vector<PII> nums2;
int main() {
    int n, head, add, key, nex;
    cin >> n >> head;
    if (head == -1) {
        cout << "0 -1";
        return 0;
    }
    for (int i = 0; i < n; i++) {
        cin >> add >> key >> nex;
        nums[add] = {add, key, nex};
    }
    while (head != -1) {
        nums2.push_back({head, nums[head].key});
        head = nums[head].next;
    }
    sort(nums2.begin(), nums2.end(), cmp);
    printf("%d %05d\n", nums2.size(), nums2[0].first);
    for (int i = 0; i < nums2.size() - 1; i++) {
        printf("%05d %d %05d\n", nums2[i].first, nums2[i].second, nums2[i + 1].first);
    }
    printf("%05d %d -1\n", nums2[nums2.size() - 1].first, nums2[nums2.size() - 1].second);
    return 0;
}

1053 Path of Equal Weight

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 100;
int weight[N], sum, s;
vector<int> trees[N], tmp;
vector<vector<int> > res;
bool cmp(const vector<int> &a, const vector<int> &b) {
    for (int i = 0; ; i++) {
        if (a[i] != b[i]) return a[i] > b[i];
    }
}
void dfs(int x) {
    if (sum == s && trees[x].empty()) {
        res.push_back(tmp);
        return;
    }
    if (sum > s) return;
    for (int i = 0; i < trees[x].size(); i++) {
        sum += weight[trees[x][i]];
        tmp.push_back(weight[trees[x][i]]);
        dfs(trees[x][i]);
        sum -= weight[trees[x][i]];
        tmp.pop_back();
    }
}
int main() {
    int n, m, cur, k, child;
    cin >> n >> m >> s;
    for (int i = 0; i < n; i++) {
        cin >> weight[i];
    }
    s -= weight[0];
    tmp.push_back(weight[0]);
    for (int i = 0; i < m; i++) {
        cin >> cur >> k;
        for (int j = 0; j < k; j++) {
            cin >> child;
            trees[cur].push_back(child);
        }
    }
    dfs(0);
    sort(res.begin(), res.end(), cmp);
    for (int i = 0; i < res.size(); i++) {
        for (int j = 0; j < res[i].size(); j++) {
            printf("%d", res[i][j]);
            if (j < res[i].size() - 1) printf(" ");
            else printf("\n");
        }
    }
    return 0;
}

1054 The Dominant Color

#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
map<int, int> nums;
vector<pair<int, int> > res;
bool cmp(pair<int, int> a, pair<int, int> b) {
    return a.second > b.second;
}
int main() {
    int m, n, x;
    cin >> m >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> x;
            nums[x]++;
        }
    }
    for (auto it: nums) {
        res.push_back(it);
    }
    sort(res.begin(), res.end(), cmp);
    cout << res[0].first;
    return 0;
}

柳婼的

#include <iostream>
#include <map>
using namespace std;
map<int, int> nums;
int main() {
    int m, n, x;
    cin >> m >> n;
    int half = m * n / 2;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> x;
            nums[x]++;
            if (nums[x] > half) {
                cout << x;
                return 0;
            }
        }
    }
    return 0;
}

1055 The World’s Richest

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
struct node {
    string name;
    int age, worth;
};
bool cmp(node a, node b) {
    if (a.worth != b.worth) return a.worth > b.worth;
    else if (a.age != b.age) return a.age < b.age;
    else return a.name < b.name;
}
vector<node> nums[201];
int main() {
    int n, k, age, worth, m, start, end;
    cin >> n >> k;
    string name;
    for (int i = 0; i < n; i++) {
        cin >> name >> age >> worth;
        nums[age].push_back({name, age, worth});
    }
    for (int i = 1; i <= k; i++) {
        cin >> m >> start >> end;
        if (start < 1) start = 1;
        if (end > 200) end = 200;
        vector<node> tmp;
        for (int j = start; j <= end; j++) {
            for (auto it: nums[j]) {
                tmp.push_back({it.name, it.age, it.worth});
            }
        }
        sort(tmp.begin(), tmp.end(), cmp);
        printf("Case #%d:\n", i);
        for (int j = 0; j < min((int)tmp.size(), m); j++) {
            printf("%s %d %d\n", tmp[j].name.c_str(), tmp[j].age, tmp[j].worth);
        }
        if (tmp.empty()) printf("None");
    }
    return 0;
}

柳婼的

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
struct node {
    string name;
    int age, worth;
} nums[100001];
bool cmp(node a, node b) {
    if (a.worth != b.worth) return a.worth > b.worth;
    else if (a.age != b.age) return a.age < b.age;
    else return a.name < b.name;
}
int main() {
    int n, k, age, worth, m, start, end;
    cin >> n >> k;
    string name;
    for (int i = 0; i < n; i++) {
        cin >> nums[i].name >> nums[i].age >> nums[i].worth;
    }
    sort(nums, nums + n, cmp);
    for (int i = 1; i <= k; i++) {
        printf("Case #%d:\n", i);
        cin >> m >> start >> end;
        int cnt = 0;
        for (int j = 0; j < n; j++) {
            if (nums[j].age >= start && nums[j].age <= end) {
                printf("%s %d %d\n", nums[j].name.c_str(), nums[j].age, nums[j].worth);
                cnt++;
            }
            if (cnt == m) break;
        }
        if (cnt == 0) printf("None");
    }
    return 0;
}

1056 Mice and Rice

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int weight[10001], ranks[10001];
vector<int> tmp, res[300];
int main() {
    int np, ng, x;
    cin >> np >> ng;
    for (int i = 0; i < np; i++) {
        cin >> weight[i];
    }
    for (int i = 0; i < np; i++) {
        cin >> x;
        tmp.push_back(x);
    }
    int depth = 0, d = np / ng + 1;
    while (d--) {
        for (int i = 0; i < tmp.size(); i += ng) {
            int ma = 0, idx = 0;
            for (int j = i; j < min(ng + i, (int)tmp.size()); j++) {
                if (weight[tmp[j]] > ma) {
                    ma = weight[tmp[j]];
                    idx = tmp[j];
                }
            }
            res[depth + 1].push_back(idx);
            for (int j = i; j < min(ng + i, (int)tmp.size()); j++) {
                if (tmp[j] != idx) res[depth].push_back(tmp[j]);
            }
        }
        tmp.clear();
        tmp = res[depth + 1];
        res[depth + 1].clear();
        depth++;
    }
    int rank = 1;
    ranks[tmp[0]] = rank++;
    for (int i = depth - 1; i >= 0; i--) {
        for (auto it: res[i]) {
            ranks[it] = rank;
        }
        rank += res[i].size();
    }
    for (int i = 0; i < np; i++) {
        cout << ranks[i];
        if (i < np - 1) cout << " ";
    }
    return 0;
}

1057 Stack

暴力（超时）

#include <iostream>
#include <string>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
stack<int> st;
vector<int> tmp;
int main() {
    int n, x;
    string op;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> op;
        if (op == "Pop") {
            if (st.empty()) cout << "Invalid" << endl;
            else {
                cout << st.top() << endl;
                tmp.erase(find(tmp.begin(), tmp.end(), st.top()));
                st.pop();
            }
        } else if (op == "Push") {
            cin >> x;
            st.push(x);
            tmp.push_back(x);
        } else if (op == "PeekMedian") {
            if (st.empty()) cout << "Invalid" << endl;
            else {
                sort(tmp.begin(), tmp.end());
                if (tmp.size() % 2) cout << tmp[(tmp.size() - 1) / 2] << endl;
                else cout << tmp[tmp.size() / 2 - 1] << endl;
            }
        }
    }
    return 0;
}

柳婼的（树状数组）

#include <iostream>
#include <stack>
using namespace std;
#define lowbit(i) ((i) & (-i))
const int N = 100010;
int c[N];
stack<int> s;
void update(int x, int v) {
    for (int i = x; i < N; i += lowbit(i))
        c[i] += v;
}
int getsum(int x) {
    int sum = 0;
    for (int i = x; i >= 1; i -= lowbit(i))
        sum += c[i];
    return sum;
}
void PeekMedian() {
    int left = 1, right = N, mid, k = (s.size() + 1) / 2;
    while (left < right) {
        mid = (left + right) / 2;
        if (getsum(mid) >= k) 
            right = mid;
        else 
            left = mid + 1;
    }
    printf("%d\n", left);
}
int main() {
    int n, tmp;
    scanf("%d", &n);
    char str[15];
    for (int i = 0; i < n; i++) {
        scanf("%s", str);
        if (str[1] == 'u') {
            scanf("%d", &tmp);
            s.push(tmp);
            update(tmp, 1);
        } else if (str[1] == 'o') {
            if (!s.empty()) {
                update(s.top(), -1);
                printf("%d\n", s.top());
                s.pop();
            } else {
                printf("Invalid\n");
            }
        } else {
            if (!s.empty())
                PeekMedian();
            else
                printf("Invalid\n");
        }
    }
    return 0;
}

1058 A+B in Hogwarts - PAT (Advanced Level) Practice (pintia.cn)

#include <iostream>
int main() {
    int a1, a2, a3, b1, b2, b3, c1, c2, c3, t;
    scanf("%d.%d.%d %d.%d.%d", &a1, &a2, &a3, &b1, &b2, &b3);
    c3 = (a3 + b3) % 29;
    t = (a3 + b3) / 29;
    c2 = (a2 + b2 + t) % 17;
    t = (a2 + b2 + t) / 17;
    c1 = a1 + b1 + t;
    printf("%d.%d.%d", c1, c2, c3);
    return 0;
}

1059 Prime Factors

#include <iostream>
#include <cmath>
using namespace std;
typedef long long LL;
int main() {
    LL n;
    cin >> n;
    cout << n << "=";
    if (n == 1) cout << 1;
    for (LL i = 2; i <= sqrt(n); i++) {
        int cnt = 0;
        if (n % i == 0) {
            while (n % i == 0) {
                cnt++;
                n /= i;
            }
        }
        if (cnt > 1) cout << i << "^" << cnt;
        else if (cnt == 1) cout << i;
        if (cnt != 0 && n > 1) cout << "*";
    }
    if (n > 1) cout << n;
    return 0;
}

1060 Are They Equal

#include <iostream>
#include <string>
using namespace std;
string convert(string str, int n) {
    int idx = 0, len = str.size(), k = 0;
    string t;
    while (idx < len && str[idx] == '0') idx++;
    if (str[idx] == '.') {
        idx++;
        while (idx < len && str[idx] == '0') {
            idx++;
            k--;
        }
        bool flag = false;
        while (t.size() < n && idx < len) {
            t.push_back(str[idx++]);
            flag = true;
        }
        while (t.size() < n) t.push_back('0');
        if (!flag) k = 0;
    } else {
        for (int j = idx; str[j] != '.' && j < len; j++) k++;
        while (str[idx] != '.' && t.size() < n && idx < len)
            t.push_back(str[idx++]);
        if (t.size() < n) idx++;
        while (idx < len && t.size() < n) 
            t.push_back(str[idx++]);
        while (t.size() < n) t.push_back('0');
    }
    return "0." + t + "*10^" + to_string(k);
}
int main() {
    int n;
    string a, b;
    cin >> n >> a >> b;
    a = convert(a, n);
    b = convert(b, n);
    if (a == b) cout << "YES " << a;
    else cout << "NO " << a << " " << b;
    return 0;
}

1061 Dating

#include <iostream>
#include <string>
using namespace std;
int main() {
    string a, b, c, d;
    cin >> a >> b >> c >> d;
    int sa = a.size(), sb = b.size(), sc = c.size(), sd = d.size();
    int week, hour, minute, cnt = 0;
    string weeks[7] = {"MON", "TUE", "WED", "THU", "FRI", "SAT", "SUN"};
    bool is_first = true;
    for (int i = 0; i < min(sa, sb); i++) {
        if (a[i] == b[i] && a[i] >= 'A' && a[i] <= 'G' && is_first) {
            week = a[i] - 'A';
            is_first = false;
            continue;
        }
        if (!is_first && a[i] == b[i] && ((a[i] >= 'A' && a[i] <= 'N') || isdigit(a[i]))) {
            if (a[i] >= 'A' && a[i] <= 'N') {
                hour = a[i] - 'A' + 10;
            } else if (isdigit(a[i])) {
                hour = a[i] - '0';
            }
            break;
        }
    }
    for (int i = 0; i < min(sc, sd); i++) {
        if (c[i] == d[i] && isalpha(c[i])) {
            minute = i;
            break;
        }
    }
    printf("%s %02d:%02d", weeks[week].c_str(), hour, minute);
    return 0;
}

1062 Talent and Virtue

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
struct node {
    int num, virtue, talent, sum;
};
bool cmp(node a, node b) {
    if (a.sum != b.sum) return a.sum > b.sum;
    else if (a.virtue != b.virtue) return a.virtue > b.virtue;
    else if (a.talent != b.talent) return a.talent > b.talent;
    else return a.num < b.num;
}
vector<node> sage, nobleman, fool, small;
int main() {
    int n, l, h, num, virtue, talent;
    cin >> n >> l >> h;
    for (int i = 0; i < n; i++) {
        cin >> num >> virtue >> talent;
        int sum = virtue + talent;
        if (virtue >= h && talent >= h) {
            sage.push_back({num, virtue, talent, sum});
        } else if (virtue >= h && talent >= l) {
            nobleman.push_back({num, virtue, talent, sum});
        } else if (virtue >= talent && talent >= l) {
            fool.push_back({num, virtue, talent, sum});
        } else if (virtue >= l && talent >= l) {
            small.push_back({num, virtue, talent, sum});
        }
    }
    sort(sage.begin(), sage.end(), cmp);
    sort(nobleman.begin(), nobleman.end(), cmp);
    sort(fool.begin(), fool.end(), cmp);
    sort(small.begin(), small.end(), cmp);
    cout << sage.size() + nobleman.size() + fool.size() + small.size()<< endl;
    for (auto it: sage) {
        printf("%08d %d %d\n", it.num, it.virtue, it.talent);
    }
    for (auto it: nobleman) {
        printf("%08d %d %d\n", it.num, it.virtue, it.talent);
    }
    for (auto it: fool) {
        printf("%08d %d %d\n", it.num, it.virtue, it.talent);
    }
    for (auto it: small) {
        printf("%08d %d %d\n", it.num, it.virtue, it.talent);
    }
    return 0;
}

1063 Set Similarity

#include <iostream>
#include <map>
using namespace std;
map<int, bool> nums[51];
int main() {
    int n, m, x, k, a, b;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> m;
        for (int j = 0; j < m; j++) {
            scanf("%d", &x);
            nums[i][x] = true;
        }
    }
    cin >> k;
    for (int i = 0; i < k; i++) {
        cin >> a >> b;
        map<int, bool> tmp;
        tmp = nums[a];
        int common = 0, total = 0;
        for (auto it: nums[b]) {
            if (tmp[it.first]) {
                tmp[it.first] = false;
                common++;
                total++;
            } else {
                total++;
            }
        }
        for (auto it: tmp) {
            if (it.second) total++;
        }
        printf("%.1f\%\n", common * 100.0 / total);
    }
    return 0;
}

1064 Complete Binary Search Tree

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1001;
int in[N], level[N], n, idx = 0;
void dfs(int root) {
    if (root >= n) return;
    dfs(root * 2 + 1);
    level[root] = in[idx++];
    dfs(root * 2 + 2);
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> in[i];
    }
    sort(in, in + n);
    dfs(0);
    for (int i = 0; i < n; i++) {
        cout << level[i];
        if (i < n - 1) cout << " ";
    }
    return 0;
}

1065 A+B and C (64bit)

#include <iostream>
using namespace std;
typedef long long LL;
int main() {
    int n;
    LL a, b, c;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a >> b >> c;
        LL t = a + b;
        if (a > 0 && b > 0 && t < 0) {
            cout << "Case #" << i << ": true" << endl;
        } else if (a < 0 && b < 0 && t > 0) {
            cout << "Case #" << i << ": false" << endl;
        } else if (a + b > c) {
            cout << "Case #" << i << ": true" << endl;
        } else {
            cout << "Case #" << i << ": false" << endl;
        }
    }
    return 0;
}

1066 Root of AVL Tree

#include <iostream>
using namespace std;
struct node {
    int val;
    node *left, *right;
};
node* rotateLeft(node* root) {
    node *t = root->right;
    root->right = t->left;
    t->left = root;
    return t;
}
node* rotateRight(node* root) {
    node *t = root->left;
    root->left = t->right;
    t->right = root;
    return t;
}
node* rotateLeftRight(node* root) {
    root->left = rotateLeft(root->left);
    return rotateRight(root);
}
node* rotateRightLeft(node* root) {
    root->right = rotateRight(root->right);
    return rotateLeft(root);
}
int getHeight(node* root) {
    if (root == NULL) return 0;
    return max(getHeight(root->left), getHeight(root->right)) + 1;
}
node* insert(node* root, int val) {
    if (root == NULL) {
        root = new node();
        root->val = val;
        root->left = NULL;
        root->right = NULL;
    } else if (val < root->val) {
        root->left = insert(root->left, val);
        if (getHeight(root->left) - getHeight(root->right) == 2) {
            root = val < root->left->val ? rotateRight(root) : rotateLeftRight(root);
        }
    } else {
        root->right = insert(root->right, val);
        if (getHeight(root->right) - getHeight(root->left) == 2) {
            root = val > root->right->val ? rotateLeft(root) : rotateRightLeft(root);
        }
    }
    return root;
}
int main() {
    int n, val;
    cin >> n;
    node *root = NULL;
    for (int i = 0; i < n; i++) {
        cin >> val;
        root = insert(root, val);
    }
    cout << ("%d", root->val);
    return 0;
}

1067 Sort with Swap(0, i)

#include <iostream>
#include <algorithm>
using namespace std;
int nums[100001];
int main() {
    int n, x, res = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        nums[x] = i;
    }
    for (int i = 1; i < n; i++) {
        if (nums[i] != i) {
            while (nums[0] != 0) {
                swap(nums[0], nums[nums[0]]);
                res++;
            }
            if (nums[i] != i) {
                swap(nums[0], nums[i]);
                res++;
            }
        }
    }
    cout << res;
    return 0;
}

1068 Find More Coins

dfs

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int nums[10001], n, m;
vector<int> tmp;
void dfs(int x, int t) {
    if (t == m) {
        for (int i = 0; i < tmp.size(); i++) {
            cout << tmp[i];
            if (i < tmp.size() - 1) cout << " ";
        }
        exit(0);
    }
    if (t > m || x == n) return;
    tmp.push_back(nums[x]);
    dfs(x + 1, t + nums[x]);
    tmp.pop_back();
    dfs(x + 1, t);
}
int main() {
    int sum = 0;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
        sum += nums[i];
    }
    if (sum < m) cout << "No Solution";
    else {
        sort(nums, nums + n);
        dfs(0, 0);
        cout << "No Solution";
    }
    return 0;
}

柳婼的（dp）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int dp[100001], nums[100001];
bool choice[100001][110];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> nums[i];
    }
    sort(nums + 1, nums + n + 1, greater<int>());
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= nums[i]; j--) {
            if (dp[j] <= dp[j - nums[i]] + nums[i]) {
                choice[i][j] = true;
                dp[j] = dp[j - nums[i]] + nums[i];
            }
        }
    }
    if (dp[m] != m) cout << "No Solution";
    else {
        vector<int> res;
        int v = m, idx = n;
        while(v > 0) {
            if (choice[idx][v] == true) {
                res.push_back(nums[idx]);
                v -= nums[idx];
            }
            idx--;
        }
        for (int i = 0; i < res.size(); i++) {
            cout << res[i];
            if (i < res.size() - 1) cout << " ";
        }
    }
    return 0;
}

1069 The Black Hole of Numbers

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
    string n;
    cin >> n;
    while(n.size() < 4) n = '0' + n;
    do {
        string a = n, b = n;
        sort(a.begin(), a.end());
        sort(b.begin(), b.end(), greater<char>());
        int c = stoi(b) - stoi(a);
        n = to_string(c);
        while(n.size() < 4) n = '0' + n;
        cout << b << " - " << a << " = " << n << endl;
    } while (n != "6174" && n!= "0000");
    return 0;
}

1070 Mooncake

#include <iostream>
#include <algorithm>
using namespace std;
struct node{
    double amount, price, profit;
} nums[1001];
bool cmp(node &a, node &b) {
    return a.profit > b.profit;
}
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> nums[i].amount;
    }
    for (int i = 0; i < n; i++) {
        cin >> nums[i].price;
        nums[i].profit = nums[i].price / nums[i].amount;
    }
    sort(nums, nums + n, cmp);
    double res;
    for (int i = 0; i < n; i++) {
        if (nums[i].amount >= m) {
            res += m * nums[i].profit;
            break;
        } else {
            res += nums[i].price;
            m -= nums[i].amount;
        }
    }
    printf("%.2f", res);
    return 0;
}

1071 Speech Patterns

#include <iostream>
#include <string>
#include <map>
using namespace std;
map<string, int> nums;
int main() {
    string str;
    getline(cin, str);
    str += '.';
    for (int i = 0; i < str.size(); i++) {
        for (int j = i; j < str.size(); j++) {
            if (isalpha(str[j])) str[j] = tolower(str[j]);
            if (!isalnum(str[j])) {
                if (j != i) {
                    nums[str.substr(i, j - i)]++;
                }
                i = j;
                break;
            }
        }
    }
    string res = nums.begin()->first;
    int m = nums.begin()->second;
    for (auto it: nums) {
        if (m < it.second) {
            m = it.second;
            res = it.first;
        }
    }
    cout << res << " " << m;
    return 0;
}

1072 Gas Station

dijkstra

#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;
const int N = 1012;
const int INF = 0x3f3f3f3f;
vector<pair<int, int> > g[N];
int dist[N], n, m, sums[11], mins[11];
bool visit[N];
void dijkstra(int x) {
    fill(dist, dist + N, INF);
    fill(visit, visit + N, false);
    dist[x] = 0;
    for (int i = 0; i < n + m; i++) {
        int u = -1, mind = INF;
        for (int j = 1; j <= n + m; j++) {
            if (!visit[j] && mind > dist[j]) {
                mind = dist[j];
                u = j;
            }
        }
        if (u == -1) return;
        visit[u] = true;
        for (int j = 0; j < g[u].size(); j++) {
            int v = g[u][j].first;
            int dis = g[u][j].second;
            if (!visit[v] && dist[v] > dist[u] + dis) {
                dist[v] = dist[u] + dis;
            }
        }
    }
}
int main() {
    int k, d, dis, t1, t2;
    string p1, p2;
    cin >> n >> m >> k >> d;
    for (int i = 0; i < k; i++) {
        cin >> p1 >> p2 >> dis;
        if (p1[0] == 'G') t1 = n + stoi(p1.substr(1));
        else t1 = stoi(p1);
        if (p2[0] == 'G') t2 = n + stoi(p2.substr(1));
        else t2 = stoi(p2);
        g[t1].push_back({t2, dis});
        g[t2].push_back({t1, dis});
    }
    int real_sum = INF, real_min = 0, real_id = 0;
    for (int i = 1; i <= m; i++) {
        dijkstra(n + i);
        int res = INF, sum = 0;
        bool flag = true;
        for (int j = 1; j <= n; j++) {
            if (dist[j] > d) {
                flag = false;
                break;
            }
            sum += dist[j];
            res = min(res, dist[j]);
        }
        if (flag) {
            if (real_min < res) {
                real_sum = sum;
                real_id = i;
                real_min = res;
            } else if (real_min == res) {
                if (real_sum > sum) {
                    real_sum = sum;
                    real_id = i;
                }
            }
        }
    }
    if (real_min == 0) cout << "No Solution";
    else printf("G%d\n%.1f %.1f", real_id, (double)real_min, (double)real_sum / n);
    return 0;
}

1073 Scientific Notation

#include <iostream>
#include <string>
using namespace std;
int main() {
    string str;
    cin >> str;
    if (str[0] == '-') cout << "-";
    int exp, i;
    for (i = 3; i < str.size(); i++) {
        if (str[i] == 'E') break;
    }
    if (str[i + 1] == '-') {
        exp = stoi(str.substr(i + 2));
        cout << "0.";
        for (int j = 0; j < exp - 1; j++) cout << 0;
        cout << str[1] << str.substr(3, i - 3);
    } else {
        exp = stoi(str.substr(i + 1));
        if (str[1] != '0') cout << str[1];
        if (exp < i - 3) {
            for (int j = 0; j < exp; j++) {
                cout << str[j + 3];
            }
            cout << ".";
            for (int j = exp; j < i - 3; j++) {
                cout << str[j + 3];
            }
        } else {
            for (int j = 0; j < exp; j++) {
                if (j < i - 3) cout << str[j + 3];
                else cout << 0;
            }
        }
    }
    return 0;
}

柳婼的

#include <iostream>
#include <string>
using namespace std;
int main() {
    string s;
    cin >> s;
    int i = 0;
    while (s[i] != 'E') i++;
    string t = s.substr(1, i - 1);
    int n = stoi(s.substr(i + 1));
    if (s[0] == '-') cout << "-";
    if (n < 0) {
        cout << "0.";
        for (int j = 0; j < abs(n) - 1; j++) cout << '0';
        for (int j = 0; j < t.length(); j++)
            if (t[j] != '.') cout << t[j];
    } else {
        cout << t[0];
        int cnt, j;
        for (j = 2, cnt = 0; j < t.length() && cnt < n; j++, cnt++) 
            cout << t[j];
        if (j == t.length()) {
            for (int k = 0; k < n - cnt; k++) cout << '0';
        } else {
            cout << '.';
            for (int k = j; k < t.length(); k++) cout << t[k];
        }
    }
    return 0;
}

1074 Reversing Linked List

数组模拟

#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;
struct node {
    string addr, nex;
    int val;
} ;
map<string, node> nums1;
vector<node> nums2;
int main() {
    int n, k, val;
    string start, addr, nex;
    cin >> start >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> addr >> val >> nex;
        nums1[addr] = {addr, nex, val};
    }
    while (start != "-1") {
        nums2.push_back({nums1[start].addr, nums1[start].nex, nums1[start].val});
        start = nums1[start].nex;
    }
    for (i = 0; i <= nums2.size() - k; i += k) {
        for (int j = i + k - 1; j > i; j--) {
            cout << nums2[j].addr << " " << nums2[j].val << " " << nums2[j - 1].addr << endl;
        }
        cout << nums2[i].addr << " " << nums2[i].val << " ";
        if (i + 2 * k <= nums2.size()) cout << nums2[i + 2 * k - 1].addr << endl;
        else if (i + k < nums2.size()) cout << nums2[i + k].addr << endl;
        else cout << "-1\n";
    }
    for (int j = i; j < nums2.size(); j++) {
        cout << nums2[j].addr << " " << nums2[j].val << " " << nums2[j].nex << endl;
    }
    return 0;
}

柳婼的

#include <iostream>
using namespace std;
const int N = 100005;
int datas[N], nexts[N], list[N], res[N];
int main() {
    int first, k, n, sum = 0, tmp;
    cin >> first >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> tmp;
        cin >> datas[tmp] >> nexts[tmp];
    }
    while (first != -1) {
        list[sum++] = first;
        first = nexts[first];
    }
    for (int i = 0; i < sum; i++) res[i] = list[i];
    for (int i = 0; i < (sum - sum % k); i++) 
        res[i] = list[i / k * k + k - 1 - i % k];
    for (int i = 0; i < sum - 1; i++) 
        printf("%05d %d %05d\n", res[i], datas[res[i]], res[i + 1]);
    printf("%05d %d -1", res[sum - 1], datas[res[sum - 1]]);
    return 0;
}

1075 PAT Judge

#include <iostream>
#include <algorithm>
using namespace std;
struct node {
    int userId = 99999, totle, s[6] = {-1, -1, -1, -1, -1, -1}, perfect;
    bool isShow;
} nums[10001];
bool cmp(node &a, node &b) {
    if (a.totle != b.totle) return a.totle > b.totle;
    else if (a.perfect != b.perfect) return a.perfect > b.perfect;
    return a.userId < b.userId;
}
int w[6];
int main() {
    int n, k, m;
    cin >> n >> k >> m;
    for (int i = 1; i <= k; i++) {
        cin >> w[i];
    }
    int userId, problemId, score;
    for (int i = 0; i < m; i++) {
        cin >> userId >> problemId >> score;
        nums[userId].userId = userId;
        if (score < 1) nums[userId].s[problemId] = max(0, nums[userId].s[problemId]);
        if (score >= 0) nums[userId].isShow = true;
        if (score > nums[userId].s[problemId]) {
            if (score == w[problemId]) nums[userId].perfect++;
            nums[userId].totle += score - max(0, nums[userId].s[problemId]);
            nums[userId].s[problemId] = score;
        }
    }
    sort(nums, nums + 10001, cmp);
    int rank = 1;
    for (int i = 0; i < 10000; i++) {
        if (!nums[i].isShow) break;
        if (i != 0 && nums[i].totle != nums[i - 1].totle) rank = i + 1;
        printf("%d %05d %d ", rank, nums[i].userId, nums[i].totle);
        for (int j = 1; j <= k; j++) {
            if (nums[i].s[j] < 0) cout << "-";
            else cout << nums[i].s[j];
            if (j < k) cout << " ";
            else cout << endl;
        }
    }
    return 0;
}

1076 Forwards on Weibo

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> g[1001];
bool visit[1001];
int bfs(int u, int l) {
    queue<int> q;
    q.push(u);
    fill(visit, visit + 1001, false);
    visit[u] = true;
    int res = 0, cnt = 0;
    while (!q.empty()) {
        if (cnt >= l) break;
        int len = q.size();
        for (int i = 0; i < len; i++) {
            u = q.front();
            q.pop();
            for (int j = 0; j < g[u].size(); j++) {
                if (!visit[g[u][j]]) {
                    visit[g[u][j]] = true;
                    res++;
                    q.push(g[u][j]);
                }
            }
        }
        cnt++;
    }
    return res;
}
int main() {
    int n, l, m, x, k, query;
    cin >> n >> l;
    for (int i = 1; i <= n; i++) {
        cin >> m;
        for (int j = 0; j < m; j++) {
            cin >> x;
            g[x].push_back(i);
        }
    }
    cin >> k;
    for (int i = 0; i < k; i++) {
        cin >> query;
        int res = bfs(query, l);
        cout << res << endl;
    }
    return 0;
}

1077 Kuchiguse

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string strs[101];
int main() {
    int n, len = 257;
    cin >> n;
    getchar();
    for (int i = 0; i < n; i++) {
        getline(cin, strs[i]);
        len = min((int)strs[i].size(), len);
    }
    string res = "";
    for (int i = 1; i <= len; i++) {
        char ch = strs[0][strs[0].size() - i];
        for (int j = 0; j < n; j++) {
            if (strs[j][strs[j].size() - i] != ch) {
                if (res.empty()) cout << "nai";
                else cout << res;
                return 0;
            }
        }
        res = ch + res;
    }
    cout << res;
    return 0;
}

1078 Hashing

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 20001;
vector<int> primes;
bool st[N];
bool res[N];
int main() {
    int m, n, x;
    cin >> m >> n;
    for (int i = 2; i < N; i++) {
        if (!st[i]) {
            primes.push_back(i);
            if (i >= m) {
                m = i;
                break;
            }
            for (int j = i * 2; j < N; j += i) {
                st[j] = true;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        cin >> x;
        bool flag = false;
        for (int j = 0; j < m; j++) {
            if (!res[(x + j * j) % m]) {
                cout << (x + j * j) % m;
                res[(x + j * j) % m] = true;
                flag = true;
                break;
            }
        }
        if (!flag) cout << "-";
        if (i < n - 1) cout << " ";
    }
    return 0;
}

1079 Total Sales of Supply Chain

#include <iostream>
#include <vector>
using namespace std;
struct node{
    int val;
    vector<int> child;
} trees[100001];
double r, res;
void dfs(int u, double p) {
    if (trees[u].child.empty()) {
        res += trees[u].val * p;
        return;
    } 
    for (int i = 0; i <trees[u].child.size(); i++) {
        dfs(trees[u].child[i], p + p * r);
    }
}
int main() {
    int n, k, x;
    double p;
    cin >> n >> p >> r;
    r /= 100;
    for (int i = 0; i < n; i++) {
        cin >> k;
        if (k == 0) {
            cin >> x;
            trees[i].val = x;
        } else {
            for (int j = 0; j < k; j++) {
                cin >> x;
                trees[i].child.push_back(x);
            }
        }
    }
    dfs(0, p);
    printf("%.1f", res);
    return 0;
}

1080 Graduate Admission

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct student {
    int num, ge, gi, total, apps[6], rank;
} students[40001];
int limits[101];
vector<int> schools[101];
bool cmp(student &a, student &b) {
    if (a.total != b.total) return a.total > b.total;
    else if (a.ge != b.ge) return a.ge > b.ge;
    else return a.num < b.num;
}
int main() {
    int n, m, k, ge, gi, total, rank = 1;
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++) {
        cin >> limits[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> students[i].ge >> students[i].gi;
        students[i].total = students[i].ge + students[i].gi;
        for (int j = 0; j < k; j++) {
            cin >> students[i].apps[j];
        }
        students[i].num = i;
    }
    sort(students, students + n, cmp);
    for (int i = 0; i < n; i++) {
        if (i != 0 && (students[i].total != students[i - 1].total || students[i].ge != students[i - 1].ge)) rank++;
        students[i].rank = rank;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k; j++) {
            int t = students[i].apps[j];
            if (limits[t]) {
                schools[t].push_back(students[i].num);
                limits[t]--;
                while (limits[t] == 0 && i < n - 1 && students[i].rank == students[i + 1].rank) {
                    schools[t].push_back(students[i + 1].num);
                    i++;
                }
                break;
            }
        }
    }
    for (int i = 0; i < m; i++) {
        sort(schools[i].begin(), schools[i].end());
        for (int j = 0; j < schools[i].size(); j++) {
            cout << schools[i][j];
            if (j < schools[i].size() - 1) cout << " ";
        }
        cout << endl;
    }
    return 0;
}

1081 Rational Sum

#include <iostream>
using namespace std;
typedef long long LL;
LL gcd(LL a, LL b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}
void convert(LL a, LL b) {
    if (a * b < 0) {
        cout << "-";
        a = abs(a);
        b = abs(b);
    }
    LL t = a / b;
    if (t) cout << t;
    a -= b * t;
    if (a == 0) {
        if (t == 0) cout << 0;
        return;
    }
    if (t != 0) cout << " ";
    cout << a << "/" << b;
}
int main() {
    LL n, numerator, denominator, a, b;
    cin >> n;
    for (int i = 0; i < n; i++) {
        scanf("%lld/%lld", &a, &b);
        if (i != 0) {
            LL c = numerator * b + denominator * a;
            LL d = denominator * b;
            LL t = gcd(c, d);
            numerator = c / t;
            denominator = d / t;
        } else numerator = a, denominator = b;
    }
    convert(numerator, denominator);
    return 0;
}

1082 Read Number in Chinese

大模拟

#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main() {
    string dicts[10] = {"ling", "yi", "er", "san", "si", "wu", "liu", "qi", "ba", "jiu"};
    int n;
    vector<string> res;
    cin >> n;
    if (n == 0) {
        cout << "ling";
        return 0;
    }
    if (n < 0) {
        res.push_back("Fu");
        n = -n;
    }
    int raw = n;
    if (n >= 100000000) {
        res.push_back(dicts[n / 100000000]);
        res.push_back("Yi");
        n = n % 100000000;
    }
    bool zero = false;
    if (n >= 10000) {
        if (n / 10000000) {
            res.push_back(dicts[n / 10000000]);
            res.push_back("Qian");
            n %= 10000000;
        } else if (raw > 10000000){
            zero = true;
        }
        if (n / 1000000) {
            if (zero) {
                res.push_back("ling");
                zero = false;
            }
            res.push_back(dicts[n / 1000000]);
            res.push_back("Bai");
            n %= 1000000;
        } else if (raw > 1000000) {
            zero = true;
        }
        if (n / 100000) {
            if (zero) {
                res.push_back("ling");
                zero = false;
            }
            res.push_back(dicts[n / 100000]);
            res.push_back("Shi");
            n %= 100000;
        } else  if (raw > 100000){
            zero = true;
        }
        if (n / 10000) {
            if (zero) {
                res.push_back("ling");
                zero = false;
            }
            res.push_back(dicts[n / 10000]);
            n %= 10000;
        }
        res.push_back("Wan");
    }
    zero = false;
    if (n / 1000) {
        res.push_back(dicts[n / 1000]);
        res.push_back("Qian");
        n %= 1000;
    } else if (raw > 1000){
        zero = true;
    }
    if (n / 100) {
        if (zero) {
            res.push_back("ling");
            zero = false;
        }
        res.push_back(dicts[n / 100]);
        res.push_back("Bai");
        n %= 100;
    } else if (raw > 100){
        zero = true;
    }
    if (n / 10) {
        if (zero) {
            res.push_back("ling");
            zero = false;
        }
        res.push_back(dicts[n / 10]);
        res.push_back("Shi");
        n %= 10;
    } else if (raw > 10){
        zero = true;
    }
    if (n % 10) {
        if (zero) {
            res.push_back("ling");
            zero = false;
        }
        res.push_back(dicts[n % 10]);
    }
    for (int i = 0; i < res.size(); i++) {
        cout << res[i];
        if (i < res.size() - 1) cout << " ";
    }
    return 0;
}

优化

#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main() {
    string nums[10] = {"ling", "yi", "er", "san", "si", "wu", "liu", "qi", "ba", "jiu"};
    string wei[5] = {"Shi", "Bai", "Qian", "Wan", "Yi"};
    string str;
    cin >> str;
    int len = str.length();
    int left = 0, right = len - 1;
    if (str[0] == '-') {
        cout << "Fu";
        left++;
    }
    while (left + 4 <= right)
        right -= 4;
    while (left < len) {
        bool flag = false, isPrint = false;
        while (left <= right) {
            if (left > 0 && str[left] == '0') 
                flag = true;
            else {
                if (flag == true) {
                    cout << " ling";
                    flag = false;
                }
                if (left > 0) 
                    cout << " ";
                cout << nums[str[left] - '0'];
                isPrint = true;
                if (left != right)
                    cout << " " << wei[right - left - 1];
            }
            left++;
        }
        if (isPrint == true && right != len - 1) 
            cout << " " << wei[(len - 1 - right) / 4 + 2];
        right += 4;
    }
    return 0;
}

1083 List Grades

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
struct node{
    string name, num;
    int grade;
} nums[100001];
bool cmp(node a, node b) {
    return a.grade > b.grade;
}
int main() {
    int n, left, right;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> nums[i].name >> nums[i].num >> nums[i].grade;
    }
    cin >> left >> right;
    sort(nums, nums + n, cmp);
    bool flag = true;
    for (int i = 0; i < n; i++) {
        if (nums[i].grade >= left && nums[i].grade <= right) {
            cout << nums[i].name << " " << nums[i].num << endl;
            flag = false;
        }
    }
    if (flag) cout << "NONE";
    return 0;
}

1084 Broken Keyboard

#include <iostream>
#include <string>
using namespace std;
bool st[256];
int main() {
    string a, b;
    cin >> a >> b;
    for (int i = 0; i < a.size(); i++) {
        if (isalpha(a[i])) a[i] = tolower(a[i]);
        st[a[i]] = true;
    }
    for (int i = 0; i < b.size(); i++) {
        if (isalpha(b[i])) b[i] = tolower(b[i]);
        st[b[i]] = false;
    }
    for (int i = 0; i < a.size(); i++) {
        if (st[a[i]]) {
            char t = a[i];
            if (isalpha(t)) t = toupper(t);
            cout << t;
            st[a[i]] = false;
        }
    }
    return 0;
}

柳婼的

#include <iostream>
using namespace std;
int main() {
    string s1, s2, res;
    cin >> s1 >> s2;
    for (int i = 0; i < s1.size(); i++) 
        if (s2.find(s1[i]) == string::npos && res.find(toupper(s1[i])) == string::npos)
            res += toupper(s1[i]);
    cout << res;
    return 0;
}

1085 Perfect Sequence

暴力（超时）

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
LL nums[100001], res = 1, p;
void dfs(LL l, LL r) {
    if (res > r - l + 1) return;
    if (nums[l] * p < nums[r]) {
        dfs(l + 1, r);
        dfs(l, r - 1);
    } else {
        res = max(res, r - l + 1);
    }
}
int main() {
    int n;
    cin >> n >> p;
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    sort(nums, nums + n);
    dfs(0, n - 1);
    cout << res;
    return 0;
}

柳婼的

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
LL nums[100001];
int main() {
    int n, p, res = 1;
    cin >> n >> p;
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    sort(nums, nums + n);
    for (int i = 0; i < n; i++) {
        // res = max((int)(upper_bound(nums, nums + n, nums[i] * p) - (nums + i)), res);
        for (int j = i + res; j < n; j++) {
            if (nums[i] * p >= nums[j]) {
                res = max(res, j - i + 1);
            } else break;
        }
    }
    cout << res;
    return 0;
}

1086 Tree Traversals Again

#include <iostream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
struct node{
    int l, r;
} trees[31];
stack<int> st;
vector<int> in, pre, post;
int build(int preL, int preR, int inL, int inR) {
    if (preL > preR) return -1;
    int root = in[inL], idx = preL;
    for (int i = preL; i <= preR; i++) {
        if (root == pre[i]) {
            idx = i;
            break;
        }
    }
    int cntL = idx - preL;
    trees[root].l = build(preL, preL + cntL - 1, inL + 1, inL + cntL);
    trees[root].r = build(idx + 1, preR, inL + cntL + 1, inR);
    return root;
}
void dfs(int root) {
    if (root == -1) return;
    dfs(trees[root].l);
    dfs(trees[root].r);
    post.push_back(root);
}
int main() {
    int n, x;
    string ops;
    cin >> n;
    for (int i = 0; i < 2 * n; i++) {
        cin >> ops;
        if (ops == "Push") {
            cin >> x;
            st.push(x);
            in.push_back(x);
        } else {
            pre.push_back(st.top());
            st.pop();
        }
    }
    int root = build(0, n - 1, 0, n - 1);
    dfs(root);
    for (int i = 0; i < post.size(); i++) {
        cout << post[i];
        if (i < post.size() - 1) cout << " ";
    }
    return 0;
}

柳婼的

#include <iostream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
stack<int> st;
vector<int> pre, in, post, value;
void postorder(int root, int start, int end) {
    if (start > end) return;
    int i = start;
    while (i < end && in[i] != pre[root]) i++;
    postorder(root + 1, start, i - 1);
    postorder(root + 1 + i - start, i + 1, end);
    post.push_back(pre[root]);
}
int main() {
    int n, x, key = 0;
    string ops;
    cin >> n;
    for (int i = 0; i < 2 * n; i++) {
        cin >> ops;
        if (ops == "Push") {
            cin >> x;
            value.push_back(x);
            pre.push_back(key);
            st.push(key++);
        } else {
            in.push_back(st.top());
            st.pop();
        }
    }
    postorder(0, 0, n - 1);
    for (int i = 0; i < n; i++) {
        cout << value[post[i]];
        if (i < n - 1) cout << " ";
    }
    return 0;
}

1087 All Roads Lead to Rome

#include <iostream>
#include <vector>
#include <map>
#include <string>
using namespace std;
typedef pair<int, int> PII;
const int N = 201;
const int INF = 0x3f3f3f3f;
map<string, int> strToInt;
string intToStr[N], start;
vector<PII> g[N];
int d[N], haps[N], pre[N], cnt[N], happys[N], cnt2[N], n;
bool visit[N];
void dijkstra(int a) {
    fill(d, d + n, INF);
    d[a] = 0;
    cnt2[a] = 1;
    for (int i = 0; i < n; i++) {
        int u = -1, mind = INF;
        for (int j = 0; j < n; j++) {
            if (!visit[j] && d[j] < mind) {
                u = j;
                mind = d[j];
            }
        }
        if (u == -1) return;
        visit[u] = true;
        for (int j = 0; j < g[u].size(); j++) {
            int v = g[u][j].first, dis = g[u][j].second;
            if (!visit[v]) {
                if (d[v] > d[u] + dis) {
                    d[v] = d[u] + dis;
                    happys[v] = happys[u] + haps[v];
                    cnt[v] = cnt[u] + 1;
                    cnt2[v] = cnt2[u];
                    pre[v] = u;
                } else if (d[v] == d[u] + dis) {
                    if (happys[v] < happys[u] + haps[v]) {
                        happys[v] = happys[u] + haps[v];
                        cnt[v] = cnt[u] + 1;
                        pre[v] = u;
                    } else if (happys[v] == happys[u] + haps[v]) {
                        if (cnt[v] > cnt[u] + 1) {
                            cnt[v] = cnt[u] + 1;
                            pre[v] = u;
                        }
                    }
                    cnt2[v] += cnt2[u];
                }
            }
        }
    }
}
vector<int> res;
void dfs(int u) {
    res.push_back(u);
    if (u == strToInt[start]) {
        for (int i = res.size() - 1; i >= 0; i--) {
            cout << intToStr[res[i]];
            if (i > 0) cout << "->";
        }
    } else {
        dfs(pre[u]);
    }
}
int main() {
    string city1, city2;
    int k, hap, cost;
    cin >> n >> k >> start;
    for (int i = 0; i < n - 1; i++) {
        cin >> city1 >> hap;
        strToInt[city1] = i;
        intToStr[i] = city1;
        haps[i] = hap;
    }
    strToInt[start] = n - 1;
    intToStr[n - 1] = start; 
    for (int i = 0; i < k; i++) {
        cin >> city1 >> city2 >> cost;
        g[strToInt[city1]].push_back({strToInt[city2], cost});
        g[strToInt[city2]].push_back({strToInt[city1], cost});
    }
    dijkstra(strToInt[start]);
    cout << cnt2[strToInt["ROM"]] << " " << d[strToInt["ROM"]] << " " << happys[strToInt["ROM"]] << " " << happys[strToInt["ROM"]] / cnt[strToInt["ROM"]] << endl;
    dfs(strToInt["ROM"]);
    return 0;
}

1088 Rational Arithmetic

#include <iostream>
#include <string>
using namespace std;
typedef long long LL;
LL gcd(LL a, LL b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
string convert(LL a, LL b) {
    string res;
    if (b == 0) return "Inf";
    LL tt = a;
    if (tt < 0) res += "(-";
    a = abs(a), b = abs(b);
    LL d = gcd(a, b);
    a /= d;
    b /= d;
    LL t = a / b;
    a -= t * b;
    if (t && a) res += to_string(t) + " " + to_string(a) + "/" + to_string(b);
    else if(t && a == 0) res += to_string(t);
    else if(t == 0 && a) res += to_string(a) + "/" + to_string(b);
    else res += "0";
    if (tt < 0) res += ")";
    return res;
}
string add(LL a1, LL b1, LL a2, LL b2) {
    LL a, b;
    a = a1 * b2 + a2 * b1;
    b = b1 * b2;
    return convert(a, b);
}
string sub(LL a1, LL b1, LL a2, LL b2) {
    LL a, b;
    a = a1 * b2 - a2 * b1;
    b = b1 * b2;
    return convert(a, b);
}
string mul(LL a1, LL b1, LL a2, LL b2) {
    LL a, b;
    a = a1 * a2;
    b = b1 * b2;
    return convert(a, b);
}
string div(LL a1, LL b1, LL a2, LL b2) {
    LL a, b;
    a = a1 * b2;
    b = b1 * a2;
    if (b < 0) a = -a, b = -b;
    return convert(a, b);
}
int main() {
    LL a1, b1, a2, b2;
    scanf("%lld/%lld %lld/%lld", &a1, &b1, &a2, &b2);
    cout << convert(a1, b1) << " + " << convert(a2, b2) << " = " << add(a1, b1, a2, b2) << endl;
    cout << convert(a1, b1) << " - " << convert(a2, b2) << " = " << sub(a1, b1, a2, b2) << endl;
    cout << convert(a1, b1) << " * " << convert(a2, b2) << " = " << mul(a1, b1, a2, b2) << endl;
    cout << convert(a1, b1) << " / " << convert(a2, b2) << " = " << div(a1, b1, a2, b2) << endl;
    return 0;
}

1089 Insert or Merge

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 101;
int nums[N], now[N], tmp[N], tmp2[N];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> nums[i];
    for (int i = 0; i < n; i++)
        cin >> now[i];
    int id = 0;
    for (int i = 0; i < n - 1; i++) {
        if (now[i + 1] < now[i]) {
            id = i;
            break;
        }
    }
    bool isInsert = true;
    for (int j = id + 1; j < n; j++) {
        if (nums[j] != now[j]) {
            isInsert = false;
            break;
        }
    }
    if (isInsert) {
        cout << "Insertion Sort" << endl;
        sort(nums, nums + id + 2);
    } else {
        cout << "Merge Sort" << endl;
        bool flag = true;
        int k = 1;
        while (flag) {
            flag = false;
            for (int i = 0; i < n; i++) {
                if (nums[i] != now[i])
                    flag = true;
            }
            k *= 2;
            for (int i = 0; i < n / k; i++)
                sort(nums + i * k, nums + (i + 1) * k);
            sort(nums + n / k * k, nums + n);
        }
    }
    for (int i = 0; i < n; i++) {
        cout << nums[i];
        if (i < n - 1) cout << " ";
    }
    return 0;
}

1090 Highest Price in Supply Chain

#include <iostream>
#include <vector>
using namespace std;
vector<int> g[100001];
int cnt[100001], res = 0;
void dfs(int n, int t) {
    if (res < t) {
        res = t;
        cnt[t] = 1;
    } else cnt[t]++;
    for (int i = 0; i < g[n].size(); i++) {
        dfs(g[n][i], t + 1);
    }
}
int main() {
    int n, x;
    double p, r;
    cin >> n >> p >> r;
    for (int i = 0; i < n; i++) {
        cin >> x;
        if (x == -1) {
            g[n].push_back(i);
        } else {
            g[x].push_back(i);
        }
    }
    dfs(n, 0);
    for (int i = 0; i < res - 1; i++) {
        p *= (100 + r) / 100.0;
    }
    printf("%.2f %d", p, cnt[res]);
    return 0;
}

1091 Acute Stroke

#include <iostream>
#include <queue>
using namespace std;
int g[61][1287][129], m, n, l, t;
bool v[61][1287][129];
struct node {
    int i, j, k;
};
int x[6] = {1, -1, 0, 0, 0, 0};
int y[8] = {0, 0, 1, -1, 0, 0};
int z[8] = {0, 0, 0, 0, 1, -1};
int bfs(int i, int j, int k) {
    v[i][j][k] = true;
    int cnt = 1;
    queue<node> q;
    q.push({i, j, k});
    while (!q.empty()) {
        node u = q.front();
        q.pop();
        i = u.i, j = u.j, k = u.k;
        for (int id = 0; id < 6; id++) {
            int a = i + x[id], b = j + y[id], c = k + z[id];
            if (a >= 0 && a < l && b >= 0 && b < m && c >= 0 && c < n && !v[a][b][c] && g[a][b][c] == 1) {
                cnt++;
                v[a][b][c] = true;
                q.push({a, b, c});
            }
        }
    }
    if (cnt < t) return 0;
    else return cnt;
}
int main() {
    cin >> m >> n >> l >> t;
    for (int i = 0; i < l; i++) {
        for (int j = 0; j < m; j++) {
            for (int k = 0; k < n; k++) {
                scanf("%d", &g[i][j][k]);
            }
        }
    }
    int res = 0;
    for (int i = 0; i < l; i++) {
        for (int j = 0; j < m; j++) {
            for (int k = 0; k < n; k++) {
                if (!v[i][j][k] && g[i][j][k]) {
                    res += bfs(i, j, k);
                }
            }
        }
    }
    cout << res;
    return 0;
}

1092 To Buy or Not to Buy

#include <iostream>
#include <string>
using namespace std;
int nums[256];
int main() {
    string a, b;
    cin >> a >> b;
    for (int i = 0; i < a.size(); i++) {
        nums[a[i]]++;
    }
    bool flag = true;
    int cnt = 0;
    for (int i = 0; i < b.size(); i++) {
        if (nums[b[i]] <= 0) {
            flag = false;
            cnt++;
        }
        nums[b[i]]--;
    }
    if (flag) cout << "Yes " << a.size() - b.size();
    else cout << "No " << cnt;
    return 0;
}

1093 Count PAT’s

#include <iostream>
#include <string>
using namespace std;
const int N = 100001;
const int MOD = 1000000007;
int p[N], t[N];
int main() {
    string str;
    cin >> str;
    int res = 0;
    for (int i = 1; i < str.size(); i++) {
        p[i] = p[i - 1];
        if (str[i - 1] == 'P') p[i]++;
    }
    for (int i = str.size() - 1; i >= 0; i--) {
        t[i] = t[i + 1];
        if (str[i + 1] == 'T') t[i]++;
    }
    for (int i = 1; i < str.size() - 1; i++) {
        if (str[i] == 'A') {
            res = (res + p[i] * t[i] % MOD) % MOD;
        }
    }
    cout << res;
    return 0;
}

柳婼的

#include <iostream>
#include <string>
using namespace std;
const int N = 100001;
const int MOD = 1000000007;
int p[N], t[N];
int main() {
    string s;
    cin >> s;
    int res = 0, len = s.size(), p = 0, t = 0;
    for (int i = 0; i < len; i++) {
        if (s[i] == 'T') t++;
    }
    for (int i = 0; i < len; i++) {
        if (s[i] == 'P') p++;
        if (s[i] == 'T') t--;
        if (s[i] == 'A') res = (res + p * t % MOD) % MOD;
    }
    cout << res;
    return 0;
}

1094 The Largest Generation

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> trees[101];
int res, cntn;
void bfs(int u) {
    queue<int> q;
    q.push(u);
    int depth = 1;
    while (!q.empty()) {
        int cnt = q.size();
        for (int i = 0; i < cnt; i++) {
            u = q.front();
            q.pop();
            for (int j = 0; j < trees[u].size(); j++) {
                q.push(trees[u][j]);
            }
        }
        if (cntn < cnt) {
            res = depth;
            cntn = cnt;
        }
        depth++;
    }
    return;
}
int main() {
    int n, m, id, k, x;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> id >> k;
        for (int j = 0; j < k; j++) {
            cin >> x;
            trees[id].push_back(x);
        }
    }
    bfs(1);
    cout << cntn << " " << res;
    return 0;
}

1095 Cars on Campus

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
struct node{
    int time;
    string op;
};
bool cmp(node a, node b) {
    return a.time < b.time;
}
map<string, int> strToInt;
map<int, string> intToStr;
vector<node> nums[10001], finall;
int times[86401];
int main() {
    string a, op;
    int n, k, h, m, s, id = 1;
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> a;
        if (!strToInt[a]) {
            strToInt[a] = id;
            intToStr[id++] = a;
        }
        scanf("%d:%d:%d", &h, &m, &s);
        cin >> op;
        int time = h * 60 * 60 + m * 60 + s;
        nums[strToInt[a]].push_back({time, op});
    }
    int total[id + 1];
    for (int i = 1; i < id; i++) {
        sort(nums[i].begin(), nums[i].end(), cmp);
        for (int j = 0; j < nums[i].size() - 1; j++) {
            if (nums[i][j].op == "in" && nums[i][j + 1].op == "out") {
                finall.push_back(nums[i][j]);
                finall.push_back(nums[i][j + 1]);
                total[i] += nums[i][j + 1].time - nums[i][j].time;
            } 
        }
    }
    sort(finall.begin(), finall.end(), cmp);
    int t = 0;
    for (int i = 0; i <= 86400; i++) {
        if (i != 0) times[i] = times[i - 1];
        while (finall[t].time == i) {
            if (finall[t].op == "in") times[i]++;
            else times[i]--;
            t++;
            if (t == finall.size()) break;
        }
    }
    for (int i = 0; i < k; i++) {
        scanf("%d:%d:%d", &h, &m, &s);
        int time = h * 60 * 60 + m * 60 + s;
        cout << times[time] << endl;
    }
    int maxTime = 0;
    vector<string> res;
    for (int i = 0; i < id; i++) {
        if (maxTime < total[i]) {
            maxTime = total[i];
            res.clear();
            res.push_back(intToStr[i]);
        } else if (maxTime == total[i]) {
            res.push_back(intToStr[i]);
        }
    }
    for (auto it: res) {
        cout << it << " ";
    }
    h = maxTime / 3600, m = maxTime % 3600 / 60, s = maxTime % 60;
    printf("%02d:%02d:%02d", h, m, s);
    return 0;
}

1096 Consecutive Factors

#include <iostream>
#include <cmath>
using namespace std;
typedef long long LL;
int main() {
    LL n, t;
    cin >> n;
    int l = 0, j = 0, res = 0;
    for (int i = 2; i < sqrt(n) + 1; i++) {
        t = 1;
        for (j = i; j < sqrt(n) + 1; j++) {
            t *= j;
            if (n % t != 0) break;
        }
        if (j - i > l) {
            l = j - i;
            res = i;
        }
    }
    if (l == 0) cout << "1\n" << n;
    else {
        cout << l << endl;
        for (int k = res; k < l + res; k++) {
            cout << k;
            if (k < l + res - 1) cout << "*";
        }
    }
    return 0;
}

1097 Deduplication on a Linked List

#include <iostream>
#include <vector>
using namespace std;
const int N = 100001;
struct node {
    int add, key, nex;
} nums[N];
bool st[N];
int main() {
    int start, n, add, key, nex;
    cin >> start >> n;
    for (int i = 0; i < n; i++) {
        cin >> add >> key >> nex;
        nums[add] = {add, key, nex};
    }
    vector<node> list, red;
    while (start != -1) {
        if (!st[abs(nums[start].key)]) {
            list.push_back(nums[start]);
            st[abs(nums[start].key)] = true;
        } else {
            red.push_back(nums[start]);
        }
        start = nums[start].nex;
    }
    if (!list.empty()) {
        for (int i = 0; i < list.size() - 1; i++) {
            printf("%05d %d %05d\n", list[i].add, list[i].key, list[i + 1].add);
        }
        printf("%05d %d -1\n", list[list.size() - 1].add, list[list.size() - 1].key);
    }
    if (!red.empty()) {
        for (int i = 0; i < red.size() - 1; i++) {
            printf("%05d %d %05d\n", red[i].add, red[i].key, red[i + 1].add);
        }
        printf("%05d %d -1\n", red[red.size() - 1].add, red[red.size() - 1].key);
    }
    return 0;
}

1098 Insertion or Heap Sort

错误答案

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 101;
int a[N], b[N];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    int id = 0;
    for (int i = 1; i < n; i++) {
        if (b[i] >= b[i - 1]) id = i;
        else break;
    }
    bool isInsert = true;
    for (int j = id + 1; j < n; j++) {
        if (a[j] != b[j]) {
            isInsert = false;
            break;
        }
    }
    if (isInsert) {
        cout << "Insertion Sort" << endl;
        sort(b, b + id + 2);
    } else {
        cout << "Heap Sort" << endl;
        int i = 0, t = b[0];
        while(2 * i + 1 < n) {
            if (b[2 * i + 1] > b[2 * i + 2]) swap(b[2 * i + 1], b[2 * i + 2]);
            if (b[i] > b[2 * i + 2]) {
                swap(b[i], b[2 * i + 2]);
                i = 2 * i + 2;
            } else if (b[i] > b[2 * i + 1]) {
                swap(b[i], b[2 * i + 1]);
                i = 2 * i + 1;
            } else {
                break;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        cout << b[i];
        if (i < n - 1) cout << " ";
    }
    return 0;
}

柳婼的

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void down(vector<int> &b, int low, int high) {
    int i = 1, j = i * 2;
    while (j <= high) {
        if (j + 1 <= high && b[j] < b[j + 1]) j = j + 1;
        if (b[i] >= b[j]) break;
        swap(b[i], b[j]);
        i = j;
        j = i * 2;
    }
}
int main() {
    int n, p = 2;
    cin >> n;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    while (p <= n && b[p - 1] <= b[p]) p++;
    int idx = p;
    while (p <= n && a[p] == b[p]) p++;
    if (p == n + 1) {
        cout << "Insertion Sort\n";
        sort(b.begin() + 1, b.begin() + idx + 1);
    } else {
        cout << "Heap Sort\n";
        p = n;
        while(p > 2 && b[p] >= b[1]) p--;
        swap(b[1], b[p]);
        down(b, 1, p - 1);
    }
    for (int i = 1; i <= n; i++) {
        cout << b[i];
        if (i < n) cout << " ";
    }
    return 0;
}

1099 Build A Binary Search Tree

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 101;
struct node {
    int data, l, r;
} a[N];
int b[N], cnt;
vector<int> res;
void dfs(int root) {
    if (root == -1) return;
    dfs(a[root].l);
    a[root].data = b[cnt++];
    dfs(a[root].r);
}
void bfs(int root) {
    queue<int> q;
    q.push(root);
    while (!q.empty()) {
        root = q.front();
        q.pop();
        res.push_back(a[root].data);
        if (a[root].l != -1) q.push(a[root].l);
        if (a[root].r != -1) q.push(a[root].r);
    }
}
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i].l >> a[i].r;
    for (int i = 0; i < n; i++) cin >> b[i];
    sort(b, b + n);
    dfs(0);
    bfs(0);
    for (int i = 0; i < n; i++) {
        cout << res[i];
        if (i < n - 1) cout << " ";
    }
    return 0;
}

1100 Mars Numbers

#include <iostream>
#include <string>
using namespace std;
int main() {
    int n;
    string x;
    string shi[12] = {"tam", "hel", "maa", "huh", "tou", "kes", "hei", "elo", "syy", "lok", "mer", "jou"};
    string ge[12] = {"jan", "feb", "mar", "apr", "may", "jun", "jly", "aug", "sep", "oct", "nov", "dec"};
    cin >> n;
    getchar();
    for (int i = 0; i < n; i++) {
        getline(cin, x);
        if (x == "0") cout << "tret" << endl;
        else if (isdigit(x[0])) {
            int t = stoi(x);
            int a = t / 13;
            int b = t % 13;
            if (a && b) cout << shi[a - 1] << " " << ge[b - 1] << endl;
            else if (a) cout << shi[a - 1] << endl;
            else if (b) cout << ge[b - 1] << endl;
        } else {
            if (x == "tret") cout << 0 << endl;
            else if (x.size() > 3) {
                int a = 0;
                for (int i = 0; i < 12; i++) {
                    if (x.substr(0, 3) == shi[i]) a += (i + 1) * 13;
                    if (x.substr(4, 3) == ge[i]) a += i + 1;
                }
                cout << a << endl;
            } else {
                for (int i = 0; i < 12; i++) {
                    if (x == shi[i]) cout << (i + 1) * 13 << endl;
                    if (x == ge[i]) cout << i + 1 << endl;
                }
            }
        }
    }
    return 0;
}

1101 Quick Sort

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 100001;
const int INF = 0x3f3f3f3f;
int nums[N], minr[N], maxl[N];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    fill(minr, minr + n, INF);
    for (int i = 1; i < n; i++) {
        maxl[i] = max(maxl[i - 1], nums[i - 1]);
    }
    for (int i = n - 2; i >= 0; i--) {
        minr[i] = min(minr[i + 1], nums[i + 1]);
    }
    vector<int> res;
    for (int i = 0; i < n; i++) {
        if (nums[i] >= maxl[i] && nums[i] <= minr[i]) {
            res.push_back(nums[i]);
        }
    }
    cout << res.size() << endl;
    for (int i = 0; i < res.size(); i++) {
        cout << res[i];
        if (i < res.size() - 1) cout << " ";
    }
    cout << endl;
    return 0;
}

柳婼的

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int v[100001];
int main() {
    int n, max = 0, cnt = 0;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        b[i] = a[i];
    }
    sort(a.begin(), a.end());
    for (int i = 0; i < n; i++) {
        if (a[i] == b[i] && b[i] > max) 
            v[cnt++] = b[i];
        if (b[i] > max) max = b[i];
    }
    cout << cnt << endl;
    for (int i = 0; i < cnt; i++) {
        cout << v[i];
        if (i < cnt - 1) cout << " ";
    }
    cout << endl;
    return 0;
}

1102 Invert a Binary Tree

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct node{
    int l, r;
} trees[11];
bool st[11];
vector<int> level, in;
void bfs(int u) {
    queue<int> q;
    q.push(u);
    while (!q.empty()) {
        u = q.front();
        level.push_back(u);
        q.pop();
        if (trees[u].l != -1) q.push(trees[u].l);
        if (trees[u].r != -1) q.push(trees[u].r);
    }
}
void dfs(int u) {
    if (u == -1) return;
    dfs(trees[u].l);
    in.push_back(u);
    dfs(trees[u].r);
}
int main() {
    int n, root;
    char a, b;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a >> b;
        if (isdigit(a)) {
            trees[i].r = a - '0';
            st[a - '0'] = true;
        } else {
            trees[i].r = -1;
        }
        if (isdigit(b)) {
            trees[i].l = b - '0';
            st[b - '0'] = true;
        } else {
            trees[i].l = -1;
        }
    }
    for (int i = 0; i < n; i++) {
        if (!st[i]) root = i;
    }
    bfs(root);
    dfs(root);
    for (int i = 0; i < n; i++) {
        cout << level[i];
        if (i < n - 1) cout << " ";
        else cout << endl;
    }
    for (int i = 0; i < n; i++) {
        cout << in[i];
        if (i < n - 1) cout << " ";
    }
    return 0;
}

1103 Integer Factorization

dfs

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector<int> res, tmp, v;
int n, k, p, t, m, sumt, mint = -1;
void dfs(int idx, int a) {
    if (a == k && t == n) {
        if (sumt > mint) {
            mint = sumt;
            res = tmp;
        }
        return;
    }
    if (a >= k || t >= n) return;
    for (int i = idx; i >= 0; i--) {
        t += v[i];
        sumt += i;
        tmp.push_back(i + 1);
        dfs(i, a + 1);
        tmp.pop_back();
        sumt -= i;
        t -= v[i];
    }
}
int main() {
    cin >> n >> k >> p;
    for (int i = 1; i <= n; i++) {
        int b = pow(i, p);
        v.push_back(b);
        if (b > n) break;
    }
    dfs(v.size() - 1, 0);
    if (mint == -1)
        cout << "Impossible";
    else {
        cout << n << " = ";
        for (int i = 0; i < res.size(); i++) {
            cout << res[i] << "^" << p;
            if (i < res.size() - 1) cout << " + ";
        }
    }
    return 0;
}

1104 Sum of Number Segments

精度问题（坑）

#include <iostream>
using namespace std;
const int N = 100001;
double nums[N];
int n;
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    long long res = 0;
    for (int i = 0; i < n; i++) {
        res += (long long)(nums[i] * 1000) * i * (n - i + 1);
    }
    printf("%.2f", res / 1000.0);
    return 0;
}

柳婼的

#include <iostream>
using namespace std;
int main() {
    int n;
    double tmp;
    long long res;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> tmp;
        res += (long long)(tmp * 1000) * i * (n - i + 1);
    }
    printf("%.2f", res / 1000.0);
    return 0;
}

1105 Spiral Matrix

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int nums[10001], id, res[100][100];
int main() {
    int t, n, m, mi = 10001;
    cin >> t;
    for (int i = 0; i < t; i++) {
        cin >> nums[i];
    }
    sort(nums, nums + t, greater<int>());
    for (int i = 1; i * i <= t; i++) {
        if (t % i == 0) n = i;
    }
    m = t / n;
    int l = 0, r = n - 1, u = 0, d = m - 1;
    while (l <= r && u <= d) {
        for (int i = l; i <= r; i++) 
            res[u][i] = nums[id++];
        u++;
        if (u > d) break;
        for (int i = u; i <= d; i++) 
            res[i][r] = nums[id++];
        r--;
        if (r < l) break;
        for (int i = r; i >= l; i--) 
            res[d][i] = nums[id++];
        d--;
        if (u > d) break;
        for (int i = d; i >= u; i--)
            res[i][l] = nums[id++];
        l++;
        if (l > r) break;
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cout << res[i][j];
            if (j < n - 1) cout << " ";
        }
        cout << endl;
    }
    return 0;
}

1106 Lowest Price in Supply Chain

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
vector<int> trees[100001];
int depth = 1, cnt = 0;
void bfs(int u) {
    queue<int> q;
    q.push(u);
    bool flag = false;
    while (!q.empty()) {
        int size = q.size();
        cnt = 0;
        for (int i = 0; i < size; i++) {
            u = q.front();
            q.pop();
            if (trees[u].empty()) {
                flag = true;
                cnt++;
            } 
            for (int i = 0; i < trees[u].size(); i++) {
                q.push(trees[u][i]);
            }
            
        }
        if (flag) return;
        depth++;
    }
}
int main() {
    int n, k, x;
    double p, r;
    cin >> n >> p >> r;
    for (int i = 0; i < n; i++) {
        cin >> k;
        for (int j = 0; j < k; j++) {
            cin >> x;
            trees[i].push_back(x);
        }
    }
    bfs(0);
    printf("%.4f %d", p * pow(1 + r / 100, depth - 1), cnt);
    return 0;
}

#include <iostream>
#include <string>
using namespace std;
int main() {
    int n, cnt = 0;
    string x;
    double sum, t;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x;
        try {
            t = stod(x);
            if (t > 1000 || t < -1000) {
                cout << "ERROR: " << x << " is not a legal number" << endl;
                continue;
            }
            int j = 0;
            bool flag = true;
            while (j < x.size() && x[j] != '.') j++;
            if (j != x.size() && j + 3 < x.size()) {
                cout << "ERROR: " << x << " is not a legal number" << endl;
                continue;
            }
            if (flag) {
                cnt++;
                sum += t;
            }
        } catch(exception) {
            cout << "ERROR: " << x << " is not a legal number" << endl;
        }
    }
    if (cnt == 0) cout << "The average of 0 numbers is Undefined" << endl;
    else if (cnt == 1) printf("The average of 1 number is %.2f", sum);
    else printf("The average of %d numbers is %.2f", cnt, sum / cnt);
    return 0;
}

1108 Finding Average

#include <iostream>
#include <string>
using namespace std;
int main() {
    int n, cnt = 0;
    string x;
    double sum, t;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x;
        try {
            t = stod(x);
            if (t > 1000 || t < -1000) {
                cout << "ERROR: " << x << " is not a legal number" << endl;
                continue;
            }
            int j = 0;
            bool flag = true;
            while (j < x.size() && x[j] != '.') j++;
            if (j != x.size() && j + 3 < x.size()) {
                cout << "ERROR: " << x << " is not a legal number" << endl;
                continue;
            }
            if (flag) {
                cnt++;
                sum += t;
                // cout << t << " " << sum << " " << cnt << endl;
            }
            
        } catch(exception) {
            cout << "ERROR: " << x << " is not a legal number" << endl;
        }
    }
    if (cnt == 0) cout << "The average of 0 numbers is Undefined" << endl;
    else if (cnt == 1) printf("The average of 1 number is %.2f", sum);
    else printf("The average of %d numbers is %.2f", cnt, sum / cnt);
    return 0;
}

柳婼的

#include <iostream>
#include <cstring>
using namespace std;
int main() {
    int n, cnt = 0;
    char a[50], b[50];
    double t, sum;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a;
        sscanf(a, "%lf", &t);
        sprintf(b, "%.2f", t);
        bool flag = false;
        for (int j = 0; j < strlen(a); j++) 
            if (a[j] != b[j]) flag = true;
        if (flag || t < -1000 || t > 1000) {
            cout << "ERROR: " << a << " is not a legal number" << endl;
            continue;
        } else {
            sum += t;
            cnt++;
        }
    }
    if (cnt == 0) cout << "The average of 0 numbers is Undefined" << endl;
    else if (cnt == 1) printf("The average of 1 number is %.2f", sum);
    else printf("The average of %d numbers is %.2f", cnt, sum / cnt);
    return 0;
}

1109 Group Photo

#include <iostream>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
typedef pair<string, int> PII;
PII nums[10001];
bool cmp(PII a, PII b) {
    if (a.second != b.second) return a.second > b.second;
    return a.first < b.first;
}
void fun(int start, int n) {
    if (n % 2 == 0) {
        for (int i = n - 1; i >= 1; i-=2) {
            cout << nums[start + i].first << " ";
        }
        for (int i = 0; i < n; i+=2) {
            cout << nums[start + i].first;
            if (i + 2 == n) cout << endl;
            else cout << " ";
        }
    } else {
        for (int i = n - 2; i >= 1; i-=2) {
            cout << nums[start + i].first << " ";
        }
        for (int i = 0; i < n; i+=2) {
            cout << nums[start + i].first;
            if (i + 1 == n) cout << endl;
            else cout << " ";
        }
    }
}
int main() {
    int n, k, height;
    string name;
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> name >> height;
        nums[i] = {name, height};
    }
    sort(nums, nums + n, cmp);
    int num = n / k;
    int last = n - num * k + num;
    fun(0, last);
    for (int j = 1; j < k; j++) {
        fun(last + (j - 1) * num, num);
    }
    return 0;
}

1110 Complete Binary Tree

bfs

#include <iostream>
#include <string>
#include <queue>
using namespace std;
struct node{
    int l = -1, r = -1;
} nums[100];
bool st[100], isCBT = true, flag;
int bfs(int u) {
    queue<int> q;
    q.push(u);
    int cnt = 1, a = 0;
    while(!q.empty()) {
        u = q.front();
        q.pop();
        if (nums[u].l != -1) {
            q.push(nums[u].l);
            if (flag) isCBT = false;
        } else flag = true;
        if (nums[u].r != -1) {
            q.push(nums[u].r);
            if (flag) isCBT = false;
        } else flag = true;
    }
    return u;
}
int main() {
    int n, root = 0;
    string l, r;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> l >> r;
        if (l != "-") {
            nums[i].l = stoi(l);
            st[stoi(l)] = true;
        }
        if (r != "-") {
            nums[i].r = stoi(r);
            st[stoi(r)] = true;
        }
    }
    for (int i = 0; i < n; i++) {
        if (!st[i]) root = i;
    }
    int last = bfs(root);
    if (!isCBT) cout << "NO " << root;
    else cout << "YES " << last;
    return 0;
}

dfs

#include <iostream>
#include <string>
#include <queue>
using namespace std;
struct node{
    int l = -1, r = -1;
} nums[100];
bool st[100];
int maxn = -1, last;
void dfs(int root, int index) {
    if (maxn < index) {
        maxn = index;
        last = root;
    }
    if (nums[root].l != -1) dfs(nums[root].l, index * 2);
    if (nums[root].r != -1) dfs(nums[root].r, index * 2 + 1);
}
int main() {
    int n, root = 0;
    string l, r;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> l >> r;
        if (l != "-") {
            nums[i].l = stoi(l);
            st[stoi(l)] = true;
        }
        if (r != "-") {
            nums[i].r = stoi(r);
            st[stoi(r)] = true;
        }
    }
    for (int i = 0; i < n; i++) {
        if (!st[i]) root = i;
    }
    dfs(root, 1);
    if (maxn != n) cout << "NO " << root;
    else cout << "YES " << last;
    return 0;
}

1111 Online Map

dijkstra

#include <iostream>
#include <vector>
using namespace std;
const int N = 501;
const int INF = 0x3f3f3f3f;
struct node{
    int v, dist, time;
};
vector<node> g[N];
int d[N], cost1[N], cost2[N], cnt[N], pre[N], start, dest, n;
bool visit[N];
void dijkstra1(int a) {
    fill(d, d + N, INF);
    d[a] = 0;
    for (int i = 0; i < n; i++) {
        int u = -1, mind = INF;
        for (int j = 0; j < n; j++) {
            if (!visit[j] && mind > d[j]) {
                mind = d[j];
                u = j;
            }
        }
        if (u == -1) return;
        visit[u] = true;
        for (int j = 0; j < g[u].size(); j++) {
            int v = g[u][j].v, dist = g[u][j].dist, time = g[u][j].time;
            if (d[u] + dist < d[v]) {
                d[v] = d[u] + dist;
                cost1[v] = cost1[u] + time;
                pre[v] = u;
            } else if (d[u] + dist == d[v]) {
                if (cost1[v] > cost1[u] + time){
                    pre[v] = u;
                    cost1[v] = cost1[u] + time;
                }
            }
        }
    }
}
vector<int> res1;
void dfs1(int x) {
    if (x != start) {
        res1.push_back(x);
        dfs1(pre[x]);
    } else res1.push_back(start);
}
void dijkstra2(int a) {
    fill(cost2, cost2 + N, INF);
    fill(visit, visit + N, false);
    cost2[a] = 0;
    cnt[a] = 1;
    for (int i = 0; i < n; i++) {
        int u = -1, mind = INF;
        for (int j = 0; j < n; j++) {
            if (!visit[j] && mind > cost2[j]) {
                mind = cost2[j];
                u = j;
            }
        }
        if (u == -1) return;
        visit[u] = true;
        for (int j = 0; j < g[u].size(); j++) {
            int v = g[u][j].v, dist = g[u][j].dist, time = g[u][j].time;
            if (cost2[u] + time < cost2[v]) {
                cost2[v] = cost2[u] + time;
                cnt[v] = cnt[u] + 1;
                pre[v] = u;
            } else if (cost2[u] + time == cost2[v]) {
                if (cnt[v] > cnt[u] + 1){
                    pre[v] = u;
                    cnt[v] = cnt[u] + 1;
                }
            }
        }
    }
}
vector<int> res2;
void dfs2(int x) {
    if (x != start) {
        res2.push_back(x);
        dfs2(pre[x]);
    } else res2.push_back(start);
}
int main() {
    int m, v1, v2, one, len, time;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> v1 >> v2 >> one >> len >> time;
        g[v1].push_back({v2, len, time});
        if (!one) g[v2].push_back({v1, len, time});
    }
    cin >> start >> dest;
    dijkstra1(start);
    dfs1(dest);
    dijkstra2(start);
    dfs2(dest);
    if (res1 == res2) {
        cout << "Distance = " << d[dest] << "; Time = " << cost2[dest] << ": ";
        for (int i = res1.size() - 1; i >= 0; i--) {
            cout << res1[i];
            if (i > 0) cout << " -> ";
        }
    } else {
        cout << "Distance = " << d[dest] << ": ";
        for (int i = res1.size() - 1; i >= 0; i--) {
            cout << res1[i];
            if (i > 0) cout << " -> ";
            else cout << endl;
        }
        cout << "Time = " << cost2[dest] << ": ";
        for (int i = res2.size() - 1; i >= 0; i--) {
            cout << res2[i];
            if (i > 0) cout << " -> ";
        }
    }
    return 0;
}

1112 Stucked Keyboard

#include <iostream>
#include <string>
using namespace std;
int st[257];
int main() {
    int k, i = 0;
    string a;
    cin >> k >> a;
    for (; i <= a.size() - k; i++) {
        char t = a[i];
        bool flag = false;
        for (int j = i + 1; j < i + k; j++) {
            if (a[j] != t) {
                flag = true;
                break;
            }
        }
        if (flag) st[t] = 1;
        else i += k - 1;
    }
    for (; i < a.size(); i++) {
        st[a[i]] = 1;
    }
    for (int i = 0; i < a.size(); i++) {
        if (!st[a[i]]) {
            cout << a[i];
            st[a[i]] = 2;
        }
    }
    cout << endl;
    for (int i = 0; i < a.size(); i++) {
        if (st[a[i]] == 1) cout << a[i];
        else if (st[a[i]] == 2) {
            cout << a[i];
            i += k - 1;
        }
    }
    return 0;
}

1113 Integer Set Partition

#include <iostream>
#include <algorithm>
using namespace std;
int nums[100001];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> nums[i];
    sort(nums, nums + n);
    long long res = 0;
    for (int i = 0; i < n / 2; i++) {
        res += nums[n - i - 1] - nums[i];
    }
    if (n % 2 == 0) cout << 0 << " " << res;
    else {
        res += nums[n / 2];
        cout << 1 << " " << res;
    }
    return 0;
}

1114 Family Property

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
const int N = 10001;
struct node {
    int fa, mo, set, area;
    vector<int> childs;
} nums[N];
struct family {
    int id, cnt;
    double set, area;
};
bool cmp(family &a, family &b) {
    if (a.area != b.area) return a.area > b.area;
    return a.id < b.id;
}
bool visit[N];
int fa[N], cnt[N];
set<int> ids, ids2, resid;
int find(int x) {
    if (fa[x] != x) fa[x] = find(fa[x]);
    return fa[x];
}
void union1(int a, int b) {
    ids.insert(b);
    int fa1 = find(a);
    int fb = find(b);
    if (fa1 != fb) {
        if (fa1 < fb) fa[fb] = fa1;
        else fa[fa1] = fb;
    }
}
int main() {
    int n, id, k, child;
    for (int i = 1; i < N; i++) fa[i] = i;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> id;
        ids.insert(id);
        ids2.insert(id);
        cin >> nums[id].fa >> nums[id].mo >> k;
        if (nums[id].fa != -1) union1(id, nums[id].fa);
        if (nums[id].mo != -1) union1(id, nums[id].mo);
        for (int i = 0; i < k; i++) {
            cin >> child;
            nums[id].childs.push_back(child);
            union1(id, child);
        }
        cin >> nums[id].set >> nums[id].area;
    }
    for (auto id: ids) {
        cnt[find(id)]++;
        resid.insert(find(id));
    }
    family tmp[N];
    for (int i = 0; i < N; i++) {
        if (cnt[i]) tmp[i] = {i, cnt[i], 0, 0};
    }
    for (auto id: ids2) {
        tmp[find(id)].set += nums[id].set;
        tmp[find(id)].area += nums[id].area;
    }
    vector<family> res;
    for (auto id: resid) {
        tmp[id].set /= tmp[id].cnt;
        tmp[id].area /= tmp[id].cnt;
        res.push_back(tmp[id]);
    }
    sort(res.begin(), res.end(), cmp);
    cout << res.size() << endl;
    for (int i = 0; i < res.size(); i++) {
        printf("%04d %d %.3f %.3f\n", res[i].id, res[i].cnt, res[i].set, res[i].area);
    }
    return 0;
}

1115 Counting Nodes in a Binary Search Tree

#include <iostream>
#include <queue>
using namespace std;
struct node {
    int data, l = -1, r = -1;
} nums[1001];
int idx = 0, last = 0, llast = 0;
void insert(int x, int root) {
    if (x <= nums[root].data) {
        if (nums[root].l == -1) {
            nums[root].l = idx;
            nums[idx++].data = x;
        } else insert(x, nums[root].l);
    } else {
        if (nums[root].r == -1) {
            nums[root].r = idx;
            nums[idx++].data = x;
        } else insert(x, nums[root].r);
    }
}
void bfs(int u) {
    queue<int> q;
    q.push(u);
    while (!q.empty()) {
        int size = q.size();
        llast = last;
        last = size;
        for (int i = 0; i < size; i++) {
            u = q.front();
            q.pop();
            if (nums[u].l != -1) q.push(nums[u].l);
            if (nums[u].r != -1) q.push(nums[u].r);
        }
    }
}
int main() {
    int n, root, x;
    cin >> n >> root;
    nums[idx++].data = root;
    for (int i = 1; i < n; i++) {
        cin >> x;
        insert(x, 0);
    }
    bfs(0);
    cout << last << " + " << llast << " = " << last + llast;
    return 0;
}

1116 Come on! Let’s C

#include <iostream>
#include <map>
using namespace std;
const int N = 10001;
bool st[N], visit[N];
map<int, int> nums;
int main() {
    for (int i = 2; i < N; i++) {
        if (!st[i]) {
            for (int j = i * 2; j < N; j += i) st[j] = true;
        }
    }
    int n, x;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        nums[x] = i;
    }
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x;
        if (nums[x] == 0) {
            printf("%04d: Are you kidding?\n", x);
        } else if (visit[x]) {
            printf("%04d: Checked\n", x);
        } else {
            if (nums[x] == 1) {
                printf("%04d: Mystery Award\n", x);
                visit[x] = true;
            } else if (!st[nums[x]]) {
                printf("%04d: Minion\n", x);
                visit[x] = true;
            } else {
                printf("%04d: Chocolate\n", x);
                visit[x] = true;
            }
        }
    }
    return 0;
}

1117 Eddington Number

#include <iostream>
#include <algorithm>
using namespace std;
int nums[100001];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    sort(nums, nums + n, greater<int>());
    int res = 0;
    for (int i = 1; i <= n; i++) {
        if (i >= nums[i - 1]) break;
        else res = i;
    }
    cout << res;
    return 0;
}

1118 Birds in Forest

#include <iostream>
#include <set>
using namespace std;
const int N = 10001;
int fa[N], cnt[N], maxb;
set<int> birds;
int find(int x) {
    if (fa[x] != x) {
        fa[x] = find(fa[x]);
    }
    return fa[x];
}
void union1(int a, int b) {
    int faa = find(a);
    int fbb = find(b);
    if (faa != fbb) {
        fa[fbb] = faa;
    }
}
int main() {
    for (int i = 1; i < N; i++) {
        fa[i] = i;
    }
    int n, k, x, y;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> k >> x;
        maxb = max(maxb, x);
        for (int j = 1; j < k; j++) {
            cin >> y;
            maxb = max(maxb, y);
            union1(x, y);
        }
    }
    int mtree = 0;
    for (int i = 1; i <= maxb; i++) {
        if (find(i) == i) mtree++;
    }
    cout << mtree << " " << maxb << endl;
    cin >> k;
    for (int i = 0; i < k; i++) {
        cin >> x >> y;
        if (fa[x] != fa[y]) cout << "No" << endl;
        else cout << "Yes" << endl;
    }
    return 0;
}

1119 Pre- and Post-order Traversals

#include <iostream>
#include <vector>
using namespace std;
const int N = 31;
int pre[N], post[N];
vector<int> in;
bool flag = true;
void getIn(int preleft, int preright, int postleft, int postright){
    if (preleft == preright) {
        in.push_back(pre[preleft]);
        return;
    }
    if (pre[preleft] == post[postright]) {
        int i = preleft + 1;
        while (i <= preright && pre[i] != post[postright - 1]) i++;
        if (i - preleft > 1) 
            getIn(preleft + 1, i - 1, postleft, postleft + (i - preleft - 1) - 1);
        else
            flag = false;
        in.push_back(post[postright]);
        getIn(i, preright, postleft + (i - preleft - 1), postright - 1);
    }
}
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> pre[i];
    for (int i = 0; i < n; i++)
        cin >> post[i];
    getIn(0, n - 1, 0, n - 1);
    if (flag) cout << "Yes" << endl;
    else cout << "No" << endl;
    for (int i = 0; i < in.size(); i++) {
        cout << in[i];
        if (i < in.size() - 1) cout << " ";
        else cout << endl;
    }
    return 0;
}

1120 Friend Numbers

#include <iostream>
#include <vector>
using namespace std;
int nums[40];
int main() {
    int n, x;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x;
        int t = 0;
        while (x > 0) {
            t += x % 10;
            x /= 10;
        }
        nums[t]++;
    }
    vector<int> res;
    for (int i = 0; i < 40; i++) {
        if (nums[i]) res.push_back(i);
    }
    cout << res.size() << endl;
    for (int i = 0; i < res.size(); i++) {
        cout << res[i];
        if (i < res.size() - 1) cout << " ";
    }
    return 0;
}

1121 Damn Single

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 100001;
int g[N], tmp[N];
int main() {
    fill(g, g + N, -1);
    fill(tmp, tmp + N, -1);
    int n, a, b, m, c;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a >> b;
        g[a] = b;
        g[b] = a;
    }
    cin >> m;
    vector<int> tmp1, res;
    for (int i = 0; i < m; i++) {
        cin >> c;
        if (g[c] == -1) res.push_back(c);
        else if (tmp[g[c]] == -1) {
            tmp[g[c]] = 1;
            tmp1.push_back(c);
        }
    }
    for (auto i: tmp1) {
        if (tmp[i] == -1) res.push_back(i);
    }
    sort(res.begin(), res.end());
    cout << res.size() << endl;
    for (int i = 0; i < res.size(); i++) {
        printf("%05d", res[i]);
        if (i < res.size() - 1) cout << " ";
    }
    return 0;
}

1122 Hamiltonian Cycle

#include <iostream>
#include <vector>
using namespace std;
int n, g[201][201];
bool visit[201];
bool check(int q) {
    bool flag = true;
    if (q != n + 1) flag = false;
    fill(visit, visit + 201, false);
    int x, last, start;
    cin >> last;
    start = last;
    visit[start] = true;
    for (int i = 1; i < q; i++) {
        cin >> x;
        if (!g[last][x]) flag = false;
        visit[x] = true;
        last = x;
    }
    if (start != last) flag = false;
    for (int i = 1; i <= n; i++) {
        if (!visit[i]) flag = false;
    }
    return flag;
}
int main() {
    int m, a, b, k, q;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        g[a][b] = 1;
        g[b][a] = 1;
    }
    cin >> k;
    for (int i = 0; i < k; i++) {
        cin >> q;
        if (check(q)) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

柳婼的

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main() {
    int n, m, cnt, k, a[201][201] = {0};
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int t1, t2;
        cin >> t1 >> t2;
        a[t1][t2] = a[t2][t1] = 1;
    }
    cin >> cnt;
    while (cnt--) {
        cin >> k;
        vector<int> v(k);
        set<int> s;
        int flag1 = 1, flag2 = 1;
        for (int i = 0; i < k; i++) {
            cin >> v[i];
            s.insert(v[i]);
        }
        if (s.size() != n || k - 1 != n || v[0] != v[k - 1]) flag1 = 0;
        for (int i = 0; i < k - 1; i++) 
            if (a[v[i]][v[i+1]] == 0) flag2 = 0;
        printf("%s", flag1 && flag2 ? "YES\n" : "NO\n");
    }
    return 0;
}

1123 Is It a Complete AVL Tree

#include <iostream>
#include <queue>
using namespace std;
struct node{
    int val;
    node *left, *right;
};
node* rotateLeft(node* root) {
    node *t = root->right;
    root->right = t->left;
    t->left = root;
    return t;
}
node* rotateRight(node* root) {
    node *t = root->left;
    root->left = t->right;
    t->right = root;
    return t;
}
node* rotateLeftRight(node* root) {
    root->left = rotateLeft(root->left);
    return rotateRight(root);
}
node* rotateRightLeft(node* root) {
    root->right = rotateRight(root->right);
    return rotateLeft(root);
}
int getHeight(node* root) {
    if (root == NULL) return 0;
    return max(getHeight(root->left), getHeight(root->right)) + 1;
}
node* insert(node* root, int val) {
    if (root == NULL) {
        root = new node();
        root->val = val;
        root->left = NULL;
        root->right = NULL;
    } else if (val < root->val) {
        root->left = insert(root->left, val);
        if (getHeight(root->left) - getHeight(root->right) == 2) {
            root = val < root->left->val ? rotateRight(root) : rotateLeftRight(root);
        }
    } else {
        root->right = insert(root->right, val);
        if (getHeight(root->right) - getHeight(root->left) == 2) {
            root = val > root->right->val ? rotateLeft(root) : rotateRightLeft(root);
        }
    }
    return root;
}
vector<int> res;
bool bfs(node* u) {
    queue<node*> q;
    q.push(u);
    int t = 1;
    bool flag1 = true, flag2 = true;
    while (!q.empty()) {
        u = q.front();
        q.pop();
        if (u == NULL) flag1 = false;
        else {
            if (!flag1) flag2 = false;
            res.push_back(u->val);
            q.push(u->left);
            q.push(u->right);
        }
    }
    return flag2;
}
int main() {
    int n, val;
    cin >> n;
    node * root = NULL;
    for (int i = 0; i < n; i++) {
        cin >> val;
        root = insert(root, val);
    }
    int flag = bfs(root);
    for (int i = 0; i < res.size(); i++) {
        cout << res[i];
        if (i < res.size() - 1) cout << " ";
        else cout << endl;
    }
    if (flag) cout << "YES";
    else cout << "NO";
    return 0;
}

1124 Raffle for Weibo Followers

#include <iostream>
#include <string>
#include <map>
#include <vector>
using namespace std;
string nums[1001];
map<string, bool> st;
int main() {
    int m, n, s;
    cin >> m >> n >> s;
    for (int i = 1; i <= m; i++) {
        cin >> nums[i];
    }
    bool flag = false;
    for (int i = s; i <= m;) {
        if (!st[nums[i]]) {
            flag = true;
            st[nums[i]] = true;
            cout << nums[i] << endl;
            i += n;
        } else i++;
    }
    if (!flag) cout << "Keep going...";
    return 0;
}

1125 Chain the Ropes

#include <iostream>
#include <algorithm>
using namespace std;
int nums[10001];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    sort(nums, nums + n);
    double res = nums[0];
    for (int i = 1; i < n; i++) {
        res = (res + nums[i]) / 2;
    }
    cout << (int)res;
    return 0;
}

1126 Eulerian Path

#include <iostream>
using namespace std;
const int N = 501;
int degree[N], g[N][N], n;
bool visit[N];
void dfs(int u) {
    visit[u] = true;
    for (int i = 1; i <= n; i++) {
        if (!visit[i] && g[u][i])
            dfs(i);
    }
}
int main() {
    int m, a, b;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        degree[a]++;
        degree[b]++;
        g[a][b] = g[b][a] = 1;
    }
    int odd = 0;
    for (int i = 1; i <= n; i++) {
        if (degree[i] % 2) odd++;
        cout << degree[i];
        if (i < n) cout << " ";
        else cout << endl;
    }
    dfs(a);
    for (int i = 1; i <= n; i++) {
        if (!visit[i]) {
            cout << "Non-Eulerian";
            return 0;
        }
    }
    if (odd == 0) cout << "Eulerian";
    else if (odd == 2) cout << "Semi-Eulerian";
    else cout << "Non-Eulerian";
    return 0;
}

1127 ZigZagging on a Tree

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N = 31;
struct node{
    int l, r;
} trees[N];
int in[N], post[N], n;
int build(int leftIn, int rightIn, int leftPost, int rightPost) {
    if (leftIn > rightIn) return -1;
    int root = post[rightPost], id = leftIn;
    for (int i = leftIn; i <= rightIn; i++) {
        if (in[i] == root) id = i;
    }
    int leftCnt = id - leftIn;
    trees[root].l = build(leftIn, id - 1,leftPost, leftPost + leftCnt - 1);
    trees[root].r = build(id + 1, rightIn, leftPost + leftCnt, rightPost - 1);
    return root;
}
vector<int> res;
void bfs(int u) {
    queue<int> q;
    q.push(u);
    int depth = 1;
    while (!q.empty()) {
        int size = q.size();
        vector<int> tmp;
        for (int i = 0; i < size; i++) {
            u = q.front();
            q.pop();
            tmp.push_back(u);
            if (trees[u].l != -1) q.push(trees[u].l);
            if (trees[u].r != -1) q.push(trees[u].r);
        }
        if (depth % 2)
            for (int i = tmp.size() - 1; i >= 0; i--)
                res.push_back(tmp[i]);
        else
            for (int i = 0; i < tmp.size(); i++)
                res.push_back(tmp[i]);
        depth += 1;
    }
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) 
        cin >> in[i];
    for (int i = 0; i < n; i++) 
        cin >> post[i];
    int root = build(0, n - 1, 0, n - 1);
    bfs(root);
    for (int i = 0; i < res.size(); i++) {
        cout << res[i];
        if (i < res.size() - 1) cout << " ";
    }
    return 0;
}

1128 N Queens Puzzle

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1001;
bool de[2*N], inde[2*N], row[N];
int main() {
    int n, k, x;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> k;
        bool flag = true;
        memset(de, false, sizeof(de));
        memset(inde, false, sizeof(inde));
        memset(row, false, sizeof(row));
        for (int j = 1; j <= k; j++) {
            cin >> x;
            if (de[x+j] || inde[-x+j+k] || row[x])flag = false; 
            else de[x+j] = inde[-x+j+k] = row[x] = true;
        }
        if (flag) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

1129 Recommendation System

暴力（超时）

#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
map<int, int> nums;
bool cmp(pair<int, int> a, pair<int, int> b) {
    if (a.second != b.second) return a.second > b.second;
    return a.first < b.first;
}
int main() {
    int n, k, x;
    cin >> n >> k >> x;
    nums[x]++;
    for (int i = 1; i < n; i++) {
        cin >> x;
        vector<pair<int, int> > t(nums.begin(), nums.end());
        sort(t.begin(), t.end(), cmp);
        cout << x << ":";
        for (int i = 0; i < min(k, (int)t.size()); i++) {
            cout << " " << t[i].first;
        }
        cout << endl;
        nums[x]++;
    }
    return 0;
}

柳婼的

#include <iostream>
#include <set>
using namespace std;
int nums[50001];
struct node{
    int num, val;
    bool operator < (const node &a) const {
        if (val != a.val) return val > a.val;
        return num < a.num;
    }
};
int main() {
    int n, k, x;
    cin >> n >> k >> x;
    nums[x]++;
    set<node> st;
    st.insert({x, nums[x]});
    for (int i = 1; i < n; i++) {
        cin >> x;
        cout << x << ":";
        int j = 0;
        for (auto it = st.begin(); j < k && it != st.end(); it++) {
            cout << " " << it->num;
            j++;
        }
        cout << endl;
        auto t = st.find({x, nums[x]});
        if (t != st.end()) st.erase(t);
        nums[x]++;
        st.insert({x, nums[x]});
    }
    return 0;
}

1130 Infix Expression

#include <iostream>
#include <string>
using namespace std;
struct node {
    string x;
    int l, r;
} trees[21];
bool st[21];
string dfs(int u) {
    if (trees[u].l == -1 && trees[u].r == -1) return trees[u].x;
    if (trees[u].l == -1 && trees[u].r != -1) return "(" + trees[u].x + dfs(trees[u].r) + ")";
    if (trees[u].l != -1 && trees[u].r != -1) return "(" + dfs(trees[u].l) + trees[u].x + dfs(trees[u].r) + ")";
}
int main() {
    int n, l, r, root;
    string x;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x >> l >> r;
        trees[i] = {x, l, r};
        st[l] = st[r] = true;
    }
    for (int i = 1; i <= n; i++) {
        if (!st[i]) root = i;
    }
    string res = dfs(root);
    if (res[0] == '(') res = res.substr(1, res.size() - 2);
    cout << res;
    return 0;
}

1131 Subway Map

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
const int N = 10001;
unordered_map<int, int> line;
vector<int> g[N], tmp, res;
int dest, mind, mint, pre, pret;
bool visit[N];
int cnt() {
    int cnt = -1, pre = 0;
    for (int i = 1; i < tmp.size(); i++) {
        if (line[tmp[i - 1] * 10000 + tmp[i]] != pre) cnt++;
        pre = line[tmp[i - 1] * 10000 + tmp[i]]; 
    }
    return cnt;
}
void dfs(int u, int d) {
    if (u == dest && (mind > d || mind == d && mint > cnt())) {
        mind = d;
        mint = cnt();
        res = tmp;
    }
    if (u == dest) return;
    for (int i = 0; i < g[u].size(); i++) {
        if (!visit[g[u][i]]) {
            visit[g[u][i]] = true;
            tmp.push_back(g[u][i]);
            dfs(g[u][i], d + 1);
            tmp.pop_back();
            visit[g[u][i]] = false;
        }
    }
}
int main() {
    int n, k, x, y;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> k >> x;
        for (int j = 1; j < k; j++) {
            cin >> y;
            g[x].push_back(y);
            g[y].push_back(x);
            line[x * 10000 + y] = line[y * 10000 + x] = i;
            x = y;
        }
    }
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x >> dest;
        mind = 0x3f3f3f3f, mint = 0x3f3f3f3f, pre = 0, pret = x;
        tmp.clear();
        tmp.push_back(x);
        visit[x] = true;
        dfs(x, 0);
        visit[x] = false;
        cout << mind << endl;
        for (int j = 1; j < res.size(); j++) {
            if (line[res[j - 1] * 10000 + res[j]] != pre) {
                if (pre != 0) printf("Take Line#%d from %04d to %04d.\n", pre, pret, res[j - 1]);
                pre = line[res[j - 1] * 10000 + res[j]];
                pret = res[j - 1];
            }
        }
        printf("Take Line#%d from %04d to %04d.\n", pre, pret, dest);
    }
    return 0;
}

1132 Cut Integer

#include <iostream>
#include <string>
using namespace std;
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string z;
        cin >> z;
        int c = stoi(z);
        int a = stoi(z.substr(0, z.size() / 2));
        int b = stoi(z.substr(z.size() / 2));
        if (a * b == 0 || c % (a * b)) cout << "No" << endl;
        else cout << "Yes" << endl;
    }
    return 0;
}

1133 Splitting A Linked List

#include <iostream>
#include <vector>
using namespace std;
struct node {
    int add, val, nex;
} nums[100001];
vector<int> res1, res2, res3, res;
int main() {
    int start, n, k, add, val, nex;
    cin >> start >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> add >> val >> nex;
        nums[add] = {add, val, nex};
    }
    int t = start;
    while (t != -1) {
        if (nums[t].val < 0) res1.push_back(t);
        else if (nums[t].val <= k) res2.push_back(t);
        else res3.push_back(t);
        t = nums[t].nex;
    }
    for (auto it: res1) res.push_back(it);
    for (auto it: res2) res.push_back(it);
    for (auto it: res3) res.push_back(it);
    for (int i = 0; i < res.size() - 1; i++) {
        printf("%05d %d %05d\n", nums[res[i]].add, nums[res[i]].val, nums[res[i + 1]].add);
    }
    printf("%05d %d -1", nums[res[res.size() - 1]].add, nums[res[res.size() - 1]].val);
    return 0;
}

1134 Vertex Cover

#include <iostream>
#include <vector>
#include <set>
using namespace std;
const int N = 10001;
vector<int> g[N];
set<int> res;
int main() {
    int n, m, a, b, k;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    cin >> k;
    for (int i = 0; i < k; i++) {
        cin >> n;
        res.clear();
        for (int j = 0; j < n; j++) {
            cin >> a;
            for (int i = 0; i < g[a].size(); i++) {
                if (a < g[a][i]) res.insert(a * 10000 + g[a][i]);
                else res.insert(g[a][i] * 10000 + a);
            }
        }
        if (res.size() == m) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

柳婼的

#include <iostream>
#include <vector>
using namespace std;
const int N = 10001;
vector<int> g[N];
bool st[N];
int main() {
    int n, m, a, b, k;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        g[a].push_back(i);
        g[b].push_back(i);
    }
    cin >> k;
    for (int i = 0; i < k; i++) {
        cin >> n;
        fill(st, st + N, false);
        for (int j = 0; j < n; j++) {
            cin >> a;
            for (int i = 0; i < g[a].size(); i++) 
                st[g[a][i]] = true;
        }
        bool flag = true;
        for (int j = 0; j < m; j++) {
            if (!st[j]) {
                flag = false;
                break;
            }
        }
        if (flag) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

1135 Is It A Red-Black Tree

#include <iostream>
using namespace std;
struct node {
    int val;
    node *l, *r;
};
node* build(node* root, int val) {
    if (root == NULL) {
        root = new node();
        root->val = val;
        root->l = root->r = NULL;
    } else if (abs(val) <= abs(root->val)) {
        root->l = build(root->l, val);
    } else 
        root->r = build(root->r, val);
    return root;
}
bool judge1(node* root) {
    if (root == NULL) return true;
    if (root->val < 0) {
        if (root->l != NULL && root->l->val < 0) return false;
        if (root->r != NULL && root->r->val < 0) return false;
    }
    return judge1(root->l) && judge1(root->r);
}
int getnum(node* root) {
    if (root == NULL) return 0;
    int l = getnum(root->l);
    int r = getnum(root->r);
    if (root->val > 0) return max(l, r) + 1;
    else return max(l, r);
}
bool judge2(node* root) {
    if (root == NULL) return true;
    int l = getnum(root->l);
    int r = getnum(root->r);
    if (l != r) return false;
    return judge2(root->l) && judge2(root->r);
}
int main() {
    int k, n, x, start;
    cin >> k;
    for (int i = 0; i < k; i++) {
        cin >> n;
        node* root = NULL;
        for (int j = 0; j < n; j++) {
            cin >> x;
            if (j == 0) start = x;
            root = build(root, x);
        }
        if (start < 0 || !judge1(root) || !judge2(root)) 
            cout << "No" << endl;
        else cout << "Yes" << endl;
    }
    return 0;
}

1136 A Delayed Palindrome

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
bool check(string s) {
    for (int i = 0; i < s.size() / 2; i++) {
        if (s[i] != s[s.size() - i - 1]) return false;
    }
    return true;
}
string add(string a, string b) {
    if (a.size() < b.size()) swap(a, b);
    string res = "";
    int i, t = 0;
    for (i = 0; i < b.size(); i++) {
        t = a[a.size() - i - 1] - '0' + b[b.size() - i - 1] - '0' + t;
        res += (t % 10) + '0';
        t /= 10;
    }
    for (; i < a.size(); i++) {
        t = a[a.size() - i - 1] - '0' + t;
        res += (t % 10) + '0';
        t /= 10;
    }
    if (t) res += '1';
    reverse(res.begin(), res.end());
    return res;
}
int main() {
    string a;
    int cnt = 0;
    cin >> a;
    while(!check(a) && cnt < 10) {
        string b = a;
        reverse(a.begin(), a.end());
        string c = add(a, b);
        cout << b << " + " << a << " = " << c << endl;
        a = c;
        cnt++;
    }
    if (check(a)) cout << a << " is a palindromic number.";
    else cout << "Not found in 10 iterations.";
    return 0;
}

1137 Final Grading

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
using namespace std;
struct node {
    string id;
    int gp, gm, gf, g;
};
vector<node> nums;
map<string, int> mgp;
map<string, int> mgm;
map<string, int> mgf;
set<string> ids;
bool cmp(node &a, node &b) {
    if (a.g != b.g) return a.g > b.g;
    else return a.id < b.id;
}
int main() {
    int p, m, n, g;
    string id;
    cin >> p >> m >> n;
    for (int i = 0; i < p; i++) {
        cin >> id >> g;
        mgp[id] = g;
        ids.insert(id);
    }
    for (int i = 0; i < m; i++) {
        cin >> id >> g;
        mgm[id] = g;
        ids.insert(id);
    }
    for (int i = 0; i < n; i++) {
        cin >> id >> g;
        mgf[id] = g;
        ids.insert(id);
    }
    for (auto id: ids) {
        if (mgp[id] >= 200) {
            if(mgm.find(id) == mgm.end()) mgm[id] = -1;
            if (mgm[id] > mgf[id]) g = mgm[id] * 0.4 + mgf[id] * 0.6 + 0.5;
            else g = mgf[id];
            if (g >= 60) {
                nums.push_back({id, mgp[id], mgm[id], mgf[id], g});
            }
        } 
    }
    sort(nums.begin(), nums.end(), cmp);
    for (auto it: nums) {
        cout << it.id << " " << it.gp << " " << it.gm << " " << it.gf << " " << it.g << endl;
    }
    return 0;
}

1138 Postorder Traversal

#include <iostream>
using namespace std;
const int N = 50001;
int pre[N], in[N];
bool flag;
void build(int preL, int preR, int inL, int inR) {
    if (preL > preR || flag) return;
    int root = pre[preL], id = inL;
    for (int i = inL; i <= inR; i++) {
        if (root == in[i]) {
            id = i;
            break;
        }
    }
    int cntL = id - inL;
    build(preL + 1, preL + cntL, inL, id - 1);
    build(preL + cntL + 1, preR, id + 1, inR);
    if (!flag) {
        cout << root << endl;
        flag = true;
    }
}
int main(){
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> pre[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> in[i];
    }
    build(0, n - 1, 0, n - 1);
    return 0;
}

1139 First Contact

没考虑-0000

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> g[20001];
bool visit[20001];
int main() {
    int n, m, k, a, b;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        if (a < 0) a += 20000;
        if (b < 0) b += 20000;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    cin >> k;
    for (int i = 0; i < k; i++) {
        cin >> a >> b;
        fill(visit, visit + 20001, false);
        if (a < 0) a += 20000;
        if (b < 0) b += 20000;
        visit[a] = visit[b] = true;
        vector<pair<int, int> > res;
        if (a < 10000 && b < 10000) {
            for (int j = 0; j < g[a].size(); j++) {
                if (!visit[g[a][j]] && g[a][j] < 10000) {
                    visit[g[a][j]] = true;
                    for (int p = 0; p < g[g[a][j]].size(); p++) {
                        if (!visit[g[g[a][j]][p]] && g[g[a][j]][p] < 10000) {
                            for (int q = 0; q < g[g[g[a][j]][p]].size(); q++) {
                                if (g[g[g[a][j]][p]][q] == b) {
                                    res.push_back({g[a][j], g[g[a][j]][p]});
                                    break;
                                }
                            }
                        }
                    }
                    visit[g[a][j]] = false;
                }
            }
        } else if (a > 10000 && b < 10000) {
            for (int j = 0; j < g[a].size(); j++) {
                if (!visit[g[a][j]] && g[a][j] > 10000) {
                    visit[g[a][j]] = true;
                    for (int p = 0; p < g[g[a][j]].size(); p++) {
                        if (!visit[g[g[a][j]][p]] && g[g[a][j]][p] < 10000) {
                            for (int q = 0; q < g[g[g[a][j]][p]].size(); q++) {
                                if (g[g[g[a][j]][p]][q] == b) {
                                    res.push_back({-g[a][j] + 20000, g[g[a][j]][p]});
                                    break;
                                }
                            }
                        }
                    }
                    visit[g[a][j]] = false;
                }
            }
        } else if (a < 10000 && b > 10000) {
            for (int j = 0; j < g[a].size(); j++) {
                if (!visit[g[a][j]] && g[a][j] < 10000) {
                    visit[g[a][j]] = true;
                    for (int p = 0; p < g[g[a][j]].size(); p++) {
                        if (!visit[g[g[a][j]][p]] && g[g[a][j]][p] > 10000) {
                            for (int q = 0; q < g[g[g[a][j]][p]].size(); q++) {
                                if (g[g[g[a][j]][p]][q] == b) {
                                    res.push_back({g[a][j], -g[g[a][j]][p] + 20000});
                                    break;
                                }
                            }
                        }
                    }
                    visit[g[a][j]] = false;
                }
            }
        } else if (a > 10000 && b > 10000) {
            for (int j = 0; j < g[a].size(); j++) {
                if (!visit[g[a][j]] && g[a][j] > 10000) {
                    visit[g[a][j]] = true;
                    for (int p = 0; p < g[g[a][j]].size(); p++) {
                        if (!visit[g[g[a][j]][p]] && g[g[a][j]][p] > 10000) {
                            for (int q = 0; q < g[g[g[a][j]][p]].size(); q++) {
                                if (g[g[g[a][j]][p]][q] == b) {
                                    res.push_back({-g[a][j] + 20000, -g[g[a][j]][p] + 20000});
                                    break;
                                }
                            }
                        }
                    }
                    visit[g[a][j]] = false;
                }
            }
        }
        cout << res.size() << endl;
        sort(res.begin(), res.end());
        for (int i = 0; i < res.size(); i++) {
            printf("%04d %04d\n", res[i].first, res[i].second);
        }
    }
    return 0;
}

柳婼的

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <unordered_map>
using namespace std;
unordered_map<int, bool> arr;
vector<int> v[10000];
int main() {
    int n, m, k;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        string a, b;
        cin >> a >> b;
        if (a.length() == b.length()) {
            v[abs(stoi(a))].push_back(abs(stoi(b)));
            v[abs(stoi(b))].push_back(abs(stoi(a)));
        }
        arr[abs(stoi(a)) * 10000 + abs(stoi(b))] = arr[abs(stoi(b)) * 10000 + abs(stoi(a))] = true;
    }
    cin >> k;
    for (int i = 0; i < k; i++) {
        int c, d;
        cin >> c >> d;
        vector<pair<int, int> > res;
        for (int j = 0; j < v[abs(c)].size(); j++) {
            for (int k = 0; k < v[abs(d)].size(); k++) {
                if (v[abs(c)][j] == abs(d) || abs(c) == v[abs(d)][k]) continue;
                      if (arr[v[abs(c)][j] * 10000 + v[abs(d)][k]] == true)
                          res.push_back({v[abs(c)][j], v[abs(d)][k]});
            }
        }
        cout << res.size() << endl;
        sort(res.begin(), res.end());
        for (int i = 0; i < res.size(); i++) {
            printf("%04d %04d\n", res[i].first, res[i].second);
        }
    }
    return 0;
}

1140 Look-and-say Sequence

#include <iostream>
using namespace std;
int main() {
    string s;
    int n, j;
    cin >> s >> n;
    for (int cnt = 1; cnt < n; cnt++) {
        string t;
        for (int i = 0; i < s.length(); i = j) {
            for (j = i; j < s.length() && s[j] == s[i]; j++);
            t += s[i] + to_string(j - i);
        }
        s = t;
    }
    cout << s;
    return 0;
}

1141 PAT Ranking of Institutions

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
struct node {
    string name;
    int tws, ns;
};
bool cmp(node &a, node &b) {
    if (a.tws != b.tws) return a.tws > b.tws;
    else if(a.ns != b.ns) return a.ns < b.ns;
    else return a.name < b.name;
}
unordered_map<string, vector<double> > schools;
vector<node> res;
int main() {
    int n;
    double score;
    string id, school;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> id >> score >> school;
        for (int j = 0; j < school.size(); j++) {
            school[j] = tolower(school[j]);
        }
        if (id[0] == 'B') score /= 1.5;
        else if (id[0] == 'T') score *= 1.5;
        schools[school].push_back(score);
    }
    for (auto it: schools) {
        double s = 0;
        for (double i: it.second) s += i;
        res.push_back({it.first, (int)s, it.second.size()});
    }
    sort(res.begin(), res.end(), cmp);
    cout << res.size() << endl;
    int rank = 1;
    for (int i = 0; i < res.size(); i++) {
        if (i != 0 && res[i].tws != res[i - 1].tws) rank = i + 1;
        cout << rank << " " << res[i].name << " " << res[i].tws << " " << res[i].ns << endl;
    }
    return 0;
}

1142 Maximal Clique

#include <iostream>
#include <vector>
#include <map>
using namespace std;
map<int, bool> mp;
int pre[10001];
int main() {
    int m, n, u, v, a;
    cin >> m >> n;
    for (int i = 0; i < n; i++) {
        cin >> pre[i];
        mp[pre[i]] = true;
    }
    for (int i = 0; i < m; i++) {
        cin >> u >> v;
        for (int j = 0; j < n; j++) {
            a = pre[j];
            if (a >= u && a <= v || a >= v && a <= u) break;
        }
        if (mp[u] == false && mp[v] == false)
            printf("ERROR: %d and %d are not found.\n", u, v);
        else if (mp[u] == false || mp[v] == false)
            printf("ERROR: %d is not found.\n", mp[u] == false ? u : v);
        else if (a == u || a == v)
            printf("%d is an ancestor of %d.\n", a, a == u ? v : u);
        else
            printf("LCA of %d and %d is %d.\n", u, v, a);
    }
    return 0;
}

1143 Lowest Common Ancestor

#include <iostream>
#include <vector>
#include <map>
using namespace std;
map<int, bool> mp;
int pre[10001];
int main() {
    int m, n, u, v, a;
    cin >> m >> n;
    for (int i = 0; i < n; i++) {
        cin >> pre[i];
        mp[pre[i]] = true;
    }
    for (int i = 0; i < m; i++) {
        cin >> u >> v;
        for (int j = 0; j < n; j++) {
            a = pre[j];
            if (a >= u && a <= v || a >= v && a <= u) break;
        }
        if (mp[u] == false && mp[v] == false)
            printf("ERROR: %d and %d are not found.\n", u, v);
        else if (mp[u] == false || mp[v] == false)
            printf("ERROR: %d is not found.\n", mp[u] == false ? u : v);
        else if (a == u || a == v)
            printf("%d is an ancestor of %d.\n", a, a == u ? v : u);
        else
            printf("LCA of %d and %d is %d.\n", u, v, a);
    }
    return 0;
}

1144 The Missing Number

#include <iostream>
#include <map>
using namespace std;
int main() {
    int n, a, num = 1;
    cin >> n;
    map<int, int> m;
    for (int i = 0; i < n; i++) {
        cin >> a;
        m[a]++;
    }
    while (true)
        if (m[num++] == 0) break;
    cout << num - 1;
    return 0;
}

1145 Hashing - Average Search Time

#include <iostream>
#include <cmath>
using namespace std;
int nums[10001];
bool isprime(int x) {
    if (x <= 1) return false;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}
int main() {
    int ms, n, m, x;
    cin >> ms >> n >> m;
    while (!isprime(ms)) ms++;
    for (int i = 0; i < n; i++) {
        cin >> x;
        bool flag = false;
        for (int j = 0; j < ms; j++) {
            if (nums[(x + j * j) % ms] == 0) {
                nums[(x + j * j) % ms] = x;
                flag = true;
                break;
            }
        }
        if (!flag) cout << x << " cannot be inserted." << endl;
    }
    int times = m;
    for (int i = 0; i < m; i++) {
        cin >> x;
        bool flag = false;
        for (int j = 0; j < ms; j++) {
            if (nums[(x + j * j) % ms] == x || nums[(x + j * j) % ms] == 0) {
                times += j;
                flag = true;
                break;
            }
        }
        if (!flag) times += ms;
    }
    printf("%.1f", (double)times / m);
    return 0;
}

1146 Topological Order

#include <iostream>
#include <vector>
using namespace std;
vector<int> v[1010], res;
int main() {
    int n, m, a, b, k, in[1010], tin[1010];
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        v[a].push_back(b);
        in[b]++;
    }
    cin >> k;
    for (int i = 0; i < k; i++) {
        bool flag = true;
        for (int i = 1; i <= n; i++) {
            tin[i] = in[i];
        }
        for (int i = 0; i < n; i++) {
            cin >> a;
            if (tin[a] != 0) flag = false;
            for (int it :v[a]) tin[it]--;
        }
        if (flag) continue;
        res.push_back(i);
    }
    for (int i = 0; i < res.size(); i++) {
        cout << res[i];
        if (i < res.size() - 1) cout << " ";
    }
    return 0;
}

1147 Heaps

#include <iostream>
#include <vector>
using namespace std;
int nums[2001], n;
struct node {
    int val, l, r;
}trees[1001];
vector<int> res;
void post(int root) {
    if (root >= n) return;
    post(trees[root].l);
    post(trees[root].r);
    res.push_back(trees[root].val);
}
int main() {
    int m;
    cin >> m >> n;
    for (int i = 0; i < m; i++) {
        int flag = 0;
        fill(nums, nums + 2 * n, -1);
        for (int j = 0; j < n; j++) cin >> nums[j];
        if (nums[0] > nums[1] && nums[0] > nums[2]) flag = 1;
        if (nums[0] < nums[1] && nums[0] < nums[2]) flag = 2;
        for (int j = 0; j < n; j++) {
            trees[j].val = nums[j];
            if (flag == 1 && (2*j+1 < n && nums[j] < nums[2*j+1] || 2*j+2 < n && nums[j] < nums[2*j+2])) flag = 0;
            if (flag == 2 && (2*j+1 < n && nums[j] > nums[2*j+1] || 2*j+2 < n && nums[j] > nums[2*j+2])) flag = 0;
            trees[j].l = 2 * j + 1;
            trees[j].r = 2 * j + 2;
        }
        post(0);
        if (flag == 0) cout << "Not Heap" << endl;
        else if (flag == 1) cout << "Max Heap" << endl;
        else if (flag == 2) cout << "Min Heap" << endl;
        for (int i = 0; i < res.size(); i++) {
            cout << res[i];
            if (i < res.size() - 1) cout << " ";
            else cout << endl;
        }
        res.clear();
    }
    return 0;
}

柳婼的

#include <iostream>
using namespace std;
int a[1005], m, n;
void post(int root) {
    if (root > n) return;
    post(root * 2);
    post(root * 2 + 1);
    printf("%d%s", a[root], root == 1 ? "\n" : " ");
}
int main() {
    cin >> m >> n;
    for (int j = 0; j < m; j++) {
        int minn = 1, maxn = 1;
        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 2; i <= n; i++) {
            if (a[i] > a[i / 2]) maxn = 0;
            if (a[i] < a[i / 2]) minn = 0;
        }
        if (maxn == 1) cout << "Max Heap" << endl;
        else if (minn == 1) cout << "Min Heap" << endl;
        else cout << "Not Heap" << endl;
        post(1);
    }
    return 0;
}

1148 Werewolf - Simple Version

#include <iostream>
using namespace std;
int nums[101];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> nums[i];
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            int t = 0, flag = 0;
            for (int k = 0; k < n; k++) {
                if (nums[k] < 0 && -nums[k] != i && -nums[k] != j) {
                    t++;
                    if ((k + 1) == i || (k + 1) == j) flag++;
                }
                if (nums[k] > 0 && (nums[k] == i || nums[k] == j)) {
                    t++;
                    if ((k + 1) == i || (k + 1) == j) flag++;
                }
            }
            if (t == 2 && flag == 1) {
                cout << i << " " << j << endl;
                return 0;
            }
        }
    }
    cout << "No Solution" << endl;
    return 0;
}

1149 Dangerous Goods Packaging

#include <iostream>
#include <vector>
using namespace std;
const int N = 100001;
bool st[N];
int nums[N];
vector<int> g[N];
int main() {
    int n, m, a, b, k;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for (int i = 0; i < m; i++) {
        cin >> k;
        bool flag = true;
        fill(st, st + N, false);
        for (int j = 0; j < k; j++) {
            cin >> nums[j];
            st[nums[j]] = true;
        }
        for (int j = 0; j < k; j++) {
            for (int r = 0; r < g[nums[j]].size(); r++) {
                if (st[g[nums[j]][r]]) {
                    flag = false;
                    break;
                }
            }
            if (!flag) break;
        }
        if (flag) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

1150 Travelling Salesman Problem

#include <iostream>
using namespace std;
bool visit[205];
int g[205][205], nums[205];
int main() {
    int n, m, k, t, city1, city2, d, res = 0x3f3f3f3f, id = 0;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> city1 >> city2 >> d;
        g[city1][city2] = g[city2][city1] = d;
    }
    cin >> k;
    for (int i = 1; i <= k; i++) {
        cin >> t;
        bool isCycle = true, isSimple = true, isNA = false;
        int dist = 0;
        for (int j = 0; j < t; j++) cin >> nums[j];
        fill(visit, visit + 205, false);
        for (int j = 1; j < t; j++) {
            if (g[nums[j]][nums[j-1]]) {
                dist += g[nums[j]][nums[j-1]];
                if (!visit[nums[j]]) visit[nums[j]] = true;
                else isSimple = false;
            } else {
                isCycle = false;
                isNA = true;
            }
        }
        for (int i = 1; i <= n; i++) 
            if (!visit[i]) isCycle = false;
        if (isCycle && dist < res) {
            res = dist;
            id = i;
        }
        if (isCycle && isSimple) cout << "Path " << i << ": " << dist << " (TS simple cycle)" << endl;
        else if (isCycle && !isSimple) cout << "Path " << i << ": " << dist << " (TS cycle)" << endl;
        else if (!isCycle && isNA) cout << "Path " << i << ": NA (Not a TS cycle)" << endl;
        else if (!isCycle && !isNA) cout << "Path " << i << ": " << dist << " (Not a TS cycle)" << endl;
    }
    cout << "Shortest Dist(" << id << ") = " << res;
    return 0;
}

1151 LCA in a Binary Tree

#include <iostream>
#include <vector>
#include <map>
using namespace std;
map<int, int> pos;
vector<int> in, pre;
void lca(int inl, int inr, int preRoot, int a, int b) {
    if (inl > inr) return;
    int inRoot = pos[pre[preRoot]], aIn = pos[a], bIn = pos[b];
    if (aIn < inRoot && bIn < inRoot) 
        lca(inl, inRoot - 1, preRoot + 1, a, b);
    else if ((aIn < inRoot && bIn > inRoot) || (aIn > inRoot && bIn < inRoot))
        printf("LCA of %d and %d is %d.\n", a, b, in[inRoot]);
    else if (aIn > inRoot && bIn > inRoot)
        lca(inRoot + 1, inr, preRoot + 1 + (inRoot - inl), a, b);
    else if (aIn == inRoot)
        printf("%d is an ancestor of %d.\n", a, b);
    else if (bIn == inRoot)
        printf("%d is an ancestor of %d.\n", b, a);
}
int main() {
    int m, n, a, b;
    cin >> m >> n;
    in.resize(n + 1);
    pre.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> in[i];
        pos[in[i]] = i;
    }
    for (int i = 1; i <= n; i++) cin >> pre[i];
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        if (pos[a] == 0 && pos[b] == 0) 
            printf("ERROR: %d and %d are not found.\n", a, b);
        else if (pos[a] == 0 || pos[b] == 0)
            printf("ERROR: %d is not found.\n", pos[a] == 0 ? a : b);
        else lca(1, n, 1, a, b);
    }
    return 0;
}

1152 Google Recruitment

#include <iostream>
#include <string>
using namespace std;
typedef long long LL;
bool check(LL n) {
    if (n < 2) return false;
    for (int i = 2; i * i < n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}
int main() {
    int l, k;
    string str;
    cin >> l >> k;
    cin >> str;
    for (int i = 0; i <= l - k; i++) {
        if (check(stol(str.substr(i, k)))) {
            cout << str.substr(i, k);
            return 0;
        }
    }
    cout << 404 << endl;
    return 0;
}

1153 Decode Registration Card of PAT)

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
struct node{
    string num;
    char ch;
    int site, date, score;
}nums[10005];
bool cmp1(node &a, node &b) {
    if (a.score != b.score) return a.score > b.score;
    return a.num < b.num;
}
bool cmp2(PII &a, PII &b) {
    if (a.second != b.second) return a.second > b.second;
    return a.first < b.first;
}
int main() {
    int n, m, flag, site, date, score, x;
    char ch;
    string num;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> num >> score;
        nums[i] = {num, num[0], stoi(num.substr(1, 3)), stoi(num.substr(4, 6)), score};
    }
    for (int i = 1; i <= m; i++) {
        cin >> flag;
        if (flag == 1) {
            vector<node> t;
            cin >> ch;
            cout << "Case " << i << ": 1 " << ch << endl;
            for (int j = 0; j < n; j++) 
                if (ch == nums[j].ch) t.push_back(nums[j]);
            sort(t.begin(), t.end(), cmp1);
            for (auto it: t) 
                cout << it.num << " " << it.score << endl;
            if (t.empty()) cout << "NA" << endl;
        } else if (flag == 2) {
            cin >> site;
            cout << "Case " << i << ": 2 " << site << endl;
            int nt = 0, ns = 0;
            for (int j = 0; j < n; j++) {
                if (site == nums[j].site) {
                    nt++;
                    ns += nums[j].score;
                }
            }
            if (nt == 0) cout << "NA" << endl;
            else cout << nt << " " << ns << endl;
        } else if (flag == 3) {
            cin >> date;
            printf("Case %d: 3 %06d\n", i, date);
            map<int, int> t;
            vector<pair<int, int>> t2;
            for (int j = 0; j < n; j++) {
                if (date == nums[j].date) {
                    t[nums[j].site] ++;
                }
            }
            for (auto it: t) 
                t2.push_back({it.first, it.second});
            sort(t2.begin(), t2.end(), cmp2);
            for (auto it: t2) 
                cout << it.first << " " << it.second << endl;
            if (t2.empty()) cout << "NA" << endl;
        }
    }
    return 0;
}

1154 Vertex Coloring

#include <iostream>
#include <vector>
using namespace std;
int level[1005];
struct node{
    int val, l, r;
} nums[1005];
int n;
int build(int root) {
    if (root >= n) return -1;
    nums[root].val = level[root];
    nums[root].l = build(root * 2 + 1);
    nums[root].r = build(root * 2 + 2);
    return root;
}
vector<int> t;
void dfs(int root) {
    if (root == -1) {
        for (int i = 0; i < t.size(); i++) {
            cout << t[i];
            if (i < t.size() - 1) cout << " ";
            else cout << endl;
        }
        return;
    }
    t.push_back(nums[root].val);
    if (nums[root].l == -1 && nums[root].r == -1) dfs(nums[root].l);
    else if (nums[root].l == -1) dfs(nums[root].r);
    else if (nums[root].r == -1) dfs(nums[root].l);
    else {
        dfs(nums[root].r);
        dfs(nums[root].l);
    }
    t.pop_back();
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) 
        cin >> level[i];
    build(0);
    dfs(0);
    bool ismin = true, ismax = true;
    for (int i = 2; i <= n; i++) {
        if (level[i/2-1] > level[i-1]) ismin = false;
        if (level[i/2-1] < level[i-1]) ismax = false;
    }
    if (ismin) cout << "Min Heap" << endl;
    else printf("%s", ismax ? "Max Heap" : "Not Heap");
    return 0;
}

1155 Heap Paths

#include <iostream>
#include <vector>
using namespace std;
int level[1005];
struct node{
    int val, l, r;
} nums[1005];
int n;
bool ismax, ismin;
int build(int root) {
    if (root >= n) return -1;
    nums[root].val = level[root];
    nums[root].l = build(root * 2 + 1);
    nums[root].r = build(root * 2 + 2);
    return root;
}
vector<int> t;
void dfs(int root) {
    if (root == -1) {
        for (int i = 0; i < t.size(); i++) {
            cout << t[i];
            if (i < t.size() - 1) cout << " ";
            else cout << endl;
        }
        return;
    }
    t.push_back(nums[root].val);
    if (nums[root].l == -1 && nums[root].r == -1) dfs(nums[root].l);
    else if (nums[root].l == -1) {
        if (nums[root].val > nums[nums[root].r].val) ismax = true;
        else if (nums[root].val < nums[nums[root].r].val) ismin = true;
        dfs(nums[root].r);
    }
    else if (nums[root].r == -1) {
        if (nums[root].val > nums[nums[root].l].val) ismax = true;
        else if (nums[root].val < nums[nums[root].l].val) ismin = true;
        dfs(nums[root].l);
    }
    else {
        if (nums[root].val > nums[nums[root].r].val && nums[root].val > nums[nums[root].l].val) ismax = true;
        else if (nums[root].val < nums[nums[root].r].val && nums[root].val < nums[nums[root].l].val) ismin = true;
        dfs(nums[root].r);
        dfs(nums[root].l);
    }
    t.pop_back();
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> level[i];
    build(0);
    dfs(0);
    if (ismax && ismin) cout << "Not Heap" << endl;
    else if (ismax) cout << "Max Heap" << endl;
    else if (ismin) cout << "Min Heap" << endl;
    return 0;
}

1156 Sexy Primes

#include <iostream>
using namespace std;
bool check(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}
int main() {
    int n;
    cin >> n;
    if (check(n) && check(n - 6)) cout << "Yes\n" << n - 6;
    else if (check(n) && check(n + 6)) cout << "Yes\n" << n + 6;
    else {
        for (int i = n + 1; ; i++) {
            if (check(i) && check(i - 6) || check(i) && check(i + 6)) {
                cout << "No\n" << i;
                break;
            }
        }
    }
    return 0;
}

1157 Anniversary

#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;
map<string, bool> isAlumni;
vector<string> alumnu, guest;
int main() {
    int n;
    string num;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> num;
        isAlumni[num] = true;
    }
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> num;
        if (isAlumni[num]) alumnu.push_back(num);
        else guest.push_back(num);
    }
    cout << alumnu.size() << endl;
    if (!alumnu.empty()) {
        string mind = alumnu[0].substr(6, 8), res = alumnu[0];
        for (int i = 1; i < alumnu.size(); i++) {
            if (mind > alumnu[i].substr(6, 8)) {
                mind = alumnu[i].substr(6, 8);
                res = alumnu[i];
            }
        }
        cout << res;
    } else {
        string mind = guest[0].substr(6, 8), res = guest[0];
        for (int i = 1; i < guest.size(); i++) {
            if (mind > guest[i].substr(6, 8)) {
                mind = guest[i].substr(6, 8);
                res = guest[i];
            }
        }
        cout << res;
    }
}

1158 Telefraud Detection

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
int g[1005][1005] , father[1005];
vector<int> suspects;
int find(int x) {
    if (father[x] != x) father[x] = find(father[x]);
    return father[x];
}
void union1(int a, int b) {
    int fa = find(a);
    int fb = find(b);
    if (fa != fb) {
        if (fa < fb) father[fb] = fa;
        else father[fa] = fb;
    }
}
int main() {
    int k, n, m, caller, receiver, duration;
    cin >> k >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> caller >> receiver >> duration;
        g[caller][receiver] += duration;
    }
    for (int i = 1; i <= n; i++) {
        int to = 0, back = 0;
        for (int j = 1; j <= n; j++) {
            if (g[i][j] && g[i][j] <= 5) to++;
            if (g[i][j] && g[i][j] <= 5 && g[j][i]) back++;
            if (to > k && back <= to * 0.2) {
                suspects.push_back(i);
                break;
            }
        }
    }
    if (suspects.empty()) cout << "None" << endl;
    for (int i = 0; i < suspects.size(); i++)
        father[suspects[i]] = suspects[i];
    for (int i = 0; i < suspects.size(); i++) {
        for (int j = i + 1; j < suspects.size(); j++) {
            if (g[suspects[i]][suspects[j]] && g[suspects[j]][suspects[i]]) {
                union1(suspects[i], suspects[j]);
            }
        }
    }
    map<int, vector<int>> res;
    for (int i = 0; i < suspects.size(); i++) {
        int t = find(suspects[i]);
        res[t].push_back(suspects[i]);
    }
    for (auto it: res) {
        sort(it.second.begin(), it.second.end());
        for (int i = 0; i < it.second.size(); i++) {
            cout << it.second[i];
            if (i < it.second.size() - 1) cout << " ";
            else cout << endl;
        }
    }
    return 0;
}

1159 Structure of a Binary Tree

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;
int post[31], in[31];
struct node {
    int l, r, parent, level;
} trees[1005];
bool isFull = true;
int build(int postL, int postR, int inL, int inR, int parent, int level) {
    if (postL > postR) return -1;
    int root = post[postR], id = inL;
    for (int i = inL; i <= inR; i++) {
        if (root == in[i]) {
            id = i;
            break;
        }
    }
    int cntL = id - inL;
    trees[root].parent = parent;
    trees[root].level = level;
    trees[root].l = build(postL, postL + cntL - 1, inL, id - 1, root, level + 1);
    trees[root].r = build(postL + cntL, postR - 1, id + 1, inR, root, level + 1);
    if (trees[root].l * trees[root].r < 0) isFull = false;
    return root;
}
int main() {
    int n, m, a, b;
    cin >> n;
    for (int i = 0; i < n; i++) 
        cin >> post[i];
    for (int i = 0; i < n; i++) 
        cin >> in[i];
    int root = build(0, n - 1, 0, n - 1, -1, 0);
    cin >> m;
    string ops;
    for (int i = 0; i < m; i++) {
        cin >> ops;
        if (ops == "It") {
            cin >> ops >> ops >> ops >> ops;
            if (isFull) cout << "Yes" << endl;
            else cout << "No" << endl;
            continue;
        }
        a = stoi(ops);
        cin >> ops;
        if (ops == "is") {
            cin >> ops >> ops;
            if (ops == "root") {
                if (a == root) cout << "Yes" << endl;
                else cout << "No" << endl;
            } else if (ops == "parent") {
                cin >> ops >> b;
                if (trees[a].l == b || trees[a].r == b) cout << "Yes" << endl;
                else cout << "No" << endl;
            } else if (ops == "left") {
                cin >> ops >> ops >> b;
                if (trees[b].l == a) cout << "Yes" << endl;
                else cout << "No" << endl;
            } else if (ops == "right") {
                cin >> ops >> ops >> b;
                if (trees[b].r == a) cout << "Yes" << endl;
                else cout << "No" << endl;
            }
        } else if (ops == "and") {
            cin >> b  >> ops >> ops;
            if (ops == "siblings") {
                if (trees[a].parent == trees[b].parent) cout << "Yes" << endl;
                else cout << "No" << endl;
            } else if (ops == "on") {
                cin >> ops >> ops >> ops;
                if (trees[a].level == trees[b].level) cout << "Yes" << endl;
                else cout << "No" << endl;
            }
        }
    }
    return 0;
}

1160 Forever

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef pair<int, LL> PII;
int k, m;
vector<PII> res;
int gcd(int a, int b) {
    if (b) return gcd(b, a % b);
    else return a;
}
bool isprime(int x) {
    if (x < 2) return false;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}
void dfs(int cnt, int sum, LL x) {
    if (cnt > k || sum > m || m > sum + 9*(k-cnt)) return;
    if (cnt == k && sum == m) {
        LL y = x + 1;
        int n = 0;
        while (y) {
            n += y % 10;
            y /= 10;
        }
        if (gcd(n, m) > 2 && isprime(gcd(n, m))) res.push_back({n, x});
        return;
    }
    for (int i = 0; i <= 9; i++) {
        if (sum == 0 && i == 0) continue;
        else dfs(cnt + 1, sum + i, x * 10 + i);
    }
}
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cout << "Case " << i << endl;
        cin >> k >> m;
        res.clear();
        dfs(0, 0, 0);
        if (res.empty()) cout << "No Solution" << endl;
        else {
            sort(res.begin(), res.end());
            for (int i = 0; i < res.size(); i++) {
                cout << res[i].first << " " << res[i].second << endl;
            }
        }
    }
    return 0;
}

1161 Merging Linked Lists

#include <iostream>
#include <vector>
using namespace std;
struct node{
    int add, val, nxt;
} nums[100005];
vector<node> l1, l2, res;
int main() {
    int s1, s2, n, id;
    cin >> s2 >> s1 >> n;
    for (int i = 0; i < n; i++) {
        cin >> id;
        cin >> nums[id].val >> nums[id].nxt;
        nums[id].add = id;
    }
    while (s1 != -1) {
        l1.push_back(nums[s1]);
        s1 = nums[s1].nxt;
    }
    while (s2 != -1) {
        l2.push_back(nums[s2]);
        s2 = nums[s2].nxt;
    }
    if (l1.size() < l2.size()) swap(l1, l2);
    id = 0;
    for (int i = l2.size() - 1; i >= 0; i--) {
        res.push_back(l1[id++]);
        res.push_back(l1[id++]);
        res.push_back(l2[i]);
    }
    for (int i = id; i < l1.size(); i++) 
        res.push_back(l1[i]);
    for (int i = 0; i < res.size() - 1; i++) 
        printf("%05d %d %05d\n", res[i].add, res[i].val, res[i + 1].add);
    printf("%05d %d -1", res.back().add, res.back().val);
    return 0;
}

1162 Postfix Expression

#include <iostream>
#include <string>
using namespace std;
struct node{
    string ch;
    int l, r;
} trees[21];
bool st[21];
void postorder(int x) {
    if (x == -1) return;
    if (trees[x].l == -1) {
        cout << "(" << trees[x].ch;
        postorder(trees[x].r);
        cout << ")";
    } else {
        cout << "(";
        postorder(trees[x].l);
        postorder(trees[x].r);
        cout << trees[x].ch << ")";
    }
}
int main() {
    int n, root = 1;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> trees[i].ch >> trees[i].l >> trees[i].r;
        st[trees[i].l] = st[trees[i].r] = true;
    }
    for (int i = 1; i <= n; i++) 
        if (!st[i]) root = i;
    postorder(root);
    return 0;
}

柳婼的

#include <iostream>
#include <string>
using namespace std;
int n, root = 1, lc[31], rc[31], mark[32];
string d[32];
void deal(int x) {
    cout << "(";
    if (lc[x] * rc[x] > 1) {
        deal(lc[x]);
        deal(rc[x]);
    }
    cout << d[x];
    if (lc[x] * rc[x] < 0) deal(rc[x]);
    cout << ")";
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> d[i] >> lc[i] >> rc[i];
        mark[lc[i]] = mark[rc[i]] = 1;
    }
    while (mark[root]) root++;
    deal(root);
    return 0;
}

1163 Dijkstra Sequence

#include <iostream>
using namespace std;
const int INF = 0x3f3f3f3f;
int n, m, g[1005][1005], nums[1005], d[1005];
bool visit[1005];
bool dijkstra(int x) {
    fill(visit, visit + 1005, false);
    fill(d, d + 1005, INF);
    d[x] = 0;
    for (int i = 0; i < n; i++) {
        int u = -1, mind = INF;
        for (int j = 1; j <= n; j++) {
            if (!visit[j]) {
                if (mind > d[j]) {
                    mind = d[j];
                    u = j;
                } else if (mind == d[j]) {
                    if (j == nums[i]) u = j;
                }
            } 
        }
        if (u != nums[i]) return false;
        visit[u] = true;
        for (int j = 1; j <= n; j++) {
            if (g[u][j] && !visit[j] && d[u] + g[u][j] < d[j]) {
                d[j] = d[u] + g[u][j];
            }
        }
    }
    return true;
}
int main() {
    int a, b, c, k;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = c;
    }
    cin >> k;
    for (int j = 0; j < k; j++) {
        for (int i = 0; i < n; i++) 
            cin >> nums[i];
        if (dijkstra(nums[0])) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

1164 Good in C

#include <iostream>
#include <string>
using namespace std;
string alp[27][8];
int main() {
    for (int i = 0; i < 26; i++) {
        for (int j = 0; j < 7; j++) 
            cin >> alp[i][j];
    }
    string strs[1000], t, str;
    char ch;
    int id2 = 0;
    getchar();
    getline(cin, t);
    for (int i = 0; i < t.size(); i++) {
        ch = t[i];
        if (ch >= 'A' && ch <= 'Z') str.push_back(ch);
        else if (!str.empty()) {
            strs[id2++] = str;
            str.clear();
        }
    }
    if (!str.empty()) {
        strs[id2++] = str;
        str.clear();
    }
    for (int i = 0; i < id2; i++) {
        for (int j = 0; j < 7; j++) {
            for (int k = 0; k < strs[i].size(); k++) {
                cout << alp[strs[i][k] - 'A'][j];
                if (k < strs[i].size() - 1) cout << " ";
                else cout << endl;
            }
        }
        if (i < id2 - 1) cout << endl;
    }
    return 0;
}

1165 Block Reversing

#include <iostream>
#include <vector>
using namespace std;
struct node {
    int add, val, nxt;
} nums[100005];
int main() {
    int start, n, k, add, val, nxt;
    cin >> start >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> add;
        nums[add].add = add;
        cin >> nums[add].val >> nums[add].nxt;
    }
    vector<int> tmps, res;
    while (start != -1) {
        tmps.push_back(start);
        start = nums[start].nxt;
    }
    int t = tmps.size() / k;
    for (int i = t * k; i < tmps.size(); i++) {
        res.push_back(tmps[i]);
    }
    for (int i = t * k - k; i >= 0; i -= k) {
        for (int j = 0; j < k; j++) {
            res.push_back(tmps[i + j]);
        }
    }
    for (int i = 0; i < res.size() - 1; i++) {
        printf("%05d %d %05d\n", nums[res[i]].add, nums[res[i]].val, nums[res[i + 1]].add);
    }
    printf("%05d %d -1", nums[res.back()].add, nums[res.back()].val);
    return 0;
}

1166 Summit

#include <iostream>
#include <vector>
using namespace std;
int g[205][205], nums[205];
bool st[205];
int main() {
    int n, m, a, b, k;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        g[a][b] = g[b][a] = 1;
    }
    cin >> k;
    for (int i = 1; i <= k; i++) {
        cout << "Area " << i;
        cin >> m;
        fill (st, st + 205, false);
        for (int j = 0; j < m; j++) {
            cin >> nums[j];
            st[nums[j]] = true;
        }
        bool flag1 = false, flag2 = false, flag3 = false;
        for (int p = 0; p < m; p++) {
            for (int q = p + 1; q < m; q++) {
                if (g[nums[p]][nums[q]] == 0) {
                    flag1 = true;
                    break;
                }
            }
            if (flag1) {
                cout << " needs help." << endl;
                break;
            }
        }
        if (!flag1) {
            for (int p = 1; p <= n; p++) {
                if (!st[p]) {
                    flag2 = false;
                    for (int q = 0; q < m; q++) 
                        if (g[p][nums[q]] == 0) flag2 = true;
                    if (!flag2) {
                        cout << " may invite more people, such as " << p << "." << endl;
                        flag3 = true;
                        break;
                    }
                }
            }
            if (!flag3) cout << " is OK." << endl;
        }
    }
    return 0;
}

1167 Cartesian Tree

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct node {
    int val, l, r;
} trees[32];
int in[32];
vector<int> level;
int build(int l, int r) {
    if (l > r) return -1;
    int mind = 0x3f3f3f3f, root = l;
    for (int i = l; i <= r; i++) {
        if (mind > in[i]) {
            mind = in[i];
            root = i;
        }
    }
    trees[root].val = mind;
    trees[root].l = build(l, root - 1);
    trees[root].r = build(root + 1, r);
    return root;
}
void bfs(int u) {
    queue<int> q;
    q.push(u);
    while (!q.empty()) {
        u = q.front();
        q.pop();
        level.push_back(trees[u].val);
        if (trees[u].l != -1) q.push(trees[u].l);
        if (trees[u].r != -1) q.push(trees[u].r);
    }
}
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) 
        cin >> in[i];
    int root = build(0, n - 1);
    bfs(root);
    for (int i = 0; i < n; i++) {
        cout << level[i];
        if (i < n - 1) cout << " ";
    }
    return 0;
}

1168 Prime Day

#include <iostream>
#include <string>
using namespace std;
bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}
int main() {
    string n;
    cin >> n;
    bool flag = true;
    for (int i = 0; i < 8; i++) {
        if (isPrime(stoi(n))) 
            cout << n << " Yes" << endl;
        else {
            cout << n << " No" << endl;
            flag = false;
        }
        n = n.substr(1);
    }
    if (flag) cout << "All Prime!";
    return 0;
}

1169 The Judger

#include<iostream>
#include <vector>
using namespace std;
bool st[100005], out[11];
int g[12][1005];
vector<int> nums;
bool check(int x) {
    for (int i = 0; i < nums.size(); i++) {
        for (int j = i + 1; j < nums.size(); j++) {
            if (x == abs(nums[i] - nums[j])) return true;
        }
    }
    return false;
}
int main() {
    int a, b, n, m;
    cin >> a >> b >> n >> m;
    st[a] = st[b] = true;
    nums.push_back(a);
    nums.push_back(b);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            cin >> g[i][j];
    }
    for (int i = 0; i < m; i++) {
        vector<int> tmp;
        for (int j = 0; j < n; j++) {
            if (!out[j]) {
                if (!st[g[j][i]] && check(g[j][i])) {
                    nums.push_back(g[j][i]);
                    st[g[j][i]] = true;
                } else {
                    tmp.push_back(j + 1);
                    out[j] = true;
                }
            }
        }
        if (!tmp.empty()) {
            for (int j = 0; j < tmp.size(); j++) 
                cout << "Round #" << i + 1 << ": " << tmp[j] << " is out." << endl;
        }
    }
    vector<int> res;
    for (int i = 0; i < n; i++) 
        if (!out[i]) res.push_back(i + 1);
    if (!res.empty()) {
        cout << "Winner(s):";
        for (int i = 0; i < res.size(); i++)
            cout << " " << res[i];
    } else cout << "No winner.";
    return 0;
}

1170 Safari Park

#include <iostream>
#include <vector>
#include <map>
using namespace std;
int g[505][505];
int main() {
    int n, r, k, a, b;
    cin >> n >> r >> k;
    for (int i = 0; i < r; i++) {
        cin >> a >> b;
        g[a][b] = g[b][a] = 1;
    }
    cin >> r;
    for (int i = 0; i < r; i++) {
        map<int, vector<int>> nums;
        for (int j = 1; j <= n; j++) {
            cin >> a;
            nums[a].push_back(j);
        }
        if (nums.size() == k) {
            bool flag = true;
            for (auto it: nums) {
                for (int p = 0; p < it.second.size(); p++) {
                    for (int q = p + 1; q < it.second.size(); q++) {
                        if (g[it.second[p]][it.second[q]]) flag= false;
                    }
                }
            }
            if (flag) cout << "Yes" << endl;
            else cout << "No" << endl;
        } else if (nums.size() < k) cout << "Error: Too few species." << endl;
        else if (nums.size() > k) cout << "Error: Too many species." << endl;
    }
    return 0;
}

1171 Replacement Selection

#include <iostream>
#include <queue>
using namespace std;
int nums[100005];
int main() {
    int n, m;
    cin >> n >> m;
    priority_queue<int, vector<int>, greater<int>> q1, q2;
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
        if (i < m) q1.push(nums[i]);
    }
    int id = m;
    while (q1.size()) {
        int now = q1.top();
        cout << now;
        q1.pop();
        if (id < n) {
            if (nums[id] < now) q2.push(nums[id]);
            else q1.push(nums[id]);
            id++;
        }
        if (q1.size()) cout << " ";
        else {
            swap(q1, q2);
            cout << endl;
        }
    }
    return 0;
}

1172 Panda and PP Milk

#include <iostream>
using namespace std;
int nums[10005], tmps[10005];
int main() {
    int n, res = 0;
    cin >> n;
    fill(tmps, tmps + n, 200);
    for (int i = 0; i < n; i++) cin >> nums[i];
    for (int i = 0; i < n; i++) {
        int t = nums[i], id = 0;
        for (int j = i - 1; j >= 0; j--) {
            if (t < nums[j]) {
                id++;
                tmps[j] = max(tmps[j], 200 + id * 100);
                t = nums[j];
            } else if (t == nums[j]) {
                tmps[j] = max(tmps[j], 200 + id * 100);
            } else break;
        }
        t = nums[i], id = 0;
        for (int j = i + 1; j < n; j++) {
            if (t < nums[j]) {
                id++;
                tmps[j] = max(tmps[j], 200 + id * 100);
                t = nums[j];
            } else if (t == nums[j]) {
                tmps[j] = max(tmps[j], 200 + id * 100);
            } else break;
        }
    }
    for (int i = 0; i < n; i++) 
        res += tmps[i];
    cout << res;
    return 0;
}

1173 How Many Ways to Buy a Piece of Land

#include <iostream>
using namespace std;
int nums[10005];
int main() {
    int n, m, res = 0;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> nums[i];
    for (int i = 0; i < n; i++) {
        int t = 0;
        for (int j = i; j < n; j++) {
            t += nums[j];
            if (t <= m) res++;
            else break;
        }
    }
    cout << res;
    return 0;
}

1174 Left-View of Binary Tree

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int in[25], pre[25];
vector<int> res;
struct node {
    int l, r;
} trees[200005];
int build(int preL, int preR, int inL, int inR) {
    if (preL > preR) return -1;
    int root = pre[preL], id = inL;
    for (int i = inL; i <= inR; i++) {
        if (root == in[i]) {
            id = i;
            break;
        }
    }
    int cntL = id - inL;
    trees[root].l = build(preL + 1, preL + cntL, inL, id - 1);
    trees[root].r = build(preL + cntL + 1, preR, id + 1, inR);
    return root;
}
void bfs(int root) {
    queue<int> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            root = q.front();
            q.pop();
            if (i == 0) res.push_back(root);
            if (trees[root].l != -1) q.push(trees[root].l);
            if (trees[root].r != -1) q.push(trees[root].r);
        }
    }
}
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> in[i];
    for (int i = 0; i < n; i++) cin >> pre[i];
    int root = build(0, n - 1, 0, n - 1);
    bfs(root);
    for (int i = 0; i < res.size(); i++) {
        cout << res[i];
        if (i < res.size() - 1) cout << " ";
        else cout << endl;
    }
    return 0;
}

1175 Professional Ability Test - PAT (Advanced Level) Practice (pintia.cn)

柳婼的

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct node {
    int v, score, voucher;
    bool operator < (const node &x) const {
        if(score != x.score) return score > x.score;
        else return voucher < x.voucher;
    }
};
struct bian {
    int next, S, D;
};
vector<bian> E[1005];
vector<pair<int,int>> Dis(1005, {2e9, -1});
int N, M, T1, T2, S, D, f, T, in[1005], in2[1005], Last[1005];
queue<int> DAG;
int huan() {
    vector<int> S;
    while(DAG.size()) {
        int now = DAG.front();
        DAG.pop();
        S.push_back(now);
        for(auto it : E[now]) {
            in2[it.next]--;
            if(!in2[it.next]) DAG.push(it.next);
        }
    }
    return S.size() == N;
}
void dijkstra() {
    vector<int> vis(1005);
    priority_queue<node> Q;
    Q.push({1002, 0, 0});
    Dis[1002].first = Dis[1002].second = 0;
    while(Q.size()) {
        node now = Q.top();
        Q.pop();
        if(vis[now.v]) continue;
        vis[now.v] = 1;
        Dis[now.v].first = now.score;
        Dis[now.v].second = now.voucher;
        for (auto it : E[now.v]) {
            if(vis[it.next]) continue;
            if((Dis[it.next].first > Dis[now.v].first + it.S) || ((Dis[it.next].first == Dis[now.v].first + it.S) && (Dis[it.next].second < Dis[now.v].second + it.D))) {
                Dis[it.next].first = Dis[now.v].first + it.S;
                Dis[it.next].second = Dis[now.v].second + it.D;
                Last[it.next] = now.v;
                Q.push({it.next, Dis[it.next].first, Dis[it.next].second});
            }
        }
    }
    return;
}
int main() {
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        cin >> T1 >> T2 >> S >> D;
        E[T1].push_back({T2, S, D});
        in[T2]++, in2[T2]++;
    }
    for (int i = 0; i < N; i++) {
        if (in[i] == 0) {
            E[1002].push_back({i, 0, 0});
            DAG.push(i);
        }
    }
    f = huan();
    dijkstra();
    cin >> T;
    if(f) cout << "Okay.\n";
    else cout << "Impossible.\n";
    for (int i = 1, q; i <= T; i++) {
        cin >> q;
        if(!in[q]) cout << "You may take test " << q << " directly.\n";
        else if(!f) cout << "Error.\n";
        else {
            vector<int> path;
            int now = q;
            while(q != 1002) {
                path.push_back(q);
                q = Last[q];
            }
            for (int j = path.size() - 1; j >= 0; j--) {
                cout << path[j];
                if(j) cout << "->";
            }
            cout << '\n';
        }
    }
    return 0;
}

1176 The Closest Fibonacci Number

#include <iostream>
#include <algorithm>
using namespace std;
int dp[43];
int main() {
    int n, res = 0, m = 0x3f3f3f3f;
    cin >> n;
    dp[0] = dp[1] = 1;
    if (n == 1) {
        cout << n;
        return 0;
    }
    for (int i = 2; i < 43; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
        if (m > abs(dp[i] - n)) {
            m = abs(dp[i] - n);
            res = dp[i];
        }
    }
    cout << res;
    return 0;
}

1177 Subsequence in Substring

#include <iostream>
#include <string>
using namespace std;
int main() {
    string s, p;
    cin >> s >> p;
    int m = 0x3f3f3f3f, idx, l = 0, r = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == p[0]) {
            idx = 1;
            for (int j = i + 1; j < s.size(); j++) {
                if (j - i >= m) break;
                if (s[j] == p[idx]) idx++;
                if (idx == p.size()) {
                    l = i, r = j;
                    m = r - l;
                }
            }
        }
    }
    for (int i = l; i <= r; i++) {
        cout << s[i];
    }
    return 0;
}

1178 File Path

#include <iostream>
#include <string>
#include <map>
using namespace std;
map<string, string> superior;
map<int, string> last;
int main() {
    int n, k;
    string root, str, res;
    cin >> n >> root;
    last[1] = root;
    superior[root] = root;
    getchar();
    for (int i = 1; i < n; i++) {
        getline(cin, str);
        int depth = 0;
        while (str[depth] == ' ') depth++;
        superior[str.substr(depth)] = last[depth];
        last[depth + 1] = str.substr(depth);
    }
    cin >> k;
    for (int i = 0; i < k; i++) {
        cin >> str;
        if (!superior.count(str)) cout << "Error: " << str << " is not found." << endl;
        else {
            res = "\n";
            while (str != root) {
                res = "->" + str + res;
                str = superior[str];
            }
            cout << root << res;
        }
    }
    return 0;
}

1179 Chemical Equation

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int n, m, k, num, used[101], res[101];
string s;
vector<int> product, tmp;
vector<vector<int> > equa[101];
bool cmp(const vector<int> &a, const vector<int> &b) {
    for (int i = 0; ; i++) 
        if (a[i] != b[i]) return a[i] < b[i];
}
void dfs(int x) {
    if (x == m) {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < equa[product[i]][res[i]].size(); j++) {
                if (j != 0) cout << " + ";
                printf("%02d", equa[product[i]][res[i]][j]);
            }
            printf(" -> %02d\n", product[i]);
        }
        exit(0);
    }
    for (int i = 0; i < equa[product[x]].size(); i++) {
        int flag = 1;
        vector<int> A = equa[product[x]][i];
        for (auto it: A) 
            if (used[it] != 1) {
                flag = 0;
                break;
            }
        if (flag == 0) continue;
        for (auto it: A) used[it] = 2;
        res[x] = i;
        dfs(x + 1);
        for (auto it: A) used[it] = 1;
    }
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> num;
        used[num] = 1;
    }
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> num;
        if (used[num] == 1) equa[num].push_back({num});
        product.push_back(num);
    }
    cin >> k;
    for (int i = 0; i < k; i++) {
        tmp.clear();
        while (cin >> num >> s) {
            tmp.push_back(num);
            if (s == "->") {
                cin >> num;
                equa[num].push_back(tmp);
                break;
            }
        }
    }
    for (int i = 0; i < m; i++) 
        sort(equa[product[i]].begin(), equa[product[i]].end(), cmp);
    dfs(0);
    return 0;
}

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。