BZOJ 1106: [POI2007]立方体大作战tet 树状数组 + 贪心

时间:2022-09-04 08:21:56

Description

  一个叫做立方体大作战的游戏风靡整个Byteotia。这个游戏的规则是相当复杂的,所以我们只介绍他的简单规
则:给定玩家一个有2n个元素的栈,元素一个叠一个地放置。这些元素拥有n个不同的编号,每个编号正好有两个
元素。玩家每次可以交换两个相邻的元素。如果在交换之后,两个相邻的元素编号相同,则将他们都从栈中移除,
所有在他们上面的元素都会掉落下来并且可以导致连锁反应。玩家的目标是用最少的步数将方块全部消除。

Input

  第一行包含一个正整数n(1<=n<=50000)。接下来2n行每行一个数ai,从上到下描述整个栈,保证每个数出现且
仅只出现两次(1<=ai<=n)。初始时,没有两个相同元素相邻。并且保证所有数据都能在1000000步以内出解。

Output

  第一行包含一个数m,表示最少的步数。

题解:

考虑当前要消掉数字 $i$, 出现的位置分别为 $arr[i],brr[i]$,不难发现 $arr[i]$ 到 $brr[i]$ 之间的数字一定会在过程中被消掉(这样一定是最有策略).
我们思考一下我们为了消掉 $i$ 所需要单独执行的操作数.
那么一定是 $arr[i]$ 到 $brr[i]$ 之间可以消掉的全都消掉后,没被消掉的数的个数.
树状数组维护一波前缀和即可.
第一次 +1, 第二次 -1 加加减减搞一搞即可.

#include<bits/stdc++.h>
#define setIO(s) freopen(s".in","r",stdin)
#define maxn 10000000
using namespace std;
int C[maxn],pos[maxn];
int n,m,ans=0;
int lowbit(int t) { return t & (-t); }
void update(int x,int d)
{
while(x <= m) C[x] += d, x += lowbit(x);
}
int query(int x)
{
int t=0;
while(x>0) t+=C[x], x -= lowbit(x);
return t;
}
int main()
{
// setIO("input");
scanf("%d",&n), m=(n<<1);
for(int i=1;i<=m;++i)
{
int a;
scanf("%d",&a);
if(!pos[a])
{
pos[a] = i;
update(i, 1);
}
else
{
ans += query(i) - query(pos[a]);
update(pos[a], -1);
}
}
printf("%d\n",ans);
return 0;
}

  

