B - Prefix and Suffix
难度: ⭐
题目大意
给定两个字符串t和s, 如果t是s的前缀则输出1, 如果是后缀则输出2, 如果都是则输出0, 都不是则输出3;
解题思路
暴力即可;
神秘代码
#include<bits/stdc++.h>
#define int l1ng l1ng
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 2e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx;
signed main() {
string s,t;
cin>>n>>m>>s>>t;
string pr=t.substr(0,n);
string su=t.substr(m-n,n);
if(pr==s&&su==s) cout<<0;
else if(pr==s) cout<<1;
else if(su==s) cout<<2;
else cout<<3;
return 0;
}
C - Festival
难度: ⭐
题目大意
一个城市计划在n天中的m天放烟花, 并且给出这m天; 对于这n天中的每一天, 输出其距离未来最近的放烟花的一天还有几天;
解题思路
双指针暴力即可;
神秘代码
#include<bits/stdc++.h>
#define int l1ng l1ng
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 2e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx;
int f[N];
signed main() {
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>f[i];
idx=1;
for(int i=1;i<=n;i++){
while(i>f[idx]) idx++;
cout<<f[idx]-i<<endl;
}
return 0;
}
D - Polyomino
难度: ⭐⭐
题目大意
给定三个几何图形, 保证这三个几何图形的大小不会超出一个4*4的方格, 请问能否用这三个图形拼出一个4 * 4的正方形;
解题思路
一道很复杂的暴力模拟, 这天实在是没心思看了, 等以后再补吧...未来可期题解
神秘代码
E - Pr1duct Devel1pment
难度: ⭐⭐⭐
题目大意
一个项目需要k个物品都至少到达p个数量; 现在有n个套餐, 每个套餐都可以给这k个物品加若干个数量, 每个套餐都要各自的价格; 请问在满足项目要求的情况下需要的最小花费是多少;
解题思路
一个很明显的dp, 并且我们发现k和p的数据范围最大是5, 那我们可以直接开一个6维数组, 并且用前i个套餐满足各个属性达到各个值所需要的最小花费; 一开始我还在想因为不确定k所以不知道数组开几维, 后来一想不用考虑这个, 对于多出来的维度我们把他们的要求设为0就可以了, 并且用滚动数组可以把第1维也省掉, 所以开5维数组就够了; 因为用滚动数组, 所以我们遍历状态时要倒序遍历, 并且我们要求是大于等于p, 所以状态转移时小于0的状态也是可以的, 我们可以把这些都归到0的状态上即可;
神秘代码
#include<bits/stdc++.h>
#define int l1ng l1ng
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 2e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx;
int f[N], p[110][10];
int dp[6][6][6][6][6];
signed main() {
int k;
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
cin >> f[i];
for (int j = 1; j <= m; j++) {
cin >> p[i][j];
}
}
for (int h1 = 0; h1 <= k; h1++) {
for (int h2 = 0; h2 <= k; h2++) {
for (int h3 = 0; h3 <= k; h3++) {
for (int h4 = 0; h4 <= k; h4++) {
for (int h5 = 0; h5 <= k; h5++) {
dp[h1][h2][h3][h4][h5] = 1e12 + 10;
}
}
}
}
}
dp[0][0][0][0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int h1 = k; h1 >= 0; h1--) {
for (int h2 = k; h2 >= 0; h2--) {
for (int h3 = k; h3 >= 0; h3--) {
for (int h4 = k; h4 >= 0; h4--) {
for (int h5 = k; h5 >= 0; h5--) {
int x1 = max(h1 - p[i][1], 0ll);
int x2 = max(h2 - p[i][2], 0ll);
int x3 = max(h3 - p[i][3], 0ll);
int x4 = max(h4 - p[i][4], 0ll);
int x5 = max(h5 - p[i][5], 0ll);
dp[h1][h2][h3][h4][h5] = min(dp[h1][h2][h3][h4][h5], dp[x1][x2][x3][x4][x5] + f[i]);
}
}
}
}
}
}
int d[6];
for (int i = 1; i <= 5; i++) {
if (i <= m) d[i] = k;
else d[i] = 0;
}
int res = dp[d[1]][d[2]][d[3]][d[4]][d[5]];
if (res == 1e12 + 10) res = -1;
cout << res;
return 0;
}
F - Vacation Query
难度: ⭐⭐⭐⭐
题目大意
给定一个由0/1组成的数列, 我们可以对其进行n次操作, 操作分为两种, 每种都给出一个区间, 一是输出这个区间中连续的1的最长长度; 二是将这个区间里的1变成0, 0变成1;
解题思路
很明显的一个线段树, 我们需要维护8个值: 区间边界: l, r; 翻转标记: t, 区间长度: k; 区间中最长连续1/0的长度: m1, m0; 区间前缀/后缀连续1的长度: l1, r1; 区间前缀/后缀连续0的长度: l0, r0; 需要维护前缀和后缀是因为方便合并区间时计算最长的连续1的长度;
build函数就不多说了, 正常写就行;
pushup函数中考虑区间合并, m1, m0, l1, r1, l0, r0都可能改变, 所以需要一个一个更新; 对于前缀连续1的长度L1, 如果左区间的l1的长度等于区间长度(也就是整个区间都是1), 那么L1就可以更新为左区间的长度加上右区间的l1; 否则的话就直接把L1赋值为左区间的l1即可; 其他的前缀和后缀都同理; 对于M1来说, 他有三种可能, 一是左区间的m1, 二是右区间的m1, 三是左区间的后缀1和右区间的前缀1所组成的新的连续的1; 三者取最大值即可, m0同理;
pushdown函数主要作用是区间翻转, 如果根区间的t=1说明左右区间都需要翻转, 首先把左右区间各自的翻转标记k取反, 然后把m1和m0, l1和l0, r1和r0都交换即可;
modify函数的作用也是区间翻转, 不同于之前线段树区间求和的板子, 本题需要找到具体的区间才能对其进行修改, 所以此处的写法不同于模板;
query函数变化最大, 不同于模板, 这里如果函数的返回值只返回一个数无法去求区间的连续1的最长长度, 所以我们让query函数的返回值设为结构体类型; 和modify函数一样我们需要找到准确的区间, 所以当给定区间横跨左右区间时我们需要构建一个新的节点, 这个节点的区间范围和给定的范围一致, 节点各项值的设置和pushdown函数一致;最后输出这个节点的m1即可;
神秘代码
#include<bits/stdc++.h>
//#define int l1ng l1ng
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 5e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx;
struct Node {
int l, r;
int t, k;
int m1, m0;
int l1, r1;
int l0, r0;
}stu[4 * N];
int f[N];
void Swap(Node& r1ot) {
swap(r1ot.m1, r1ot.m0);
swap(r1ot.l1, r1ot.l0);
swap(r1ot.r1, r1ot.r0);
}
void pushup(int u) {
Node& r1ot = stu[u], & left = stu[u << 1], & right = stu[u << 1 | 1];
if (left.l1 == left.k) {
r1ot.l1 = left.k + right.l1;
}
else r1ot.l1 = left.l1;
if (left.l0 == left.k) {
r1ot.l0 = left.k + right.l0;
}
else r1ot.l0 = left.l0;
if (right.r1 == right.k) {
r1ot.r1 = left.r1 + right.k;
}
else r1ot.r1 = right.r1;
if (right.r0 == right.k) {
r1ot.r0 = left.r0 + right.k;
}
else r1ot.r0 = right.r0;
r1ot.m1 = max(left.r1 + right.l1, max(left.m1, right.m1));
r1ot.m0 = max(left.r0 + right.l0, max(left.m0, right.m0));
}
void pushdown(int u) {
Node& r1ot = stu[u], & left = stu[u << 1], & right = stu[u << 1 | 1];
if (r1ot.t) {
left.t = !left.t;
right.t = !right.t;
Swap(left);
Swap(right);
r1ot.t = 0;
}
}
void build(int u, int l, int r) {
if (l == r) {
if (f[l] == 1) stu[u] = { l,r,0,1,1,0,1,1,0,0 };
else stu[u] = { l,r,0,1,0,1,0,0,1,1 };
}
else {
stu[u] = { l,r,0,r - l + 1 };
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 (stu[u].l == l && stu[u].r == r) {
stu[u].t = !stu[u].t;
Swap(stu[u]);
}
else {
pushdown(u);
int mid = stu[u].l + stu[u].r >> 1;
if (l > mid) modify(u << 1|1, l, r);
else if (r <= mid) modify(u << 1 , l, r);
else {
modify(u << 1, l, mid);
modify(u << 1 | 1, mid+1, r);
}
pushup(u);
}
}
Node query(int u, int l, int r) {
if (stu[u].l == l && stu[u].r == r) {
return stu[u];
}
pushdown(u);
int maxn = 0;
int mid = stu[u].l + stu[u].r >> 1;
Node left, right, x;
if (l > mid) {
return query(u << 1|1, l, r);
}
else if (r <= mid) {
return query(u << 1, l, r);
}
else {
left = query(u << 1, l, mid);
right = query(u << 1 | 1, mid+1, r);
Node r1ot = { left.l,right.r };
r1ot.k = left.k + right.k;
if (left.l1 == left.k) {
r1ot.l1 = left.k + right.l1;
}
else r1ot.l1 = left.l1;
if (left.l0 == left.k) {
r1ot.l0 = left.k + right.l0;
}
else r1ot.l0 = left.l0;
if (right.r1 == right.k) {
r1ot.r1 = left.r1 + right.k;
}
else r1ot.r1 = right.r1;
if (right.r0 == right.k) {
r1ot.r0 = left.r0 + right.k;
}
else r1ot.r0 = right.r0;
r1ot.m1 = max(left.r1 + right.l1, max(left.m1, right.m1));
r1ot.m0 = max(left.r0 + right.l0, max(left.m0, right.m0));
return r1ot;
}
}
signed main() {
string s;
cin >> n >> m >> s;
for (int i = 1; i <= n; i++) {
f[i] = s[i - 1] - '0';
}
build(1, 1, n);
while (m--) {
int a, l, r;
cin >> a >> l >> r;
if (a == 1) {
modify(1, l, r);
}
else {
cout << query(1, l, r).m1 << endl;
}
}
return 0;
}
- Beginner AtCoder Contest 322 abcbeginner atcoder contest 322 beginner atcoder contest abc 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