Codeforces Round 937 (Div. 4)

, ,

欢乐div. 4

A. Stair, Peak, or Neither?

输入 a, b, c
如果数字形成一个阶梯，输出“ STAIR”，如果数字形成一个峰值，输出“ PEAK”，否则输出“ NONE”(输出不带引号的字符串)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>  
  
using namespace std;  
typedef long long ll;  
const int N = 2e6 + 10;  
ll t;  
int main() {  
    cin >> t;  
    ll a, b ,c;  
    while (t--) {  
        cin >> a >> b >> c;  
        if (a < b && b < c) {  
            cout << "STAIR" << endl;  
        } else if (a < b && b > c) {  
            cout << "PEAK" << endl;  
        } else {  
            cout << "NONE" << endl;  
        }    }    return 0;  
}

B. Upscaling


思路：两个看成一个处理

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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 2e6 + 10;
ll t, n;
int main() {
    cin >> t;
    ll a, b ,c;
    while (t--) {
        cin >> n;
        vector<string> ans(n * 2, string(n * 2, '.'));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if ((i + j) % 2 == 0) {
                    for (int k = 0; k < 2; k++) {
                        for (int l = 0; l < 2; l++) {
                            ans[i * 2 + k][j * 2 + l] = '#';
                        }
                    }
                }
            }
        }
        for (auto it : ans) {
            cout << it << endl;
        }
    }
    return 0;
}

C. Clock Conversion

24 小时制转 12 小时

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;  
typedef long long ll;  
const int N = 2e6 + 10;  
ll t, n;  
  
string convert24HourTo12Hour(const string& time24) {  
    // Extract hours and minutes from the input string  
    int hour = stoi(time24.substr(0, 2));  
    string minutes = time24.substr(3);  
  
    // Determine the period (AM/PM)  
    string period = hour >= 12 ? "PM" : "AM";  
  
    // Convert hour to 12-hour format  
    hour = hour % 12;  
    if (hour == 0) hour = 12; // Handle midnight and noon cases  
  
    // Format the hour to ensure it has two digits    string hourStr = (hour < 10) ? "0" + to_string(hour) : to_string(hour);  
  
    // Construct the final string  
    return hourStr + ":" + minutes + " " + period;  
}  
int main() {  
    cin >> t;  
    ll a, b ,c;  
    while (t--) {  
        string inputTime;  
//        cout << "Enter time in 24-hour format (HH:MM): ";  
        cin >> inputTime;  
  
        string convertedTime = convert24HourTo12Hour(inputTime);  
        cout << convertedTime << endl;  
  
    }    return 0;  
}

D. Product of Binary Decimals

只包换 1 和 0 的数的乘积 (1≤n≤105)\left(1 \leq n \leq 10^5\right)
思路，先 BFS 枚举 n 范围内的所有可能数，倒序枚举，如果为因子则循环除去，如果最后为 1 输出 YES 否则 NO

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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 2e6 + 10;
ll t, n;
#define debug(x) cout << #x << " = " << x << endl

vector<long long> generateBinaryDecimals(int n) {
    queue<long long> q;
    q.push(1); // Start with 1 as the first binary decimal number
    vector<long long> result;

    while (!q.empty()) {
        long long num = q.front();
        q.pop();

        // Check if the current number is less than or equal to n
        if (num <= n) {
            result.push_back(num);

            // Generate the next numbers by appending 0 and 1
            q.push(num * 10);
            q.push(num * 10 + 1);
        }
    }

    return result;
}

