A – First ABC 2 (abc322 A)
题目大意
给定一个字符串,找到最先出现ABC
的位置。
解题思路
直接查找判断即可。
神奇的代码
#include
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
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
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 day(m);
for (auto& i : day)
cin >> i;
int cur = 0;
for (int i = 1; i day[cur])
++cur;
cout
D – Polyomino (abc322 D)
题目大意
给定三个多米诺骨牌,问能否不重叠地摆成(4 times 4)的方格。
解题思路
数不大,直接暴力搜索。
考虑搜索方式,虽然给了个(4 times 4)的多米诺骨牌的表示形式,但我们就枚举这个 (4 times 4) 的方格的位置。
设想我们的画布就是一个(4 times 4)的方格,然后枚举一个多米诺骨牌盖章左上角的位置(可以在这个画布之外),以及旋转的角度,然后一盖,在该区域的多米诺骨就被保留下来。最后我们就看该区域是否填满了,且没重叠,且无多米诺骨牌在外面。
代码实现里没有真正的盖,只取了盖在画布上的格子,方法类似于
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
array, 3> tu;
int cnt = 0;
for (auto& i : tu)
for (auto& j : i) {
cin >> j;
cnt += count(j.begin(), j.end(), '#');
}
array, 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 = 0 && nx = 0 && ny = 0 && nx = 0 && ny ok = [&](int k) {
if (k == 3) {
return true;
}
auto bak = page;
for (int x = -3; x
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
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 dp(sz, inf);
dp[0] = 0;
auto dtr = [&](int x) {
vector ret(k);
for (int i = k - 1; i >= 0; --i) {
ret[i] = x % base;
x /= base;
}
return ret;
};
auto tr = [&](const vector& x) {
int ret = 0;
for (int i = 0; i > c;
vector x(k);
vector dp2 = dp;
for (auto& i : x)
cin >> i;
for (int j = 0; j
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
using namespace std;
using LL = long long;
const int N = 5e5 + 8;
class segment {
#define lson root > 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 > 1;
if (ll 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 > 1;
node L, R;
if (ll mid)
R = query(rson, mid + 1, r, ll, rr);
if (ll > mid)
return R;
else if (rr > 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
G – Two Kinds of Base (abc322 G)
题目大意
解题思路
神奇的代码
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net