题解 CF1371E1 【Asterism (Easy Version)】
huayucaiji
2020-07-05 12:02:46
首先我们可以确定是一个 $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)$$
$i-x$ 就表示已经用过多少怪兽，剩下 $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;
}
```