BZOJ 1106: [POI2007]立方体大作战tet 树状数组 + 贪心的更多相关文章

  1. bzoj 1106 &lbrack;POI2007&rsqb;立方体大作战tet 树状数组优化

    [POI2007]立方体大作战tet Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 821  Solved: 601[Submit][Status][ ...

  2. BZOJ1106&lbrack;POI2007&rsqb;立方体大作战tet - 树状数组

    描述 一个叫做立方体大作战的游戏风靡整个Byteotia.这个游戏的规则是相当复杂的,所以我们只介绍他的简单规则:给定玩家一个有2n个元素的栈,元素一个叠一个地放置.这些元素拥有n个不同的编号,每个编 ...

  3. BZOJ 1106&colon; &lbrack;POI2007&rsqb;立方体大作战tet

    1106: [POI2007]立方体大作战tet Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 682  Solved: 496[Submit][St ...

  4. BZOJ 1106 &lbrack;POI2007&rsqb;立方体大作战tet(树状数组)

    [题目链接] http://www.lydsy.com/JudgeOnline/problem.php?id=1106 [题目大意] 给定玩家一个有2n个元素的栈,元素一个叠一个地放置. 这些元素拥有 ...

  5. &lbrack;BZOJ 1106&rsqb; &lbrack;POI2007&rsqb; 立方体大作战tet 【树状数组】

    题目链接:BZOJ - 1106 题目分析 从1到2n枚举每一个位置. 如果枚举到某一个数,这个数已经是第二次出现,那么就看它和第一次出现的位置之间有多少数还没有被匹配,有多少没有匹配的就要进行多少次 ...

  6. 【BZOJ】1106&colon; &lbrack;POI2007&rsqb;立方体大作战tet

    题意 给定一个长度为\(2n(1 \le n \le 500000)\)的序列,\(1\)~\(n\)各出现两次,可以交换相邻两项,两个同样的数放在一起会对消,求把所有数对消的最小交换次数. 分析 如 ...

  7. BZOJ1106&colon; &lbrack;POI2007&rsqb;立方体大作战tet

    1106: [POI2007]立方体大作战tet Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 419  Solved: 302[Submit][St ...

  8. &lbrack;POI2007&rsqb;立方体大作战tet

    题目 BZOJ 洛谷 做法 很巧妙的题,注意每种颜色只有两个 消除一种颜色,其实就是看中间有多少个没有被消除的块,这种动态距离问题显然能用树状数组解决 洛谷输出方案,暴力往下爬就行 My comple ...

  9. bzj1106&colon; &lbrack;POI2007&rsqb;立方体大作战tet

    比较玄幻的题目. 考虑两个不同的元素 假设位置是 a...a...b...b... 那么不需要通过交换ab来消除ab,各自弄就行 若是 a...b...b...a... 那也没必要交换,先把b消掉就好 ...

随机推荐

  1. pip安装指定版本的package

    起因 最近到一个项目组,用了一套高大上的运维工具来搭建开发环境. 有vagrant控制VirtualBox启动虚拟机.有ansible来运行playbook初始化环境. 然后遇到了一个坑,项目现有的p ...

  2. php&lowbar;zip 类

    <?php /** * Created by PhpStorm. * User: StarZhan * Date: 2016/5/24 * Time: 12:04 */class PHPZip{ ...

  3. java 同步锁方法

    方法一:动态同步锁 class Demo_thread implements Runnable{ public static int sum = 0; public synchronized void ...

  4. 看懂UML类图和时序图

    看懂UML类图和时序图 这里不会将UML的各种元素都提到,我只想讲讲类图中各个类之间的关系: 能看懂类图中各个类之间的线条.箭头代表什么意思后,也就足够应对 日常的工作和交流: 同时,我们应该能将类图 ...

  5. Bootstrap--全局CSS样式之栅格系统

    Bootstrap 提供了一套响应式.移动设备优先的流式栅格系统,随着屏幕或视口(viewport)尺寸的增加,系统会自动分为最多12列.它包含了易于使用的预定义类,还有强大的mixin 用于生成更具 ...

  6. Laravel 中国 - 巨匠级PHP开发框架 Laravel 中国社区

    http://m.baidu.com/from=844b/bd_page_type=1/ssid=0/uid=3151E6C0905477A13653132D762BB6FB/pu=sz%401320 ...

  7. Android tcpdump抓包应用实现

    Android tcpdump抓包应用实现   Android应用很多时候都会涉及到网络,在请求网络出错时,我们可以通过抓包来分析网络请求,返回的数据等,通常我们是用tcpdump这个工具来抓包,再通 ...

  8. Confluence 6 编辑一个空间的配色方案

    空间默认继承全局的配色方案.但是,如果你是空间管理员的话,你可以对默认继承的全局方案进行调整,使用自定义的配色方案. 为一个空间修改配色方案: 进入空间后,然后从边栏的底部选择 空间工具(Space ...

  9. js事件处理

    1.js中常用的事件处理程序(event Handler) onabort 用户终止了页面的加载 onblur 用户离开了对象 onchange 用户修改了对象 onclick 用户点击了对象 one ...

  10. 第219天:Angular---过滤器

    在Angular中,过滤器的功能主要是格式化数据表达式,且可以自定义过滤器.作用域(scope)主要服务于页面模板,在控制器和页面中起桥梁作用,保存模板中的数据对象,为模板中的元素提供方法和属性. 一 ...