A - First ABC 2
解题思路
签到
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
void solve() {
int n;
cin >> n;
string s;
cin >> s;
int p = s.find("ABC");
if (p == -1) cout << p << '\n';
else cout << p + 1 << '\n';
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int t;
t = 1;
while (t--) {
solve();
}
return 0;
}
B - Prefix and Suffix
解题思路
签到
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
void solve() {
int n, m;
string s, t;
cin >> n >> m >> s >> t;
int ok1 = t.substr(0, n) == s;
int ok2 = t.substr(m - n, n) == s;
if (ok1 && ok2) {
cout << 0 << '\n';
} else if (ok1) {
cout << 1 << '\n';
} else if (ok2) {
cout << 2 << '\n';
} else {
cout << 3 << '\n';
}
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int t;
t = 1;
while (t--) {
solve();
}
return 0;
}
C - Festival
解题思路
倒过来枚举，\(last\) 维护从后往前的第一个放烟花的位置。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
void solve() {
int n, m;
cin >> n >> m;
vector<bool> st(n + 1, false);
vector<int> ans(n + 1, 0);
for (int i = 1; i <= m; i++) {
int x;
cin >> x;
st[x] = true;
}
int last;
for (int i = n; i >= 1; i--) {
if (st[i]) last = i;
ans[i] = last - i;
}
for (int i = 1; i <= n; i++) {
cout << ans[i] << "\n";
}
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int t;
t = 1;
while (t--) {
solve();
}
return 0;
}
D - Polyomino
解题思路
直接暴力模拟 \(3\) 个矩阵的旋转和平移，然后看看 # 能不能不重叠的填满 \(4\times 4\) 的矩阵。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
void solve() {
array<string, 4> a, b, c;
for (int i = 0; i < 4; i++) {
cin >> a[i];
}
for (int i = 0; i < 4; i++) {
cin >> b[i];
}
for (int i = 0; i < 4; i++) {
cin >> c[i];
}
auto rotate = [&](array<string, 4> &s) {
array<string, 4> t;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
t[i] += s[3 - j][i];
}
}
s = t;
};
for (int da = 0; da < 4; da++) {
for (int db = 0; db < 4; db++) {
for (int dc = 0; dc < 4; dc++) {
for (int dxa = -3; dxa <= 3; dxa++) {
for (int dya = -3; dya <= 3; dya++) {
for (int dxb = -3; dxb <= 3; dxb++) {
for (int dyb = -3; dyb <= 3; dyb++) {
for (int dxc = -3; dxc <= 3; dxc++) {
for (int dyc = -3; dyc <= 3; dyc++) {
array<string, 4> s;
bool ok = true;
auto cover = [&](auto &a, int dx, int dy) {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
int x = i + dx;
int y = j + dy;
if (a[i][j] == '#') {
if (x < 0 || x >= 4 || y < 0 || y >= 4 || s[x][y] == '#') {
ok = false;
} else {
s[x][y] = '#';
}
}
}
}
};
s.fill("....");
cover(a, dxa, dya);
cover(b, dxb, dyb);
cover(c, dxc, dyc);
for (int i = 0; i < 4; i++) {
if (s[i] != "####") {
ok = false;
}
}
if (ok) {
cout << "Yes\n";
return ;
}
}
}
}
}
}
}
rotate(c);
}
rotate(b);
}
rotate(a);
}
cout << "No\n";
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int t;
t = 1;
while (t--) {
solve();
}
return 0;
}
E - Product Development
解题思路
\(6\) 维 DP，记 \(dp(i,a,b,c,d,e)\) 为考虑前 \(i\) 个计划，第 \(1-5\) 个物品目前的价值至少为 \(a,b,c,d,e\)，然后和背包一样正常转移即可。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL dp[110][6][6][6][6][6];
void solve() {
int n, k, p;
cin >> n >> k >> p;
memset(dp, 0x3f, sizeof dp);
LL INF = dp[0][1][0][0][0][0];
dp[0][0][0][0][0][0] = 0;
for (int i = 1; i <= n; i++) {
int val;
cin >> val;
vector<int> cur(6, 0);
for (int j = 1; j <= k; j++) {
cin >> cur[j];
}
for (int a = 0; a <= p; a++) {
for (int b = 0; b <= p; b++) {
for (int c = 0; c <= p; c++) {
for (int d = 0; d <= p; d++) {
for (int e = 0; e <= p; e++) {
dp[i][a][b][c][d][e] = min(dp[i][a][b][c][d][e], dp[i - 1][a][b][c][d][e]);
dp[i][a][b][c][d][e] = min(dp[i][a][b][c][d][e], dp[i - 1][max(0, a - cur[1])][max(0, b - cur[2])][max(0, c - cur[3])][max(0, d - cur[4])][max(0, e - cur[5])] + val);
}
}
}
}
}
}
LL ans;
if (k == 1) ans = dp[n][p][0][0][0][0];
else if (k == 2) ans = dp[n][p][p][0][0][0];
else if (k == 3) ans = dp[n][p][p][p][0][0];
else if (k == 4) ans = dp[n][p][p][p][p][0];
else ans = dp[n][p][p][p][p][p];
if (ans == INF) ans = -1;
cout << ans << "\n";
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int t;
t = 1;
while (t--) {
solve();
}
return 0;
}
F - Vacation Query
解题思路
比较套路的线段树题，我们只要在线段树维护一下几个变量：
\(maxlen[2],mxl[2],mxr[2],tl,tr,l,r\)：分别表示 \(0/1\) 的最长连续段，和前缀最长，后缀最长，区间左边，右边的字符事啥，以及区间左右端点。
然后在维护一个懒标记 \(tag\) 实现区间修改，区间修改等价于把 \(maxlen[0],mxl[0],mxr[0]\) 和 \(maxlen[1],mxl[1],mxr[1]\) 交换了一下。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e5 + 10;
struct info {
int cur[2][3], tl, tr, l, r;
info operator + (const info &x) {
info res = {};
res.tl = tl, res.tr = x.tr;
res.l = l, res.r = x.r;
for (int i = 0; i < 2; i++) {
res.cur[i][0] = max(cur[i][0], x.cur[i][0]);
res.cur[i][1] = cur[i][1];
res.cur[i][2] = x.cur[i][2];
if (cur[i][1] == r - l + 1) {
res.cur[i][1] = max(res.cur[i][1], cur[i][0] + (tr == i && tr == x.tl) * x.cur[i][1]);
}
if (x.cur[i][2] == x.r - x.l + 1) {
res.cur[i][2] = max(res.cur[i][2], x.cur[i][0] + (tr == i && tr == x.tl) * cur[i][2]);
}
res.cur[i][0] = max(res.cur[i][0], (tr == i && tr == x.tl) * (cur[i][2] + x.cur[i][1]));
}
return res;
};
};
struct node {
info val;
int tag;
} tr[4 * N];
string s;
void pushup(int u) {
tr[u].val = tr[u << 1].val + tr[u << 1 | 1].val;
}
void build(int u, int l, int r) {
tr[u].val.l = l, tr[u].val.r = r;
if (l == r) {
tr[u].val.tl = tr[u].val.tr = s[l] - '0';
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 3; j++) {
tr[u].val.cur[i][j] = i == tr[u].val.tl;
}
}
return ;
}
int mid = (l + r) >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void pushdown(int u) {
if (tr[u].tag) {
tr[u << 1].tag ^= 1;
tr[u << 1 | 1].tag ^= 1;
swap(tr[u << 1].val.cur[0], tr[u << 1].val.cur[1]);
swap(tr[u << 1 | 1].val.cur[0], tr[u << 1 | 1].val.cur[1]);
tr[u << 1].val.tl ^= 1;
tr[u << 1].val.tr ^= 1;
tr[u << 1 | 1].val.tl ^= 1;
tr[u << 1 | 1].val.tr ^= 1;
tr[u].tag = 0;
}
}
void modify(int u, int l, int r) {
if (tr[u].val.l >= l && tr[u].val.r <= r) {
swap(tr[u].val.cur[0], tr[u].val.cur[1]);
tr[u].val.tl ^= 1;
tr[u].val.tr ^= 1;
tr[u].tag ^= 1;
return ;
}
pushdown(u);
int mid = (tr[u].val.l + tr[u].val.r) >> 1;
if (l <= mid) modify(u << 1, l, r);
if (r > mid) modify(u << 1 | 1, l, r);
pushup(u);
}
info query(int u, int l, int r) {
if (tr[u].val.l >= l && tr[u].val.r <= r) return tr[u].val;
pushdown(u);
int mid = (tr[u].val.l + tr[u].val.r) >> 1;
if (r <= mid) return query(u << 1, l, r);
else if (l > mid) return query(u << 1 | 1, l, r);
return query(u << 1, l, r) + query(u << 1 | 1, l, r);
}
void solve() {
int n, q;
cin >> n >> q >> s;
s = '?' + s;
build(1, 1, n);
while (q--) {
int c, l, r;
cin >> c >> l >> r;
if (c == 1) modify(1, l, r);
else {
cout << query(1, l, r).cur[1][0] << "\n";
}
}
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int t;
t = 1;
while (t--) {
solve();
}
return 0;
}
- Beginner AtCoder Contest 322beginner atcoder contest 322 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 332 beginner atcoder contest 315