题解 CF1371E1 【Asterism (Easy Version)】
huayucaiji
·
·
题解
首先我们可以确定是一个 O(n^2) 的算法。而且我们知道为了赢得所有的对战，易得x_{min}=\max(a_i)-n+1。此时 \max(a_i) 放在最后一个位置。我们分三个情况讨论：
1.x<\max(a_i)-n+1，此时无解，即 f(x)=0，p\mid f(x)，所以不是我们想要的解。
2.x>\max(a_i)，此时任意排列都可以，即 f(x)=n!，因为 p\leq n，p\mid f(x)，所以不是我们想要的解。
3.max(a_i)-n+1\leq x\leq\max(a_i)，此时有可能有解。
因此我们只需要考虑第三种情况。由于时间充裕，我们可以枚举 x，用 O(n) 的时间来计算 f(x)。
我们采取计算每一位上有多少个可以放的怪兽，因为可以放在 i 上的怪兽一定可以放在 i+1 的位置上，满足单调性，所以可以从前往后扫。我们记 t_i 为糖果数量小于等于 i 的怪兽的数量。我们可以用排列组合得出下面的式子：
f(x)=\prod\limits_{i=x}^{x+n-1} t_i-(i-x)
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read() {
char ch=getchar();
int f=1,x=0;
while(ch<'0'||ch>'9') {
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
const int maxn=2e4+10;
int n,a[maxn],p,t[maxn<<1];
vector<int> ans;
signed main() {
n=read();p=read();
for(int i=1;i<=n;i++) {
a[i]=read();
t[a[i]]++;
}
sort(a+1,a+n+1);
for(int i=1;i<=a[n]+n;i++) {
t[i]=t[i]+t[i-1];
}
int k=max(0LL,a[n]-n+1);
for(int x=k;x<=a[n];x++) {
bool flag=1;
for(int i=x;i<x+n-1;i++) {
if((t[i]-(i-x))%p==0) {
flag=0;
break;
}
}
if(flag) {
ans.push_back(x);
}
}
cout<<ans.size()<<endl;
int sz=ans.size();
for(int i=0;i<sz;i++) {
cout<<ans[i]<<" ";
}
return 0;
}
```