bachzart's Blog
0%

PAT_520_争霸赛

Posted on In ,
Symbols count in article: 5.8k Reading time ≈ 8 mins.

昨天不知道在哪里看到的 PAT 上的活动广告了，想着没有事情，就做做看吧

520-1 吾眸唯卿

水题，没啥说的。

Code

1
2
3
4
5
6
7
8
#include <iostream>

int main() {

    std::cout << "520 stars in the sky, but only one shines bright in my eye." << std::endl;

    return 0;
}

520-2 恋爱纪念日

还是水题。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>

using std::cout;

int main() {
    int stage, budgets;
    std::cin >> stage >> budgets;

    if (stage == 1) {
        cout << (budgets > 1000 ? "zhu guang wan can" : "he ka fei") << std::endl;
    } else if (stage == 2) {
        cout << (budgets > 10000 ? "hao hua ying yuan VIP bao chang" : "gong yuan ye can") << std::endl;
    } else if (stage == 3) {
        cout << (budgets > 200 ? "chi huo guo" : "shai tai yang") << std::endl;
    }

    return 0;
}

PS：这是完事儿后精简了一下的代码。

520-3 恋爱中的智商

依然水题呢，注意输入数据没有必要全部保存，可以边输入边处理。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <vector>
using namespace std;

int main() {

    int n, num;
    vector<int> ans;
    
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> num;
        if (num == 0) ans.push_back(i);
    }

    for (int i = 0; i < ans.size(); ++i) {
        if (i > 0) cout << ' ';
        cout << ans[i];
    }

    cout << endl << ans.size() << endl;

    return 0;
}

520-4 天作之和

Analysis

这里要动点脑子了，条件是要求 $ (m + 1) / n + (n + 1) / m $ 正好是一个整数，于是：
$$
\begin{align}
\frac{m + 1}{n}+ \frac{n + 1}{m} &= \frac{m(m + 1) + n(n + 1)}{mn} \\
&= \frac{m^2 + n^2 + m + n}{mn} \\
&= \frac{(m + n)^2 - 2mn + m + n}{mn} \\
&= \frac{(m + n)(m + n + 1) - 2mn}{mn} \\
\end{align}
$$

令 $s = m + n$，得到：
$$
\begin{align*}
\frac{(m + n)(m + n + 1) - 2mn}{mn} &= \frac{s(s + 1) - 2mn}{mn} \tag{5}
\end{align*}
$$

此时，只需要考虑 $s(s + 1)$ 能否被 $mn$ 整除即可。但实际上，这个题只需要得到第 2 个式子就行了（实际提交的也是这个版本），换句话说，只要能把“是否是整数”转化为“能否被整除”，这道题基本就结束了，额外再注意下溢出就行了。

Code

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 <iostream>
using namespace std;

int main() {

    int a, b;
    cin >> a >> b;

    bool flag = false;
    int ans = 0;
    for (int s = b; s >= a; --s) {
        for (int m = 1; m < s; ++m) {
            int n = s - m;
            long long m1 = m, n1 = n;
            if ((m1 * (m1 + 1) + n1 * (n1 + 1)) % (n1 * m1) == 0) {
                cout << s << endl;
                return 0;
            }
        }
    }
    /*
    other method: 
    for (int s = n; s >= a; --s) {
        for (int m = 1; m < s; ++m) {
            if (s * (s + 1) % (m * (s - m)) == 0) {
                cout << s << endl;
                return 0;
            }
        }
    }
    */

    cout << 0 << endl;

    return 0;
}

520-5 情侣号

又来个水题。

Code

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
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int main() {

    int p, n;
    cin >> p >> n;
    int pos = p - 1;

    string num1, num2;
    while(n--) {
        cin >> num1 >> num2;

        bool same = true;
        for (int i = 0; i < 11; ++i) {
            if (i != pos && num1[i] != num2[i]) same = false;
        }

        cout << same << endl;
    }

    return 0;
}

