HHKB Programming Contest 2023(AtCoder Beginner Contest 327) 赛后总结
又没来得及写题解。。。
赛时
A - ab
查找 ab
和 ba
,只要其中一者存在就行。
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
int main() {
cin >> n >> s;
cout << (s.find("ab") != string::npos || s.find("ba") != string::npos ? "Yes" : "No");
return 0;
}
B - A^A
由于范围比较小,考虑枚举,注意从 \(1\) 开始。
#include <bits/stdc++.h>
using namespace std;
long long b;
long long poww(int a, int b) {
long long ans = 1;
for (int i = 1; i <= b; ans *= a, i++) {
}
return ans;
}
int main() {
cin >> b;
for (int i = 1; i <= 15; i++) {
long long s = 1ll * poww(i, i);
if (s == b) {
cout << i;
return 0;
}
}
cout << -1;
return 0;
}
C - Number Place
照题意模拟。
#include <bits/stdc++.h>
using namespace std;
const int pos[9][9][2] = {
{{0, 0}, {0, 1}, {0, 2}, {1, 0}, {1, 1}, {1, 2}, {2, 0}, {2, 1}, {2, 2}},
{{0, 3}, {0, 4}, {0, 5}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}},
{{0, 6}, {0, 7}, {0, 8}, {1, 6}, {1, 7}, {1, 8}, {2, 6}, {2, 7}, {2, 8}},
{{3, 0}, {3, 1}, {3, 2}, {4, 0}, {4, 1}, {4, 2}, {5, 0}, {5, 1}, {5, 2}},
{{3, 3}, {3, 4}, {3, 5}, {4, 3}, {4, 4}, {4, 5}, {5, 3}, {5, 4}, {5, 5}},
{{3, 6}, {3, 7}, {3, 8}, {4, 6}, {4, 7}, {4, 8}, {5, 6}, {5, 7}, {5, 8}},
{{6, 0}, {6, 1}, {6, 2}, {7, 0}, {7, 1}, {7, 2}, {8, 0}, {8, 1}, {8, 2}},
{{6, 3}, {6, 4}, {6, 5}, {7, 3}, {7, 4}, {7, 5}, {8, 3}, {8, 4}, {8, 5}},
{{6, 6}, {6, 7}, {6, 8}, {7, 6}, {7, 7}, {7, 8}, {8, 6}, {8, 7}, {8, 8}}
};
int a[9][9];
int cnt[10];
bool check() {
for (int i = 0; i < 9; i++) {
fill(cnt + 1, cnt + 9 + 1, 0);
for (int j = 0; j < 9; j++) {
cnt[a[i][j]]++;
}
bool flag = 1;
for (int j = 1; j <= 9; j++) {
if (cnt[j] != 1) {
flag = 0;
break;
}
}
if (!flag) {
// cout << "break point:1\n";
return 0;
}
}
for (int i = 0; i < 9; i++) {
fill(cnt + 1, cnt + 9 + 1, 0);
for (int j = 0; j < 9; j++) {
cnt[a[j][i]]++;
}
bool flag = 1;
for (int j = 1; j <= 9; j++) {
if (cnt[j] != 1) {
flag = 0;
break;
}
}
if (!flag) {
// cout << "break point:2\n";
return 0;
}
}
for (int i = 0; i < 9; i++) {
fill(cnt + 1, cnt + 9 + 1, 0);
for (int j = 0; j < 9; j++) {
cnt[a[pos[i][j][0]][pos[i][j][1]]]++;
}
bool flag = 1;
for (int j = 1; j <= 9; j++) {
if (cnt[j] != 1) {
flag = 0;
break;
}
}
if (!flag) {
// cout << "break point:3\n";
return 0;
}
}
return 1;
}
int main() {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
cin >> a[i][j];
}
}
cout << (check() ? "Yes" : "No");
return 0;
}
赛后
D - Good Tuple Problem
二分图 01
染色。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
int n, m, c[MAXN], a[MAXN], b[MAXN], flag;
bool vis[MAXN];
vector<int> g[MAXN];
void dfs(int x, int y) {
if (vis[x]) {
if (c[x] != y) {
flag = 1;
}
return;
}
vis[x] = 1, c[x] = y;
for (int i = 0; i < g[x].size(); i++) {
dfs(g[x][i], !y);
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> a[i];
}
for (int i = 1; i <= m; i++) {
cin >> b[i];
}
for (int i = 1; i <= m; i++) {
g[a[i]].push_back(b[i]), g[b[i]].push_back(a[i]);
}
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
dfs(i, 0);
}
}
cout << (flag ? "No" : "Yes");
return 0;
}
E - Maximize Rating
水 DP,赛时竟然没有写出来,我太蒻了。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e3 + 10, INF = 6e3;
int n, a[MAXN];
double ans = -INF, dp[MAXN][MAXN];
double getSum(int x) {
double sum = 0;
for (int i = 0; i < x; i++) {
sum += pow(0.9, i);
}
return sum;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = n; i; i--) {
for (int j = 1; j <= n; j++) {
dp[i][j] = dp[i + 1][j], dp[i][j] = max(dp[i][j], dp[i + 1][j - 1] + pow(0.9, j - 1) * a[i]);
}
}
for (int i = 1; i <= n; i++) {
ans = max(ans, dp[1][i] / getSum(i) - 1200 / sqrt(i));
}
cout << fixed << setprecision(6) << ans;
return 0;
}
- Contest Programming Beginner AtCoder HHKBcontest programming beginner atcoder contest programming securities beginner contest programming beginner registry contest programming christmas beginner contest programming beginner keyence contest programming beginner systems beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335