AtCoder Beginner Contest 265

https://atcoder.jp/contests/abc265

A - Apple

有两种购买策略：\(x\) 元买一个苹果 or \(y\) 元买三个苹果，问买 \(n\) 个苹果最少要花多少钱

#include <bits/stdc++.h>

using namespace std;

int main () {
    int x, y, n;
    cin >> x >> y >> n;
    if (n < 3 || x * 3 <= y) {
        cout << x * n << endl;
    }
    else {
        cout << (n/3)*y + (n%3)*x;
    }
}

B - Explore

从 \(i-1\) 走到 \(i\) 点需要消耗 \(a_i\), 有 \(m\) 个点 \(b_i\) 存在补助，初始有 \(t\), 问能不能从 \(1\) 走到 \(n\)

注意先减再添加补助

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 1e5 + 5;
int n, m, t;
int a[N], b[N];

signed main () {
    cin >> n >> m >> t;
    for (int i = 2; i <= n; i++)     cin >> a[i];
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        b[x] = y;
    }

    for (int i = 2; i <= n; i++) {
        
        t -= a[i];
        if (t <= 0) {
            cout << "No\n";
            return 0;
        }
        t += b[i];
    }
    cout << "Yes\n";
}


//模拟

C - Belt Conveyor

有 \(n*m\) 的地图，初始在 \((1,1)\), 规则：\(U\) 向上一格，\(D\) 向下一格，\(R\) 向右一格，\(R\) 向左一格。
问走到哪里时下一步就出界，永不出界输出 \(-1\)

按题意模拟，如果走完了整个地图还不出界，则永不出界。

#include <bits/stdc++.h>

using namespace std;
const int N = 505;
int n, m;
char a[N][N];

bool check (int x, int y) {
    if (x > n || x <= 0 || y > m || y <= 0)
        return false;
    return true;
}

signed main () {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }

    int x = 1, y = 1, sx, sy;
    int cnt = n * m;
    while (1) {
        cnt --;
        sx = x, sy = y;
        if (a[x][y] == 'U') x --;
        else if (a[x][y] == 'D')    x ++;
        else if (a[x][y] == 'R')    y ++;
        else if (a[x][y] == 'L')    y --;
        if (!check (x, y)) {
            cout << sx << ' ' << sy;
            break;
        }
        if (cnt <= 0) {
            cout << -1;
            break;
        }
        //x = sx, y = sy;
    }
}

//一直走走到出界

D - Iroha and Haiku (New ABC Edition)

现有一数列 \(A=(A_0,...,A_{N-1})\), 问能不能找到四点 \(x,y,z,w\), 满足：

暴力 \(set\) 查找

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 2e5 + 5;
int n, p, q, r;
int sum[N];

signed main () {
    cin >> n >> p >> q >> r;
    set<int> s;
    s.insert (0);

    for (int i = 1; i <= n; i++) {
        int x;  cin >> x;
        sum[i] = sum[i-1] + x;
        s.insert (sum[i]);
    }

    for (int i = 1; i <= n; i++) {
        if (s.count (sum[i-1]+p) && s.count (sum[i-1]+p+q) && s.count (sum[i-1]+p+q+r)) {
            cout << "Yes\n";
            return 0;
        }
    }
    cout << "No\n";
}

//sum[y-1]-sum[x-1]=p
//sum[z-1]-sum[y-1]=q
//sum[w-1]-sum[z-1]=r

E - Warp

假设现在在 \((x,y)\), 下一步可以选择走到 \((x+A,y+B)\) or \((x+C,y+D)\) or \((x+E,y+F)\), 且有 \(m\) 个障碍， 问走 \(n\) 步能有多少种可能的路径

定义状态 \(f[i][j][k]：\) 表示 1走了 \(i\) 次，2走了 \(j\) 次，3走了 \(k\) 次。
线性 dp 路径转移即可

#include <bits/stdc++.h>
#define int long long

using namespace std;
typedef pair<int, int> pii;
const int N = 305, mod = 998244353;
int A, B, C, D, E, F, n, m;
int f[N][N][N]; //1走了i次，2走了j次，3走了k次

signed main () {
    cin >> n >> m >> A >> B >> C >> D >> E >> F;
    set<pii> s;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        s.insert({x, y});
    }

    f[0][0][0] = 1;
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n - i; j++)
            for (int k = 0; k <= n - i - j; k++) {
                int x = i*A + j*C + k*E, y = i*B + j*D + k*F;
                if (!i && !j && !k)     continue;
                if (s.count ({x, y}))   continue;
                if (i)  f[i][j][k] += f[i-1][j][k];
                if (j)  f[i][j][k] += f[i][j-1][k];
                if (k)  f[i][j][k] += f[i][j][k-1];
                f[i][j][k] %= mod;
            }

    int ans = 0;
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n - i; j++) {
            ans += f[i][j][n-i-j], ans %= mod;
        }      

    cout << ans;
}

//移动n次

F - Manhattan Cafe

题意：有两点 \(p,q\), 各有 \(n\) 个维度，问有多少个点满足到 \(p\) 和 \(q\) 的曼哈顿距离均 \(\leq d\)

分析：可以把这样的点分为两类————在 \(p,q\) 之间的，在 \(p,q\) 外的。

对于在两点之外的 \(x_i\), 每走一格，\(d_{p_i},d_{q_i}\) 都会同时 \(\pm 1\)；
对于在两点之间的 \(x_i\), 则是 \(d_{p_i}+d_{q_i}=\) 定值，即 \(d_{p_i}\pm1,d_{q_i}\mp1\)。

由这两种特殊性质得，可以维护矩阵的主对角线和副对角线的前缀和，即可dp 转移

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 1005, M = 105, mod = 998244353;
int p[M], q[M], dp[N][N], C[N][N], E[N][N];
int n, d;

signed main() {
    cin >> n >> d;
    for (int i = 0; i < n; i++)     cin >> p[i];
    for (int i = 0; i < n; i++)     cin >> q[i];
    dp[0][0] = 1;

    for (int k = 0; k < n; k++) {
        int z = abs(p[k] - q[k]);
        for (int i = 0; i <= d; i++)
            for (int j = 0; j <= d; j++) {
                C[i+1][j+1] = (C[i][j] + dp[i][j]) % mod; //主对角线
                E[i+1][j] = (E[i][j+1] + dp[i][j]) % mod; //副对角线
                dp[i][j] = (C[i][max(j-z, 0ll)] + C[max(i-z, 0ll)][j]) % mod;
                
                int m = max(z - j, 0ll);
                if (i >= m)     dp[i][j] = (dp[i][j] + E[i+1-m][j-z+m]) % mod;
                if (i >= z)     dp[i][j] = (dp[i][j] - E[i-z][j+1] + mod) % mod;
            }
    }

    int ans = 0;
    for (int i = 0; i <= d; i++)
        for (int j = 0; j <= d; j++)
            ans = (ans + dp[i][j]) % mod;
    
    cout << ans;
}