AtCoder Grand Contest 044 – 解题报告

A – Pay to Win

一个 DP。考虑反向构造：从 \(0\) 到 \(X\)。最后过程肯定是先加加减减然后再除、亦复如是。

// A.cpp
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int base[] = {2, 3, 5};

int T;
ll n, prices[4];
map<ll, ll> dp;

ll dfs(ll u)
{
    if (dp.count(u))
        return dp[u];
    dp[u] = 0x7fffffffffffffff;
    for (int i = 0; i < 3; i++)
    {
        int x = base[i];
        ll lft = u / x, rig = (u + x - 1) / x;
        dp[u] = min(dp[u], dfs(lft) + prices[i] + 1LL * prices[3] * abs(u - 1LL * lft * x));
        dp[u] = min(dp[u], dfs(rig) + prices[i] + 1LL * prices[3] * abs(u - 1LL * rig * x));
    }
    if (u < dp[u] / prices[3])
        dp[u] = min(dp[u], 1LL * prices[3] * u);
    return dp[u];
}

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%lld%lld%lld%lld%lld", &n, &prices[0], &prices[1], &prices[2], &prices[3]), dp.clear(), dp[0] = 0, dp[1] = prices[3];
        printf("%lld\n", dfs(n));
    }
    return 0;
}

B – Joker

真就暴力。

需要发现一个性质：

\[ \sum_{i = 1}^n d_{p_i} =\Theta(n^3) \]

其中 \(d_i\) 代表点 \(d\) 直接走的代价。既然代价只有 \(\Theta(n^3)\)，所以每次 BFS 的时候最多只能消掉 \(\Theta(n^3)\) 的代价。所以直接暴力。

日了狗。

// B.cpp
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAX_N = 550, dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};

int n, pi[MAX_N * MAX_N], dist[MAX_N * MAX_N], idx[MAX_N][MAX_N];
int ptot, xi[MAX_N * MAX_N], yi[MAX_N * MAX_N], rem[MAX_N * MAX_N];

void dfs(int u)
{
    for (int d = 0; d < 4; d++)
    {
        int dstx = xi[u] + dx[d], dsty = yi[u] + dy[d];
        int nd = dist[u] + 1 - rem[idx[dstx][dsty]];
        if (dist[idx[dstx][dsty]] > nd)
            dist[idx[dstx][dsty]] = nd, dfs(idx[dstx][dsty]);
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n * n; i++)
        scanf("%d", &pi[i]);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            idx[i][j] = ++ptot, xi[ptot] = i, yi[ptot] = j;
            dist[ptot] = min(min(n - i + 1, i), min(n - j + 1, j));
        }
    int ans = 0;
    for (int i = 1; i <= n * n; i++)
    {
        int u = pi[i];
        ans += dist[u] - 1, rem[u] = 1;
        for (int d = 0; d < 4; d++)
        {
            int dstx = xi[u] + dx[d], dsty = yi[u] + dy[d];
            dist[u] = min(dist[idx[dstx][dsty]], dist[u]);
        }
        dfs(idx[xi[u]][yi[u]]);
    }
    printf("%d\n", ans);
    return 0;
}

C – Strange Dance

这题不就是「联合省选 A 组」树吗？

// C.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 631441;

int n, ptot = 1, ans[MAX_N], triple[MAX_N];
char str[MAX_N];

struct node
{
    int ch[3], val, pos;
    bool tag;
} nodes[MAX_N << 1];

void pushdown(int p)
{
    if (nodes[p].tag)
    {
        swap(nodes[p].ch[1], nodes[p].ch[2]), nodes[p].tag = false;
        for (int i = 0; i < 3; i++)
            if (nodes[p].ch[i])
                nodes[nodes[p].ch[i]].tag ^= 1;
    }
}

void update(int p)
{
    if (p == 0)
        return;
    pushdown(p);
    int tmp = nodes[p].ch[2];
    nodes[p].ch[2] = nodes[p].ch[1], nodes[p].ch[1] = nodes[p].ch[0], nodes[p].ch[0] = tmp;
    update(nodes[p].ch[0]);
}

void insert(int x, int ps)
{
    int p = 1;
    for (int i = 0; i < n; i++)
    {
        int b = x % 3;
        if (nodes[p].ch[b] == 0)
            nodes[p].ch[b] = ++ptot;
        p = nodes[p].ch[b], x /= 3;
    }
    nodes[p].pos = ps;
}

void collect(int u, int acc, int dep)
{
    if (dep == n)
        return (void)(ans[nodes[u].pos] = acc);
    pushdown(u);
    for (int i = 0; i < 3; i++)
        if (nodes[u].ch[i])
            collect(nodes[u].ch[i], acc + triple[dep] * i, dep + 1);
}

int main()
{
    scanf("%d%s", &n, str + 1);
    int upper = triple[0] = 1;
    for (int i = 1; i <= n; i++)
        upper *= 3, triple[i] = upper;
    for (int i = 0; i < upper; i++)
        insert(i, i);
    for (int i = 1; str[i]; i++)
        if (str[i] == 'S')
            nodes[1].tag ^= 1, pushdown(1);
        else
            update(1);
    collect(1, 0, 0);
    for (int i = 0; i < upper; i++)
        printf("%d ", ans[i]);
    puts("");
    return 0;
}