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;
}
