AtCoder Beginner Contest 322
推荐视频：AtCoder Beginner Contest 322 A 至 F 題讲解 by dreamoon
A. First ABC 2
解题思路:
遍历寻找连续的\(ABC\).
时间复杂度:\(O(n)\).
代码:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
#define fi first
#define se second
void solve()
{
int n;
cin>>n;
string s;
cin>>s;
for(int i = 0;i<n - 2;i++)
{
if(s[i] == 'A' && s[i+1] == 'B' && s[i+2] =='C')
{
cout<<(i + 1)<<endl;
return;
}
}
cout<<-1<<endl;
}
int main()
{
int t = 1;
// scanf("%d",&t);
while(t--)
{
solve();
}
return 0;
}
B. Prefix and Suffix
解题思路:
直接取\(T\)串的前后缀和\(S\)比较即可。
时间复杂度:\(O(n)\).
代码:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
#define fi first
#define se second
void solve()
{
int n,m;
cin>>n>>m;
string s,t;
cin>>s>>t;
string pre = t.substr(0,n);
string suf = t.substr(m - 1 - n + 1,n);
if(s == pre)
{
if(s == suf)
{
cout<<0<<endl;
}
else
{
cout<<1<<endl;
}
}
else if(s == suf)
{
cout<<2<<endl;
}
else
{
cout<<3<<endl;
}
}
int main()
{
int t = 1;
// scanf("%d",&t);
while(t--)
{
solve();
}
return 0;
}
C. Festival
解题思路:
从最后一天往前减，如果遇到了放烟花日就是\(0\),否则就是后一天距离最近烟花日$ + 1$。
\(ans[i] = ans[i+1] + 1\)。
时间复杂度:\(O(n)\)
代码:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
#define fi first
#define se second
void solve()
{
int n,m;
cin>>n>>m;
vector<int> a(m + 1),ans(n + 10);
for(int i = 1;i<=m;i++)
{
scanf("%d",&a[i]);
}
int cnt = n;
for(int i = m;i;i--)
{
while(cnt > a[i])
{
ans[cnt] = ans[cnt+1] + 1;
cnt --;
}
ans[cnt--] = 0;
}
while(cnt > 0)
{
ans[cnt] = ans[cnt+1] + 1;
cnt --;
}
for(int i = 1;i<=n;i++)
{
printf("%d\n",ans[i]);
}
}
int main()
{
int t = 1;
// scanf("%d",&t);
while(t--)
{
solve();
}
return 0;
}
D. Polyomino
解题思路:
一共三个图形，我们状态压缩他们能覆盖的所有地方然后三层遍历判断是否无相交全覆盖即可。
操作一：旋转
将整个\(4 \times 4\)图沿着中心顺时政旋转\(90°\)
auto rotate = [&]()
{
vector<vector<char>> g(5, vector<char>(5));
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
g[j][3 - i] = s[i][j];
}
}
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
s[i][j] = g[i][j];
}
}
};
操作二：平移
不难发现，我们一个图像无论在那个位置，根据图的大小，最多一个方向移动三个单位，上下左右都是如此。
auto move = [&](int dx, int dy)
{
int res = 0;
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
if (s[i][j] == '#')
{
int x = i + dx;
int y = j + dy;
if (check(x, y))
{
res |= 1 << ((x * 4) + y);
}
else
{
return -1;
}
}
}
}
状态压缩:
我们将\(16\)个格子分别看成\(0\sim 15\).如果覆盖了某个格子，那么当前状态就是二进制第\(i\)位为1。
最终答案就是不相交全覆盖，具体实现见代码。
时间复杂度:\(O(3\times 4^3 \times6 ^2)\)
代码:
#include <bits/stdc++.h>
using namespace std;
vector<int> add()
{
vector<string> s(5);
for (int i = 0; i < 4; i++)
{
cin >> s[i];
}
auto rotate = [&]()
{
vector<vector<char>> g(5, vector<char>(5));
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
g[j][3 - i] = s[i][j];
}
}
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
s[i][j] = g[i][j];
}
}
};
auto check = [&](int a, int b)
{
if (a < 0 || b < 0 || a > 3 || b > 3)
{
return false;
}
return true;
};
auto move = [&](int dx, int dy)
{
int res = 0;
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
if (s[i][j] == '#')
{
int x = i + dx;
int y = j + dy;
if (check(x, y))
{
res |= 1 << ((x * 4) + y);
}
else
{
return -1;
}
}
}
}
// if (res == 63232)
// {
// cout << dx << ' ' << dy << endl;
// for (int i = 0; i < 4; i++)
// {
// cout << s[i] << endl;
// }
// cout << endl;
// }
return res;
};
vector<int> v;
for (int k = 1; k <= 4; k++)
{
for (int i = -3; i <= 3; i++)
{
for (int j = -3; j <= 3; j++)
{
int t = move(i, j);
if (t != -1)
{
v.push_back(t);
}
}
}
rotate();
}
return v;
}
void solve()
{
vector<vector<int>> mask(5);
for (int i = 1; i <= 3; i++)
{
mask[i] = add();
}
for (auto x : mask[1])
{
for (auto y : mask[2])
{
for (auto z : mask[3])
{
if ((x | y | z) != ((1 << 16) - 1))
{
continue;
}
else if ((x & y) || (x & z) || (y & z))
{
continue;
}
puts("Yes");
return;
}
}
}
puts("No");
}
int main()
{
int t = 1;
while (t--)
{
solve();
}
return 0;
}
E. Product Development
解题思路：
背包转移即可。
超过\(p\)和\(p\)等价，取较小花费即可。
注意空间限制，背包滚动数组，从大到小枚举。
写法一：六维滚动\(O(np^5)\)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll f[10][10][10][10][10];
void solve()
{
ll n, k, p;
cin >> n >> k >> p;
vector<vector<ll>> a(n + 10, vector<ll>(100));
vector<ll> c(n + 10);
vector<ll> up(10, 0);
for (int i = 1; i <= k; i++)
{
up[i] = p;
}
for (ll u = up[5]; u >= 0; u--)
{
for (ll v = up[4]; v >= 0; v--)
{
for (ll x = up[3]; x >= 0; x--)
{
for (ll y = up[2]; y >= 0; y--)
{
for (ll z = up[1]; z >= 0; z--)
{
f[u][v][x][y][z] = 1e13;
}
}
}
}
}
f[0][0][0][0][0] = 0;
for (int i = 1; i <= n; i++)
{
cin >> c[i];
for (int j = 1; j <= k; j++)
{
cin >> a[i][j];
}
for (ll u = up[5]; u >= 0; u--)
{
for (ll v = up[4]; v >= 0; v--)
{
for (ll x = up[3]; x >= 0; x--)
{
for (ll y = up[2]; y >= 0; y--)
{
for (ll z = up[1]; z >= 0; z--)
{
f[min(up[5], u + a[i][5])][min(up[4], v + a[i][4])][min(up[3], x + a[i][3])][min(up[2], y + a[i][2])][min(up[1], z + a[i][1])] =
min(f[min(up[5], u + a[i][5])][min(up[4], v + a[i][4])][min(up[3], x + a[i][3])][min(up[2], y + a[i][2])][min(up[1], z + a[i][1])],
f[u][v][x][y][z] + c[i]);
}
}
}
}
}
}
if (f[up[5]][up[4]][up[3]][up[2]][up[1]] > 1e12)
{
puts("-1");
}
else
{
cout << f[up[5]][up[4]][up[3]][up[2]][up[1]] << endl;
}
}
int main()
{
int t = 1;
while (t--)
{
solve();
}
return 0;
}
写法二：进制压缩\(O(n(p + 1)^{k + 1})\)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve()
{
int n, k, p;
cin >> n >> k >> p;
vector<ll> pw(k + 10);
pw[0] = 1;
for (int i = 1; i <= k; i++)
{
pw[i] = pw[i - 1] * (p + 1);
}
vector<ll> f(pw[k] + 10, -1ll);
f[0] = 0;
for (int i = 1; i <= n; i++)
{
ll c;
cin >> c;
vector<ll> v(k + 1);
for (int j = 0; j < k; j++)
{
cin >> v[j];
}
for (int s = pw[k] - 1; s >= 0; s--)
{
int t = 0;
for (int j = 0; j < k; j++)
{
int a = (s / pw[j]) % (p + 1);
int na = min((ll)p, a + v[j]);
t += na * pw[j];
}
if (f[s] != -1 && (f[t] == -1 || f[t] > f[s] + c))
{
f[t] = f[s] + c;
}
}
}
cout << f[pw[k] - 1];
}
int main()
{
int t = 1;
while (t--)
{
solve();
}
return 0;
}
写法三：状态压缩\(O(n2^{3k}k)\)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve()
{
int n, k, p;
cin >> n >> k >> p;
int fs = 0;
// 由于p最大为5，用二进制位仅需三位即可表示
// 我们这里单独看成二进制的话一个数位不够，所以用三个二进制位表示一个方面
// 其余的和上一个(p + 1)进制处理一样
for (int i = 0; i < k; i++)
{
fs = fs + (p << (3 * i));
}
vector<ll> f(fs + 10, -1);
f[0] = 0;
for (int i = 1; i <= n; i++)
{
int c = 0;
cin >> c;
vector<int> v(k + 1);
for (int j = 0; j < k; j++)
{
cin >> v[j];
}
for (int s = fs; s >= 0; s--)
{
if (f[s] == -1)
{
continue;
}
int t = 0;
for (int u = 0; u < k; u++)
{
// 三位三位拿出来看，加上当前的发展方案的提升，是否能到达目标
int cur = min(p, ((s >> (3 * u)) & 7) + v[u]);
t |= (cur << (3 * u));
}
if (f[t] == -1 || f[t] > f[s] + c)
{
f[t] = f[s] + c;
}
}
}
cout << f[fs];
}
int main()
{
int t = 1;
while (t--)
{
solve();
}
return 0;
}
F. Vacation Query
解题思路:
懒标记线段树板子。
维护最大连续子段和。
\(01\)翻转问题。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e5 + 10;
struct Node
{
int l, r;
int lc, rc;
int pre, suf;
int s[2];
int sum = 0;
int laz = 0;
} tr[N << 2];
int n, m;
string s;
int a[N];
void pushup(int u)
{
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
tr[u].lc = tr[u << 1].lc;
tr[u].rc = tr[u << 1 | 1].rc;
tr[u].pre = tr[u << 1].pre;
if (tr[u << 1].pre == tr[u << 1].sum && tr[u << 1].rc == tr[u << 1 | 1].lc)
{
tr[u].pre = tr[u << 1].sum + tr[u << 1 | 1].pre;
}
tr[u].suf = tr[u << 1 | 1].suf;
if (tr[u << 1 | 1].suf == tr[u << 1 | 1].sum && tr[u << 1 | 1].lc == tr[u << 1].rc)
{
tr[u].suf = tr[u << 1 | 1].sum + tr[u << 1].suf;
}
tr[u].s[0] = max(tr[u << 1].s[0], tr[u << 1 | 1].s[0]);
tr[u].s[1] = max(tr[u << 1].s[1], tr[u << 1 | 1].s[1]);
if (tr[u << 1].rc == tr[u << 1 | 1].lc)
{
int t = tr[u << 1].rc;
tr[u].s[t] = max(tr[u].s[t], tr[u << 1].suf + tr[u << 1 | 1].pre);
}
}
void pushdown(int u)
{
if (tr[u].laz)
{
tr[u << 1].laz ^= 1;
tr[u << 1].lc ^= 1;
tr[u << 1].rc ^= 1;
swap(tr[u << 1].s[0], tr[u << 1].s[1]);
tr[u << 1 | 1].laz ^= 1;
tr[u << 1 | 1].lc ^= 1;
tr[u << 1 | 1].rc ^= 1;
swap(tr[u << 1 | 1].s[0], tr[u << 1 | 1].s[1]);
}
tr[u].laz = 0;
}
void build(int u, int l, int r)
{
tr[u].l = l;
tr[u].r = r;
if (l == r)
{
tr[u].lc = tr[u].rc = a[l];
tr[u].sum = tr[u].pre = tr[u].suf = 1;
tr[u].s[a[l]] = 1;
return;
}
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void modify(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r)
{
tr[u].laz ^= 1;
tr[u].lc ^= 1;
tr[u].rc ^= 1;
swap(tr[u].s[0], tr[u].s[1]);
return;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid)
{
modify(u << 1, l, r);
}
if (r > mid)
{
modify(u << 1 | 1, l, r);
}
pushup(u);
}
auto query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r)
{
return tr[u];
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (r <= mid)
{
return query(u << 1, l, r);
}
else if (l > mid)
{
return query(u << 1 | 1, l, r);
}
else
{
auto a = query(u << 1, l, r);
auto b = query(u << 1 | 1, l, r);
Node res;
res.sum = a.sum + b.sum;
res.lc = a.lc;
res.rc = b.rc;
res.pre = a.pre;
if (a.pre == a.sum && a.rc == b.lc)
{
res.pre = a.sum + b.pre;
}
res.suf = b.suf;
if (b.suf == b.sum && b.lc == a.rc)
{
res.suf = b.sum + a.suf;
}
res.s[0] = max(a.s[0], b.s[0]);
res.s[1] = max(a.s[1], b.s[1]);
if (a.rc == b.lc)
{
int t = a.rc;
res.s[t] = max(res.s[t], a.suf + b.pre);
}
return res;
}
pushup(u);
}
void solve()
{
scanf("%d %d", &n, &m);
cin >> s;
s = ' ' + s;
for (int i = 1; i <= n; i++)
{
a[i] = s[i] - '0';
}
build(1, 1, n);
for (int i = 1; i <= m; i++)
{
int op = 0;
scanf("%d", &op);
int a, b;
scanf("%d %d", &a, &b);
if (op == 1)
{
modify(1, a, b);
}
else
{
auto t = query(1, a, b);
printf("%d\n", t.s[1]);
}
}
}
int main()
{
int t = 1;
while (t--)
{
solve();
}
return 0;
}
附带类似线段树题:
小白逛公园
[COCI2010-2011#6] STEP
- 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