2022ICPC亚洲网络选拔赛A.01 Sequence(线段树 | 前缀和)

发布于 2022-09-18  1099 次阅读


题目链接: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;
}
19岁,性别未知,ACM-XCPC退役选手,CCPC全国邀请赛金牌,ICPC亚洲区域赛银牌,武汉某院校计算机科学与技术专业本科在读。
最后更新于 2022-09-19