[BZOJ1106/POI2007]Tet立方体大作战

时间:2022-09-04 08:21:38

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

题解:简单观察可以得到一个结论:对于同一个数,相差的距离就是交换的次数。但是当然不是单纯的直接计算每个数的距离就行了,因为每一步操作可能影响后续的结果。故考虑用树状数组维护,每次找到每个数的第一个位置之后将其插入到树状数组;第二次出现之后,查询当前两个位置之间的距离,然后将该数从树状数组中删除。

代码:

-------------------------------------------------------------------------------------------------

#include <cstdio>
#define MAXN 100005

int n, x, a[MAXN], s[MAXN], ans;

int lowbit(int o) { return o & -o; }

void insert(int o, int x) { while (o <= n) s[o] += x, o += lowbit(o); }

int query(int o) { int res = 0; while (o) res += s[o], o -= lowbit(o); return res; }

int main()
{
  freopen("tet.in", "r", stdin);
  freopen("tet.out", "w", stdout);
  scanf("%d", &n), n <<= 1;
  for (int i = 1; i <= n; i++)
  {
    scanf("%d", &x);
    if (!a[x]) insert(i, 1), a[x] = i;
    else ans += query(i) - query(a[x]), insert(a[x], -1);
  }
  printf("%d", ans);
return 0;
}

-------------------------------------------------------------------------------------------------

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

  1. &lbrack;BZOJ1106&rsqb;&lbrack;POI2007&rsqb; Tet 立方体大作战

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

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

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

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

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

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

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

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

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

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

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

  7. Day6 - G - 立方体大作战tet HYSBZ - 1106

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

  8. Test 3&period;27 T1 立方体大作战

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

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

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

随机推荐

  1. Using python to process Big Data

    Pandas is a great lib to process BIg Data. 1) pandas.pivot_table(data,values=None,columns=None,aggfu ...

  2. iOS开发 UIWebView&plus;JavaScript 交互总结

    算是个人项目经验的,印象比较深的Web+JS交互的使用 iOS原生应用与Web页面元素交互方式有很多,JavaScriptCore.拦截协议.第三方框架WebViewJavaScriptBridge. ...

  3. 新霸哥带你进入java的世界

    新霸哥从近期大家的留言中注意到了大家对基础知识比较重视,很多的朋友希望多讲一些入门的知识,为了满足广大开发爱好者的需求,新霸哥决定从最基础的做起,一点一点的帮助大家一起走进云计算的世界.下面新霸哥首先 ...

  4. HTML5&plus;开发移动app教程3-mui开发示例

    下面就开始一个简答的例子,以及mui相关内容 mui 官网:http://dcloudio.github.io/mui/ 说明:http://dev.dcloud.net.cn/mui/ui/inde ...

  5. 移动web开发入门级

    http://www.infoq.com/cn/articles/development-of-the-mobile-web-deep-concept/

  6. System&period;Drawing&period;Graphics中比较重要的几个方法

    方法 常见参数 绘制的图形 DrawLine 钢笔.起点和终点 一段直线 DrawRectangle 钢笔.位置和大小 空心矩形 DrawEllipse 钢笔.位置和大小 空心椭圆 FillRecta ...

  7. Characterization of Dynkin diagrams

    Nowadays, I am reading D.J.Benson's nice book, volume I of Representations and cohomology. I found i ...

  8. 如何创建线程第一种继承Thread类

    步骤 1:定义一个类 继承Thread类.2:重写Thread类的run方法.3:直接创建Thread的子类对象创建线程.4:调用start方法开启线程并调用线程的任务run方法执行.-------- ...

  9. Chrome下解决本地异步请求失败的问题(Origin null is not allowed by Access-Control-Allow-Origin&period; )

    Chrome更新版本后发现打开本地Jquery easyui没有数据,查看控制台才发现如下问题解决的办法是设置启动参数"--allow-file-access-from-files&quot ...

  10. &lbrack;Winfrom&rsqb;Cefsharp配置与初始化

    摘要 在做客户端程序的时候,本来打算使用wpf的,但在内嵌cefsharp的时候,发现输入法有问题,所以使用了winform作为cefsharp的容器. 系列文章 CefSharp 在同一窗口打开链接 ...