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
5
5
2
3
1
4
1
4
3
5
2
样例输入2
3
1
2
3
1
2
3
Sample Output
2
样例输出2
3
HINT
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的更多相关文章
-
BZOJ1106[POI2007]立方体大作战tet - 树状数组
描述 一个叫做立方体大作战的游戏风靡整个Byteotia.这个游戏的规则是相当复杂的,所以我们只介绍他的简单规则:给定玩家一个有2n个元素的栈,元素一个叠一个地放置.这些元素拥有n个不同的编号,每个编 ...
-
BZOJ 1106: [POI2007]立方体大作战tet
1106: [POI2007]立方体大作战tet Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 682 Solved: 496[Submit][St ...
-
bzoj 1106 [POI2007]立方体大作战tet 树状数组优化
[POI2007]立方体大作战tet Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 821 Solved: 601[Submit][Status][ ...
-
BZOJ 1106: [POI2007]立方体大作战tet 树状数组 + 贪心
Description 一个叫做立方体大作战的游戏风靡整个Byteotia.这个游戏的规则是相当复杂的,所以我们只介绍他的简单规 则:给定玩家一个有2n个元素的栈,元素一个叠一个地放置.这些元素拥有n ...
-
【BZOJ】1106: [POI2007]立方体大作战tet
题意 给定一个长度为\(2n(1 \le n \le 500000)\)的序列,\(1\)~\(n\)各出现两次,可以交换相邻两项,两个同样的数放在一起会对消,求把所有数对消的最小交换次数. 分析 如 ...
-
[BZOJ 1106] [POI2007] 立方体大作战tet 【树状数组】
题目链接:BZOJ - 1106 题目分析 从1到2n枚举每一个位置. 如果枚举到某一个数,这个数已经是第二次出现,那么就看它和第一次出现的位置之间有多少数还没有被匹配,有多少没有匹配的就要进行多少次 ...
-
BZOJ 1106 [POI2007]立方体大作战tet(树状数组)
[题目链接] http://www.lydsy.com/JudgeOnline/problem.php?id=1106 [题目大意] 给定玩家一个有2n个元素的栈,元素一个叠一个地放置. 这些元素拥有 ...
-
[POI2007]立方体大作战tet
题目 BZOJ 洛谷 做法 很巧妙的题,注意每种颜色只有两个 消除一种颜色,其实就是看中间有多少个没有被消除的块,这种动态距离问题显然能用树状数组解决 洛谷输出方案,暴力往下爬就行 My comple ...
-
bzj1106: [POI2007]立方体大作战tet
比较玄幻的题目. 考虑两个不同的元素 假设位置是 a...a...b...b... 那么不需要通过交换ab来消除ab,各自弄就行 若是 a...b...b...a... 那也没必要交换,先把b消掉就好 ...
随机推荐
-
Spring源码分析——BeanFactory体系之接口详细分析
Spring的BeanFactory的继承体系堪称经典.这是众所周知的!作为Java程序员,不能错过! 前面的博文分析了Spring的Resource资源类Resouce.今天开始分析Spring的I ...
-
Web API删除JSON格式的文件记录
Insus.NET的系列Web Api学习文章,这篇算是计划中最后一篇了,删除JSON格式的文件记录.前一篇<Web Api其中的PUT功能演示>http://www.cnblogs.co ...
-
《HeadFirst设计模式》读后感——对学习设计模式的一些想法
最近看完了<HeadFirst设计模式>,GOF的<设计模式——可复用面向对象软件的基础>的创建型模式也读完了,经历了从一无所知到茅塞顿开再到充满迷惑的过程. 不得不说< ...
-
mahout中kmeans算法和Canopy算法实现原理
本文讲一下mahout中kmeans算法和Canopy算法实现原理. 一. Kmeans是一个很经典的聚类算法,我想大家都非常熟悉.虽然算法较为简单,在实际应用中却可以有不错的效果:其算法原理也决定了 ...
-
#pragma 预处理指令
Linux C 编程一站式学习 #pragma 预处理指示供编译器实现一些非标准的特性,C 标准没有规定 #pragma 后面应该写什么以及起什么作用,由编译器自己规定.有的编译器用 #pragma ...
-
JDK-windows7环境变量配置-亲测版本 以及HelloWorld
1.下载并安装jdk,假设安装1.6.0_45版本到C:\Program Files\Java,则安装完毕后,目录结构为: C:\PROGRAM FILES\JAVA├─jdk1.6.0_45│ ├─ ...
-
HDOJ--ACMSteps--2.1.8--Leftmost Digit-(取对数,数学)
Problem Description Given a positive integer N, you should output the leftmost digit of N^N. Input T ...
-
UNIX环境高级编程——system V消息队列
unix早期通信机制中的信号能够传送的信息量有限,管道则只能传送无格式字节流,这远远是不够的. 消息队列(也叫报文队列)客服了这些缺点: 消息队列就是一个消息的链表. 可以把消 ...
-
Codeforces 1016G Appropriate Team 数论 FWT
原文链接https://www.cnblogs.com/zhouzhendong/p/CF1016G.html 题目传送门 - CF1016G 题意 给定 $n,x,y$ ,以及一个含有 $n$ 个元 ...
-
Java容器解析系列(6) Queue Deque AbstractQueue 详解
首先我们来看一下Queue接口: /** * @since 1.5 */ public interface Queue<E> extends Collection<E> { / ...