E1,暴力+组合数学 对每个x都求一遍就行
/* 在位置i的糖果数量是x+i-1, 所以先把minx和maxx确定下来 当a数组递增排列时,minx=max(minx,ai-i+1) 当a中最大值出现在第一位时,取到maxx=ai x遍历范围[max(0,minx),max(maxx,n)], 将ai-x,然后ai只能出现在i及以后,那么从大到小求一个乘积,如果碰到%p=0,就是不行 */ #include<bits/stdc++.h> using namespace std; #define ll long long #define N 2005 ll n,p,a[N],maxx,minx; vector<ll>v; int check(ll x){ ll b[N],mul=1; for(int i=1;i<=n;i++)b[i]=a[i]-x+1; for(int i=n;i>=1;i--){//值为b[i]的数只能在位置b[i]及以后 if(b[i]<=0)b[i]=1; mul=mul*(n-b[i]+1-(n-i)); mul%=p; if(mul%p==0)return 0; } return 1; } int main(){ cin>>n>>p; for(int i=1;i<=n;i++)cin>>a[i]; /* n=2000;p=1999; for(int i=1;i<=2000;i++)a[i]=i; */ minx=0,maxx=0; sort(a+1,a+1+n); for(int i=1;i<=n;i++) minx=max(minx,a[i]-i+1); maxx=a[n]; for(int i=minx;i<=max(maxx,n);i++) if(check(i))v.push_back(i); cout<<v.size()<<'\n'; for(auto x:v)cout<<x<<" "; }
E2 数据为1e5,像E1那样暴力肯定不行,要先预处理出一个数组b,bi=i-a数组中值<=i的个数,然后用双指针在上面跑
#include<bits/stdc++.h> using namespace std; #define N 500005 #define ll long long ll n,p,a[N],minx,maxx; map<ll,ll>b; int main(){ cin>>n>>p; for(int i=1;i<=n;i++)scanf("%lld",&a[i]); sort(a+1,a+1+n); minx=0;maxx=max(a[n]-1,n); for(int i=1;i<=n;i++)minx=max(minx,a[i]-i+1); for(int i=minx;i<=maxx+2*n;i++){ int pos=upper_bound(a+1,a+1+n,i)-a-1; b[i]=i-pos; b[i]%=p;b[i]+=2*p;b[i]%=p; } ll p1=minx,p2=minx-1; map<ll,ll>mp; vector<ll>v; for(int x=minx;x<=maxx;x++){ while(p2<x+n-1){ ++p2; mp[b[p2]]++; } while(p1<x){ mp[b[p1]]--; p1++; } if(mp[x%p]==0) v.push_back(x); } cout<<v.size()<<'\n'; for(auto x:v)cout<<x<<" "; }