欢乐div. 4
A. Stair, Peak, or Neither?
输入 a, b, c
如果数字形成一个阶梯，输出“ STAIR”，如果数字形成一个峰值，输出“ PEAK”，否则输出“ NONE”(输出不带引号的字符串)。
#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
/image-20240401170521653.png)forces%20Round%20937%20(Div.%204)/image-20240401170521653.png)
思路：两个看成一个处理
#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 小时
#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 的数的乘积 $\left(1 \leq n \leq 10^5\right)$
思路，先 BFS 枚举 n 范围内的所有可能数，倒序枚举，如果为因子则循环除去，如果最后为 1 输出 YES 否则 NO
#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 的差别只有一个字符串
#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 的节点，构建深度最小的树
思路：
- 先通过 a 和 c 构造完全二叉树，然后其中可以插入任意 b，所以有a + 1 != c（不能构成完全二叉树） 就是-1
- 我们一个一个点添加，一层一层遍历，每个节点对当前层的接口数的贡献是-1。如果是节点2，对下一层接口数贡献为2，节点1贡献为1。如果当前层接口数用完了就下一层，初始值层0设为1
#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;
}