hihoCoder 1233 : Boxes(盒子)

hihoCoder #1233 : Boxes(盒子)

时间限制:1000ms

单点时限:1000ms

内存限制:256MB


Description - 题目描述

  There is a strange storehouse in PKU. In this storehouse there are n slots for boxes, forming a line. In each slot you can pile up any amount of boxes. The limitation is that you can only pile a smaller one above a bigger one, in order to keep balance. The slots are numbered from 1 to n. The leftmost one is slot 1.

  At first there is exactly one box in each slot. The volume of the box in slot i is vi. As a virgo, you decide to sort these boxes by moving some of them. In each move you can choose a slot and move the top box in this slot to an adjacent slot (of course you can only put it on the top). You should ensure that the limitation mentioned above is still satisfied after this move. After the sort operation, there should be exactly one box in each slot, and for each pair of adjacent slots, the box in the left one should be smaller than the box in the right one.

  Your task is to calculate the minimum number of moves you need to sort the boxes.

PKU里有个奇怪的仓库。仓库里有n个连成一线的盒子槽。每个槽上可以叠堆人员数量的盒子。为了保持平衡,唯一的限制是:只能把小盒子放在大盒子上面。槽的编号为从1到n。最左边的槽为1。

开始时,每个槽都有一个盒子。槽i中盒子的体积为vi。作为处女座,你决定通过移动盒子来对其进行排序。每次移动时你都能选择一个槽,把顶部的盒子移动到相邻的槽(当然你还是只能放在顶部)。你需要确保移动后依然满足上述的限制。排序过后,每个槽都应有一个盒子,并且对于任意一对相邻的槽,左边的盒子要小于右边的盒子。

你的任务就是计算完成盒子排序的最少移动次数。

CN

Input - 输入

  In the first line there’s an integer T(T≤6000), indicating the number of test cases. The following 2T lines describe the test cases.

  In each test case, the first line contains an integer n, indicating the number of slots. The second line contains n integers v1,v2…vn, indicating the volume of the boxes. It is guaranteed that all vi in a test case are different.

  Please note that n<8,0≤vi≤104

第一行有一个整数T,表示测试用例的数量。随后有2T行的测试用例。

对于每组测试用例,第一行有一个整数n,表示槽的数量。第二行有n个整数 v1,v2 … vn,表示盒子的体积。保证一组用例中所有的vi都是不同的。

请注意n<8,0≤vi≤10^4

CN

Output - 输出

  For each test case, print a line containing one integer indicating the answer. If it’s impossible to sort the boxes, print -1.

对于每组测试用例,输出一行整数答案。如果无法完成盒子排序,输出-1。

CN

Sample Input - 样例输入

4
3
2 1 3
2
7 8
2
10000 1000
3
97 96 95

Sample Output - 样例输出

4
0
-1
20

题解

  开始时脑袋一抽冒了个2^(8*8)的状态表示,看到2^21后恍然大悟。 写完时没注意T,弄了个在线查询超时了……默默地改成打表

    压缩状态:

       [1--] [2--] [3--] [4--] [5--] [6--] [7--]

      最多7个数,把数字离散化成位置。

      用3位二进制标记第i小的数存放的位置,[0, 6]或[1, 7]的方式都差不多。 状态数2^(3*7)。

      (但是想了想为什么不把3位全用上,估计是因为2^(3*8)……)

    后面就是BFS打表,枚举所有情况。

后记:

打表刚刚写完的时候在本地的VS跑了2.5s的初始化,结果hihoCoder上居然A了?!哈?还只花了0.1s

吓得我以为hihoCoder用的是80GHz的CPU……

后面经过对比估计是VS和G++ STL的区别,VS不知道为什么这次queue特别低效。

经过稍微优化后也只能达到1.3s的初始化速度,G++基本为0.2s内初始化完成。

估计还是queue的锅,不知这速度差距是不是算得上BUG了。

