这里是写题面的 JRY,这一次的题面是不是很资慈呀 ( •̀∀•́ )。
因为之前在造比赛的时候 VFK 点名要让我来写题面,在感觉受宠若惊的同时为了不辜负 boss 的信任,当然要把题面写的生动有趣啦(笑)。
如果大家喜欢的话以后的题面里还是会继续这样写的 (*•̀ㅂ•́)و 。(当然前提是 VFK 还会再让我写题面)
最后插播一个小花絮,其实原来第三题的标题是长这样的:
后来因为它实在是太 ydcydc 了,所以就被无情的改掉啦 (╯°Д°)╯︵ ┻━┻。
公告
我们发现 613,Chloe_fan,xjt 这三位选手的 C 题代码,以及 Chloe_fan,xjt 这两位选手的 A 题代码过于相似,经过管理员之间的讨论,我们决定取消他们这次比赛的参赛成绩。如果这几位选手存在异议,请在评论中提出。
希望各位参赛选手能以此为鉴,掌握开黑的正确姿势(雾),诚信比赛。
实验室外的攻防战
By matthew99
题解By C_SUNSHINE
算法一
我们建立
这个算法能通过Subtask 1得到
不会bfs的戳这里
算法二
我们使用冒泡排序进行模拟,在交换时判断一下,如果经过
这个算法能通过Subtask 1~2得到
不会冒泡排序的戳这里
为什么这样是对的呢?因为自信!
算法三
我们可以猜一发结论,假设
那么我们怎么判断是否存在这样的
我们按照编号从小到大枚举
这个算法能通过全部Subtask得到
不会树状数组的戳这里
密码锁
By matthew99
得分情况
一个字形容——惨
49分——SanSiroWaltz 和 BillXu2000
26分——xuhaike
19分——很多人
0分——很多人
算法一
对于subtask1,我们可以枚举每条边的定向,然后暴力求出强连通分量数。
什么你说你不会求强连通分量数?直接floyd跑一遍求传递闭包,把所有的互相能到达的点都缩起来就可以了。当然你也可以BFS。
如果使用
算法二
懂逆元的同学都应该知道模意义下统计一个东西的概率,我们可以先统计出强连通分量数的期望,最后乘上
注意到定向后的图是个有向完全图,即竞赛图,竞赛图的强连通分量缩点之后,一定是一个链状的图,满足每个点和后面的点都有连边。
如何统计答案呢,设这张图为
暴力枚举所有可能的点集
时间复杂度
算法三
妈妈我会数学!
对于
时间复杂度
算法四
对于后面的数据,我们发现m比较小,因此最好能想出一个在指数意义上和n无关的算法。
对于一个点集,它是割集的概率无非就是这个点集中的点与点集外的所有点的所有连边都是从这个点集连出去的概率,也就是每条边是连出去的概率乘起来。对于概率非0.5的边我们称其为特殊边,对于大小为
一个想法就是枚举有贡献的边的集合,如果一条边有贡献,那么它的两个端点必然有且仅有一个在
时间复杂度为
算法五
我们发现之前的复杂度在于背包DP上,对什么进行背包DP呢,对每个连通块进行背包DP,等等你说每个连通块?
一个连通块,如果有
时间复杂度为
a^-1 + b problem
By shanquan2
题解By jiry_2
算法一
直接暴力模拟整个过程,逆元可以通过费马小定理用快速幂求,也可以直接用扩展欧几里得求,这两个方法都是单次
时间复杂度
算法二
当没有求逆元操作的时候,我们可以直接更新总和:整体加上
时间复杂度
算法三
对于集合中的一个数,我们考虑若干次操作之后它会变成什么。显然每一时刻,都存在常数
于是问题就转化成了,每一次给出一个函数
当
首先,我们可以把
因为
当然,这个做法想要拿到
时间复杂度
算法四
考虑优化算法三。考虑算法三中
先考虑第一个地方,我们构造多项式
第二个地方的处理方法类似,我们构造多项式
这样我们就得到了一个