AtCoder Beginner Contest 336

A - Long Loong

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;

void solve()
{
    int n;
    cin >> n;
    string s;
    for (int i = 1; i <= n; i++)
    {
        s += 'o';
    }
    cout << "L" + s + "ng" << endl;
}

int main()
{
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

B - CTZ

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;

void solve()
{
    ll n;
    cin >> n;
    int cnt = 0;
    for (int i = 0; i < 63; i++)
    {
        if (n >> i & 1)
        {
            cout << cnt << endl;
            return;
        }
        cnt++;
    }
}

int main()
{
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

C - Even Digits

解题思路:

进制转换，看作5进制。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;

void solve()
{
    ll n;
    cin >> n;
    ll ans = 0;
    map<int, int> mp;
    mp[0] = 0;
    mp[1] = 2;
    mp[2] = 4;
    mp[3] = 6;
    mp[4] = 8;
    n--;
    while (n)
    {
        ans = ans * 10 + mp[n % 5];
        n /= 5;
    }
    ll res = 0;
    while (ans)
    {
        res = res * 10 + (ans % 10);
        ans /= 10;
    }
    cout << res << endl;
}

int main()
{
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

D - Pyramid

解题思路:

枚举每个点作为中心点，往左能取的最长长度和往右能取的最长长度中的最小值就是该位置的上界。

总体取最大值。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    vector<int> l(n + 10), r(n + 10);
    for (int i = 1; i <= n; i++)
    {
        l[i] = min(a[i], l[i - 1] + 1);
    }
    int ans = 0;
    for (int i = n; i; i--)
    {
        r[i] = min(a[i], r[i + 1] + 1);
        // cout << i << ' ' << l[i] << ' ' << r[i] << endl;
        ans = max(ans, min(l[i], r[i]));
    }
    cout << ans << endl;
}

int main()
{
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

E - Digit Sum Divisible

解题思路:

数位\(dp\)。

最多有\(14\)个数位，每个数位\(9\)种非零值，数位和共有\(14 \times 9 = 126\)中情况。

枚举模上每种数位和的情况，如果数位和等于当前枚举数位和并且数字模上数位和为\(0\)，那么就有一个答案。

\(f[i][j][k]:枚举到第i位时，数位总和为j时，当前数字mod上枚举的数位和为k时的答案数量。\)

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
vector<int> h(20);
ll f[16][200][200];

ll dfs(int u, int s, int cur, bool lim, int k)
{
    if (u == 0)
    {
        return (s == k && cur == 0);
    }
    if (!lim && f[u][s][cur] != -1)
    {
        return f[u][s][cur];
    }
    ll res = 0;
    int up = lim ? h[u] : 9;
    for (int i = 0; i <= up; i++)
    {
        res += dfs(u - 1, s + i, (cur * 10 + i) % k, (lim && (i == up)), k);
    }
    if (!lim)
    {
        f[u][s][cur] = res;
    }
    return res;
}

void solve()
{

    ll n;
    cin >> n;
    int len = 0;
    while (n)
    {
        h[++len] = n % 10;
        n /= 10;
    }
    int s = 9 * 14;
    ll ans = 0;
    for (int i = 1; i <= s; i++)
    {
        memset(f, -1, sizeof f);
        ans += dfs(len, 0, 0, true, i);
    }
    cout << ans << endl;
}

int main()
{
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

F - Rotation Puzzle

解题思路:

我们有四种旋转方法，那么就有四个转移方向。暴力枚举\(4^{20}\)。

我们发现，同一个操作连续进行两次，等于没有操作，所以\(4 \times3^{19}\)。

还是太大了，我们从前往后搜\(10\)步，再从后往前搜\(10\)步，\(2 \times 4 \times 3^{10} = 472392\)。

所以，双向宽搜。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;

struct node
{
    vector<vector<int>> a;
    int d = 0;
    int op;
};

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n + 1, vector<int>(m + 1)), f(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> g[i][j];
            f[i][j] = (i - 1) * m + j;
        }
    }
    auto deal = [&](vector<vector<int>> a, int x, int y)
    {
        vector<vector<int>> b;
        b = a;
        for (int i = 1; i <= n - 1; i++)
        {
            for (int j = 1; j <= m - 1; j++)
            {
                b[i + x][j + y] = a[n - i + x][m - j + y];
            }
        }
        return b;
    };
    queue<node> q;
    map<vector<vector<int>>, int> vis;
    q.push({g, 0, -1});
    vis[g] = 0;
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        // 从0走到10就是10步了
        if (t.d == 10)
        {
            continue;
        }
        for (int i = 0; i < 4; i++)
        {
            if (i == t.op)
            {
                continue;
            }
            // 传入的是初始矩阵和x，y轴的左上角偏移量
            auto v = deal(t.a, (i / 2), (i % 2));
            if (vis.find(v) == vis.end())
            {
                vis[v] = t.d + 1;
                q.push({v, t.d + 1, i});
            }
        }
    }
    queue<node> s;
    s.push({f, 0, -1});
    while (s.size())
    {
        auto t = s.front();
        s.pop();
        if (vis.find(t.a) != vis.end())
        {
            cout << t.d + vis[t.a] << endl;
            return;
        }
        if (t.d == 10)
        {
            continue;
        }
        for (int i = 0; i < 4; i++)
        {
            if (i == t.op)
            {
                continue;
            }
            auto v = deal(t.a, i / 2, i % 2);
            // 这里直接加入
            // 如果这里向上面一样判断，那么10步以上的答案都直接被过滤掉
            s.push({v, t.d + 1, i});
        }
    }
    puts("-1");
}

int main()
{
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}