跳转至

2021 final

L1-1 人与神

代码

Python
1
2
3
4
5
6
7
print("To iterate is human, to recurse divine.") # 比较快

#include <iostream>
int main() {
    std::cout << "To iterate is human, to recurse divine.";
    return 0;
}

L1-2 两小时学完 C 语言

标签

简单数学

思路

根据幼儿园二年级芝士，剩余字数 = 总字数 - 每分钟能看字数 * 看的时长

代码

C++
1
2
3
4
5
6
7
8
9
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, k, m;
    cin >> n >> k >> m;
    cout << n - k * m;
    return 0;
}

L1-3 强迫症

标签

字符串，模拟

思路

判断输入字符串的长度，为 6 则直接输出（注意补一个'-'）; 为 4 则判断属于 19xx 还是 20xx 年。

代码

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin >> s;
    if (s.length() == 6) {
        for (int i = 0; i < 6; i++) {
            cout << s[i];
            if (i == 3) cout << '-';
        }
    }
    else {
        int y = (s[0] - '0') * 10 + (s[1] - '0');
        if (y < 22) {
            cout << "20" << s[0] << s[1] << "-" << s[2] << s[3];
        }
        else {
            cout << "19" << s[0] << s[1] << "-" << s[2] << s[3];
        }
    }
    return 0;
}

L1-4 降价提醒机器人

标签

模拟

思路

每次输入的 p 和 m 对比即可，小于 m 就输出，记得保留一位小数

代码

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<double> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i];
        if (p[i] < m) {
            cout << "On Sale! " << fixed << setprecision(1) << p[i] << '\n';
        }
    }
    return 0;
}

L1-5 大笨钟的心情

标签

模拟

思路

存储 24 小时的心情指数，每次询问与 50 进行比较即可

代码

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
int main() {
    int a[25];
    for (int i = 0; i < 24; i++) cin >> a[i];
    int n;
    cin >> n;
    while (n >= 0 && n <= 23) {
        cout << a[n] << " ";
        if (a[n] > 50) cout << "Yes\n";
        else cout << "No\n";
        cin >> n;
    }
    return 0;
}

L1-6 吉老师的回归

标签

字符串，模拟

思路

将每道题的描述和 qiandao 与 easy 进行比对，若存在其中一个就跳过，否则存入这道题。最后如果 m 大于存储题目的数量就说明做完了，否则根据下标输出。

代码

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    string q = "qiandao", e = "easy";
    cin >> n >> m;
    vector<string> ans;
    n++; // 没有清除输入缓存，getline 会读取一个换行符，这里用 n++来抵消
    while (n--) {
        string s;
        getline(cin, s); // 输入的题目描述含空格，可用 getline 来读取
        bool f = 0;
        for (int i = 0; i < s.length(); i++) {
            bool be = 1, bq = 1;
            for (int j = 0; j < 4; j++) {
                if (s[i + j] != e[j]) {
                    be = 0;
                    break;
                }
            }
            for (int j = 0; j < 7; j++) {
                if (s[i + j] != q[j]) {
                    bq = 0;
                    break;
                }
            }
            if (be || bq) {
                f = 1;
                break;
            }
        }
        if (!f) ans.push_back(s);
    }
    if (m + 1 >= ans.size()) cout << "Wo AK le";
    else cout << ans[m + 1];
    return 0;
}

L1-7 天梯赛的善良

标签

模拟

思路

  1. 使用两个变量记录最值，再分别记录最值出现的次数，有新的最值出现时更新最值和 cnt
  2. 或者使用 map 来存储数量

代码

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 1.
#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    int mx = -1, mn = 1e7;
    int cnt_mx = 0, cnt_mn = 0;
    while (n--) {
        int a;
        cin >> a;
        if (a > mx) mx = a, cnt_mx = 1;
        else if (a == mx) cnt_mx++;
        if (a < mn) mn = a, cnt_mn = 1;
        else if (a == mn) cnt_mn++;
    }
    cout << mn << " " << cnt_mn << endl;
    cout << mx << " " << cnt_mx;
}

// 2.
int main() {
    int n;
    cin >> n;
    map<int, int> m;
    int mx = 0, mn = 1e7;
    while (n--) {
        int a;
        cin >> a;
        mn = min(mn, a);
        mx = max(mx, a);
        m[a]++;
    }
    cout << mn << " " << m[mn] << endl;
    cout << mx << " " << m[mx];
}

