首页 > 代码库 > bzoj1106 [POI2007]立方体大作战tet
bzoj1106 [POI2007]立方体大作战tet
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
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
2
样例输出2
3
HINT
对于一个串，我们要把它的元素交换位置合并起来
对于合并，可以看成直接删除这两个元素，并且答案+=两者之间的距离
比如
直接从左往右读入，读到数字第一次出现的时候记录位置，第二次出现的时候直接和第一次合并掉。
这样的贪心证明是正确的：
1、假设有这样一个串12321，那么先合并两个2一定比先合并两个1更优
所以发现如果两对元素的位置是嵌套关系的话先删掉中间那对更优
2、假设又有123456712的串，要合并1、2，那么先合并1和先合并2是没有区别的
所以发现如果两对元素之间是有交集的话无论哪对先删都一样
3、显然如果两对元素之间没有交集的话肯定互不影响
综上，这样的贪心是正确的
最后只有用树状数组维护一下距离了
#include<cstdio>#define LL long longinline int read(){ int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}int n;LL ans;int c[100010];int mrk[100010];inline int lowbit(int x){return x&(-x);}inline void add(int x,int d){ for(int i=x;i<=2*n;i+=lowbit(i)) c[i]+=d;}inline int query(int x){ int s=0; for (int i=x;i;i-=lowbit(i)) s+=c[i]; return s;}int main(){ n=read(); for (int i=1;i<=2*n;i++) { int x=read(); if (mrk[x]) { ans+=(LL)query(i-1)-query(mrk[x]); add(mrk[x],-1); }else { mrk[x]=i; add(i,1); } } printf("%lld\n",ans); return 0;}
bzoj1106 [POI2007]立方体大作战tet
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。