HHKB Programming Contest 2023(AtCoder Beginner Contest 327)
A. ab
解题思路:
模拟即可。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve()
{
int n;
cin >> n;
string s;
cin >> s;
for (int i = 0; i < n - 1; i++)
{
if (s[i] == 'a' && s[i + 1] == 'b')
{
puts("Yes");
return;
}
if (s[i] == 'b' && s[i + 1] == 'a')
{
puts("Yes");
return;
}
}
puts("No");
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
B. A^A
解题思路:
\(a^a\),我们发现\(a\)到达\(18\)的时候就会超过\(10^{18}\)了(可能更早)，暴力模拟即可。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll qmi(ll a, ll b)
{
ll res = 1;
while (b)
{
if (b & 1)
{
res = res * a;
}
a = a * a;
b >>= 1;
}
return res;
}
void solve()
{
ll b = 0;
cin >> b;
for (ll i = 1; i <= 20; i++)
{
if (qmi(i, i) == b)
{
cout << i << endl;
return;
}
}
cout << -1 << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
C. Number Place
解题思路:
按题意模拟即可。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve()
{
vector<vector<int>> g(12, vector<int>(12));
for (int i = 1; i <= 9; i++)
{
for (int j = 1; j <= 9; j++)
{
cin >> g[i][j];
}
}
for (int i = 1; i <= 9; i++)
{
set<int> s;
for (int j = 1; j <= 9; j++)
{
if (!s.count(g[i][j]))
{
s.insert(g[i][j]);
}
}
if (s.size() != 9)
{
// cout << i << endl;
cout << "No" << endl;
return;
}
}
for (int i = 1; i <= 9; i++)
{
set<int> s;
for (int j = 1; j <= 9; j++)
{
if (!s.count(g[j][i]))
{
s.insert(g[j][i]);
}
}
if (s.size() != 9)
{
// cout << i << endl;
cout << "No" << endl;
return;
}
}
int row = 0;
int col = 0;
for (int k = 0; k < 9; k++)
{
set<int> s;
row = k / 3;
col = k % 3;
for (int i = 1; i <= 3; i++)
{
int x = row * 3 + i;
for (int j = 1; j <= 3; j++)
{
int y = col * 3 + j;
if (!s.count(g[x][y]))
{
s.insert(g[x][y]);
}
}
}
if (s.size() != 9)
{
cout << "No" << endl;
return;
}
}
cout << "Yes" << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
D. Good Tuple Problem
解题思路:
扩展域并查集。
对于每个下标有\(0和1\)两个域.
举例：
若\(X_{A_i} \neq X_{B_i}\),那么一定有\(A_i\)的\(1\)域和\(B_i\)的\(0\)域合并，\(A_i\)的\(0\)域和\(B_i\)的\(1\)域合并。
遍历\(A,B\),合并所有\(01\)域，然后遍历判断所有下标，如果改下标\(01\)域在同一个集合中，那么不存在\(X\)。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve()
{
int n, m;
cin >> n >> m;
vector<int> a(m + 1), b(m + 1);
for (int i = 1; i <= m; i++)
{
cin >> a[i];
}
for (int i = 1; i <= m; i++)
{
cin >> b[i];
}
vector<int> p(2 * n + 10);
for (int i = 1; i <= 2 * n; i++)
{
p[i] = i;
}
auto find = [&](auto self, int x) -> int
{
if (x != p[x])
{
p[x] = self(self, p[x]);
}
return p[x];
};
auto merge = [&](int a, int b)
{
int pa = find(find, a);
int pb = find(find, b);
if (pa != pb)
{
p[pa] = pb;
}
};
for (int i = 1; i <= m; i++)
{
merge(a[i], b[i] + n);
merge(a[i] + n, b[i]);
}
for (int i = 1; i <= n; i++)
{
if (find(find, i) == find(find, i + n))
{
puts("No");
return;
}
}
puts("Yes");
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
E. Maximize Rating
解题思路:
\(f[i][j]:前i个竞赛中选取j个竞赛计算(\sum_{i= 1}^k(0.9)^{k-i}Q_i)的最大值\)。
\[f[i][j] = max(f[i-1][j-1]*0.9 + p[i],f[i-1][j]) \]其中两个式子分别对应这第\(i\)个竞赛选或不选：
如果选，那么取的第\(j\)个竞赛就是\(p[i]\),其余\(j-1\)个竞赛就是从前\(i-1\)个竞赛中取的，\(f[i-1][j-1] \to f[i][j]\)。
如果不选，第\(j\)个竞赛就是从前\(i-1\)个竞赛中取的,\(f[i-1][j] \to f[i][j]\)。
最后，枚举选多少个竞赛，带入公式，取最大值即可。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve()
{
int n;
cin >> n;
vector<int> p(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> p[i];
}
vector<vector<double>> f(n + 1, vector<double>(n + 1));
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= i; j++)
{
f[i][j] = max(f[i - 1][j - 1] * 0.9 + p[i], f[i - 1][j]);
}
}
double ans = -1e18;
for (int i = 1; i <= n; i++)
{
ans = max(f[n][i] / (10.0 * (1 - pow(0.9, i))) - (1200 / sqrt(i)), ans);
}
printf("%.15lf", ans);
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}