L1-8 乘法口诀数列

标签

模拟

思路

定义下标 pre 和 now 表示当前进行运算的两个数，根据题意模拟即可，注意两位数的插入

代码

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
int main() {
    int a, b, n;
    cin >> a >> b >> n;
    vector<int> ans;
    ans.push_back(a);
    ans.push_back(b);
    int pre = 0, now = 1;
    while (ans.size() < n) {
        int p = ans[pre] * ans[now];
        if (p > 9) ans.push_back(p / 10);
        ans.push_back(p % 10);
        pre++, now++;
    }
    for (int i = 0; i < n; i++) { // 注意只需要输出 n 个
        if (i) cout << " ";
        cout << ans[i];
    }
}

L2-1 包装机

标签

字符串，模拟，栈

思路

定义一个数组记录每条轨道当前的首个物品（下标）, 利用栈模拟，使用 vector 记录框里抓出的物品，模拟

注意栈满的状态

代码

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = (j); i <= (k); i++)
#define per(i, k, j) for(int i = (k); i >= (j); i--)
#define ll long long
using namespace std;
int n, m, smx;
vector<char> ans;
stack<char> st;
int p[105];
string s[105];
void out() {
    if (st.empty()) return;
    ans.push_back(st.top());
    st.pop();
}
void solve()
{
    cin >> n >> m >> smx;
    rep(i, 1, n) {
        cin >> s[i];
        s[i] = "%" + s[i]; // 方便从 1 开始计数
        p[i] = 1; // 从 1 开始抓物品
    }
    int op;
    cin >> op;
    while (op != -1) {
        if (op == 0) {
            out();
        }
        else {
            if (p[op] < m + 1) {
                if (st.size() == smx) out(); // 筐满，先扔出
                st.push(s[op][p[op]]);
                p[op]++;
            }
        }
        cin >> op;
    }
    for (auto c : ans) cout << c;
}
int main()
{
    int T_T = 1;
    // cin >> T_T;
    while (T_T--)
        solve();
    return 0;
}

L2-2 病毒溯源

标签

链表，搜索，模拟

思路

可以用链表（我用了 vector 来模拟）记录每个病毒产生的变异毒株。由于源头唯一，可用 vis=1 来记录某个病毒是否由变异得来，最后 vis 为 0 的那个病毒即为源头。 对每个病毒产生的变异毒株序号进行排序，这样就能保证所有长度相同的序列，最先得到的一定是最小的序列，长度更大时再更新答案。 或者也可以用 vector 比较大小来判断是否更新答案

代码

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = (j); i <= (k); i++)
#define per(i, k, j) for(int i = (k); i >= (j); i--)
#define ll long long
using namespace std;
vector<int> List[10005]; // 记录该病毒的变异毒株
int n;
bool vis[10005]; // 记录是否由变异得来
vector<int> now;
int ans[10005];
int len = 0;
void dfs(int x) {
    now.push_back(x); // 更新状态
    if (List[x].empty()) { // 不能再往下变异传递
        if (now.size() > len) { // 更新答案
            len = now.size();
            for (int i = 0; i < len; i++)
                ans[i] = now[i];
        }
        now.pop_back(); // 回溯
        return;
    }
    for (auto i : List[x]) {
        dfs(i);
    }
    now.pop_back(); // 回溯
}
void solve()
{
    cin >> n;
    rep(i, 0, n - 1) {
        int k;
        cin >> k;
        rep(j, 0, k - 1) {
            int a;
            cin >> a;
            vis[a] = 1;
            List[i].push_back(a);
        }
        sort(List[i].begin(), List[i].end());
    }
    rep(i, 0, n - 1) {
        if (!vis[i]) { // 找到源头
            dfs(i);
            break;
        }
    }
    cout << len << '\n';
    for (int i = 0; i < len; i++) {
        if (i != 0) cout << " ";
        cout << ans[i];
    }
}
int main()
{
    int T_T = 1;
    // cin >> T_T;
    while (T_T--)
        solve();
    return 0;
}

L2-3 清点代码库

标签

数据结构，STL, 模拟

思路

使用 map 来记录每种测试输入的数量，然后以 pair 的形式丢尽 vector 里，再对 vector 进行排序

注意排序函数 cmp 的编写，题目要求首先按模块个数非递增顺序，如果有并列，则按输出序列的递增序输出

