A - First ABC 2 (abc322 A)
题目大意
给定一个字符串，找到最先出现ABC的位置。
解题思路
直接查找判断即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
string s;
cin >> n >> s;
int pos = s.find("ABC");
if (pos == string::npos)
pos = -2;
cout << pos + 1 << '\n';
return 0;
}
B - Prefix and Suffix (abc322 B)
题目大意
给定字符串 s和t，问s是不是t的前缀和后缀。
解题思路
根据前后缀定义判断即可。这里试了下python
神奇的代码
n, m = map(int, input().split(' '))
s = input()
t = input()
prefix = t.startswith(s)
suffix = t.endswith(s)
if prefix and suffix:
print(0)
elif prefix and not suffix:
print(1)
elif not prefix and suffix:
print(2)
else:
print(3)
C - Festival (abc322 C)
题目大意
\(n\)天，有\(m\)天会放烟花。
问每一天，距离未来最近的放烟花的天数。
解题思路
两个双指针一样，一个指针指向当前天数，一个指针指向未来最近的放烟花的天数，两者差就是答案。然后两个指针不断往未来移动。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector<int> day(m);
for (auto& i : day)
cin >> i;
int cur = 0;
for (int i = 1; i <= n; ++i) {
if (i > day[cur])
++cur;
cout << day[cur] - i << '\n';
}
return 0;
}
D - Polyomino (abc322 D)
题目大意
给定三个多米诺骨牌，问能否不重叠地摆成\(4 \times 4\)的方格。
解题思路
数不大，直接暴力搜索。
考虑搜索方式，虽然给了个\(4 \times 4\)的多米诺骨牌的表示形式，但我们就枚举这个 \(4 \times 4\) 的方格的位置。
设想我们的画布就是一个\(4 \times 4\)的方格，然后枚举一个多米诺骨牌盖章左上角的位置（可以在这个画布之外），以及旋转的角度，然后一盖，在该区域的多米诺骨就被保留下来。最后我们就看该区域是否填满了，且没重叠，且无多米诺骨牌在外面。
代码实现里没有真正的盖，只取了盖在画布上的格子，方法类似于
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
array<array<string, 4>, 3> tu;
int cnt = 0;
for (auto& i : tu)
for (auto& j : i) {
cin >> j;
cnt += count(j.begin(), j.end(), '#');
}
array<array<char, 4>, 4> page{};
int dx1[2] = {1, -1};
int dy1[2] = {1, -1};
int dx2[2] = {1, -1};
int dy2[2] = {-1, 1};
auto fit1 = [&](int k, int x, int y, int d) {
for (int i = 0; i < 4; ++i)
for (int j = 0; j < 4; ++j) {
int nx = x + dx1[d] * i, ny = y + dy1[d] * j;
if (tu[k][i][j] == '#') {
if (nx >= 0 && nx < 4 && ny >= 0 && ny < 4) {
if (page[nx][ny] == '#') {
return false;
}
page[nx][ny] = '#';
} else {
return false;
}
}
}
return true;
};
auto fit2 = [&](int k, int x, int y, int d) {
for (int i = 0; i < 4; ++i)
for (int j = 0; j < 4; ++j) {
int nx = x + dx2[d] * j, ny = y + dy2[d] * i;
if (tu[k][i][j] == '#') {
if (nx >= 0 && nx < 4 && ny >= 0 && ny < 4) {
if (page[nx][ny] == '#') {
return false;
}
page[nx][ny] = '#';
} else {
return false;
}
}
}
return true;
};
function<bool(int)> ok = [&](int k) {
if (k == 3) {
return true;
}
auto bak = page;
for (int x = -3; x <= 7; ++x)
for (int y = -3; y <= 7; ++y) {
for (int d = 0; d < 2; ++d) {
if (fit1(k, x, y, d)) {
if (ok(k + 1))
return true;
}
page = bak;
if (fit2(k, x, y, d)) {
if (ok(k + 1))
return true;
}
page = bak;
}
}
return false;
};
if (cnt == 16 && ok(0))
cout << "Yes" << '\n';
else
cout << "No" << '\n';
return 0;
}
E - Product Development (abc322 E)
题目大意
一个产品，有\(k\)个性能参数，初始为\(0\)，要求进行一些提升计划，使得每个性能参数不小于 \(p\)，且代价最小。
每个提升计划包含一个代价，以及对这\(k\)个性能参数提升的数值。
解题思路
注意到\(k,p\)最大都只有 \(5\)。考虑搜索状态，我们可以设 \(dp[i][a1][a2][a3][a4][a5]\)表示前 \(i\)个提升计划，使得最终性能参数分别为 \(a1,a2,a3,a4,a5\)的最小代价。转移就考虑当前提升计划选或不选即可。
但这里的 \(p\)不一定是 \(5\)，也就是说这个 \(dp\)的维度不是固定的，但由于每一维度的取值只有 \(0 \sim p\)共 \(6\)种情况，最多 \(k=5\)维，因此我们可以把这最后的 \(k\)维压缩成一维的 \(6\)进制数表示。
由于 \(dp[i]\)只依赖于 \(dp[i-1]\)，因此第一维可以滚动数组优化掉。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL inf = 1e18;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, k, p;
cin >> n >> k >> p;
int base = p + 1;
const int sz = int(pow(base, k));
vector<LL> dp(sz, inf);
dp[0] = 0;
auto dtr = [&](int x) {
vector<int> ret(k);
for (int i = k - 1; i >= 0; --i) {
ret[i] = x % base;
x /= base;
}
return ret;
};
auto tr = [&](const vector<int>& x) {
int ret = 0;
for (int i = 0; i < k; ++i) {
ret = ret * base + x[i];
}
return ret;
};
for (int i = 0; i < n; ++i) {
int c;
cin >> c;
vector<int> x(k);
vector<LL> dp2 = dp;
for (auto& i : x)
cin >> i;
for (int j = 0; j < sz; ++j) {
auto now = dtr(j);
for (int i = 0; i < k; ++i)
now[i] = min(p, now[i] + x[i]);
auto nxt = tr(now);
dp2[nxt] = min(dp2[nxt], dp[j] + c);
}
dp.swap(dp2);
}
LL ans = dp.back();
if (ans == inf)
ans = -1;
cout << ans << '\n';
return 0;
}
F - Vacation Query (abc322 F)
题目大意
给定一个\(01\)串\(s\)。维护两种操作。
- \(1, l,r\)，将\(s[l..r]\)的数字翻转。
- \(2,l,r\)，问\(s[l..r]\)中最长的连续的\(1\)的长度。
解题思路
不考虑修改，仅考虑查询。
考虑如何求解，对于每个\(r\)，我们要找最小的 \(l\)满足 \(sum[r] - sum[l] = r - l\)，其中 \(sum[i]\)表示 \(s[1..i]\)中 \(1\)的个数。
但这涉及到特定区间的信息，感觉难以维护。
注意到问的是连续的，还有一种思路是考虑区间信息的合并，即一个区间的最长连续段，要么在左区间，要么在右区间，要么是左区间的后缀和右区间的前缀合并起来。与此相关的其他信息（区间最长连续 \(1\)的前缀 、后缀长度、是否全是\(1\)，这些信息都可以合并），因此可以用线段树维护区间的上述信息，对于每个区间答案，合并\(\log\)次区间信息即可得到 。
考虑修改，事实上就是把\(1\)看成 \(0\)， \(0\)看成 \(1\)。因此我们分别对 \(0,1\)这两个数维护上述信息，修改时交换一下这两个信息即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 5e5 + 8;
class segment {
#define lson root << 1
#define rson root << 1 | 1
struct node {
struct info {
int ans, l, r;
bool all;
} _info[2];
bool flip;
node operator+(const node& o) {
node ret;
ret.flip = 0;
for (int i = 0; i < 2; ++i) {
const auto &L = _info[i], R = o._info[i];
ret._info[i].ans = max({L.ans, R.ans, L.r + R.l});
ret._info[i].l = L.l;
ret._info[i].r = R.r;
if (L.all)
ret._info[i].l = L.l + R.l;
if (R.all)
ret._info[i].r = L.r + R.r;
ret._info[i].all = (L.all && R.all);
}
return ret;
}
void swap_info() { swap(_info[0], _info[1]); }
int ans() { return _info[1].ans; }
} a[N << 2];
public:
void build(int root, int l, int r, const string& s) {
if (l == r) {
a[root].flip = 0;
for (int i = 0; i < 2; ++i) {
auto& info = a[root]._info[i];
info.l = info.r = info.all = info.ans = (s[l - 1] == '0' + i);
}
return;
}
int mid = (l + r) >> 1;
build(lson, l, mid, s);
build(rson, mid + 1, r, s);
a[root] = a[lson] + a[rson];
}
void pushdown(int root) {
if (a[root].flip) {
a[lson].flip ^= 1;
a[lson].swap_info();
a[rson].flip ^= 1;
a[rson].swap_info();
a[root].flip = 0;
}
}
void update(int root, int l, int r, int ll, int rr) {
if (ll <= l && r <= rr) {
a[root].flip ^= 1;
a[root].swap_info();
return;
}
pushdown(root);
int mid = (l + r) >> 1;
if (ll <= mid)
update(lson, l, mid, ll, rr);
if (rr > mid)
update(rson, mid + 1, r, ll, rr);
a[root] = a[lson] + a[rson];
}
node query(int root, int l, int r, int ll, int rr) {
if (ll <= l && r <= rr) {
return a[root];
}
pushdown(root);
int mid = (l + r) >> 1;
node L, R;
if (ll <= mid)
L = query(lson, l, mid, ll, rr);
if (rr > mid)
R = query(rson, mid + 1, r, ll, rr);
if (ll > mid)
return R;
else if (rr <= mid)
return L;
else
return L + R;
}
} seg;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, q;
cin >> n >> q;
string s;
cin >> s;
seg.build(1, 1, n, s);
while (q--) {
int c, l, r;
cin >> c >> l >> r;
if (c == 1) {
seg.update(1, 1, n, l, r);
} else {
auto ans = seg.query(1, 1, n, l, r);
cout << ans.ans() << '\n';
}
}
return 0;
}
G - Two Kinds of Base (abc322 G)
题目大意
<++>
解题思路
<++>
神奇的代码
- 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