Hrbust ACM练习 2024级第4周题单题解分享

2024-09-16

105

前言

题单链接：2024级第4周题单 - Virtual Judge (vjudge.net)

很多同学困惑怎么学习 C++，我在此分享下我的经验。
我也是刚学习 C++ 没几天，按照我之前自己学习 Python 的经验来说，如果有条件买本翻译水平较好的外国著作来学习是再好不过的，退一步来说就是从网上的文章或者从下载的电子书中学习 C++。

在我的个人体验中，通过高效精练的文字中学习是比从视频和直播中学习更快的。一本好的书更是能作为参考书来随时查阅。

网站我推荐 OI Wiki，在这个网站你可以学习到竞赛所需的语言知识和算法知识，另外推荐使用洛谷 OJ 中的官方题单进行能力训练。

祝大家学有所成！

A 题

直接累加会超时，打表观察后直接计算。

Python Code

from math import ceil

n = int(input())
if n % 2 == 0:
    print(ceil(n / 2))
else:
    print(-ceil(n / 2))

Python Code 另一种实现

n = int(input())
s = (n + 1) // 2
if n % 2 == 0:
    print(s)
else:
    print(-s)

Cpp Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ll n;
    cin >> n;
    ll s = (n + 1) / 2;
    if (n % 2 == 1) {
        cout << -s;
    } else {
        cout << s;
    }
    return 0;
}

B 题

直接用标准库实现即可

Cpp Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int n;
    cin >> n;
    vector<int> l;

    while (n > 0) {
        n--;
        int a;
        cin >> a;

        if (a == 1) {
            int t;
            cin >> t;
            l.push_back(t);
        } else if (a == 2) {
            sort(l.begin(), l.end());
        } else if (a == 3) {
            reverse(l.begin(), l.end());
        } else if (a == 4) {
            cout << l.size() << endl;
        } else if (a == 5) {
            for (int i : l) {
                cout << i << " ";
            }
            cout << endl;
        } else if (a == 6) {
            l.clear();
        }
    }
    return 0;
}

C 题

直接用标准库实现即可

Cpp Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int n;
    cin >> n;
    stack<int> l;
    while (n > 0) {
        n--;
        int a;
        cin >> a;

        if (a == 1) {
            int t;
            cin >> t;
            l.push(t);
        } else if (a == 2) {
            cout << l.top() << endl;
        } else if (a == 3) {
            l.pop();
        } else if (a == 4) {
            cout << l.size() << endl;
        }
    }
}

D 题

直接用标准库实现即可

Cpp Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int n;
    cin >> n;
    stack<int> l;
    while (n > 0) {
        n--;
        int a;
        cin >> a;

        if (a == 1) {
            int t;
            cin >> t;
            l.push(t);
        } else if (a == 2) {
            cout << l.top() << endl;
        } else if (a == 3) {
            l.pop();
        } else if (a == 4) {
            cout << l.size() << endl;
        }
    }
}

E 题

按照要求操作即可

Cpp Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int T, m, i = 0;
    long long unsigned n;
    cin >> T;

    while (T > 0) {
        T--;
        i++;
        cout << "Case " << i << ":" << endl;
        cin >> n >> m;
        deque<int> l;
        while (m > 0) {
            m--;
            string a;
            cin >> a;

            if (a == "pushLeft") {
                int number;
                cin >> number;
                if (l.size() == n) {
                    cout << "The queue is full" << endl;
                } else {
                    l.push_front(number);
                    cout << "Pushed in left: " << number << endl;
                }
            } else if (a == "pushRight") {
                int number;
                cin >> number;
                if (l.size() == n) {
                    cout << "The queue is full" << endl;
                } else {
                    l.push_back(number);
                    cout << "Pushed in right: " << number << endl;
                }
            } else if (a == "popLeft") {
                if (l.size() == 0) {
                    cout << "The queue is empty" << endl;
                } else {
                    cout << "Popped from left: " << l.front() << endl;
                    l.pop_front();
                }
            } else if (a == "popRight") {
                if (l.size() == 0) {
                    cout << "The queue is empty" << endl;
                } else {
                    cout << "Popped from right: " << l.back() << endl;
                    l.pop_back();
                }
            }
        }
    }
    return 0;
}

F 题

原题链接：HDU 1022

车库是个 stack 命名为 st
火车进入序列（顺序）是 st_in
火车退出序列（顺序）是 st_out

