首页 > 代码库 > BZOJ1106: [POI2007]立方体大作战tet
BZOJ1106: [POI2007]立方体大作战tet
1106: [POI2007]立方体大作战tet
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 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
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
Source
题解：
又被坑了。。。
一直在想有什么算法能够根据数据来确定先换谁，在换谁。。。思路完全不对啊。。。
直接贪心的去换离得最近的木块即可
别人的题解：
首先如果对于两个相同数字的方块，如果他们之间还有可以配对的两个方块，显然先消掉中间的方块更优。
但是如果他们之间有k个无法配对的方块，我们就至少需 要k次交换消掉现在的这两块。我们就可以统计一下每两个相同的方块之间有多少无法配对的方块。可以用一个树状数组来维护……
orz。。。
代码：
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm>10 11 #include<iostream>12 13 #include<vector>14 15 #include<map>16 17 #include<set>18 19 #include<queue>20 21 #include<string>22 23 #define inf 100000000024 25 #define maxn 100000+100026 27 #define maxm 500+10028 29 #define eps 1e-1030 31 #define ll long long32 33 #define pa pair<int,int>34 35 #define for0(i,n) for(int i=0;i<=(n);i++)36 37 #define for1(i,n) for(int i=1;i<=(n);i++)38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)42 43 using namespace std;44 45 inline int read()46 47 {48 49 int x=0,f=1;char ch=getchar();50 51 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}52 53 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}54 55 return x*f;56 57 }58 int n,v[maxn],s[maxn];59 inline void add(int x,int y)60 {61 for(;x<=2*n;x+=x&(-x))s[x]+=y;62 }63 inline int sum(int x)64 {65 int t=0;66 for(;x;x-=x&(-x))t+=s[x];67 return t;68 }69 70 int main()71 72 {73 74 freopen("input.txt","r",stdin);75 76 freopen("output.txt","w",stdout);77 78 n=read();79 int ans=0;80 for1(i,2*n)81 {82 int x=read();83 if(!v[x]){v[x]=i;add(i,1);}84 else 85 {86 ans+=sum(i)-sum(v[x]-1)-1;87 add(v[x],-1);88 }89 } 90 printf("%d\n",ans); 91 92 return 0;93 94 }
BZOJ1106: [POI2007]立方体大作战tet
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。