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
Sample Output #1
2
Sample Input #2
3
1
2
3
1
2
3
Sample Output
3
Solution
假设要消去第i个和第j个方块,那么当这两个方块消去时,只会影响有一个元素在区(i,j)中的两个元素的距离。那么我们需要以一种方式去消去这些方块。在决定两种方块的消去顺序时,假设其对应区间为包含关系,那么显然先消去被包含的区间要更优。若两个区间仅存在交集,那么无论先消去哪两个都一样。如果两个区间的交集为空,那么消去顺序对答案没有影响。综上所述,我们得到如下贪心策略:每当遇到一个重复出现的元素时就消去它。每次消去的操作次数即为区间中还没有消去的元素个数,可以转化为区间和用树状数组维护。如果一个点上有元素就设为1,消去后变为0。
#include <iostream>
#include <cstdio>
#define N 50002
using namespace std;
int n,i,pos[N],c[N],ans;
int lowbit(int x)
{
return x&(-x);
}
void modify(int x,int y)
{
for(int i=x;i<=2*n;i+=lowbit(i)) c[i]+=y;
}
int sum(int x)
{
int ans=0;
for(int i=x;i>=1;i-=lowbit(i)) ans+=c[i];
return ans;
}
int main()
{
freopen("tet.in","r",stdin);
freopen("tet.out","w",stdout);
cin>>n;
for(i=1;i<=2*n;i++){
int x;
cin>>x;
if(pos[x]==0){
pos[x]=i;
modify(i,1);
}
else{
ans+=sum(i)-sum(pos[x]);
modify(pos[x],-1);
}
}
cout<<ans<<endl;
fclose(stdin);
fclose(stdout);
return 0;
}
Test 3.27 T1 立方体大作战的更多相关文章
-
[BZOJ1106][POI2007] Tet 立方体大作战
Description 一个叫做立方体大作战的游戏风靡整个Byteotia.这个游戏的规则是相当复杂的,所以我们只介绍他的简单规则:给定玩家一个有2n个元素的栈,元素一个叠一个地放置.这些元素拥有n个 ...
-
BZOJ1106: [POI2007]立方体大作战tet
1106: [POI2007]立方体大作战tet Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 419 Solved: 302[Submit][St ...
-
BZOJ 1106: [POI2007]立方体大作战tet
1106: [POI2007]立方体大作战tet Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 682 Solved: 496[Submit][St ...
-
BZOJ1106[POI2007]立方体大作战tet - 树状数组
描述 一个叫做立方体大作战的游戏风靡整个Byteotia.这个游戏的规则是相当复杂的,所以我们只介绍他的简单规则:给定玩家一个有2n个元素的栈,元素一个叠一个地放置.这些元素拥有n个不同的编号,每个编 ...
-
[BZOJ1106/POI2007]Tet立方体大作战
Description 一个叫做立方体大作战的游戏风靡整个Byteotia.这个游戏的规则是相当复杂的,所以我们只介绍他的简单规则:给定玩家一个有2n个元素的栈,元素一个叠一个地放置.这些元素拥有n个 ...
-
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 ...
-
Day6 - G - 立方体大作战tet HYSBZ - 1106
一个叫做立方体大作战的游戏风靡整个Byteotia.这个游戏的规则是相当复杂的,所以我们只介绍他的简单规则:给定玩家一个有2n个元素的栈,元素一个叠一个地放置.这些元素拥有n个不同的编号,每个编号正好 ...
-
[bzoj1106]立方体大作战
先贪心,容易发现如果两个点中间没有点对,那么一定可以先把这两个点消掉分析一下,就可以发现这样两个点的答案就是这两个点对中间不成对的点数量扫描过去,线段树维护每一个点的权值(是否会被算入答案)即可 1 ...
随机推荐
-
Enterprise Solution 虚拟测试环境
在不联网的情况下,一台物理电脑安装数据库服务,VMware创建多个虚拟机,虚拟机中多个客户端并发连接到物理主机.可共用同一个物理主机的数据库,也可以测试多用户并发等问题. 1 安装微软虚拟网卡.在控 ...
-
PackageManager使用
参考:http://www.linuxidc.com/Linux/2012-02/53072.htm Android系统为我们提供了很多服务管理类,包括ActivityManager.PowerMan ...
-
关于 Xcode bitcode 错误
关于 bitcode 报错 有类似上图关于bitcode的错误用以下方法解决:
-
Linux find example
find | xargs echo >> x1 find -exec echo {} \; >> x2 1.查找/var目录下属主为root并且属组为mail的所有文件:fin ...
-
Entity Framework Code First在Oracle下的伪实现
为什么要说是伪实现,因为还做不到类似MsSql中那样完全的功能.Oralce中的数据库还是要我们自己手动去创建的.这里,我们舍掉了Model First中的EDMX文件,自己在代码里面写模型与映射关系 ...
-
201521123057 《Java程序设计》 第8周学习总结
1. 本周学习总结 1.1 以你喜欢的方式(思维导图或其他)归纳总结集合与泛型相关内容 2. 书面作业 1.List中指定元素的删除(题目4-1) 1.1 实验总结 答:remove中注意应该使用eq ...
-
ubuntu下唤醒或休眠远程计算机
ubuntu让我明白,没有什么完美的东西,要想完美必须付出代价.要么花时间折腾,要么花时间赚钱买系统. 人生也是一样,所以不要期待什么完美.哪有那么好的人,在合适的时间合适的地点让你遇见,还对你有感觉 ...
-
CSS 水平居中和垂直居中
1.水平居中——行内元素 text-align: center; 2.水平居中——定宽块状元素 margin: auto,满足定宽和块状两个条件的元素是可以通过设置“左右margin”值为“auto” ...
-
HDU-3507 Print Article (斜率优化)
题目大意:将n个数分成若干个区间,每个区间的代价为区间和的平方加上一个常数m,求最小代价. 题目分析:定义状态dp(i)表示前 i 个数已经分好的最小代价,则状态转移方程为 dp(i)=min(dp( ...
-
Json中相同或者重复记录的值相加组成新的Json
var data = [ {"Networking": "WiFi", "count_value": "2000"}, ...