ABC387

A - Happy New Year 2025

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a, b;
    cin >> a >> b;
    cout << (a + b) * (a + b);
    return 0;
}

B - 9x9 Sum

#include <bits/stdc++.h>
using namespace std;
int cnt[9 * 9 + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int sum, n;
    sum = 0;
    for (int i = 1; i <= 9; i++)
        for (int j = 1; j <= 9; j++)
        {
            cnt[i * j]++;
            sum += i * j;
        }
    cin >> n;
    cout << sum - n * cnt[n];
    return 0;
}

C - Snake Numbers

实际上可以套一个数位 DP 的板子。当然也可以按照我的方式，手动算。

#include <bits/stdc++.h>
#define int long long
using namespace std;
// f[i][j]: i 开头的 j 位数有多少个蛇数
// 实际上就是 j-1 位可以是 0~i-1，i^{j-1}
int f[10][20];
// 返回 1~x 有多少个蛇数
int len, num[20];
int cal(int x)
{
    len = 0;
    while (x > 0)
    {
        num[++len] = x % 10;
        x /= 10;
    }
    if (len < 2)
        return 0;
    int res = 0;
    // 所有小于 len 位的都行
    for (int i = 1; i <= 9; i++)
        for (int j = 2; j <= len - 1; j++)
            res += f[i][j];
    // 恰好 len 位且最高位小于 num[len] 的
    for (int i = 1; i <= num[len] - 1; i++)
        res += f[i][len];
    // 恰好 len 位且最高位就是 num[len] 的
    for (int i = len - 1; i >= 1; i--)
    {
        // 此时后面的方案数，相当于第 i 位是 0~now 时后面随便填 0~num[len]-1
        // 每种第 i 位的选择都恰好有 num[len]^(i-1) 这么多种方案
        int now = min(num[i], num[len]);
        res += now * f[num[len]][i];
        // 第 i 位能不能取到上限 num[i]
        if (num[i] >= num[len])
            break;
        // 完整的自己本身
        if (i == 1)
            res++;
    }
    return res;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    for (int i = 1; i <= 9; i++)
        for (int j = 1; j <= 19; j++)
        {
            f[i][j] = 1;
            for (int k = 1; k <= j - 1; k++)
                f[i][j] *= i;
        }
    int l, r;
    cin >> l >> r;
    cout << cal(r) - cal(l - 1) << "\n";
    return 0;
}

D - Snaky Walk

传统走迷宫的基础上，不允许同样的方向，那就多记录一下上一步的方向就好了。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000;
int h, w, sx, sy, ex, ey;
char g[MAXN + 5][MAXN + 5];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int f[MAXN + 5][MAXN + 5][5];
queue<int> qx;
queue<int> qy;
queue<int> qt;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> h >> w;
    for (int i = 1; i <= h; i++)
        for (int j = 1; j <= w; j++)
        {
            cin >> g[i][j];
            if (g[i][j] == 'S')
                sx = i, sy = j;
            if (g[i][j] == 'G')
                ex = i, ey = j;
        }
    for (int i = 0; i < 4; i++)
    {
        qx.push(sx);
        qy.push(sy);
        qt.push(i);
        f[sx][sy][i] = 1;
    }
    while (!qx.empty())
    {
        int x = qx.front();
        int y = qy.front();
        int t = qt.front();
        qx.pop(), qy.pop(), qt.pop();
        for (int i = 0; i < 4; i++)
        {
            if (i % 2 == t % 2)
                continue;
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 1 || nx > h || ny < 1 || ny > w ||
                g[nx][ny] == '#' ||
                f[nx][ny][i])
                continue;
            f[nx][ny][i] = f[x][y][t] + 1;
            qx.push(nx);
            qy.push(ny);
            qt.push(i);
        }
    }
    int ans = 0;
    for (int i = 0; i < 4; i++)
        if (f[ex][ey][i] && (ans == 0 || f[ex][ey][i] < ans))
            ans = f[ex][ey][i];
    cout << ans - 1;
    return 0;
}