A - Long Loong

模拟。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int x;
    cin >> x;
    cout << "L";
    while (x--)
        cout << "o";
    cout << "ng" << endl;
    return 0;
}

B - CTZ

对自带函数的运用。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int x;
    cin >> x;
    cout << __builtin_ctz(x) << endl;
    return 0;
}

C - Even Digits

转五进制，重载一下每一位具体数字。主播在 CF1811E Living Sequence 中做过类似 trick。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
string c = "02468";
void f(ll x, ll m)
{
    if (x / m)
        f(x / m, m);
    cout << c[x % m];
}
int main()
{
    ll n;
    cin >> n;
    f(n - 1, 5);
    return 0;
}

D - Pyramid

扫两遍看一下自己最大能装到多大。

#include <bits/stdc++.h>
using namespace std;
template <typename T>
void chkmx(T &x, T y) { x = max(x, y); }
int n;
int a[200020];
int pre[200020];
int suf[200020];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        pre[i] = min(pre[i - 1] + 1, a[i]);
    for (int i = n; i >= 1; i--)
        suf[i] = min(suf[i + 1] + 1, a[i]);
    int ans = 0;
    for (int i = 1; i <= n; i++)
        chkmx(ans, min(pre[i], suf[i]));
    cout << ans << endl;
    return 0;
}

E - Digit Sum Divisible

原题 P4127 [AHOI2009] 同类分布，数位 DP。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f[20][200][200];
ll len;
ll a[20];
ll n;
ll p;
ll dp(ll pos, ll sum, ll st, int lim)
{
    if (pos > len && sum == 0)
        return 0;
    if (pos > len)
        return st == 0 && sum == p ? 1 : 0;
    ll &t = f[pos][sum][st];
    if (!lim && ~t)
        return t;
    ll ret = 0;
    ll res = lim ? a[len - pos + 1] : 9;
    for (int i = 0; i <= res; i++)
        ret += dp(pos + 1, sum + i, (10LL * st + i) % p, i == res && lim);
    return lim ? ret : t = ret;
}
ll calc(ll x)
{
    len = 0;
    while (x)
        a[++len] = x % 10, x /= 10;
    ll ret = 0;
    for (p = 1; p <= 9 * len; p++)
    {
        memset(f, -1, sizeof(f));
        ret += dp(1, 0, 0, 1);
    }
    return ret;
}
int main()
{
    cin >> n;
    cout << calc(n) << endl;
    return 0;
}

F - Rotation Puzzle

发现每一次只能选择 $4$ 个位置，直接搜复杂度 $4^{20}$ 显然不可行。考虑折半搜索，从头开始搜 $4^{10}$ 个从尾开始搜 $4^{10}$ 个然后合并起来。

#include <bits/stdc++.h>
using namespace std;
typedef vector<vector<int>> mtx;
template <typename T>
void chkmn(T &x, T y) { x = min(x, y); }
mtx a, b;
int n, m;
void prt(mtx &a)
{
    for (auto i : a)
    {
        for (int j : i)
            cout << j << ' ';
        cout << '\n';
    }
    cout << '\n';
}
void RSZ(mtx &a)
{
    a.resize(n);
    for (int i = 0; i < n; i++)
        a[i].resize(m);
}
bool in(int x, int y) { return 0 <= x && x < n && 0 <= y && y < m; }
void RRT(mtx &a, int x, int y)
{
    mtx b;
    RSZ(b);
    b = a;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (x <= i && i <= n + x - 2 && y <= j && j <= m + y - 2)
                a[i][j] = b[n + x - 2 - (i - x)][m + y - 2 - (j - y)];
        }
    }
}
map<mtx, int> frt;
map<mtx, int> bck;
queue<pair<mtx, int>> q; // {matrix,step}
int main()
{
    cin >> n >> m;
    RSZ(a);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            int x;
            cin >> x;
            a[i][j] = x;
        }
    }
    q.push({a, 0});
    frt[a] = 0;
    // RRT(a, 0, 0);
    // prt(a);
    // RRT(a, 1, 1);
    // prt(a);
    while (!q.empty())
    {
        mtx u = q.front().first;
        int stp = q.front().second;
        q.pop();
        if (stp == 10)
            continue;
        for (int i = 0; i < 2; i++)
        {
            for (int j = 0; j < 2; j++)
            {
                mtx v = u;
                RRT(v, i, j);
                if (!frt.count(v))
                    frt[v] = stp + 1, q.push({v, stp + 1});
            }
        }
    }

    RSZ(b);
    int tmp = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            b[i][j] = ++tmp;
    q.push({b, 0});
    bck[b] = 0;
    while (!q.empty())
    {
        mtx u = q.front().first;
        int stp = q.front().second;
        q.pop();
        if (stp == 10)
            continue;
        for (int i = 0; i < 2; i++)
        {
            for (int j = 0; j < 2; j++)
            {
                mtx v = u;
                RRT(v, i, j);
                if (!bck.count(v))
                    bck[v] = stp + 1, q.push({v, stp + 1});
            }
        }
    }

    int ans = 21;
    for (auto p : frt)
    {
        mtx M = p.first;
        if (bck.count(M))
            chkmn(ans, p.second + bck[M]);
    }
    cout << (ans == 21 ? -1 : ans) << endl;
    return 0;
}