代码 C++

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <queue>
 5 int n, ed, bit[8] = { 1 }, map[10005];
 6 unsigned int opt[2 << 21 | 1], data[8];
 7 std::queue<int> q;
 8
 9 int red(){
10     int now, tmp[8], i;
11     scanf("%d", &n);
12     for (i = 0; i < n; ++i) scanf("%d", data + i);
13     memcpy(tmp, data, sizeof data);
14     std::sort(tmp, tmp + n);
15     for (i = 0; i < n; ++i) map[tmp[i]] = i;
16     for (i = now = 0; i < n; ++i) now ^= bit[map[data[i]]] * (i + 1);
17     return now;
18 }
19
20 void setData(int d){
21     int i, j;
22     memset(data, -1, sizeof data);
23     for (i = 1; i <= n; ++i, d >>= 3){
24         if (~data[j = (d & 7) - 1]) continue;
25         data[j] = i;
26     }
27 }
28 void BFS(){
29     int now, nxt, i;
30     while (!q.empty()){
31         setData(now = q.front()); q.pop();
32         for (i = 0; i < n; ++i){
33             if (data[i] == -1) continue;
34             if (i < n - 1){
35                 if (data[i] < data[i + 1]){
36                     nxt = now + bit[data[i] - 1];
37                     if (opt[now] + 1 < opt[nxt]) opt[nxt] = opt[now] + 1, q.push(nxt);
38                 }
39             }
40             if (i > 0){
41                 if (data[i] < data[i - 1]){
42                     nxt = now - bit[data[i] - 1];
43                     if (opt[now] + 1 < opt[nxt]) opt[nxt] = opt[now] + 1, q.push(nxt);
44                 }
45             }
46         }
47     }
48 }
49 void rdy(){
50     memset(opt, -1, sizeof opt);
51     int now, i;
52     for (i = 1; i < 8; ++i) bit[i] = bit[i - 1] << 3;
53     for (i = now = 0; i < 7; n = ++i, BFS()){
54         q.push(now += bit[i] * (i + 1)); opt[now] = 0;
55     }
56 }
57
58 int main(){
59     rdy();
60     int t;
61     for (scanf("%d", &t); t--; printf("%d\n", opt[red()]));
62     return 0;
63 }
时间: 02-05

hihoCoder 1233 : Boxes(盒子)的相关文章

ACM学习历程—Hihocoder 1233 Boxes(bfs)(2015北京网赛)

hihoCoder挑战赛12 时间限制:1000ms 单点时限:1000ms 内存限制:256MB   描述 There is a strange storehouse in PKU. In this storehouse there are n slots for boxes, forming a line. In each slot you can pile up any amount of boxes. The limitation is that you can only pile a

hihocoder 1233 Boxes

题意:类汉诺塔的一个东西……移动规则与汉诺塔一样,但初始状态为题目中给出的每根棍上一个盘子,目标状态为盘子在棍上按大小顺序排列,盘子只能在相邻的棍儿上移动. 解法:广搜并打表记录从目标状态到所有可能的初始状态的答案.我记录每个盘子的位置为状态,vis用七位数组(被队友吐槽还真敢写啊=3=),然后每次转移状态的时候转化为每个棍儿上最小的盘子是啥(反正很抽象又不好解释……我懂就好啦哈哈哈哈哈哈哈哈哈哈(被队友嘲笑自暴自弃中)).答案的记录用转化为排列序数的方式. 代码: #include<stdio

第十四周 5.30 --- 6.5

新的一周 / w \ 大家都在图书馆看书..我在图书馆睡觉... 5.31 做cf 碰到一道 bfs 的题,想起这题还没有补 hiho 1233 Boxes 去年一神就教过我...可是又不会了.. 还是状态的表示没有想清楚,是每一个块的权值 乘以 位置的编号 表示一个状态 1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include&l

HDU 5810 Balls and Boxes(盒子与球)

HDU 5810 Balls and Boxes(盒子与球) Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Description 题目描述 Mr. Chopsticks is interested in random phenomena, and he conducts an experiment to study randomness. In the experiment

[Swift]LeetCode546. 移除盒子 | Remove Boxes

Given several boxes with different colors represented by different positive numbers. You may experience several rounds to remove boxes until there is no box left. Each time you can choose some continuous boxes with the same color (composed of k boxes

[LeetCode] Remove Boxes 移除盒子

Given several boxes with different colors represented by different positive numbers. You may experience several rounds to remove boxes until there is no box left. Each time you can choose some continuous boxes with the same color (composed of k boxes

Uva12657 (Boxes in a Line)移动盒子

UVA 12657 Boxes in a Line You have n boxes in a line on the table numbered 1 . . . n from left to right. Your task is to simulate 4kinds of commands:• 1 X Y : move box X to the left to Y (ignore this if X is already the left of Y )• 2 X Y : move box

深入理解CSS盒子模型

前言:前阵子在做一个项目时,在页面布局方面遇到了一点小问题,于是上stackoverflow上求助.ifaou在帮助我解决我问题的同时,还推荐我阅读一篇有关CSS盒子模型的文章<The CSS Box Model>,阅读之后受益匪浅,才知道自己对盒子模型知识还是如此欠缺.恰逢学期末,项目验收后暂时告一段落,有空闲的时间.于是想把这篇文章翻译出来,一方面再给自己一点挑战和锻炼,另一方面也给大家参考,让更多的人受益. 这篇文章适合初级web设计朋友,让你对盒子模型有更近一步的理解.但是在阅读这篇文

UVa 12657 Boxes in a Line(应用双链表)

Boxes in a Line You have n boxes in a line on the table numbered 1 . . . n from left to right. Your task is to simulate 4 kinds of commands: ? 1 X Y : move box X to the left to Y (ignore this if X is already the left of Y ) ? 2 X Y : move box X to th