/ Vijos / 讨论 / Vijos /

[置顶] <夜夜的模拟赛之十三岁的梦想> 通知&答疑 专用贴

夜夜十三岁啦
作为女孩子,夜夜憧憬着自己的未来
如果NOIP能满分就好了!如果能有男朋友就好了!如果有人能送我花裙子就好了!
一场NOIP提高组难度的模拟赛,如果你们都能来参加就好了!

开始时间 2015-10-03 18:30:00
结束时间 2015-10-03 21:30:00

NOIP模拟赛
题目难度: NOIP提高组
赛制 OI
题量 4题

主办 少女夜夜
负责 twd2

<<<实时更新>>>
+--------------------------------------------------------------------------------------+
* 比赛所有题目的内存限制都是512MB,时间限制请参见每一题。
* 所有题目均以最后一次提交为准,请避免编译错误。
* 详细帮助请参阅https://vijos.org/wiki/help#contest
* 比赛结束前均可在比赛页面右边点击参加比赛来参与比赛。
* C++选手请慎用cin cout, 比赛的评测机为Windows Server 2008 R2 对于64位整数, 可以采用 %I64d
* 18:32 比赛已经开始了,祝各位好运
* 19:03 比赛已经开始30mins了,后台工作人员twd2决定亲自上场参加比赛
* 19:50 请注意,第二题中,0<=X,A,B<C且X,A,B都是整数
* 20:25 请注意,第三题第二个样例的输出有误,应该是16.0。
* 20:28 此外,请注意,c/c++选手对于double的输出,请采用%f而不要用%lf
* 21:30 比赛结束啦,夜夜在此一鞠躬

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

解题报告

Problem A:

因为(1! + 2! + .. +n!) %m = 1!%m + 2!%m + ... +n!%m,显然如果n>=m则n!%m=0。
因为有一个点的n在10^8以内,所以有些人60分
有些人没数清楚几个0?用int读入的应该是90分,挂在第六个点,自然溢出后n是负的

Problem B:

对于15%的数据:直接输出无解。通过:6,7,8三个点。

对于20%的数据:直接把0 0 0...c-1 c-1 c-1输出,通过:1,2,3,4四个点。
上面两个可以结合,35分。

对于45%的数据:直接暴力X,A,B,O(N)暴力判定,通过:1,2,3,4,6,7,8,9,10九个点。
如果加一个break,可以额外通过11,12,13,14,15五个点,即70分。

对于70%的数据:前45%同上。
考虑c>n-10,那么我们可以发现X(c+i)=(X(c+i-1)*A+B)%c%(c+i),那么外层就没有意义了,所以X(c+i)=(X(c+i-1)*A+B)%c。
枚举X,A可以求B。通过:11,12,13,14,15五个点,25分。
加上上面算法,70分。

对于95%的数据:前45%同上。
在上面算法的基础上,我们发现,X(c+i)的后继应该是固定的,如果有不同,直接输出Unsuccess。
那么这样判定变成了O(c)的,即判定每个后继是否对应。可以通过:11,12,13,14,15,16,17,18,19,20五个点。

对于100%的数据:余下的部分一定是N=O(c)的,考虑用O(c^2N)的算法即可。

Problem C:

令X[i]为从i出发,首次抵达N的期望用时。那么X[N]=0。
对于i<N,X[i]可以由其余的X得到。比如说,在样例2中X[2]=(1/2)*(X[1]+1+X[2]+1)。
这样我们可以得到一个N元方程组,其中X[N]=0固定。解方程后的解X[1]就是问题的答案。

Problem D:

对于20%的数据:答案不会很大,可以直接枚举B和C。

对于80%的数据:动态规划。
考虑F[i][j][0/1][0/1][0/1]表示用了i根火柴棒,考虑了A,B和C的最低i位。
其中A,B是否已经结束(即是否不会有更高位),以及是否需要进位分别用2*2*2的状态表示。
转移的时候枚举最高位的情况,时间复杂度O(n^2)。