思路很简单，每次循环只要车库有车，就先比较车库最口上的车和 st_out 下一个要求出去的车是不是一样的，如果是一样的就出车（st 出车，st_out 删掉要求出车）。
如果车库没车或者车库有车但是车库最口上的车和 st_out 下一个要求出去的车不一样，就从 st_in 取一辆车。
如果从 st_in 取车的时候发现无车可取（st_in 的 size 为 0），那就退出循环。

退出循环后只有两种可能

车库没车，从 st_in 取车也没车。这个时候退出的循环，其实就是车全部按照序列走光了。那就是成功了。这时候 st_out 的 size 一定是 0，st 的 size 也是 0。
车库有车，但是车库有车但是车库最口上的车和 st_out 下一个要求出去的车不一样，从 st_in 取车没车。这个时候退出循环说明车被堵住了，没法按照退出序列把车开出去，那就是失败了。这时候 st_out 的 size 一定不为 0，st 的 size 也不为 0。

Cpp Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int n_o;
    while (cin >> n_o) {
        deque<int> st_in;
        deque<int> st_out;
        stack<int> st;
        deque<string> operations;
        int n = n_o;

        getchar();  // read space
        while (n > 0) {
            st_in.push_back(getchar());
            n--;
        }

        getchar();  // read space
        n = n_o;
        while (n > 0) {
            st_out.push_back(getchar());
            n--;
        }

        while (true) {
            if (st.size() != 0 && st.top() == st_out.front()) {
                st.pop();
                st_out.pop_front();
                operations.push_back("out");
            } else {
                if (st_in.size() == 0) {
                    break;
                } else {
                    st.push(st_in.front());
                    st_in.pop_front();
                    operations.push_back("in");
                }
            }
        }

        if (st.size() == 0) {
            cout << "Yes." << endl;
            for (string s : operations) {
                cout << s << endl;
            }
        } else {
            cout << "No." << endl;
        }
        cout << "FINISH" << endl;
    }
    return 0;
}

G 题

原题链接：UVA 673

这题要注意：需要检查的字符串可能为空

Python Code

def a(s):
    st = []
    d = {"(": ")", "[": "]"}

    for c in s:
        if c in ")]":
            if st and d[st[-1]] == c:
                st.pop()
            else:
                return "No"
        else:
            st.append(c)

    return "No" if st else "Yes"


[print(a(input().strip())) for _ in range(int(input()))]

Cpp Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

string a(string s) {
    stack<char> l;
    map<char, char> d = {{'(', ')'}, {'[', ']'}};

    for (char c : s) {
        if (c == ')' || c == ']') {
            if (!l.empty() && d[l.top()] == c) {
                l.pop();
            } else {
                return "No";
            }
        } else {
            l.push(c);
        }
    }
    if (l.empty()) {
        return "Yes";
    } else {
        return "No";
    }
}

int main() {
    int n;
    cin >> n;
    getchar();  // 读取上一行输入数据后输入的回车
    while (n > 0) {
        string s;
        getline(cin, s);  // 用 getline 而不是用 cin 是因为后面的字符串序列可能为空
        cout << a(s) << endl;
        n--;
    }
    return 0;
}

H 题

24.9.22 更新

原题是 The 2024 ICPC Asia East Continent Online Contest (I) 的 F 题

此题未通过

这题对于我来说太难，一直超时，跳过

c = int(input())

while c > 0:
    rt = 0
    c -= 1
    n = int(input())
    index_max = n - 1
    l = list(map(int, input().split()))
    for i, e in enumerate(l):
        l_step = 0
        r_step = 0
        l_max_number = e
        r_max_number = e
        for l_number in l[i::-1]:
            if l_number > l_max_number:
                l_max_number = l_number
                l_step += 1
            if l_number < l_max_number:
                break
        for r_number in l[i + 1 :]:
            if r_number > r_max_number:
                r_max_number = r_number
                r_step += 1
            if r_number < r_max_number:
                break
        rt += l_step + r_step
    print(rt)

I 题

24.9.22 凌晨更新题解

原题链接：HDU 2034

没啥难度，题目的 A-B 是 A\cap \complement_UB （A\cap \overline{B}）

Cpp Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int n, m;
    while (cin >> n) {
        cin >> m;
        vector<int> a, b;

        if (n == 0 and m == 0) {
            return 0;
        }

        int _number;
        while (n > 0) {
            n--;
            cin >> _number;
            a.push_back(_number);
        }
        while (m > 0) {
            m--;
            cin >> _number;
            b.push_back(_number);
        }

        sort(a.begin(), a.end());
        sort(b.begin(), b.end());
        bool flag = false;
        for (int number : a) {
            if (!binary_search(b.begin(), b.end(), number)) {
                cout << number << " ";
                flag = true;
            }
        }
        if (flag == false) {
            cout << "NULL";
        }
        cout << endl;
    }

    return 0;
}

