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