Educational Codeforces Round 86 (Rated for Div. 2)

AB不写了
C.Yet Another Counting Problem
给定a,b,给q个询问,要求在\([l,r]\)范围内求出\((i\ mod\ a)\ mod\ b!=(i\ mod\ b)\ mod\ a\)的数量。
打一下表可以发现,周期为lcm(a,b),里面符合的数为max(a,b)及以后的数。

代码 展开/收缩

还有一个方法,把a*b的前缀和表预处理出来,然后算一下有几组多几个然后就好了

代码 展开/收缩

D.Multiple Testcases
要求把n个问题分组,然后给定\(c_i\)从1-k表示大于等于i的问题数量不能超过\(c_i\)
问最少要分几组。
记录一下答案每组组内的数量,然后将问题从大到小加入答案,贪心地将其放在越前面越好,那么我们得到的sum数组可以确认是一个递减的数组,那么就可以使用二分来获得可以放的最前面的那个位置。

代码 展开/收缩

E.Placing Rooks
在一个n*n的棋盘中,将n个棋子放入棋盘,每个棋子可以上下左右直线攻击,要求所有位置都能被棋子攻击到,并且棋子之间能互相攻击的对数为k,棋子不能穿透其他棋子。
因为要n个棋子覆盖掉n*n的所有格子,所以要么是列从1-n要么是行从1-n,2种情况,最后答案乘2即可,那么考虑列从1-n。然后要获得k对能够互相攻击的棋子的话, 那么显然n个棋子要放在n-k行上,并且没有行是空的(我不是很想证:<),那么可以转化为小球放盒子问题,n个小球(棋子)各不相同(列不相同),n-k个盒子(行)各不相同,那么答案就是\((n-k)!Stirling2(n,n-k)\),8种小球放盒子问题(球是否相同,盒子是否相同,是否可以空)可以百度一下,然后斯特林数的求法为 \(S(n,m)=\sum_{k=0}^{m}\frac{(-1)^k}{k!}*\frac{(m-k)^n}{(m-k)!}\),然后n-k行有C(n,n-k)种选法,乘上即可,然后因为行列都可以,所以最后乘二(k=0不乘)

对于答案的具体解释可以查看hjt的博客,容斥原理。

代码 展开/收缩

发表评论

电子邮件地址不会被公开。 必填项已用*标注