int main() {
    vector<ll> tmp = generateBinaryDecimals(100000);
//    for (auto it : tmp) {
//        cout << it << endl;
//    }
    cin >> t;
    // remove 1
    tmp.erase(tmp.begin());
    sort(tmp.begin(), tmp.end(), greater<ll>());
    ll a, b, c;
    while (t--) {
        cin >> n;
        // then
        for (auto it: tmp) {
            while (n % it == 0) {
                n /= it;
            }
        }
        if (n == 1) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

/**
1
10
11
100
101
110
111
1000
1001
1010
1011
1100
1101
1110
1111
10000
10001
10010
10011
10100
10101
10110
10111
11000
11001
11010
11011
11100
11101
11110
11111
100000
*/

E. Nearly Shortest Repeating Substring

给定一个长度为 n 的 string，取一个子串长短 k
要求 n % k == 0
将 n / k 个子串拼接后与 string 至多只有一个字符不同

思路：
枚举子串长度，map 记录，如果可行需保证 map 的 size <= 2，
如果为 1 则说明可以
如果为 2 必须保证有一个 value 为 1 且 key 1 和 key 2 的差别只有一个字符串

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>

using namespace std;
typedef long long ll;
const int N = 2e6 + 10;
ll t, n;
#define debug(x) cout << #x << " = " << x << endl
bool check(string s, int mid) {
    // check if have a substring of length mid
    int n = s.size();
    unordered_map<string, int> mp;
    for (int i = 0; i <= n - mid; i+=mid) {
        string sub = s.substr(i, mid);
        mp[sub]++;
        if (mp.size() > 2) {
            return false;
        }
    }

    if (mp.size() == 1) {
        return true;
    }
    if (mp.size() == 2) {
        // must have one value == 1
        bool f1 = 0;
        string s11 = "";
        int c = 0;
        for (auto it : mp) {
            if (it.second == 1) {
                f1 = 1;
            }
            if (s11 == "") {
                s11 = it.first;
            } else {
                for (int i = 0; i < s11.size(); i++) {
                    if (s11[i] != it.first[i]) {
                        c++;
                    }
                }
            }
        }
        if (f1 && c <= 1) {
            return true;
        } else {
            return false;
        }
    }
    return false;
}

int main() {

    ll a, b ,c;
    cin >> t;
    while (t--) {
        string s;
        cin >> n;
        cin >> s;
        // a string len n
        // find min len of string k
        // find the number n % k == 0
        vector<int> v;
        for (int i = 1; i <= n; i++) {
            if (n % i == 0) {
                v.push_back(i);
            }
        }
        ll ans = n;
        for (auto it : v) {
            if (check(s, it)) {
                ans = it;
                break;
            }
        }
        cout << ans << endl;

    }
    return 0;
}

F. 0, 1, 2, Tree!（补题）

给点a, b, c 个度分别为 2，1，0 的节点，构建深度最小的树

思路：

  1. 先通过 a 和 c 构造完全二叉树，然后其中可以插入任意 b，所以有a + 1 != c（不能构成完全二叉树） 就是-1
  2. 我们一个一个点添加，一层一层遍历，每个节点对当前层的接口数的贡献是-1。如果是节点2，对下一层接口数贡献为2，节点1贡献为1。如果当前层接口数用完了就下一层，初始值层0设为1
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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
ll t, n;
ll v[N];
#define debug(x) cout << #x << " = " << x << endl

int main() {

    ll a, b, c;
    cin >> t;
    while (t--) {
        cin >> a >> b >> c;
        // tree min height
        // a node have 2 son
        // b node have 1 son
        // c node have 0 son
        // a b c <= 10^5
        // a + b + c = 3 * 10^5

        ll tmp = 0;
        memset(v, 0, sizeof v);
        if (a + 1 != c) {
            cout << -1 << endl;
            continue;
        } else {
            v[0] = 1;
            ll h = 0;
            int l = a + b + c;
            for (int i = 1; i <= l; i++) {
                if (!v[h]) {
                    h++;
                }
                v[h]--;
                if (a) {
                    a--;
                    v[h + 1] += 2;
                } else if(b) {
                    b--;
                    v[h + 1]++;
                } else if(c) {
                    c--;
                }
            }
            cout << h << endl;
        }
    }
    return 0;
}