传送门

题意

给定长度为n的数组a，表示有n个敌人，第i个敌人有ai颗糖
定义f(x)为：
一开始你有x颗糖，对于长度为n的所有排列，都按照排列的顺序去打敌人当你的糖数量>=怪物的糖数量，那么可以打败敌人，且打败之后你的糖数量+1，f(x)的值就是满足条件的排列数，现在给定一个质数p，要求你找出所有的x，满足f(x)%p!=0
简单版本保证不超过2000
困难版本保证满足条件的x的数量不超过1e5
数据范围：n<=1e5，1<=a(i)<=1e9

E1

对于简单版本，可以考虑o(n^2)的做法。
设数组a里面的最大值为m，当x>=m时，排列方式为n!，因为p小于等于n，故不满足f(x)%p!=0
当x< m-n+1时，x不能打败最后一个敌人f(x)=0。故m-n+1<=x< m,对a排序后依次判断即可

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
#define inf 0x7fffffff
#define ll long long
vector<int> ans;
int a[3000],n,p;

int f(int x){
    int ans=1,cur=1;
    for(int i=1;i<=n;i++){
    	for(;cur<=n;cur++){
    		if(x<a[cur]){
            	break;
        	}
		} 
        if((cur-i)%p==0)return 0;
        x++;
    }
    return ans;
}

int main(){
    int i, j, k, t, m;
    scanf("%d%d",&n,&p);
    m=0;
    for(i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    sort(a+1,a+1+n);m=a[n];
    for(i=max(1,m-n+1);i<m;i++){
        if(f(i)) ans.push_back(i);
    }
    k=ans.size();
    printf("%d\n",k);
    for(i=0;i<k;i++){
        printf("%d ",ans[i]);
    }
    printf("\n");
}

E2

仔细思考可以发现符合条件的x都是连在一起的，即在同一个区间，因为对于排序后的每一个ai，x必须大于等于a[i]-i+1（打败i-1个敌人后能够达到a[i]），故x=max(x,a[i]-i+1),i=1~n。然后由于排列数不能为p的倍数，故每次可排序的数都要小于p,即当x满足a[i]-i+1时，x必须小于a[i+p-1]-i+1，故x=min(x,a[i+p-1]-(i-1)-1)。复杂度为o(n)。

C++
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
using namespace std;
#define inf 0x7fffffff
#define ll long long
ll n, m, p, a[100006];
int main(){
    ll i, j, k, t;
    scanf("%lld%lld",&n,&p);
    for(i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    ll l=1,r=1e9;
    for(i=1;i<=n;i++) l=max(l,a[i]-i+1);
    for(i=1;i+p-1<=n;i++) r=min(r,a[i+p-1]-i);
    if(l>r) printf("0\n");
    else{
        printf("%lld",r-l+1);
        for(i=l;i<=r;i++) printf("%lld ",i);
        printf("\n");
    }
}