J 题

24.9.22 凌晨更新题解

原题链接：HDU 1004

在一个字典内统计出现次数，
最后遍历找出出现次数最多的输出即可

Cpp Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int n;
    string bn;
    while (cin >> n) {
        if (n == 0) {
            return 0;
        }

        map<string, int> m;

        while (n > 0) {
            n--;
            cin >> bn;
            if (m.find(bn) == m.end()) {
                m[bn] = 1;
            } else {
                m[bn] += 1;
            }
        }

        string answer_name;
        int answer_times = 0;
        for (map<string, int>::iterator it = m.begin(); it != m.end(); it++) {
            if (it->second > answer_times) {
                answer_times = it->second;
                answer_name = it->first;
            }
        }

        cout << answer_name << endl;
    }
    return 0;
}

K 题

24.9.22 凌晨更新题解

原题链接：Codeforces 1722C

在一个字典中记录各单词出现次数，
最后再各自统计总分即可

Cpp Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int t;
    cin >> t;
    while (t > 0) {
        t--;
        int n_o;
        cin >> n_o;
        int n0 = n_o, n1 = n_o, n2 = n_o;
        string word0[1000], word1[1000], word2[1000];
        map<string, int> word_times;
        string word;
        while (n0 > 0) {
            n0--;
            cin >> word;
            word0[n0] = word;
            if (word_times.find(word) == word_times.end()) {
                word_times[word] = 1;
            } else {
                word_times[word] += 1;
            }
        }
        while (n1 > 0) {
            n1--;
            cin >> word;
            word1[n1] = word;
            if (word_times.find(word) == word_times.end()) {
                word_times[word] = 1;
            } else {
                word_times[word] += 1;
            }
        }
        while (n2 > 0) {
            n2--;
            cin >> word;
            word2[n2] = word;
            if (word_times.find(word) == word_times.end()) {
                word_times[word] = 1;
            } else {
                word_times[word] += 1;
            }
        }
        int rt0 = 0;
        for (string _word : word0) {
            if (word_times[_word] == 1) {
                rt0 += 3;
            } else if (word_times[_word] == 2) {
                rt0 += 1;
            }
        }

        int rt1 = 0;
        for (string _word : word1) {
            if (word_times[_word] == 1) {
                rt1 += 3;
            } else if (word_times[_word] == 2) {
                rt1 += 1;
            }
        }

        int rt2 = 0;
        for (string _word : word2) {
            if (word_times[_word] == 1) {
                rt2 += 3;
            } else if (word_times[_word] == 2) {
                rt2 += 1;
            }
        }

        printf("%d %d %d\n", rt0, rt1, rt2);
    }

    return 0;
}

L 题

24.9.22 凌晨更新 TL 代码
24.9.23 晚上更新 AC 代码

原题链接：Codeforces 1790D

题单的制作者今天（24.9.23）给题目加了个提示，在标题里标注这个题需要用字典（map）数据结构。

经过查询和测试后得知字典（map）数据结构遍历时，键（key）是从小到大的，我重新实现了代码。
代码分为两部分，第一部分是将数据读入字典，第二部分（从 int rt = 0; 开始）是数据处理部分。
最后字典存储的键代表这个娃的大小，对应的值表示还有多少个这样的娃没用掉。

数据处理的思路是：

遍历字典（根据键从小到大）
当检测到键对应的值大于 0（这里用 while 而不是 if，因为可以有多组套娃从同一个数开始），就召唤另一个迭代器（it_son），然后检查后继能否继续组成更长的套娃。
- 如果后继的键是前面的键+1 且键对应的值大于 0，说明可以组成更长的套娃。
如果用了这个娃，就对应值-1，表示用掉一个。
如果后继不满足组成更长的套娃的要求，那就退出循环并且最后统计结果的变量（rt）+1。

Cpp Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t > 0) {
        t--;
        int n;
        map<int, int> dict;
        cin >> n;

        while (n > 0) {
            n--;
            int _number;
            cin >> _number;
            dict[_number]++;
        }

        int rt = 0;

        for (auto it = dict.begin(); it != dict.end(); it++) {
            while (it->second > 0) {
                auto it_son = it;
                it_son++;
                int last_one = it->first;
                while (it_son->second > 0 && it_son->first - 1 == last_one) {
                    it_son->second--;
                    last_one = it_son->first;
                    it_son++;
                }
                rt++;
                it->second--;
            }
        }

        cout << rt << endl;
    }
    return 0;
}

