题目链接:The 2022 ICPC Asia Regionals Online Contest (I) (pintia.cn)
在PTA可以补题。
题意 / Problem
给定一个长度为N的01串,有Q次询问。
对于一个01串,每次可以代价为0的删除任意一个1以及和它相邻的两个数字,或者代价为1的将某个0翻转为1。
注意这个01串是环形的,也就是头尾相连,比如100也可以代价为0的进行一次删除,第1个数字的左边是第N个数字。
每次询问给定一个长度为3的倍数的区间\([l, r]\),问将这个区间组成的01串删除的最小代价。
思路 / Thought
先考虑对于一个长度为3的倍数的01串,至少需要多少代价能够删完。
考虑一下对于一个1,他可以0代价地带走3个数字,也就是1和它相邻的两个。但是可能出现连续的1,比如一个区间110000,就需要翻转一次,代价为1,因为不管用哪一个1去删除,都会带走一个1,所以我们称这两个连续的1,有效的1只有1个。
不难发现,对于任意一段连续的长度为x的1,有效的1个数为x / 2向上取整,也就是\(ceil(x * 1.0 / 2)\),当然在C++当中直接写(x + 1) / 2也是向上取整。
那么我们就是要维护一个区间的有效1的个数,对于这么多次的询问,可以用线段树来维护,但是并不是简单地记录“区间内有效1的个数”,因为这是一个环区间,所以应该拆分开来记录,将一个节点记录4个属性:{左连续1个数,除去左右连续1中间部分的有效1个数,右连续1个数,是否全部都是1}。
线段树记录下来之后通过query得到一个Node,再得到这个区间内完整的有效1个数,记录左右连续1是为了合并操作和计算环的完整的有效1个数。
难点在于节点的合并,需要分4中情况,分别是(普遍情况就是“非全1”的情况):
- 左节点全1,右节点全1
- 左节点全1,右节点普遍
- 左节点普遍,右节点全1
- 左节点普遍,右节点普遍
分这四种情况进行合并,每种情况的合并方法看代码吧。
在query得到一个区间的节点o之后,需要根据o是否是全1来判断有效1的个数,具体看代码里的实现。
最后就是计算了,假如有\(cnt\)个有效1,区间为\([l, r]\),那么代价应该是\(max(0, (r - l + 1) / 3 - cnt)\),其中\((r - l + 1) / 3\)表示需要的有效1个数,减去当前有的有效1个数,就是需要翻转的,也就是代价。
方法一代码 / Code 1
#include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 1e6 + 9; int a[maxn], N, Q; struct Node { int cl, c1, cr, all_one;//c1为除去左右连续1有效1的个数,cl, cr分别为左右连续1的个数 }tree[maxn * 4]; int f(int x){return (x + 1) / 2;} Node Merge(Node &a, Node &b) { if(a.all_one)//左全1 { if(b.all_one)//右全1 return {a.cl + b.cl, 0, a.cr + b.cr, 1}; else//右普遍 return {a.cl + b.cl, b.c1, b.cr, 0}; } else//左普遍 { if(b.all_one)//右全1 return {a.cl, a.c1, b.cr + a.cr, 0}; else//右普遍 return {a.cl, a.c1 + b.c1 + f(a.cr + b.cl), b.cr, 0}; } } void build(int s = 1,int e = N, int o = 1) { if(s == e)return tree[o] = (a[s] ? (Node){1, 0, 1, 1} : (Node){0, 0, 0, 0}), void(); int mid = (s + e) >> 1; build(s, mid, o << 1); build(mid + 1, e, o << 1 | 1); tree[o] = Merge(tree[o << 1], tree[o << 1 | 1]); } Node query(int l,int r,int s = 1, int e = N,int o = 1) { if(l <= s && e <= r)return tree[o]; int mid = (s + e) >> 1; if(r <= mid)return query(l, r, s, mid, o << 1); else if(l > mid)return query(l, r, mid + 1, e, o << 1 | 1); auto res1 = query(l, r, s, mid, o << 1); auto res2 = query(l, r, mid + 1, e, o << 1 | 1); return Merge(res1, res2); } signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> N >> Q; char s[maxn];cin >> s + 1; for(int i = 1;i <= N; ++ i)a[i] = s[i] ^ 48; build(); while(Q --) { int l, r;cin >> l >> r; auto o = query(l, r); int cnt1 = o.cl == r - l + 1 ? f(o.cl) : o.c1 + f(o.cl + o.cr); cout << max(0LL, (r - l + 1 - cnt1 * 3 + 2) / 3) << '\n'; } return 0; }
因为并不需要修改,只需要维护区间的特殊的和,所以用前缀和维护也可以,并且速度比线段树快几倍。
方法二代码 / Code 2
#include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 1e6 + 9; int a[maxn], pre[maxn], lst[maxn], prefix[maxn], N, Q; int f(int x){return (x + 1) / 2;} signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> N >> Q; char s[maxn];cin >> s + 1; for(int i = 1;i <= N; ++ i)a[i] = s[i] ^ 48; for(int i = 1, j = 0, k = 0;i <= N; ++ i) { if(!a[i])prefix[i] = prefix[pre[i - 1]] + f(k), j = i, k = 0; else ++ k; pre[i] = j; } for(int i = N, j = N + 1;i >= 1; -- i) { if(!a[i])j = i; lst[i] = j; } while(Q --) { int l, r;cin >> l >> r; int cnt1 = min(f(r - l + 1), prefix[pre[r]] - prefix[lst[l]] + f(r - pre[r] + lst[l] - l)); cout << max(0LL, (r - l - cnt1 * 3 + 3) / 3) << '\n'; } return 0; }
Comments 4 条评论
我感觉你这个线段树写的有问题,万一删除后合并的话,有效1会变化的,可能会减一
@采集一直 给定一个区间的有效1就可以直接O(1)算出答案了,不用考虑具体的“删除-合并”的过程。
虽然不太理解,但是我想通了,因为如果删除导致的合并会使得不能全部删除完,那么我肯定不会让它们合并(连续的1),做出最优的答案
@采集一直 嗯嗯