不存在的NOIP模拟赛

不存在的NOIP模拟赛

题目描述 数据删除 薛定谔的人 Are We cool Yet?
程序文件名 deletion.cpp erwin.cpp AWCY.cpp
输入文件名 deletion.in erwin.in AWCY.in
输出文件名 deletion.out erwin.out AWCY.out
每个测试点时间 2s 1s 2s
内存限制 256MB 256MB 128MB
测试点数目 10 10 20
每个测试点分值 10 10 5
评测环境

(1)就我们后面那台noilinux,速度怎么样自己琢磨,栈空间可能会卡,自己注意点

(2)难度不一定递增,因为我也不清楚难度怎么样,最终评测打开O2

数据删除

[数据删除]

我们的[数据删除]们终于通过一些[数据删除]的技巧搞明白了SCP-055是个[数据删除],一个带有逆模因[数据删除]的二叉树,有一些[数据删除]的性质,例如一个[数据删除]的节点不会在没有左节点的情况下拥有右[数据删除].

但由于一些[数据删除]的原因,我们对它知道的不多,只知道[数据删除]会把存储它的[数据删除],逐渐[数据删除],现在你有[数据删除]先序[数据删除],以及通过[数据删除]得到的后序[数据删除].现在,在[数据删除]充满这个[数据删除]之前帮助[数据删除]中序遍历,以便[数据删除]收容[数据删除].

同时,保证[数据删除]有[数据删除]的唯一的[数据删除]可能.

以下是经过了[数据删除],防遮蔽[数据删除]技术的题意

[数据删除]

三行

第一行一个正整数n,表示[数据删除]的节点数

第二行n个[数据删除],一个1-n的排列,表示[数据删除]的[数据删除]先序遍[数据删除].

第[数据删除]行n个正整数,也是[数据删除]的排列,表示后序[数据删除].

[数据删除]

一行,表示[数据删除]的中序遍历结果.

[数据删除]

7

1 5 3 4 7 2 6

3 7 4 5 6 2 1

[数据删除]

3 5 7 4 1 6 2

[数据删除]

[数据删除]如图所示

[数据删除]

对于10%的[数据删除],有[数据删除]$\leq 10$

对于30%的[数据删除],有[数据删除]$\leq 1000$

对于另外30%的[数据删除],保证[数据删除]是随机[数据删除]的

对于100%的[数据删除],有$2\leq n\leq 1000000$

薛定谔的人

[题目描述]

众所不周知,这一届的Dr.Wondertainment是一个在各个位面都非常有名的女神经病,一天她闲着无聊跑到了一个埃尔温 薛定谔还活着的一个位面去把他抓了起来,并把他放到了一个迷宫中.这个迷宫是一个树的结构,根节点是1,也是薛定谔的起点.

薛定谔每分钟会随机等概率(共(儿子数量+2或者1)种等可能情况)走到下列点中的一个去.

(1)走到一个所在节点的儿子节点之一

(2)留在现在这个点思考人生和Dr.Wondertainment妹子

(3)一个闪回回到根节点1号重新开始,当然如果他就在1号节点是没有办法闪回的

但当他走到一个叶子节点的时候就会被Dr.Wondertainment抓起来关起来,这样Dr.Wondertainment就可以在无数个位面中抓到无数的身体和心理状态的薛定谔(一次性走到叶子的,走了很长走到叶子的,反复走来走去走到精神崩溃的,走到一个叶子门口又返回来走到另一个叶子里面的薛定谔)来做各种神奇的实验了

Dr.Wondertainment在经过无穷的时间收集到了所有的无穷个薛定谔后,开始统计一些数据

(1)从每个叶子结点出现的薛定谔占全体的比例

(2)薛定谔平均在迷宫里呆的时间(min)

因为比例可能很小,所以比例请mod 1e9+7 之后输出

平均时间,用浮点数输出,保留3位小数

本题有SPJ,对于每个测试点第一问占6分,第二问占4分

[输入格式]

共两行

一个正整数n,表示树的节点数

第二行,共n-1个正整数,第i-1($2\leq i\leq n$)个正整数$fa_i$,表示节点i的父亲是$fa_i$,保证$fa_i < i$