这里折叠是代码是带 debug 的代码，将开头的 `bool debug = 1;` 改为 `bool debug = 0;` 即可 AC

Cpp Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool debug = 1;
#define dbg(x)                                                   \
    if (debug)                                                   \
        cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) \
             << NORMAL_FAINT << COLOR_RESET << endl;
const string COLOR_RESET = "\033[0m", BRIGHT_CYAN = "\033[1;36m",
             NORMAL_FAINT = "\033[0;2m";

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t > 0) {
        t--;
        int n;
        map<int, int> dict;
        cin >> n;

        while (n > 0) {
            n--;
            int _number;
            cin >> _number;
            dict[_number]++;
        }

        int rt = 0;

        for (auto it = dict.begin(); it != dict.end(); it++) {
            dbg(it->first);
            dbg(it->second);
            while (it->second > 0) {
                auto it_son = it;
                it_son++;
                int last_one = it->first;
                while (it_son->second > 0 && it_son->first - 1 == last_one) {
                    dbg(it_son->first);
                    dbg(it_son->second);
                    it_son->second--;
                    last_one = it_son->first;
                    it_son++;
                }
                rt++;
                dbg(rt);
                it->second--;
            }
        }

        cout << rt << endl;
    }
    return 0;
}

先前 TL 的题解

题解 Time limit exceeded on test 27

Cpp Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t > 0) {
        t--;
        int n;
        vector<int> v, st, temp_st;
        cin >> n;

        while (n > 0) {
            n--;
            int _number;
            cin >> _number;
            temp_st.push_back(_number);
        }
        sort(temp_st.begin(), temp_st.end());

        if (temp_st.front() == temp_st.back()) {
            cout << temp_st.size() << endl;
            continue;
        }

        int rt = 0;
        do {
            v = temp_st;
            temp_st.clear();

            for (int _number : v) {
                if (st.size() != 0) {
                    int _back = st.back();
                    if (_back == _number) {
                        temp_st.push_back(_number);
                    } else if (_back + 1 == _number) {
                        st.push_back(_number);
                    } else {
                        rt++;
                        st.clear();
                        st.push_back(_number);
                    }
                } else {
                    st.push_back(_number);
                }
            }

            if (st.size() != 0) {
                rt++;
                st.clear();
            }

        } while (temp_st.size() != 0);

        cout << rt << endl;
    }
    return 0;
}

M 题

24.9.22 下午更新 TL 代码
24.9.23 下午更新 AC 代码

原题链接：Codeforces 1800C2

虽然我不会实现最大堆，但是经过检索找到了一个 priority_queue 容器类，默认实现就是最大堆。我把原本 vector+sort 函数的模式改成 priority_queue 就成功 AC 了。

Cpp Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t > 0) {
        t--;
        int n;
        ll rt = 0;
        cin >> n;
        priority_queue<int> st;
        int _number;
        while (n > 0) {
            n--;
            cin >> _number;
            if (_number != 0) {
                st.push(_number);
            } else if (st.size() != 0) {
                rt += st.top();
                st.pop();
            }
        }
        cout << rt << endl;
    }

    return 0;
}

N 题

最基础的 10 转 2 进制

原题链接：HDU 2051

Cpp Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;

    while (cin >> n) {
        vector<int> v;
        if (n == 0) {
            v.push_back(0);
        }
        while (n > 0) {
            if (n % 2 == 0) {
                v.push_back(0);
                n /= 2;
            } else {
                v.push_back(1);
                n /= 2;
            }
        }

        while (v.size() != 0) {
            cout << v.back();
            v.pop_back();
        }
        cout << endl;
    }

    return 0;
}

网上冲浪的时候找到的另一种 Cpp 题解，巧妙的利用了递归，分享一下

#include <bits/stdc++.h>
using namespace std;

void D2B(int d) {
    if (d / 2) D2B(d / 2);
    cout << d % 2;
}

int main() {
    int n;

    while (cin >> n) {
        D2B(n);
        cout << endl;
    }

    return 0;
}

相关文章链接

前言

A 题

B 题

C 题

D 题

E 题

F 题

G 题

H 题

I 题

J 题

K 题

L 题

M 题

N 题