BZOJ1106: [POI2007]立方体大作战tet

时间:2022-09-04 09:17:36

1106: [POI2007]立方体大作战tet

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 419  Solved: 302
[Submit][Status]

Description


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

Input


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

Output

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

Sample Input

样例输入1
5
5
2
3
1
4
1
4
3
5
2
样例输入2
3
1
2
3
1
2
3

Sample Output

样例输出1
2
样例输出2
3

HINT

BZOJ1106: [POI2007]立方体大作战tetBZOJ1106: [POI2007]立方体大作战tet

Source

题解:

又被坑了。。。

一直在想有什么算法能够根据数据来确定先换谁,在换谁。。。思路完全不对啊。。。

直接贪心的去换离得最近的木块即可

别人的题解:

首先如果对于两个相同数字的方块,如果他们之间还有可以配对的两个方块,显然先消掉中间的方块更优。

但是如果他们之间有k个无法配对的方块,我们就至少需 要k次交换消掉现在的这两块。我们就可以统计一下每两个相同的方块之间有多少无法配对的方块。可以用一个树状数组来维护……

orz。。。

代码:

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<string>

 #define inf 1000000000

 #define maxn 100000+1000

 #define maxm 500+100

 #define eps 1e-10

 #define ll long long

 #define pa pair<int,int>

 #define for0(i,n) for(int i=0;i<=(n);i++)

 #define for1(i,n) for(int i=1;i<=(n);i++)

 #define for2(i,x,y) for(int i=(x);i<=(y);i++)

 #define for3(i,x,y) for(int i=(x);i>=(y);i--)

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}

     return x*f;

 }
int n,v[maxn],s[maxn];
inline void add(int x,int y)
{
for(;x<=*n;x+=x&(-x))s[x]+=y;
}
inline int sum(int x)
{
int t=;
for(;x;x-=x&(-x))t+=s[x];
return t;
} int main() { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); n=read();
int ans=;
for1(i,*n)
{
int x=read();
if(!v[x]){v[x]=i;add(i,);}
else
{
ans+=sum(i)-sum(v[x]-)-;
add(v[x],-);
}
}
printf("%d\n",ans); return ; }

BZOJ1106: [POI2007]立方体大作战tet的更多相关文章

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

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

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

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

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

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

  4. BZOJ 1106&colon; &lbrack;POI2007&rsqb;立方体大作战tet 树状数组 &plus; 贪心

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

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

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

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

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

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

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

  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. Spring源码分析——BeanFactory体系之接口详细分析

    Spring的BeanFactory的继承体系堪称经典.这是众所周知的!作为Java程序员,不能错过! 前面的博文分析了Spring的Resource资源类Resouce.今天开始分析Spring的I ...

  2. Web API删除JSON格式的文件记录

    Insus.NET的系列Web Api学习文章,这篇算是计划中最后一篇了,删除JSON格式的文件记录.前一篇<Web Api其中的PUT功能演示>http://www.cnblogs.co ...

  3. 《HeadFirst设计模式》读后感——对学习设计模式的一些想法

    最近看完了<HeadFirst设计模式>,GOF的<设计模式——可复用面向对象软件的基础>的创建型模式也读完了,经历了从一无所知到茅塞顿开再到充满迷惑的过程. 不得不说< ...

  4. mahout中kmeans算法和Canopy算法实现原理

    本文讲一下mahout中kmeans算法和Canopy算法实现原理. 一. Kmeans是一个很经典的聚类算法,我想大家都非常熟悉.虽然算法较为简单,在实际应用中却可以有不错的效果:其算法原理也决定了 ...

  5. &num;pragma 预处理指令

    Linux C 编程一站式学习 #pragma 预处理指示供编译器实现一些非标准的特性,C 标准没有规定 #pragma 后面应该写什么以及起什么作用,由编译器自己规定.有的编译器用 #pragma ...

  6. JDK-windows7环境变量配置-亲测版本 以及HelloWorld

    1.下载并安装jdk,假设安装1.6.0_45版本到C:\Program Files\Java,则安装完毕后,目录结构为: C:\PROGRAM FILES\JAVA├─jdk1.6.0_45│ ├─ ...

  7. HDOJ--ACMSteps--2&period;1&period;8--Leftmost Digit-&lpar;取对数&comma;数学&rpar;

    Problem Description Given a positive integer N, you should output the leftmost digit of N^N. Input T ...

  8. UNIX环境高级编程——system V消息队列

    unix早期通信机制中的信号能够传送的信息量有限,管道则只能传送无格式字节流,这远远是不够的.     消息队列(也叫报文队列)客服了这些缺点:     消息队列就是一个消息的链表.     可以把消 ...

  9. Codeforces 1016G Appropriate Team 数论 FWT

    原文链接https://www.cnblogs.com/zhouzhendong/p/CF1016G.html 题目传送门 - CF1016G 题意 给定 $n,x,y$ ,以及一个含有 $n$ 个元 ...

  10. Java容器解析系列&lpar;6&rpar; Queue Deque AbstractQueue 详解

    首先我们来看一下Queue接口: /** * @since 1.5 */ public interface Queue<E> extends Collection<E> { / ...