Codeforces Round 937 (Div. 4)

本文主要是介绍Codeforces Round 937 (Div. 4)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Codeforces Round 937 (Div. 4)

Codeforces Round 937 (Div. 4)

A. Stair, Peak, or Neither?

题意：略

思路：照着题模拟；

AC code：

void solve() {int a, b, c; cin >> a >> b >> c;if (a < b) {if (b < c) cout << "STAIR" << endl;else if (b > c) cout << "PEAK" << endl;else cout << "NONE" << endl;} else {cout << "NONE" << endl;}
}

B. Upscaling

题意：略

思路：可以看出我们需要输出的行字符串只有两种可能，预处理出来这两种可能，两两交替输出即可；

AC code：

void solve() {cin >> n;string s = "", t = "";int pos = 1;for (int i = 0; i < n; i ++) {if (pos) s += "##";else s += "..";pos ^= 1;}pos = 1;for (int i = 0; i < n; i ++) {if(pos) t += "..";else t += "##";pos ^= 1;}pos = 1;for (int i = 0; i < n; i ++) {if (pos) cout << s << endl << s << endl;else cout << t << endl << t << endl;pos ^= 1;}
}

C. Clock Conversion

题意：把24小时制时间转换成12小时制时间；

思路：样例给的过于优秀，顺着模拟即可，需要判断的是大于十二的以及00时刻，且注意12:00为PM；

AC code：

void solve() {int pos = 1;string s; cin >> s;if (s == "00:00") {cout << "12:00 AM" << endl;return;}int x = (s[0] - '0') * 10 + (s[1] - '0');if (x >= 12) x -= 12, pos = 0;if (x == 0) x = 12;if (x < 10) cout << '0' << x << ':';else cout << x << ':';for (int i = 3; i < s.size(); i ++) cout << s[i];if (pos) cout << " AM";else cout << " PM";cout << endl;
}

D. Product of Binary Decimals

题意：判断一个十进制正整数是否可以变成一些只有0和1组成的十进制正整数的乘积；

思路：DP，但是有一种很暴力的做法；

预处理出所有可能的五位数以内的01组成的十进制正整数，然后你会发现就32个数，暴力枚举四个数的组合乘积，然后用set或者map记录一下出现过的数，最后find查找即可。

AC code：

vector<int> v;
map<int, bool> mp;void pr() {for (int i = 0; i < 2; i++) {for (int j = 0; j < 2; j++) {for (int k = 0; k < 2; k++) {for (int l = 0; l < 2; l++) {for (int m = 0; m < 2; m++) {int num = i * 10000 + j * 1000 + k * 100 + l * 10 + m;v.push_back(num);}}}}}for (int i : v) {for (int j : v) {for (int k : v) {for (int l : v) {int num = i * j * k * l;mp[num] = true;}}}}
}void solve() {cin >> n;cout << (mp.find(n) != mp.end() ? "YES" : "NO") << endl;
}signed main() {fast();pr();T = 1;cin >> T;while (T --) {solve();}return 0;
}

E. Nearly Shortest Repeating Substring

题意：给出字符串s，找出最短的可以首尾连接成为s的字符串k，最多允许一个位置字符不相同；

思路：枚举出当前字符串所有的因子，然后找当前因子长度连接出的子串是否符合题意，取最短即可，注意首尾子串都有可能nlogn；

AC code：

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define db double
#define pb push_back
#define fast() ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;typedef long long LL;
typedef pair<char, int> PCI;
typedef pair<int, int> PII;
const int N = 2e5+10, M = 2001;
const int INF = 0x3f3f3f3f3f, MOD = 998244353;
int T, n;void solve() {cin >> n;string s; cin >> s;int ans = n;for (int i = 1; i <= n / i; i ++) {if (n % i == 0) {string t = s.substr(0, i);string now = "";while (now.size() < s.size()) now += t;if (s == now) {ans = min(ans, i);}int cnt = 0;for (int t = 0; t < n; t ++) {if (s[t] != now[t]) cnt ++;if (cnt > 1) break;}if (cnt == 1) {ans = min(ans, i);}if (n / i != i) {int j = n / i;t = s.substr(0, j);now = "";while (now.size() < s.size()) now += t;if (s == now) {ans = min(ans, j);}int cnt = 0;for (int t = 0; t < n; t ++) {if (s[t] != now[t]) cnt ++;if (cnt > 1) break;}if (cnt == 1) {ans = min(ans, j);}}}}reverse(s.begin(), s.end());for (int i = 1; i <= n / i; i ++) {if (n % i == 0) {string t = s.substr(0, i);string now = "";while (now.size() < s.size()) now += t;if (s == now) {ans = min(ans, i);}int cnt = 0;for (int t = 0; t < n; t ++) {if (s[t] != now[t]) cnt ++;if (cnt > 1) break;}if (cnt == 1) {ans = min(ans, i);}if (n / i != i) {int j = n / i;t = s.substr(0, j);now = "";while (now.size() < s.size()) now += t;if (s == now) {ans = min(ans, j);}int cnt = 0;for (int t = 0; t < n; t ++) {if (s[t] != now[t]) cnt ++;if (cnt > 1) break;}if (cnt == 1) {ans = min(ans, j);}}}}cout << ans << endl;
}signed main() {fast();T = 1;cin >> T;while (T --) {solve();}return 0;
}

这篇关于Codeforces Round 937 (Div. 4)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---