竞赛讨论区 > 【题解】Wannafly挑战赛6
头像
牛客网小运营
编辑于 2018-12-27 14:43
+ 关注

【题解】Wannafly挑战赛6

 (题解由比赛出题人提供,点击右侧“本文相关内容”的题目即可开始做题)
T1 完全平方数

[1,n]中完全平方数个数就是sqrt( n )

注意特判0

T2 比赛

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

T3 逆序对

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



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

T4 锁

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

T5 双拆分数

n <= 3显然无解

此后如果n = x有解,那么n = x + 2的情况,只需要在n = x的解的末尾加两个零就可以了,这时就相当于a和b同时乘以了一个10。

n = 4:1144是一个合法解

(s1 =  1,s2 = 144,a = 12,b = 12)

(s1 = 11, s2 =  44,a = 22,b =  2)

n = 5:16400是一个合法解

(s1 =  1,s2 = 6400,a = 80,b = 80)

(s1 = 16, s2 =  400,a = 80,b =  5)


全部评论

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

等你来战

查看全部

热门推荐