2020-2021:teams:manespace:codeforces_round_654_div2
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:manespace:codeforces_round_654_div2 [2020/07/07 23:18] iuiou |
2020-2021:teams:manespace:codeforces_round_654_div2 [2020/07/07 23:29] (当前版本) iuiou |
||
|---|---|---|---|
| 行 21: | 行 21: | ||
| =====E1 Asterism (Easy Version)===== | =====E1 Asterism (Easy Version)===== | ||
| - | 题意：定义一次比赛，主人公开始拥有x个物品，出了主人公外还有n个人，第i个人拥有$a_i$个物品，主人公要按照一定顺序来和n个人进行对决，如果一次对决中主人公拥有的物品多于那个人拥有的物品，那么主人公获胜并取得一个物品，进入下一次对决。令所有能够满足使主人公全胜的对决组合有k个，则$f(x)=k$,问对于x的不同的取值，$f(x)$的值不能被p整除的有多少？ | + | 题意：定义一次比赛，主人公开始拥有x个物品，出了主人公外还有n个人，第i个人拥有$a_i$个物品，主人公要按照一定顺序来和n个人进行对决，如果一次对决中主人公拥有的物品多于那个人拥有的物品，那么主人公获胜并取得一个物品，进入下一次对决。令所有能够满足使主人公全胜的对决组合有k个，则$f(x)=k$,问对于x的不同的取值，$f(x)$的值不能被$p$整除的有多少？ |
| - | 题解：真的很绕的一道题啊，本质是暴力枚举，至少对与这个数据较小的题是这样的。枚举每一个可能的x(一开是要稍微根据题意划分一下x的范围,首先，求出a中最大值y，如果x比a中的最大值大，那么可以随便排列，数量为n!,n≥p,所以n!被p整除，其次，每次最多只能+1，为了胜过所有人，初始值至少应该是y-n+1，这样就确定好了范围)，然后再枚举每一局开始有多少小于目前主人公手上的物品的人，用乘法原理累乘即可。题目标明了p质数，那么如果p可以整除$f(x)$那么p一定是乘法原理计算时一项的因子，所以单次枚举时，只要可以打败的人的数量被p整除则一定不满足条件。 | + | 题解：真的很绕的一道题啊，本质是暴力枚举，至少对与这个数据较小的题是这样的。枚举每一个可能的$x$(一开是要稍微根据题意划分一下$x$的范围,首先，求出$a$中最大值$y$，如果$x$比$a$中的最大值大，那么可以随便排列，数量为$n!$,$n≥p$,所以$n!$被$p$整除，所以，最大值小于y，其次，每次最多只能$+1$，为了胜过所有人，初始值至少应该是$y-n+1$，这样就确定好了范围)，然后再枚举每一局开始有多少小于目前主人公手上的物品的人，用乘法原理累乘即可。题目标明了$p$质数，那么如果$p$可以整除$f(x)$那么$p$一定是乘法原理计算时一项的因子，所以单次枚举时，只要可以打败的人的数量被$p$整除则一定不满足条件。 |
| + | |||
| + | =====E2 Asterism (Hard Version)===== | ||
| + | 题意：同上，数据范围扩展到$10^5$ | ||
| + | |||
| + | 题解：其实上一问做完后不难发现，答案有单调连序性，如果$x$不满足条件，则比$x$大的一定都不满足，这是显然的，因为对于$x+1$得情况完全可以使用$x$的情况应对，而因子中也会出现$p$的倍数，所以上界可以二分答案得到，而对于上界，如果$x$不满足条件即不能使主人公全胜，则$x-1$也不能，这也比较显然，$x$一定是越大越好啊，所以下界也可以二分得到，最终得到区间，便得到答案。复杂度$O(nlogn)$ | ||
2020-2021/teams/manespace/codeforces_round_654_div2.1594135089.txt.gz · 最后更改: 2020/07/07 23:18 由 iuiou
