NOIP模拟赛之周五的夜晚

Vijos
twd2 LV 9 MOD @ 2014-10-27 20:54:38

+--------------------------------------------------------------------------------------+

* 比赛所有题目的内存限制都是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).我们有一个结论:对于最后的交换方法,必然能找到一个断点,使得没有交换会跨过这个断点.有了这个结论,枚举断点的位置,再维护一下逆序对即可.
+--------------------------------------------------------------------------------------+

逍遥哥哥 LV 7 @ 2014-11-01 22:25:38

qiu ti jie~~
东方幻想 LV 8 @ 2014-11-01 17:36:57

好吧，我承认我眼拙了，大神表激动，只是心里有点不爽...
第七维度丶 LV 9 @ 2014-11-01 17:02:40

@twd2 请问什么时候加昨天比赛题的RP 我本来是2000RP的结果不知道为什么降了一点强迫症啊啊啊啊
圈圈烤企鹅 LV 10 @ 2014-11-01 16:29:57

第一题竟然ac了=。=。。本来看着爆0我那个蛋疼哇。。
- 第七维度丶 LV 9 @ 2014-11-01 17:01:17
  
  我爆0了不过我刚刚改了一下 AC了看我发的题解哈哈
LYT954073084 LV 10 @ 2014-11-01 16:27:48

第一题数据坑爹。。。
- LYT954073084 LV 10 @ 2014-11-01 16:32:56
  
  我算了中序遍历
  int find1()
  {
  for(int i=1;i<=n;i++)
  if(k[i]!=i)
  return 0;
  return 1;
  }
  int find2()
  {
  for(int i=n;i>=1;i--)
  if(k[i]!=i)
  return 0;
  return 1;
  }
  结果爆零了。。。
  改成
  int find1()
  {
  for(int i=1;i<n;i++)
  if(k[i]>k[i+1])
  return 0;
  return 1;
  }
  int find2()
  {
  for(int i=1;i<n;i++)
  if(k[i]<k[i+1])
  return 0;
  return 1;
  }
  就AC了
- LYT954073084 LV 10 @ 2014-11-01 16:33:49
  
  说明a[1]~a[N]根本不是1~N的排列好不好
- LYT954073084 LV 10 @ 2014-11-01 16:34:24
  
  吊打出题人。。。
  吊打吊打。。。。。。。。。。
The_Dawn LV 7 @ 2014-11-01 16:07:46

有没有标程或题解啊
sunflower LV 9 @ 2014-11-01 15:19:34

第二题的时间到底是多少。。。
- sunflower LV 9 @ 2014-11-01 15:22:08
  
  为什么是5秒。。。比赛的时候题目里不说。。。
- LYT954073084 LV 10 @ 2014-11-01 15:22:36
  
  +1
- LYT954073084 LV 10 @ 2014-11-01 15:24:12
  
  为什么不先告诉我们。。。。
  标程都用了1S+呀。。。。
  出题人吊起来-------打
- 圈圈烤企鹅 LV 10 @ 2014-11-01 17:47:17
  
  我靠。。
零浅忧 LV 7 @ 2014-11-01 14:33:29

弱弱的问一句二叉排序树的话，只要就可以每个节点满足大于左子树小于右子树或小于左子树大于右子树，还是必须满足中序遍历有序？！orz！看了个题解只满足每个节点大于左子树小于右子树或小于左子树大于右子树，竟然AC了，难道二叉排序树不应该是中序遍历有序么？
罐装小倪 LV 7 @ 2014-11-01 13:08:27

第一次来vijos看到第一道题还得百度堆和二叉排序树的概念，我是不是太弱了XWX
prwang LV 8 @ 2014-11-01 13:03:12

蒟蒟蒟蒟蒟蒟蒟蒟蒟蒟蒟蒟蒟蒻orz第二题题解没看懂orzorzorz
什么叫一次bfs处理出全部答案？蒟蒟蒟蒟蒟蒟蒟蒟蒟蒟蒟蒟蒟蒻实在是不会，各位大神能不能讲具体一点或者给个程序什么的orzorzorzorz
twd2 LV 9 MOD @ 2014-11-01 11:17:24

