竞赛讨论区 > 【题解】Wannafly挑战赛6
头像
王清楚
发布于 2021-11-23 14:32
+ 关注

【题解】Wannafly挑战赛6

T1 完全平方数

中完全平方数个数就是

注意特判0

T2 比赛

算出一个题被做出来的概率,然后枚举一下每个题是否被做出来,算算贡献

T3 逆序对

考虑每一位为0的贡献:设这当前为第i位,前面则有位,即个数,根据个数应该相同,那么的个数为这些数总数的一半,即这样的数字共有个(即后面的位数),所以每一位的贡献是总的个数为:

快速幂搞一搞就好,注意取模。

T4 锁

答案是这样的居民子集个数重要度的和不足,但加入任何一个新居民都将导致重要度的和大于等于。必要:由于上面的集合重要度都不够,他们都至少缺一把锁。若不足把锁,这些子集中必有两个缺同一把锁。把这两个子集并起来,仍然缺这把锁,无法开门,但现在子集的重要度已经达到了,与题目要求矛盾.所以合法的解至少需要把锁。充分:一共把锁,每把锁上面各写一个这种居民的子集(互不相同)。一个居民持有大部分的钥匙:他持有所有上面的子集不包括自己的锁的钥匙。可以验证这样满足要求。注意到如果所有人加起来重要度都不够,则需要一把锁,无人有钥匙:对应全集为唯一满足上面条件的集合,不能加入任意一个居民(虚满足)。

T5 双拆分数

显然无解

此后如果有解,那么的情况,只需要在的解的末尾加两个零就可以了,这时就相当于同时乘以了一个

是一个合法解

是一个合法解

全部评论

(0) 回帖
加载中...
话题 回帖

本文相关内容

等你来战

查看全部

热门推荐