侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

AtCoder Beginner Contest 322

GabrielxD
2023-10-10 / 0 评论 / 0 点赞 / 244 阅读 / 1,648 字
温馨提示:
本文最后更新于 2023-11-01,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

Tasks - AtCoder Beginner Contest 322

A - First ABC 2

方法一:模拟

思路

直接模拟查找第一个 "ABC" 出现的位置即可。

代码

#include <cstdio>

using namespace std;

const int N = 110;
int n;
char s[N];

int main() {
    scanf("%d%s", &n, s);
    for (int i = 0; i + 2 < n; ++i) {
        if (s[i] == 'A' && s[i + 1] == 'B' && s[i + 2] == 'C') {
            printf("%d\n", i + 1);
            return 0;
        }
    }
    puts("-1");

    return 0;
}

B - Prefix and Suffix

方法一:模拟

思路

按题意模拟即可。

代码

#include <cstdio>

using namespace std;

const int N = 110;
int n, m;
char s[N], t[N];

int main() {
    scanf("%d%d%s%s", &n, &m, s, t);
    int ans = 0;
    bool pf = true, sf = true;
    for (int i = 0; i < n; ++i) {
        if (s[i] != t[i]) {
            pf = false;
            break;
        }
    }
    for (int i = 0; i < n; ++i) {
        if (s[i] != t[m - n + i]) {
            sf = false;
            break;
        }
    }
    if (pf) ans |= 0b10;
    if (sf) ans |= 0b01;
    ans ^= 0b11;
    printf("%d\n", ans);

    return 0;
}

C - Festival

方法一:枚举

思路

倒着从后往前推,然后正序输出即可。

代码

#include <cstdio>
#include <cstring>

using namespace std;

const int N = 2e5 + 10;
int n, m;
int a[N];

int main() {
    scanf("%d%d", &n, &m);
    memset(a, -1, sizeof(a));
    while (m--) {
        int x; scanf("%d", &x);
        a[x] = 0;
    }
    for (int i = n; i >= 1; --i) {
        if (a[i] != 0) a[i] = a[i + 1] + 1;
    }
    for (int i = 1; i <= n; ++i) printf("%d\n", a[i]);

    return 0;
}

D - Polyomino

方法一:DFS 模拟

思路

枚举出三个 polygon 的四个旋转,然后 DFS 尝试每个 polygon 的每个旋转的每个合法位置,如果能找到合法方案即输出 "Yes"

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10;
struct Poly {
    char shape[4][4];
    int l = 4, r = 0, t = 4, b = 0;
} polys[3][4];
int g[N][N], bak[N][N];
int tot;

void rotate(Poly& dest, const Poly& src) {
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
            dest.shape[j][3 - i] = src.shape[i][j];
            if (src.shape[i][j] == '#') {
                dest.l = min(dest.l, 3 - i), dest.r = max(dest.r, 3 - i);
                dest.t = min(dest.t, j), dest.b = max(dest.b, j);
            }
        }
    }
}

void alter(const Poly& p, int x, int y, int d) {
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
            int nx = x + i, ny = y + j;
            if (p.shape[i][j] == '#') g[nx][ny] += d;
        }
    }
}

bool dfs(int u) {
    if (u == 3) {
        for (int i = 3; i <= 6; ++i) {
            for (int j = 3; j <= 6; ++j) {
                if (g[i][j] != 1) return false;
            }
        }
        return true;
    }
    for (int i = 0; i < 4; ++i) {
        const Poly& p = polys[u][i];
        for (int x = 0; x < 7; ++x) {
            for (int y = 0; y < 7; ++y) {
                if (x + p.t < 3 || x + p.b > 6 || y + p.l < 3 || y + p.r > 6) continue;
                alter(p, x, y, 1);
                if (dfs(u + 1)) return true;
                alter(p, x, y, -1);
            }
        }
    }
    return false;
}

int main() {
    for (int i = 0; i < 3; ++i) {
        Poly& p = polys[i][0];
        for (int j = 0; j < 4; ++j) {
            for (int k = 0; k < 4; ++k) {
                p.shape[j][k] = getchar();
                if (p.shape[j][k] == '#') {
                    ++tot;
                    p.l = min(p.l, k), p.r = max(p.r, k);
                    p.t = min(p.t, j), p.b = max(p.b, j);
                }
            }
            getchar();
        }
        for (int j = 1; j < 4; ++j) rotate(polys[i][j], polys[i][j - 1]);
    }
    if (tot != 16) {
        puts("No");
        return 0;
    }
    puts(dfs(0) ? "Yes" : "No");

    return 0;
}

E - Product Development

方法一:动态规划

思路