代码

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = (j); i <= (k); i++)
#define per(i, k, j) for(int i = (k); i >= (j); i--)
#define ll long long
using namespace std;
int n, m;
map<vector<int>, int> mp;
vector<pair<vector<int>, int> > ans;
bool cmp(pair<vector<int>, int> a, pair<vector<int>, int> b) {
    if (a.second != b.second) return a.second > b.second;
    return a.first < b.first;
}
void solve()
{
    cin >> n >> m;
    rep(i, 1, n) {
        vector<int> v(m);
        rep(j, 0, m - 1) {
            cin >> v[j];
        }
        mp[v]++;
    }
    for (auto& [i, j] : mp) {
        ans.push_back({i, j});
    }
    sort(ans.begin(), ans.end(), cmp);
    cout << ans.size() << '\n';
    for (auto p : ans) {
        cout << p.second << " ";
        rep(k, 0, m - 1) {
            if (k != 0) cout << " ";
            cout << p.first[k];
        }
        cout << '\n';
    }
}
int main()
{
    int T_T = 1;
    // cin >> T_T;
    while (T_T--)
        solve();
    return 0;
}

L2-4 哲哲打游戏

标签

模拟

思路

对于每个操作进行模拟即可，记录存档点只需保存当前状态，不用保存是如何到达的这个状态

代码

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = (j); i <= (k); i++)
#define per(i, k, j) for(int i = (k); i >= (j); i--)
#define ll long long
using namespace std;
const int N = 1e5 + 5;
int n, m;
int k[N];
vector<int> ed[N];
int rec[105];
void solve()
{
    cin >> n >> m;
    rep(i, 1, n) {
        cin >> k[i];
        ed[i].push_back(-1); // 为了做出选择的下标从 1 开始
        rep(j, 1, k[i]) {
            int a;
            cin >> a;
            ed[i].push_back(a);
        }
    }
    int now = 1;
    rep(i, 1, m) {
        int op, j;
        cin >> op >> j;
        if (op == 0) { // make choice
            now = ed[now][j];
        }
        else if (op == 1) { // save
            rec[j] = now;
            cout << now << '\n';
        }
        else if (op == 2) { // read
            now = rec[j];
        }

    }
    cout << now;
}
int main()
{
    int T_T = 1;
    // cin >> T_T;
    while (T_T--)
        solve();
    return 0;
}

L3-1 森森旅游

标签

图论，线段树，数据结构

思路

首先对支付现金的线路建图

因为如果要兑换旅游金，就需要把手中现金全部兑换。所以考虑支付旅游金的线路反向建图， 然后分别从起点和终点跑一边 dijkstra, 再遍历 n 个点得到初始答案，用 map+set 或直接 multiset 来存储，方便找到最小值（好吧我不会线段树）. 在每个点的答案（需要的现金）是 dis1[i] + ceil(dis2[i] / a) （向上取整）

每次更新的时候只需要判断被更新掉的答案是否为唯一极小值，如果是，则更新答案。

ps: 感觉线段树应该更快，我这方法有一个 test 到了 937ms 马上超时了，但是不会线段树

代码