[输出格式]

共两行

第一行 共n个正整数,表示在这个节点结束的概率,mod 1e9+7 之后输出,如果不是叶子节点输出0

第二行一个浮点数,表示结束的期望步数,保留三位小数

[样例输入1]

5

1 1 3 3

[样例输出1]

0 200000002 0 400000003 400000003

2.600

[样例输入2]

7

1 1 2 2 3 3

[样例输出2]

0 0 0 250000002 250000002 250000002 250000002

4.250

[数据范围]

对于10%的数据,$n\leq 10$

对于30%的数据,$n\leq 100$

对于50%的数据,$n\leq 1000$

对于80%的数据,保证树随机生成

对于100%的数据,$1\leq n\leq 100000$

对于第2~5个测试点,只要第一个问题得到了正确答案,就可以拿到满分

 

Are We cool Yet?

[题目描述]

AWCY市的公路是一个简单的结构,仅有四个地点(称为S,T,没名字和没名字),以及四条公路(称为Art,Wonder,Cooooooool,Yell,简称A,W,C,Y),均为双向公路,如图所示.

每天,都会有艺术家们带着车流量为X的超cooooooooool飞车(在早上七点突然一起在S点出现)要从S要到达T,但通过一条公路的时间并不是一个固定值,跟这个公路的车流量是一个一次函数的关系

每条公路有两个数据,拥挤值a和长度值b,如果此公路的车流量为x,则通过这条公路的时间为ax+b,$a,b \geq 0$

另,每一个艺术家都是一个没有公共道德心的艺术家,每一个艺术家都会按照自己的最短时间来行动,而不是为了整体的最短时间,你甚至可以认为一个人可以在所有人都作出决策之后改变自己的决策使得自己的时间更短

另另,车流量的单位并不是一辆车,即x不一定需要是整数

但是,当地政府认为这个城市不够cooooooooooooooool,决定增加一条路(Modern,简称M),如图所示

因为这条路非常coooooooooooooool,所以它一点都不拥挤,经过其需要的时间为一个定值m($m \geq 0$)

现在,给出X,路A,W,C,Y的拥挤值和长度值以及m,请你所有艺术家在经过他们精明的大脑的决策之后用时最长的人需要花的时间

[输入格式]

第一行一个正整数X

接下来4行每行两个非负整数$a_i$,$b_i$,分别表示A-D四条道路的拥挤值和长度值

最后一行一个非负整数m

[输出格式]

一个数t,保留三位小数

[样例输入1]

100

0 1

0 5

0 3

0 3

0

[样例输出1]

4.000

[样例解释1]

连一条长度为0的路造福群众,让人民群众可以先走A路再走Y路达到最短

[样例输入2]

10

4 0

0 50

0 50

4 0

0

[样例输出2]

80.000

[样例解释2]

连一条长度为0的路造福群众,我们来看看会发生什么不妙的事情

连接了之后相当于两个没有名字的地方挨在了一起

我们考察艺术家A的内心”

coooooool,修了一条新路,我可以在前一段段路上随便选A/C,后一段路上随便选W/Y了

总车流量才10,全部走A,A的时间也才40,都比走C快,我就走A好了,

同理,W与Y之间我也走Y就可以了”

导致的结果就是所有人都超cooooooooool地选择了A-Y这一条路

时间为80,没有原来一边走一半的超coooooooool飞车,大家都是70快…

所以这条路没有任何用处但它超cooooooooool

 

 

[样例输入3]

100

1 40

3 10

4 5

2 15

10

[样例输出3]

250.000

[样例解释3]

你要相信超cooooooool的艺术家用他们超cooooooool的大脑算出来的结果

[数据范围]

对于5%的数据,有$a_i=0$

对于另外30%的数据,有$X\leq 10,a_i,b_i\leq 10$

对于另外20%的数据,有$b_i,m=0$

对于另外30%的数据,有$a_i,b_i,m\neq 0$,且每一条路都有人走

对于100%的数据,有$1\leq X\leq 1000$,$0\leq a_i,b_i,m \leq 1000$

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注