Codeforces Round #654 (Div. 2)E1. Asterism (Easy Version)题解 思维

题目链接

题目大意

有 n 个敌人，编号为 1∼n，第 i 个敌人有 ai 个糖果。Yuzu在最开始时有 x 个糖果。当Yuzu拥有的糖果数大于等于她此时面对的敌人的糖果数时，它可以击败这个敌人，并取得1个糖果，否则她将被敌人击败，并且什么也得不到。Yuzu希望对所有的敌人都取得胜利，请帮她重新安排 n 个敌人的出现顺序，即 1∼n 的一个合法的排列 P。让我们定义 f(x) 等于初始时Yuzu有 x 个糖果时这样的排列 P 的数量。给出 n,p，其中 p 是质数，并且 p≤n。 我们称 x 是好的，当且仅当 f(x) 不能被 p 整除。找到所有好的 x。

题目思路

这个题目感觉比较巧妙，以前从来没写过类似的

1：设 a数组的最大值 为 m ,如果 x >=m 随便怎么放都是可行的，所以置换数位 n！，而 n!%p一定等于 0，所以一定不满足。 2：而如果 x+n-1< m,最后的值达不到 m 是没有满足的置换的，0%p=0 ,所以也不满足。 3：所以只要枚举 x-n-1 到 m 求出 每个 f（x）,看是否满足题意。复杂度 （n*n）; 4：求 f(x) ,总共有 n 个位置 从 m-n+1 到 m ，对应的值分别为 x到 m 。所以贪心的从大的开始安排，每个 a[i]只能安排到对应值比a[i]大或者等于的位置 。把最大的安排到可以满足的位置 一共 x+n-a[i] 个 第二大的数有 x+n-1-a[i]个位置。当 a[i]<=x 可以随便放。最后看所有可能 是否可以整除 p。

代码

#include<cstdio> #include<vector> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int maxn=2000+5,inf=0x3f3f3f3f; const int mod=1e9+7; int n,p,a[maxn]; vector<int> vec; bool flag(int x){ int fx=1,sum=n; for(int i=1;i<=n;i++){ if(a[i]<=x){ fx=fx*sum%p; }else if(x+sum-a[i]<=0){ //没有地方可以放了 return 0; }else{ fx=fx*(x+sum-a[i])%p; } sum--; } if(fx==0){ return 0; }else{ return 1; } } int main(){ scanf("%d%d",&n,&p); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } sort(a+1,a+1+n),reverse(a+1,a+1+n); for(int i=max(1,a[1]-n+1);i<a[1];i++){ //注意要有一个max，因为是正数 if(flag(i)){ vec.push_back(i); } } printf("%d\n",vec.size()); for(int i=0;i<vec.size();i++){ printf("%d%c",vec[i],(i==vec.size()-1)?'\n':' '); } return 0; }

参考链接 https://blog.csdn.net/hddddh/article/details/107096920 https://blog.csdn.net/qq_43680965/article/details/107089798?%3E