题目
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;
}
评论区