+--------------------------------------------------------------------------------------+
* 比赛所有题目的内存限制都是512MB。
* 所有题目均以最后一次提交为准，请避免编译错误。
* 详细帮助请参阅https://vijos.org/wiki/help#contest
* 比赛结束前均可在比赛页面右边点击参加比赛来参与比赛。
* c/c++选手请慎用cin cout, 评测机为Windows Server 2008 R2 对于64位整数, 可以采用%I64d输出.
+----------------------
* 第二题中: 二维魔方 被认为是3X3的方格.
* 第三题中: 满足: 1 <= P , Q , T[] <= 50为整数.
* 22:11 比赛已经结束, 稍后将开始评测.
* 22:12 题解在某一楼层中给出了.
* 22:14 最后送给大家Schubert的歌剧一则: http://pan.baidu.com/s/1kTJuAv9, 感谢大家今晚的参与.
* 22:28 twd消失了,我们正在尝试联系他,我们没有能力触发评测.
* 22:35 以及还有一道题目的数据上传错误了.
* 22:51 重测了赛后提交的数据错误的题目.
* 次日09:01 我们至今也没有联系上twd, 所以依然没有开始昨晚的评测.
* 次日09:38 twd2昨天晚上睡得比较早! 现在twd2回来了! 评测已经开始, 给您带来的不便请谅解TAT
* 次日10:29 评测结束啦！
* 次日10:43 我们发现数据有一些问题，正在修改，准备重测。
* 次日12:12 最终成绩已经揭晓suiyuan200以270分位居榜首.
+-----------------------------------
题解:
(1).第一题,只要按照题目要求去检查一下就可以了,没有什么可以多说的.
(2).第二题,因为询问非常多,我们尝试预处理BFS一次,然后直接输出答案.
(3).简单的动态规划构建出有向图,之后问题等价于最小树形图,zhu-liu算法即可解决这一题.
(4).我们有一个结论:对于最后的交换方法,必然能找到一个断点,使得没有交换会跨过这个断点.有了这个结论,枚举断点的位置,再维护一下逆序对即可.
+--------------------------------------------------------------------------------------+
109 条评论
-
Gary1999 LV 8 @ 2014-10-31 20:13:19
话说第三题的话每个文件的长度都是一样的吗？
-
@ 2014-10-31 20:15:12
不一样。。
-
@ 2014-10-31 20:15:28
不一定一样
-
@ 2014-10-31 20:20:06
orz
-
-
@ 2014-10-31 20:12:48
orz
-
@ 2014-10-31 20:07:33
orzzzzzz表示还行 比Towerlight出的简单（至少会第一题！）
-
@ 2014-10-31 20:41:30
至少会t2，t3暴搜
-
-
@ 2014-10-31 19:57:33
完了完了，大概就会第一题了
-
@ 2014-10-31 20:28:46
Orz
-
-
@ 2014-10-31 19:56:59
听人说小岛出的模拟赛比较简单就屁颠屁颠地来了
第一题给残了 第二题给跪了 第三题给晕了 第四题额
orzorzorz -
@ 2014-10-31 19:56:52
求第二题样例解释
-
@ 2014-10-31 19:58:39
就是就是...doc你在哪...ToT
-
@ 2014-10-31 20:01:53
自己手算下吧.
-
-
@ 2014-10-31 19:55:48
cout<<Too Difficult<<endl;
-
@ 2014-10-31 20:21:02
引号没打0.0
-
@ 2014-10-31 20:35:48
╭══╮╭══╮╭══╮
║╭╮║║╭╮║╰═╮║
║║║║║╰╯║ ╭╯╯
║║║║║╭╭╯╭╯╯
║╰╯║║║╰╮║╰═╮
╰══╯╰╯╰╯╰══╯
-
-
@ 2014-10-31 19:53:40
Orz doc
-
@ 2014-10-31 19:51:33
请问什么叫二叉排序树的升序？什么叫二叉排序树的降序？？
-
@ 2014-10-31 20:03:25
左<根<右
和
左>根>右
-
@ 2014-10-31 20:10:22
不能等于嘛？
-
@ 2014-10-31 20:16:23
谢谢doc
-
@ 2014-10-31 20:16:48
你自己看题.
-
@ 2014-10-31 20:33:04
这里需要注意: 大根堆小根堆都是堆, 按照升序按照降序得到的二叉排序树都是二叉排序树.....也就是说堆里面可以有两个相等的元素，但是bst里必须是严格递增或严格递减的咯？。。
-
@ 2014-10-31 20:33:58
原数列是一个排列
-
@ 2014-10-31 20:39:00
我这个不认真审题的弱渣真心该抽。。
-
-
@ 2014-10-31 19:39:29
第一题可以取等吗，还有输出要不要带"#Case i: "。。。
-
@ 2014-10-31 20:02:42
要求格式必须是Case #X: SSS, 你直接copy样例输出就可以了
-
-
@ 2014-10-31 19:32:12
艹，看错时间了，7:00才上机的，到现在才做俩题。。。233
-
@ 2014-10-31 19:33:12
Orzzzzzzzzzz
-
@ 2014-10-31 19:33:45
Orz
-
@ 2014-10-31 19:41:03
orz...
-
@ 2014-10-31 19:44:33
orz
-
@ 2014-10-31 19:47:40
有木有正确率，Orz啥
-
@ 2014-10-31 19:57:48
六点准时上机，到现在做了一题...
-
-
@ 2014-10-31 19:27:52
第二题的“轮换”只能向一个方向轮换还是可以向两个方向轮换 比如第一列从上到下为3 6 9 直接轮换成9 3 6 是不是合法的？
-
@ 2014-10-31 19:28:40
合法啊。。。。（什么方向都可以的）
-
-
@ 2014-10-31 19:21:59
噗排版已死 *会被markdown识别成*斜体*的说
-
@ 2014-10-31 19:24:04
所以我用了汉字
-
@ 2014-10-31 19:25:33
2333333333
-
@ 2014-10-31 19:25:49
OAO看到题目中提到的好吃的表示刚从食堂出来后又感觉饿了
-
@ 2014-10-31 20:17:10
嘿嘿 >_<
-
-
@ 2014-10-31 19:18:36
bst是指通常的左子树小右子树大那种的bst吗？。。
-
@ 2014-10-31 19:24:27
题目中说: 这里需要注意: 大根堆小根堆都是堆, 按照升序按照降序得到的二叉排序树都是二叉排序树.
-
-
@ 2014-10-31 19:18:21
能解释一下第二题样例吗？
-
@ 2014-10-31 19:26:00
同————————问
-
@ 2014-10-31 19:37:18
草稿纸上弄弄就可以了。。这个问题bfs类似八数码难题。。但是却有12个子状态和多组数据。。然后我放弃了。。╮(╯▽╰)╭
-
@ 2014-10-31 19:53:40
...doc人呢 TAT
-
@ 2014-10-31 20:06:10
自己手算下就可以了.
-
-
@ 2014-10-31 19:13:48
orz
-
@ 2014-10-31 19:05:27
orz
-
@ 2014-10-31 18:51:59
orz
-
@ 2014-10-31 18:50:54
哈哈哈太搞笑了题目太搞笑了哈哈哈
-
@ 2014-10-31 18:45:00
召唤doc。。。。
S.O.S-
@ 2014-10-31 19:08:58
我在.
-
-
@ 2014-10-31 18:41:19
doc暂时消失了似乎= =（不会又去陪学姐了吧…………
所以一切问题以最后doc的解释为准…………PS：欢迎立剁手flag。
-
@ 2014-10-31 19:16:45
其实也没有什么要解释的, 除了第四题里面有错别字, 其余所有的问题都可以在题目中找到回答.
真要说: 无可奉告也不是不可以. -
@ 2014-10-31 19:27:58
就是就是。。。看题都太不仔细了。。。
-
-
@ 2014-10-31 18:33:46
第一题可不可以这样打印
writeln('Case #',i,': Both');
i是询问的次数-
@ 2014-10-31 19:09:09
似乎是可以的.
-
-
@ 2014-10-31 18:33:17
第一题是否保证n=2^d-1
-
@ 2014-10-31 18:41:50
应该不保证。
-
@ 2014-10-31 18:43:10
看错了以为是满二叉树。。。
-
@ 2014-10-31 19:09:27
不保证.
-
-
@ 2014-10-31 18:29:25
被难度骗了。。。Orz
-
@ 2014-10-31 18:23:34
第一题要求严格大根堆吗？
相等算不算堆？
BST呢？-
@ 2014-10-31 18:26:04
第一行一个整数T, 表示总的询问次数.
之后有T次询问, 对于每一次询问, 第一行有一个整数N, 表示给定的完全二叉树中的结点个数, 之后一行给出了一组__[1..N]的排列A[1],...,A[N]__, 依次表示树上每一个结点i的权值.
我们假定下标i所对应的结点为根, 其左右子结点的下标分别为2i和2i+1所以权值互不相同。。。。
-
@ 2014-10-31 18:27:58
输入是1-n的排列，没有相等的数
-
@ 2014-10-31 18:40:33
应该小根堆也可以的…………但是出题人消失了= =
-
@ 2014-10-31 19:09:52
我题目写了的, 大根小根都是堆
-
@ 2014-10-31 20:24:04
？？ 堆的权值可以相同吧，，为什么说互不相同，，，，
-
-
@ 2014-10-31 18:20:59
第一题case #i：这个冒号后面有空格吗
-
@ 2014-10-31 18:26:24
根据样例是有的。。。
-
@ 2014-10-31 18:32:19
同问
-
@ 2014-10-31 19:18:50
有空格. 一个空格.
-
-
@ 2014-10-31 18:20:59
学姐好痛苦啊，吃个东西还得做题，2333~~~不幸福
-
@ 2014-10-31 19:19:02
=_=
-
-
@ 2014-10-31 18:14:56
第一题Ai范围？
-
@ 2014-10-31 18:20:38
第一行一个整数T, 表示总的询问次数.
之后有T次询问, 对于每一次询问, 第一行有一个整数N, 表示给定的完全二叉树中的结点个数, 之后一行给出了一组__[1..N]的排列A[1],...,A[N]__, 依次表示树上每一个结点i的权值.
我们假定下标i所对应的结点为根, 其左右子结点的下标分别为2i和2i+1. -
@ 2014-10-31 18:21:13
应该是0<=Ai<=10^9吧……
-
@ 2014-10-31 18:22:04
N<=1000
-
@ 2014-10-31 18:23:30
所以A[i]<=1000
-
@ 2014-10-31 19:10:18
A的范围就是N的范围, 因为是排列.
-
-
@ 2014-10-31 18:12:55
T1 的树根 是任意的一个结点吗？
-
@ 2014-10-31 18:15:19
应该都是1号结点吧
-
@ 2014-10-31 18:20:37
是吗？
-
@ 2014-10-31 18:21:30
根据样例，，，是的。。。
-
@ 2014-10-31 18:21:39
是的
-
@ 2014-10-31 18:44:24
“是的”指的是什么。。
-
@ 2014-10-31 19:10:30
题目写了, 1号点是根
-
-
@ 2014-10-31 18:11:24
第一题是严格升序还是？？？
-
@ 2014-10-31 18:20:26
第一行一个整数T, 表示总的询问次数.
之后有T次询问, 对于每一次询问, 第一行有一个整数N, 表示给定的完全二叉树中的结点个数, 之后一行给出了一组__[1..N]的排列A[1],...,A[N]__, 依次表示树上每一个结点i的权值.
我们假定下标i所对应的结点为根, 其左右子结点的下标分别为2i和2i+1. -
@ 2014-10-31 19:10:45
题目写了, 升序降序都可以
-
-
@ 2014-10-31 18:05:26
第三题题目打错了“潘泽”应改为“盘子”
-
@ 2014-10-31 19:10:58
多谢提醒
-
-
@ 2014-10-31 17:07:07
Orz求大腿
-
@ 2014-10-31 16:18:23
Orz
-
@ 2014-10-31 13:16:45
zhangdashi出现了，他说不AK剁手，，他今年可是金牌实力
-
@ 2014-11-01 14:46:03
直播剁手。。。。
orz爆0大神
-
-
@ 2014-10-30 22:02:23
#include<orz>
using namespace std;
int main()
{
int rp=orz;
rp++;
return orz;
} -
@ 2014-10-30 11:36:27
Orz
-
@ 2014-10-30 11:07:31
Orz
-
@ 2014-10-29 21:40:59
再也不来VJ的比赛找虐了QAQ
-
@ 2014-10-29 22:14:02
orz
-
-
@ 2014-10-29 21:12:22
orz
-
@ 2014-10-29 20:51:37
萌萌哒zhangdashi说他要AK zhangdashi可是初二银牌的神犇
-
@ 2014-10-29 20:32:18
Orz
-
@ 2014-10-29 15:31:58
@咸博文 RP++
-
@ 2014-10-29 15:31:41
Rp++
-
@ 2014-10-29 15:31:35
Orz
-
@ 2014-10-29 12:41:49
T T报了名才反应过来周五晚上有自习T T
-
@ 2014-10-30 16:22:26
我也是ORZ
-
@ 2014-10-30 16:23:24
话说报了名不参加会不会掉RP QAQ
-
-
@ 2014-10-28 19:00:18
1 mol orz
-
@ 2014-10-28 18:29:44
orzorz
-
@ 2014-10-28 18:28:07
orz
-
@ 2014-10-28 17:17:49
orz
-
@ 2014-10-28 17:26:33
orz
-
-
@ 2014-10-28 16:56:03
orz
