Codeforces Round #654 (Div. 2)E. Asterism(思维)⭐⭐⭐⭐

这道题让你求方案数$f(x)$不能被p整除的x.

又是一道思维盲点题：这道题的答案是一个连续的区间。

最小满足条件的x=l很好求，最大的满足条件的也求出的话，答案就出来了。 首先将a从小到大排序，可以发现对于回合i，有$(x+i-1)$个candy。 该回合可以使得f(x)乘上$(cnt-i+1),cnt为a中小于等于cand{y}_i的元素个数$。

现在来证明答案为什么是连续的区间： 求出最小的x之后，你每次增加x，都会使得$(cnt-i+1)$这个函数$f(x,i)$有几率上移,可知答案的r就是刚好有点出现$(cnt-i+1)=p$的情况的x，再减去一。

具体实现代码如下:

#include<bits/stdc++.h> using namespace std; #define fore(i, l, r) for(int i = int(l); i < int(r); i++) #define MAXN 105000 #define ll long long const ll mod=1000000007; int a[MAXN]; int n,p; inline bool read() { scanf("%d%d",&n,&p); for(int i=1;i<=n;i++) scanf("%d",a+i); sort(a+1,a+1+n); } void solve() { int l=1; for(int i=1;i<=n;i++) l=max(a[i]+1-i,l); int r=a[n]+1; for(int i=1;i<=n;i++) { if(p+i-1<=n) r = min(a[p+i-1] + 1 - i, r); } if(r==a[n]+1||r<=l)r=l; cout<<r-l<<endl; for(int i=l;i<r;i++) printf("%d%c",i,i==r?'\n':' '); } int main() { #ifdef _DEBUG freopen("input.txt", "r", stdin); #endif read(); solve(); return 0; }