ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

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

2022年9月18日 695点热度 5人点赞 4条评论

题目链接: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;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ icpc 前缀和 算法竞赛 线段树
最后更新:2022年9月19日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

  • 采集一直

    我感觉你这个线段树写的有问题,万一删除后合并的话,有效1会变化的,可能会减一

    2022年9月26日
    回复
    • Eriktse

      @采集一直 给定一个区间的有效1就可以直接O(1)算出答案了,不用考虑具体的“删除-合并”的过程。

      2022年9月27日
      回复
  • 采集一直

    虽然不太理解,但是我想通了,因为如果删除导致的合并会使得不能全部删除完,那么我肯定不会让它们合并(连续的1),做出最优的答案

    2022年9月27日
    回复
    • Eriktse

      @采集一直 嗯嗯

      2022年9月29日
      回复
  • 取消回复

    Eriktse

    18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

    文章目录
    • 题意 / Problem
    • 思路 / Thought
    • 方法一代码 / Code 1
    • 方法二代码 / Code 2

    友情链接 | 站点地图

    COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

    Theme Kratos | Hosted In TENCENT CLOUD

    赣ICP备2022001555号-1

    赣公网安备 36092402000057号