520-6 单身狗的派对

Analysis

一眼前缀和，提前计算好前缀和，然后再计算结果即可，注意下溢出问题即可。

Code

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 <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <climits>
using namespace std;

int main() {

    int L, n;
    cin >> L >> n;

    vector<int> v(n + 1);
    vector<long long> pre(n + 1, 0);

    for (int i = 1; i <= n; ++i) {
        cin >> v[i];
        pre[i] = pre[i - 1] + v[i];
    }

    long long min_sum = INT_MAX;
    int min_index = 1;

    for (int i = 1; i <= (n - L + 1); ++i) {
        long long tmp = pre[i + L - 1] - pre[i - 1];

        if (min_sum > tmp) {
            min_index = i;
            min_sum = tmp;
        }

    }

    cout << min_index << ' ' << min_sum << endl;

    return 0;
}

520-7 爱的标记

Analysis

不算难，但是题目描述有一定的混淆性，容易误导人。

Code

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
#include <iostream>
#include <string>
using namespace std;

int main() {
    string text;
    char start, end;
    
    getline(cin, text);
    cin >> start >> end;
    
    string result = "";
    int i = 0;
    
    while (i < text.length()) {
        if (text[i] == start) {
            int j = i + 1;
            while (j < text.length()) {
                if (text[j] == end) {
                    string content = text.substr(i + 1, j - i - 1);
                    if (!content.empty()) {
                        result += content;
                    }
                    i = j + 1;
                    break;
                }
                j++;
            }
            if (j >= text.length()) {
                i++;
            }
        } else {
            i++;
        }
    }

    cout << result << endl;
    
    return 0;
}

520-8 丘比特之箭

Analysis

最有意思的一道题，也不是很难，是个比较常见的排序题。不过这个题，其实对一些情况说的不是很清楚，但是 case 好像比较弱，第一次提交超时了，排序函数忘加引用了，后面加上了就 A 掉了。

Code

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 <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

struct Couple {
    string u, v;
    int idx_uv;
    int status;
    Couple(string _u, string _v, int s): u(_u), v(_v), idx_uv(s * 2), status(0) {}
    void print() {
        cout << u << ' ' << v << ' ' << idx_uv << endl;
    }
};

int main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    unordered_map<string, int> name2idx;
    vector<Couple> v;
    int v_idx = 0;
    for (int i = 0; i < n; ++i) {
        string name1, name2;
        int idxuv;
        cin >> name1 >> name2 >> idxuv;
        v.emplace_back(name1, name2, idxuv);
        name2idx[name1] = v_idx;
        name2idx[name2] = v_idx;

        ++v_idx;
    }
    
    for (int i = 0; i < k; ++i) {
        string name;
        int color;
        cin >> name >> color;
        auto it = name2idx.find(name);
        if (it == name2idx.end()) continue;
        auto& cp = v[it->second];
        if (color == 1) {
            cp.idx_uv += 520;
            cp.status += 1;
        } else {
            cp.idx_uv -= 520;
            cp.status = -2;
        }
    }

    sort(v.begin(), v.end(), [](const Couple& c1, const Couple& c2) {
        return c1.idx_uv != c2.idx_uv ? c1.idx_uv > c2.idx_uv : c1.u < c2.u;
    });

    for (int i = 0, cnt = 0; cnt < 3 && i < v.size(); ++i) {
        if (v[i].status == 2) {
            v[i].print();
            ++cnt;
        }
    }

    sort(v.begin(), v.end(), [](const Couple& c1, const Couple& c2) {
        return c1.idx_uv != c2.idx_uv ? c1.idx_uv < c2.idx_uv : c1.u < c2.u;
    });

    for (int i = 0, cnt = 0; cnt < 3 && i < v.size(); ++i) {
        if (v[i].status < 0) {
            v[i].print();
            ++cnt;
        }
    }

    return 0;
}
Buy me a coffee ? :)