C++
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = (j); i <= (k); i++)
#define per(i, k, j) for(int i = (k); i >= (j); i--)
#define lson (x << 1)
#define rson (x << 1 | 1)
#define ll long long
using namespace std;
const int N = 1e5 + 5;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
struct edge {
    int v;
    ll w;
};
struct node {
    ll dis;
    int u;
    bool operator>(const node& a) const { return dis > a.dis; }
};
vector<edge> ed1[N], ed2[N];
ll dis1[N], dis2[N], ans[N], a[N];
bool vis1[N], vis2[N];
int n, m, q;
void dijkstra() {
    memset(dis1, llinf, sizeof(dis1));
    memset(dis2, llinf, sizeof(dis2));
    priority_queue<node, vector<node>, greater<node> > q;
    q.push({0, 1});
    dis1[1] = 0;
    while (!q.empty()) {
        int u = q.top().u;
        q.pop();
        if (vis1[u]) continue;
        vis1[u] = 1;
        for (auto e : ed1[u]) {
            int v = e.v;
            ll w = e.w;
            if (dis1[v] > dis1[u] + w) {
                dis1[v] = dis1[u] + w;
                q.push({dis1[v], v});
            }
        }
    }
    // 也可以使用传参的方式只写一遍，这里直接复制了
    priority_queue<node, vector<node>, greater<node> > qq;
    qq.push({0, n});
    dis2[n] = 0;
    while (!qq.empty()) {
        int u = qq.top().u;
        qq.pop();
        if (vis2[u]) continue;
        vis2[u] = 1;
        for (auto e : ed2[u]) {
            int v = e.v;
            ll w = e.w;
            if (dis2[v] > dis2[u] + w) {
                dis2[v] = dis2[u] + w;
                qq.push({dis2[v], v});
            }
        }
    }
}
map<ll, int> mp;
set<ll> st;
ll mn = llinf;
void solve()
{
    cin >> n >> m >> q;
    while (m--) {
        int u, v;
        ll c, d;
        cin >> u >> v >> c >> d;
        ed1[u].push_back({v, c});
        ed2[v].push_back({u, d}); // 旅游金反向建图
    }
    dijkstra();
    rep(i, 1, n) {
        cin >> a[i];
        if (dis1[i] == llinf || dis2[i] == llinf) { ans[i] = llinf; continue; } // 走不通的不用管
        else ans[i] = dis1[i] + dis2[i] / a[i] + (dis2[i] % a[i] ? 1 : 0); // 向上取整，不能整除就加 1
        mn = min(mn, ans[i]);
        mp[ans[i]]++;
        if (mp[ans[i]] == 1) st.insert(ans[i]);
    }
    while (q--) {
        int x;
        ll b;
        cin >> x >> b;
        if (dis1[x] != llinf && dis2[x] != llinf) {
            ll t = dis1[x] + dis2[x] / b + (dis2[x] % b ? 1 : 0);
            mp[t]++;
            if (mp[t] == 1) st.insert(t);
            mp[ans[x]]--;
            if (mp[ans[x]] == 0) {
                st.erase(st.find(ans[x])); // 已经没有这个情况了，删除这个数
            }
            mn = *st.begin(); // 更新最小值
            ans[x] = t; // 更新这个点的答案
        }
        cout << mn << '\n';
    }
}
int main()
{
    solve();
    return 0;
}

L3-2 还原文件

标签

模拟，搜索

思路

题目说了唯一解，说明不存在相同情况的两个纸条。所以直接暴力循环匹配，直到所有纸条都匹配到相应位置

代码

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = (j); i <= (k); i++)
#define per(i, k, j) for(int i = (k); i >= (j); i--)
#define ll long long
using namespace std;
const int N = 1e5 + 5;
int n, m;
int cnt[105], a[N];
vector<int> h[105];
int vis[N];
void dfs(int x) {
    if (x == m + 1) {
        int p = 1, num = 0;
        vector<int> res;
        while (p <= n) {
            if (vis[p] == 0) {
                p++;
                continue;
            }
            if (num == 0) {
                res.push_back(vis[p]);
                p++;
                num++;
            }
            else {
                if (vis[p] == res[num - 1])
                    p++;
                else {
                    res.push_back(vis[p]);
                    p++, num++;
                }
            }
        }
        rep(i, 0, num - 1) {
            if (i) cout << " ";
            cout << res[i];
        }
        exit(0);
    }
    rep(i, 1, n) {
        if (a[i + cnt[x] - 1] != h[x][cnt[x] - 1]) continue;
        bool flag = 1;
        rep(j, 0, cnt[x] - 2) {
            if (vis[i + j] || a[i + j] != h[x][j]) {
                flag = 0;
                break;
            }
        }
        if (flag == 0) continue; // 不完全匹配，跳过
        rep(j, 0, cnt[x] - 2) vis[i + j] = x; // 最左端不标记，防止特殊情况无法标记（如 k == 2）
        dfs(x + 1);
        rep(j, 0, cnt[x] - 2) vis[i + j] = 0; // 回溯
    }
}
void solve()
{
    cin >> n;
    rep(i, 1, n) {
        cin >> a[i];
    }
    cin >> m;
    rep(i, 1, m) {
        cin >> cnt[i];
        rep(j, 1, cnt[i]) { 
            int x;
            cin >> x;
            h[i].push_back(x);
        }
    }
    dfs(1);
}
int main()
{
    int T_T = 1;
    // cin >> T_T;
    while (T_T--)
        solve();
    return 0;
}

L3-3 可怜的简单题

标签

数论

思路

不会，先鸽了 QAQ