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 的数的乘积 (1n105)\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;
}