其实就是第一题数据有问题
- The_Dawn LV 7 @ 2014-11-01 11:38:21
  
  好吧，我是错的第4题，错怪了，能给下第四题的数据么、、、
- twd2 LV 9 MOD @ 2014-11-01 11:40:18
  
  一般不给数据的
The_Dawn LV 7 @ 2014-11-01 11:10:40

。。。。我调了一早上了，你告诉我数据错了。。。。。。
自己想了几十个数据。。。。
- twd2 LV 9 MOD @ 2014-11-01 11:16:58
  
  orz
twd2 LV 9 MOD @ 2014-11-01 10:42:57

我们发现数据有一些问题，正在修改，准备重测。
- 圈圈烤企鹅 LV 10 @ 2014-11-01 10:44:08
  
  。。。。。。。。。。。。。。
- The_Dawn LV 7 @ 2014-11-01 11:10:55
  
  。。。。我调了一早上了，你告诉我数据错了。。。。。。
  自己想了几十个数据。。。。
1756500824 LV 10 @ 2014-11-01 10:36:33

第一题强烈抗议！快速读入超时，以后能不能不这么坑！！！
- Sluqy671 LV 10 @ 2014-11-01 10:44:27
  
  +1
- LYT954073084 LV 10 @ 2014-11-01 15:27:08
  
  +10086
twd2 LV 9 MOD @ 2014-11-01 10:28:49

评测结束啦！
第七维度丶 LV 9 @ 2014-11-01 10:27:16

评测开始了么- - 如果我第一题爆0我建议把twd2吊起来打 →→
- twd2 LV 9 MOD @ 2014-11-01 10:28:27
  
  为什么呀
- 第七维度丶 LV 9 @ 2014-11-01 11:27:25
  
  因为昨晚大神们都说要把你吊起来打啊→→
- twd2 LV 9 MOD @ 2014-11-01 11:36:42
  
  妈呀
- LYT954073084 LV 10 @ 2014-11-01 15:27:33
  
  对，吊起来打
- 圈圈烤企鹅 LV 10 @ 2014-11-01 16:35:59
  
  打！打！。。昨晚我熬着夜等结果。。等到凌晨终于等不下去了！！！我靠第二天我们上课那个困啊！！。。
The_Dawn LV 7 @ 2014-11-01 10:24:08

uses
math;
var //int64
i,p,pp,m,n:longint;
ans:int64;
s:ansistring;
sum:array[0..300000]of int64;
a,b,c,d:array[0..300000]of int64;
function f(x:longint):int64;
var
count,num:int64;
begin
count:=b[x];
num:=d[x];
f:=abs(num-x*count)-sum[count-1];
count:=b[n]-b[x];
num:=d[n]-d[x];
f:=f+abs(num-x*count)-sum[count];
end;

begin
readln(pp);
for i:=1 to 100000 do
sum[i]:=sum[i-1]+i;
for p:=1 to pp do
begin
fillchar(c,sizeof(c),0);

readln(s);
m:=0;
n:=length(s);
for i:=1 to n do
if s[i]='1' then
begin
inc(m);
a[m]:=1;
end
else if s[i]='0' then
begin
inc(m);
a[m]:=0; //读入
end;
n:=m;

for i:=1 to n do
if a[i]=1 then c[i]:=i; //求c数组
for i:=1 to n do
d[i]:=d[i-1]+c[i]; //c数组的前缀和

for i:=1 to n do //a数组的前缀和
b[i]:=b[i-1]+a[i];
m:=b[n];

ans:=maxlongint;
for i:=1 to n do
ans:=min(ans,f(i)); //枚举中间值

fillchar(c,sizeof(c),0);
for i:=1 to n do
if a[i]=1 then a[i]:=0 else a[i]:=1; //颠倒

for i:=1 to n do
if a[i]=1 then c[i]:=i;
for i:=1 to n do
d[i]:=d[i-1]+c[i];

for i:=1 to n do
b[i]:=b[i-1]+a[i];
m:=b[n];

