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;
}