- Vijos
- 2015-10-03 02:21:25 @
夜夜十三岁啦
作为女孩子,夜夜憧憬着自己的未来
如果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 条评论
-
王诗云 LV 8 @ 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:15:10@
我觉得第四题样例有误……
-
2015-10-03 20:14:39@
T3样例真的没错吗,,第二问我一直输出16.0
-
2015-10-03 20:09:00@
第二题a,b的值掉换算两种方案吗?
-
2015-10-03 19:59:29@
请问t3 样例1可不可以从1号岛到2号,再到1号,再到2好,。。。。。。这样时间就会=+oo
-
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:34:12@
期望时间是什么鬼
-
2015-10-03 19:30:29@
第三题样例2求解释
-
2015-10-03 19:26:39@
请问T4一定存在合法情况吗
-
2015-10-03 19:26:13@
夜夜,为什么你的最后一题超时了= =
-
2015-10-03 19:00:54@
vijos上c++读入long long 用i64d还是lld
-
2015-10-03 18:52:06@
请问T4中A B C是否可以出现前导零
-
2015-10-03 18:46:14@
第三题是无向边吗