for i:=1 to n do
ans:=min(ans,f(i));
write('Case #',p,': ');
writeln(ans);
end;

end.
第四题，自己测了无数次，编了很多数据，还是一个点都没过，，，，，求数据啊doc @doc
twd2 LV 9 MOD @ 2014-11-01 09:38:25

twd2昨天晚上睡得比较早! 现在twd2回来了! 评测已经开始, 给您带来的不便请谅解TAT
- 时光机 LV 8 @ 2014-11-01 10:17:29
  
  能给一下第4个点的数据吗？
  我的程序评测的时候出现了奇怪的问题
  
  原本读入是这样的：
  c++ int scan(){int i=0;scanf("%d",&i);return i;} n = scan();
  只有50分
  改成
  c++ scanf("%d",&n);
  就过了
  WA：
  https://vijos.org/records/545440e917f3ca29148ecbfb
  AC：
  https://vijos.org/records/5454411417f3caad128ecbfc
- twd2 LV 9 MOD @ 2014-11-01 10:45:15
  
  应该是数据有问题。
asd130530asd LV 8 @ 2014-11-01 08:48:41

强烈建议发布数据和std！
- Towerlight LV 10 @ 2014-11-01 09:04:32
  
  有那堆抄std的****玩意我下次怎么也不会发std了。
- asd130530asd LV 8 @ 2014-11-01 09:15:11
  
  抄std能干嘛......
dark邪君 LV 5 @ 2014-11-01 08:01:25

百度说二叉排序树是左子树上左右节点都要小于根，但答案好像是按照只要左子节点<根<右子结点或反过来就算是二叉排序树来判断
- Lytning LV 8 @ 2014-11-01 08:38:23
  
  @doc
- sunflower LV 9 @ 2014-11-01 09:23:56
  
  数据也符合正常的二叉排序树
于—归 LV 3 @ 2014-11-01 07:37:09

怎么会全是0？？？？？？？？？？？？？？
a710238477 LV 8 @ 2014-11-01 07:26:22

第一题全是0？？？？
flysky LV 8 @ 2014-10-31 23:58:27

program exam;
uses dos;
var a:array[0..10000000] of longint;
num,i:longint;
procedure add(no,l,r:longint);
var t:longint;
begin
if no>8 then exit;
t:=random(r-l+1)+l;
a[no]:=t;
add(no shl 1,t,r);
add(no shl 1+1,l,t);
end;
procedure add2(no,num:longint);
var t:longint;
begin
if no>8 then exit;
t:=random(num);
a[no]:=t;
add2(no shl 1,t+1);
add2(no shl 1+1,t+1);
end;
begin
randomize;
assign(output,'a.in');
rewrite(output);

add(1,0,1000);
writeln('2');
writeln('8');
for i:=1 to 8 do
write(a[i],' ');
writeln;
fillchar(a,sizeof(a),0);
writeln('8');
add2(1,1000);
for i:=1 to 8 do
write(a[i],' ');
close(output);
end.
doc！！！弱弱的问一下这个测试文件有错吗！！怎么错都对呀！一个BST，第二个HEAP
圈圈烤企鹅 LV 10 @ 2014-10-31 23:13:11

按道理一小时后应该出成绩了哇。。这次怎么了？。。
- doc LV 10 MOD @ 2014-10-31 23:16:48
  
  twd找不到了.
flykun LV 7 @ 2014-10-31 23:04:31

第一题有什么要注意的吗？不然怎么一直ac不了！！抓狂
- 圈圈烤企鹅 LV 10 @ 2014-10-31 23:07:48
  
  题目说是1到n的全排列。。我判断大小的时候不加等号是0分。。加了等号10分。。哭跪了。。orz
- doc LV 10 MOD @ 2014-10-31 23:17:11
  
  一开始有一半数据是错的...现在好了, 你可以重新提交试试看.
mrw LV 10 MOD @ 2014-10-31 23:01:25

好想把twd2吊起来打呀…………
- doc LV 10 MOD @ 2014-10-31 23:17:30
  
  丢到油锅里炸......
- doc LV 10 MOD @ 2014-10-31 23:17:51
  
  扒了他的皮......每次到这样的时候都不见人影.