多维费用(每维费用有至少需求值)求最小价值的01背包问题 类似潜水员

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 110, K = 6;
const LL INF = 0x3f3f3f3f3f3f3f3fLL;
int n, k, P;
int c[N], p[K], a[N][K];
LL f[K][K][K][K][K];

int main() {
    scanf("%d%d%d", &n, &k, &P);
    for (int i = 1; i <= k; ++i) p[i] = P;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &c[i]);
        for (int j = 1; j <= k; ++j) scanf("%d", &a[i][j]);
    }
    memset(f, 0x3f, sizeof(f));
    f[0][0][0][0][0] = 0LL;
    for (int i = 1; i <= n; ++i) {
        for (int x1 = p[1]; x1 >= 0; --x1) {
            for (int x2 = p[2]; x2 >= 0; --x2) {
                for (int x3 = p[3]; x3 >= 0; --x3) {
                    for (int x4 = p[4]; x4 >= 0; --x4) {
                        for (int x5 = p[5]; x5 >= 0; --x5) {
                            int v1 = max(0, x1 - a[i][1]);
                            int v2 = max(0, x2 - a[i][2]);
                            int v3 = max(0, x3 - a[i][3]);
                            int v4 = max(0, x4 - a[i][4]);
                            int v5 = max(0, x5 - a[i][5]);
                            f[x1][x2][x3][x4][x5] = min(f[x1][x2][x3][x4][x5], f[v1][v2][v3][v4][v5] + c[i]);
                        }
                    }
                }
            }
        }
    }
    if (f[p[1]][p[2]][p[3]][p[4]][p[5]] == INF) f[p[1]][p[2]][p[3]][p[4]][p[5]] = -1LL;
    printf("%lld\n", f[p[1]][p[2]][p[3]][p[4]][p[5]]);

    return 0;
}

F - Vacation Query

方法一:线段树

思路

你能回答这些问题吗的变形,需要区间修改,所以要用到带懒标记的线段树。

代码

#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 5e5 + 10;
int n, q;
char s[N];
struct Node {
    int l, r, c;
    int mx[2], lmx[2], rmx[2];
    bool lazy;

    void set(int x) {
        mx[x] = lmx[x] = rmx[x] = 1;
    }
} tr[N * 4];

void push_up(Node& un, Node& ln, Node& rn) {
    for (int i = 0; i <= 1; ++i) {
        un.lmx[i] = ln.r - ln.l + 1 == ln.lmx[i] ? ln.r - ln.l + 1 + rn.lmx[i] : ln.lmx[i];
        un.rmx[i] = rn.r - rn.l + 1 == rn.rmx[i] ? rn.r - rn.l + 1 + ln.rmx[i] : rn.rmx[i];
        un.mx[i] = max(max(ln.mx[i], rn.mx[i]), ln.rmx[i] + rn.lmx[i]);
    }
}

void push_up(int u) {
    push_up(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void swap(Node& u) {
    swap(u.mx[0], u.mx[1]), swap(u.lmx[0], u.lmx[1]), swap(u.rmx[0], u.rmx[1]);
}

void push_down(int u) {
    bool& lazy = tr[u].lazy;
    if (!lazy) return;
    tr[u << 1].lazy ^= 1, swap(tr[u << 1]);
    tr[u << 1 | 1].lazy ^= 1, swap(tr[u << 1 | 1]);
    lazy = false;
}

void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r;
    if (l == r) tr[u].set(s[l] - '0');
    else {
        int m = l + r >> 1;
        build(u << 1, l, m);
        build(u << 1 | 1, m + 1, r);
        push_up(u);
    }
}

void modify(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) {
        tr[u].lazy = !tr[u].lazy;
        swap(tr[u]);
    } else {
        push_down(u);
        int m = tr[u].l + tr[u].r >> 1;
        if (m >= l) modify(u << 1, l, r);
        if (m + 1 <= r) modify(u << 1 | 1, l, r);
        push_up(u);
    }
}

Node query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u];
    push_down(u);
    int m = tr[u].l + tr[u].r >> 1;
    if (m >= r) return query(u << 1, l, r);
    else if (m + 1 <= l) return query(u << 1 | 1, l, r);
    Node res;
    Node ln = query(u << 1, l, r), rn = query(u << 1 | 1, l, r);
    push_up(res, ln, rn);
    return res;
}

int main() {
    scanf("%d%d%s", &n, &q, s + 1);
    build(1, 1, n);
    int x = 1;
    while (q--) {
        int c, l, r;
        scanf("%d%d%d", &c, &l, &r);
        if (c == 1) modify(1, l, r);
        else printf("%d\n", query(1, l, r).mx[1]);
    }

    return 0;
}

G - Two Kinds of Base

暂无

0

评论区