比赛链接：https://pintia.cn/market/item/1287964475579875328

7-1 对称日

题解

模拟，注意年月日不足位在前面补零。

代码

#include <bits/stdc++.h>

using namespace std;

map<string, string> mp{

    {"Jan", "1"},

    {"Feb", "2"},

    {"Mar", "3"},

    {"Apr", "4"},

    {"May", "5"},

    {"Jun", "6"},

    {"Jul", "7"},

    {"Aug", "8"},

    {"Sep", "9"},

    {"Oct", "10"},

    {"Nov", "11"},

    {"Dec", "12"}

};

bool is_palindrome(const string &s) {

    string t(s);

    reverse(t.begin(), t.end());

    return s == t;

}

void solve() {

    string m, d, y; cin >> m >> d >> y;

    d.pop_back();

    if (y.size() < 4) y = string(4 - y.size(), '0') + y;

    if (m.size() < 2) m = '0' + m;

    if (d.size() < 2) d = '0' + d;

    string s = y + mp[m] + d;

    cout << (is_palindrome(s) ? 'Y' : 'N') << ' ' << s << "\n";

}

int main() {

    int t; cin >> t;

    while (t--) solve();

}

7-2 超标区间

题解

维护一个元素超过阈值的区间，然后以小于阈值的数为分割点。

代码

#include <bits/stdc++.h>

using namespace std;

int main() {

    int n, t; cin >> n >> t;

    int a[n + 1] = {};

    for (int i = 0; i < n; ++i) {

        cin >> a[i];

    }

    vector<pair<int, int>> res;

    int l = 0, r = 0;

    for (int i = 0; i <= n; ++i) {

        if (a[i] > t) {

            if (a[r] > t) {

                r = i;

            } else {

                l = i;

                r = i;

            }

        } else {

            if (a[r] > t) {

                res.emplace_back(l, r);

            }

            l = i;

            r = i;

        }

    }

    if (!res.empty()) {

        for (auto pr : res)

            cout << "[" << pr.first << ", " << pr.second << "]" << "\n";

    } else {

        cout << *max_element(a, a + n) << "\n";

    }

}

7-3 钱串子的加法

题解

将两个数去除前导零后统一为同一长度，模拟相加即可，注意进位。

Tips

这题数据似乎卡得不是很严，像去除前导零和计算两个数的和如果用 $O_{(n)}$ 的 s.erase(s.begin()) 和 ans = ch + ans 即使总时间复杂度会达到 $O_{(n^2)}$ 也不会超时。只会比下面 $O_{(n)}$ 的代码慢十倍左右。

代码

#include <bits/stdc++.h>

using namespace std;

map<char, int> mp1;

map<int, char> mp2;

void init() {

    int num = 0;

    for (char c : string("0123456789abcdefghijklmnopqrst")) mp1[c] = num++;

    for (auto pr : mp1) mp2[pr.second] = pr.first;

}

void del_lead_zero(string &s) {

    reverse(s.begin(), s.end());

    while (s.size() > 1 and s.back() == '0') s.pop_back();

    reverse(s.begin(), s.end());

}

void sum(string &s1, string &s2) {

    del_lead_zero(s1);

    del_lead_zero(s2);

    if (s1.size() < s2.size()) {

        swap(s1, s2);

    }

    s2 = string(s1.size() - s2.size(), '0') + s2;

    bool carry = false;

    for (int i = s1.size() - 1; i >= 0; --i) {

        int sum = mp1[s1[i]] + mp1[s2[i]] + carry;

        s1[i] = mp2[sum % 30];

        carry = (sum >= 30);

    }

    if (carry) s1 = "1" + s1;

}

int main() {

    init();

    string s1, s2; cin >> s1 >> s2;

    sum(s1, s2);

    cout << s1 << "\n";

}

7-4 全素日

题解

模拟。

代码

#include <bits/stdc++.h>

using namespace std;

bool isprime(int n) {

    if (n <= 1) return false;

    for (int i = 2; i * i <= n; ++i)

        if (n % i == 0) return false;

    return true;

}

int main() {

    string s; cin >> s;

    bool all_prime = true;

    for (int i = 0; i < s.size(); ++i) {

        string t = s.substr(i);

        bool is_prime = isprime(stoi(t));

        if (not is_prime) all_prime = false;

        cout << t << ' ' << (is ? "Yes" : "No") << "\n";

    }

    if (all_prime) cout << "All Prime!" << "\n";

}

7-5 裁判机

题解

因为时间复杂度为 $O_{(n^2)}$ 且最多的情况有 $10^4$ 个数，所以不能再用 map 或 set 这类每次操作时间复杂度为 $O_{(log_n)}$ 的容器了，可以使用 $O_{(1)}$ 的散列（数组映射）。

代码

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 1e5 + 100;

bool appear[N], sub[N];

int main() {

    int t1, t2; cin >> t1 >> t2;

    appear[t1] = appear[t2] = true;

    sub[abs(t1 - t2)] = true;

    int n, m; cin >> n >> m;

    int a[n][m] = {};

    for (int i = 0; i < n; ++i) {

        for (int j = 0; j < m; ++j) {

            cin >> a[i][j];

        }

    }

    vector<int> res = {t1, t2};

    bool out[n] = {};

    for (int j = 0; j < m; ++j) {

        for (int i = 0; i < n; ++i) {

            if (out[i]) continue;

            if (appear[a[i][j]] or !sub[a[i][j]]) {

                cout << "Round #" << j + 1 << ": " << i + 1 << " is out.\n";

                out[i] = true;

                continue;

            }

            for (auto ele : res) sub[abs(a[i][j] - ele)] = true;

            res.push_back(a[i][j]);

            appear[a[i][j]] = true;

        }

    }

    if (find(out, out + n, false) - out == n) {

        cout << "No winner.";

    } else {

        cout << "Winner(s):";

        for (int i = 0; i < n; ++i)

            if (not out[i]) cout << ' ' << i + 1;

    }

}

巴特西

PAT（乙级）2020年春季考试