- Lytning LV 8 @ 2014-10-31 23:22:08
  
  twd2已经吓得不敢出来了....
doc LV 10 MOD @ 2014-10-31 22:46:05

我们暂时隐藏掉了比赛的题目.
主要是某只judger不受控制了.
[更新: 现在已经再次开放了...]
- sunflower LV 9 @ 2014-10-31 22:49:57
  
  请问大概什么时候可以知道结果呀?
- doc LV 10 MOD @ 2014-10-31 23:18:05
  
  等到我们联系上twd
choversky LV 8 @ 2014-10-31 22:35:33

第一次参加啊，不能进题目求解！
- doc LV 10 MOD @ 2014-10-31 23:18:13
  
  已经可以了.
圈圈烤企鹅 LV 10 @ 2014-10-31 22:33:49

网页怎么抽了？。。我电脑问题还是vijos问题?...
- TA201314 LV 8 @ 2014-10-31 22:35:30
  
  +1
- doc LV 10 MOD @ 2014-10-31 22:40:51
  
  我的问题...稍等一下.
- doc LV 10 MOD @ 2014-10-31 23:18:24
  
  已经可以进去了.
doc LV 10 MOD @ 2014-10-31 22:22:12

题解:
(1).第一题,只要按照题目要求去检查一下就可以了,没有什么可以多说的.
(2).第二题,因为询问非常多,我们尝试预处理BFS一次,然后直接输出答案.
(3).简单的动态规划构建出有向图,之后问题等价于最小树形图,zhu-liu算法即可解决这一题.
(4).我们有一个结论:对于最后的交换方法,必然能找到一个断点,使得没有交换会跨过这个断点.有了这个结论,枚举断点的位置,再维护一下逆序对即可.
- 一方T行 LV 10 @ 2014-10-31 22:25:28
  
  最后一题我有了结论依旧不对，最后骗分爆0，orzorzorzorz
- Invoker LV 8 @ 2014-10-31 22:25:42
  
  orzzzzzzzzzzzzzzzzzzzzzz
一方T行 LV 10 @ 2014-10-31 22:21:45

看到分数感觉不会再爱了
- 圈圈烤企鹅 LV 10 @ 2014-10-31 22:27:08
  
  感觉noip无望了。。
- liyinghaowei LV 10 @ 2014-10-31 22:29:17
  
  卧槽，我也无望
chensy98 LV 10 @ 2014-10-31 22:16:28

第一题这么神奇？？？怎么没看到过的。。。
- 基因库 LV 8 @ 2014-10-31 22:17:30
  
  orz没看到过的+10086
  这里5分狗(╯‵□′)╯︵┻━┻
- liyinghaowei LV 10 @ 2014-10-31 22:19:31
  
  不知为何，我也5分
- chensy98 LV 10 @ 2014-10-31 22:20:30
  
  刚才稍微做了一下，也只有10分，，，为何。。。。ORZORZORZ。。。
- doc LV 10 MOD @ 2014-10-31 23:30:48
  
  一开始数据上传错了. 现在可以了. 已经重测了所有第一题的提交
a710238477 LV 8 @ 2014-10-31 22:11:22

发一下题解吧。。。
g107904 LV 8 @ 2014-10-31 22:06:36

刚回来就结束了2333
顺便求题解
基因库 LV 8 @ 2014-10-31 22:03:17

求题解。。。
Joenoip LV 6 @ 2014-10-31 22:02:42

什么时候有结果啊？
第七维度丶 LV 9 @ 2014-10-31 22:01:54

比赛结束了么
- 圈圈烤企鹅 LV 10 @ 2014-10-31 22:28:21
  
  我已经死了。。
asd130530asd LV 8 @ 2014-10-31 21:44:49

可怜的学姐
Awalk LV 8 @ 2014-10-31 21:18:59

我要是doc的学姐，看来这辈子是离不开牛排了……也就吃得上牛排……不对……牛排都不能吃一整块……
Sluqy671 LV 10 @ 2014-10-31 21:09:39