对于100%的数据,考虑上述中j所在这一维不要,时间复杂度O(n)。
.
.
+--------------------------------------------------------------------------------------+
.
.
.
【投票环节-今天的比赛你最喜欢哪一题,哪一题出得最良心?】
A. 第一题
B. 第二题
C. 第三题
D. 第四题
.
参与回答的同学将有机会获得精美礼品哦 ^_^

58 条评论

  • @ 2017-11-04 09:34:06

    A 感同身受

  • @ 2015-10-06 08:31:38

    哈c才良心

  • @ 2015-10-05 21:10:51

    problem B
    特么看到c≤400我都想到循环后继了然而还是45(╯`□´)╯︵┻━┻
    顺便一问为什么写代码的死宅这么多啊

  • @ 2015-10-05 17:29:16

    夭寿了,火柴棒都动态规划了

  • @ 2015-10-05 14:41:56

    夜夜是雷真身边的那个夜夜么= =

  • @ 2015-10-04 23:03:03

    C。好好玩的一道题。。。

  • @ 2015-10-04 21:56:44

    A,真的

  • @ 2015-10-04 19:38:30

    C最良心,仅仅是想哭而已,没什么,真的没什么

  • @ 2015-10-04 17:29:16

    B 最良心,做不来还可以直接cout<<"Unsuccessful Hack Attempt";
    15分到手

  • @ 2015-10-04 16:51:25

    A.

    ##虽然比赛时没想出来 但打表发现规律 还是AC了
    嘿;-)

  • @ 2015-10-04 16:31:53

    C,完全看不懂。

  • @ 2015-10-04 10:35:41

    T2 最良心 暴力70分

  • @ 2015-10-04 09:58:35

    “X(c+i)的后继应该是固定的,如果有不同,直接输出Unsuccess”这句话不太理解。
    “后继是固定的”是什么意思呢?这又是怎么推出来的呢?
    我只知道random()的最长有phi(c)的循环节。然而fa[]输出的random()%i就不一定有循环了。

  • @ 2015-10-04 09:27:42

    Problem B 求详解
    “考虑c>n-10,那么我们可以发现X(c+i)=(X(c+i-1)A+B)%c%(c+i),那么外层就没有意义了,所以X(c+i)=(X(c+i-1)A+B)%c。”求大神具体解释下

  • @ 2015-10-04 09:02:47

    A
    A最良心

  • @ 2015-10-04 08:08:38

    C怎么AC。。
    80是精度问题吗

  • @ 2015-10-04 00:05:20

    C
    C的方程思想很巧妙
    表示想不出来(>_<).

  • @ 2015-10-03 23:31:35

    AB

  • @ 2015-10-03 23:24:45

    C。全场良心trick

  • @ 2015-10-03 23:22:34

    Problem B

  • @ 2015-10-03 23:19:51

    A呵呵

  • @ 2015-10-03 23:15:14

    B. 第二题

  • @ 2015-10-03 23:12:24

    求T3几组评测数据~~~

  • @ 2015-10-03 23:04:10

    T3的话
    2 2
    1 1 1
    1 2 1
    答案是多少?

  • @ 2015-10-03 22:15:44

    能不能发一份T3数据啊

  • @ 2015-10-03 21:30:58

    第一次参加网上的比赛,坐等爆0 ╮(╯▽╰)╭

  • @ 2015-10-03 21:28:44

    doc说jtwd2太快了 要求在vijosex上评测呀 请大家注意

  • @ 2015-10-03 21:26:44

    waiting for judging and hoping for a high score T_T

  • @ 2015-10-03 21:16:08

    t4 例二 算着共有9种
    17根 a-b=c
    a,b ,c
    4 0 4
    4 4 0
    4 2 2
    9 2 7
    9 7 2
    11 0 11
    11 11 0
    11 10 1
    11 1 10

  • @ 2015-10-03 20:45:26

    请问,比赛结束后会出题解吗

  • @ 2015-10-03 20:43:53

    T2符合条件的解是x,b,a输出之间分别有个空格是吧,好像没说太清楚

  • @ 2015-10-03 20:20:27

    T3样例求解释

  • @ 2015-10-03 20:17:49

    第三题自环算不算自己和自己相邻 and 我第二组跑出来也一直是16.0

  • @ 2015-10-03 20:16:23

    同求T3样例 第二组应该是16.0啊

    • @ 2015-10-03 20:19:26

      第二组样例的标准解为16.05,四舍五入后为16.1。

    • @ 2015-10-03 20:25:04

      抱歉,样例输出错误,应该是16.0。

  • @ 2015-10-03 20:15:10

    我觉得第四题样例有误……

  • @ 2015-10-03 20:14:39

    T3样例真的没错吗,,第二问我一直输出16.0

    • @ 2015-10-03 20:19:18

      第二组样例的标准解为16.05,四舍五入后为16.1。

    • @ 2015-10-03 20:21:00

      然而我跑出来就是整数16.0 囧~

    • @ 2015-10-03 20:25:14

      抱歉,样例输出错误,应该是16.0。

    • @ 2015-10-03 20:26:31

      哎。。。调了一个小时。。。

    • @ 2015-10-03 22:04:15

      看到这个我感动得都要哭了...

  • @ 2015-10-03 20:09:00

    第二题a,b的值掉换算两种方案吗?

    • @ 2015-10-03 20:14:24

      当然算
      不过a,b的值调换也许就不是一种正确方案了

  • @ 2015-10-03 19:59:29

    请问t3 样例1可不可以从1号岛到2号,再到1号,再到2好,。。。。。。这样时间就会=+oo

    • @ 2015-10-03 20:00:09

      期望概率

    • @ 2015-10-03 20:02:24

      I see

    • @ 2015-10-03 20:06:03

      这样时间趋于正无穷但是概率也趋于零呀 乘积是常数呢

  • @ 2015-10-03 19:56:06

    请问T3可能出现自环吗?

  • @ 2015-10-03 19:54:27

    第三题就彻底炸了!

  • @ 2015-10-03 19:53:59

    初二狗表示看到第二题就炸了

  • @ 2015-10-03 19:42:02

    第三题第三题!!!

  • @ 2015-10-03 19:37:36

    同问T3 感觉题目表达不清

    • @ 2015-10-03 19:53:33

      就是要求从1出发,首次抵达N的期望用时。

  • @ 2015-10-03 19:34:12

    期望时间是什么鬼

    • @ 2015-10-03 19:39:41

      数学等你学到,就懂了= =

    • @ 2015-10-03 19:45:26

      在概率论和统计学中,一个离散性随机变量的期望值(或数学期望、或均值,亦简称期望,物理学中称为期待值)是试验中每次可能结果的概率乘以其结果的总和。换句话说,期望值是随机试验在同样的机会下重复多次的结果计算出的等同“期望”的平均值。需要注意的是,期望值并不一定等同于常识中的“期望”——“期望值”也许与每一个结果都不相等。(换句话说,期望值是该变量输出值的平均数。期望值并不一定包含于变量的输出值集合里。)例如,掷一枚六面骰子,其点数的期望值是3.5。

  • @ 2015-10-03 19:30:29

    第三题样例2求解释

    • @ 2015-10-03 19:33:53

      抱歉,我无法在不澄清标准算法的前提下,给你解释。

    • @ 2015-10-03 20:25:38

      抱歉,样例输出错误,应该是16.0

  • @ 2015-10-03 19:26:39

    请问T4一定存在合法情况吗

    • @ 2015-10-03 19:30:50

      有可能不存在,若不存在,答案就是0。

  • @ 2015-10-03 19:26:13

    夜夜,为什么你的最后一题超时了= =

  • @ 2015-10-03 19:00:54

    vijos上c++读入long long 用i64d还是lld

    • @ 2015-10-03 19:02:59

      C++选手请慎用cin cout, 评测机为Windows Server 2008 R2 对于64位整数, 可以采用%I64d输出.

    • @ 2015-10-03 19:03:47

      可采用i64d还是一定要用i64d

    • @ 2015-10-03 19:10:33

      你当然也可以用lld,只不过可能会答案错误。

  • @ 2015-10-03 18:52:06

    请问T4中A B C是否可以出现前导零

  • @ 2015-10-03 18:46:14

    第三题是无向边吗