2020.10.17【普及组】模拟赛C组 总结
发布日期:2021-06-21 02:54:44 浏览次数:5 分类:技术文章

本文共 1291 字,大约阅读时间需要 4 分钟。

总结

这次比赛 120 分,老师说上 200 是不容易的,但我觉得这不是我真的水平

改题情况

T1

题目大意:有 N 个小朋友,每个小朋友有 \(B_i\) 个朋友,问从中随机选 3 人使得 3 人关系完全相同的概率\(PS.\)关系相同就是指要么 3 个人互相是朋友,要么 3 个人互相都不是朋友。

状态:未改出

\(Update\ \ 16:02:\)已改出


不过我请教过

他说
\(Ans = 1 - \dfrac{\sum_{i=1}^n B_i \times (n-B_i-1)}{2C_n^3}\)
\(\dfrac{\sum_{i=1}^n B_i \times (n-B_i-1)}{2}\) 是乘法原理方案数,
\(\div 2\) 是因为朋友关系是双向的
\(\div C_n^3\) 是求概率,当然这是不同的概率,相同的自然要用 1 减。

\(Update\ \ 16:02:\ \ B_i \times (n-B_i-1)\)的原理:\(n-B_i-1\)是去掉自己的朋友和自己剩下的人数,根据乘法原理便是\(B_i \times (n-B_i-1)\)

奇怪的知识点:概率

概率 = \(\dfrac{合法方案}{总方案}\)\(1 - \dfrac{不合法方案}{总方案}\)

T2

题目大意

有 N 个物品,每个物品有要花的钱 \(a_i\) ,要花的积分 \(b_i\) 和价值 \(val_i\)

现在有 v1 元, v2 积分和 k 次免费拿物品的机会,问你最多能拿多少价值的物品

改题情况:已 AC

\(F_{p,q,k}\) 为用了 p 元, q 积分和 k 次白嫖机会的最大价值

由于会有价值或积分为 0 的情况,会已不用白嫖卡白嫖的情况,逆推法样例过不了,然后交上去就对了。
但是我不敢交,于是 80 分没了。。。\(2020.16.26:\) 看了一下

的代码,顺推完美解决

T3

暴力模拟,懒了懒了,考试时 AC

心得

调了一个多钟,先从深搜又到广搜,从 while 拓展到 if (因为要同时移动),还是很有成就感的

T4

题目大意

有 N 个人要打车,共有 K 辆车,第 i 辆车在 \(T_i\) 到达,到达时剩下 \(Z_i\) 个座位。

无论多少人打车都只用 D 元,人每等一分钟多耗 1 元,问所有人到目的地最少要多少钱

改题情况:已 AC

\(F_{i,j}\) 为第 i 辆车时总共上了 j 个人时的最小时间

容易发现这就是一个多重背包,变成滚动数组就是 \(F_j\)\(F_j= \min(F_j,F_{j-l}+T_i \times l + D)\),其中\(i\leftarrow1\ \ To\ \ k\)\(j\leftarrow n\ \ DownTo\ \ Z_i\)\(l\leftarrow Z_i\ \ DownTo\ \ 0\)

总结

这次比赛有点可惜,T1 概率真的涨见识了,T2 的顺推让我不再完全依赖顺推。

T3 增强了代码实现能力,T4 需要多动脑(毕竟很像摆渡车)

转载地址:https://blog.csdn.net/KonjakuLAF/article/details/115714537 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:2020.10.24【普及组】模拟赛C组 总结
下一篇:2020.09.12【NOIP提高组&普及组】模拟赛C组2

发表评论

最新留言

关注你微信了!
[***.104.42.241]2024年03月30日 21时18分22秒