第四题一定包含两种盘子吗
- doc LV 10 MOD @ 2014-10-31 21:24:43
  
  可能某一种盘子是0个...
a710238477 LV 8 @ 2014-10-31 21:08:56

问一下，比赛结束就发题解吗
- doc LV 10 MOD @ 2014-10-31 21:25:04
  
  发简述题解. 因为题目不难.
- zhoulixuanwu LV 8 @ 2014-11-01 11:29:58
  
  蒟蒻的烦恼
TSWDD LV 8 @ 2014-10-31 21:05:28

弱弱地问一下内存限制多少？200M吗？
- Platypus LV 9 @ 2014-10-31 21:15:40
  
  512
基因库 LV 8 @ 2014-10-31 21:05:03

破坏队形

(╯‵□′)╯︵┻━┻

随风奔跑自由是方向！！
｡　 ∧＿∧｡ﾟ
　ﾟ　(ﾟ ´Д｀ﾟ)っﾟ
　　　(つ　 /
　　　| （⌒）
　　し⌒
追逐雷和闪电的力量！！
∧_∧
ﾍ(･ω･ﾍ)
　＼　＼
　＜￣￣＼
做完第一题后就开始睡觉噜(:3▓▒
- sun_ LV 5 @ 2014-10-31 21:08:50
  
  Orz
- 圈圈烤企鹅 LV 10 @ 2014-10-31 21:25:07
  
  orz
- Icarus LV 5 @ 2014-10-31 21:34:58
  
  orz
第七维度丶 LV 9 @ 2014-10-31 21:04:00

因为我貌似只会第一题所以想问清楚打印答案的冒号与后面的Both等有空格么我可不想在阴沟里翻船
- a710238477 LV 8 @ 2014-10-31 21:09:43
  
  有一个空格（直接复制样例吧）
东方幻想 LV 8 @ 2014-10-31 20:46:31

做到第三题我突然想到一个很严肃的问题
敢问doc
大虾天妇罗是什么玩意？
貌似做起来比题目麻烦...
ps：能先透露一下第二题搜索能过几个点吗？好让我决定继续乱搞第二题还是第四题还是继续纠结第三题...
- sun_ LV 5 @ 2014-10-31 21:09:31
  
  好吃吗Orz
- 于—归 LV 3 @ 2014-11-01 07:35:07
  
  天妇罗是河豚？？
一方T行 LV 10 @ 2014-10-31 20:41:52

╭══╮╭══╮╭══╮
║╭╮║║╭╮║╰═╮║
║║║║║╰╯║　╭╯╯
║║║║║╭╭╯╭╯╯　
║╰╯║║║╰╮║╰═╮
╰══╯╰╯╰╯╰══╯
- doc LV 10 MOD @ 2014-10-31 20:43:37
  
  我说, 似乎比赛还有75分钟吧. 你就来这里水了?
- 圈圈烤企鹅 LV 10 @ 2014-10-31 20:46:39
  
  坐等爆0呢。。无聊着就来水了。。
Icarus LV 5 @ 2014-10-31 20:30:37

OOOOORRRRRRZZZZZ
蒟蒻只是在崩溃后过来膜拜下神犇们
prwang LV 8 @ 2014-10-31 20:30:29

第三题内存是多少？128? 256? 512?
- wzhyhm LV 8 @ 2014-10-31 20:31:15
  
  看lz 512
aslmaswd_x2 LV 8 @ 2014-10-31 20:24:20

第三题 P ,Q 的范围?
- doc LV 10 MOD @ 2014-10-31 20:31:40
  
  满足: 1 <= P , Q , T[] <= 50为整数.
_Tacey LV 3 @ 2014-10-31 20:13:57

(3) 用一个已经保存了的文件来替换当前的新文件中,花费时间为P
“中”？
- doc LV 10 MOD @ 2014-10-31 20:15:19
  
  ...没有"中"...笔误

NOIP模拟赛之周五的夜晚

109 条评论

状态

开发

支持

NOIP模拟赛 之 周五的夜晚

109 条评论

状态

开发

支持

还没有账户？

登录

NOIP模拟赛之周五的夜晚