codeforces-#654-E1

codeforces-#654-E1

七月 09, 2020

E1. Asterism (Easy Version)

题意

一个玩家初始能力值为x (x未知)

有n个敌人 每个敌人有能力值pi

玩家需要以某种顺序逐个挑战每个敌人

当玩家能力值x>=当前敌人能力值pi 那么可以击败它 然后玩家能力值x++

否则跳过这个敌人玩家能力不变

定义f(x)为 玩家初始能力为x时 有多少种不同的挑战顺序能击败所有敌人

现在问对于已知n个敌人能力值和一个素数p

有多少种x使得f(x)%p !=0

输出种类数m 并升序输出所有x

题解

从变化中寻找不变的因素 一个显然的事实是 无论以哪种顺序依次击败所有敌人

每次击败一个敌人自身能力值x都会+1

那么下次玩家一定能从剩下的敌人中选出能力值pi<=x的其中一个敌人挑战

以此类推那么对于一个初始能力值为x的玩家

$$
f(x)= (小于等于x的敌人个数)(小于等于x+1的敌人个数-1) (小于等于x+2的敌人个数-2) ….
$$
若某时刻发现剩下的敌人中没有能力值pi<=当前x的那么表示这种初始能力值不能击败所有敌人f(x)=0

由于初始能力值x>最大的敌人能力值pi x无论如何增大f(x)不变

而题目说明m最多不会超过1e5那么只要x枚举到max(敌人能力值)

每次On计算f(x) 总复杂度On^2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const int Max=2e3+5;
const int mod=2e3;
int data[Max],cnt[Max];
vector<int>ans;

int main() {
    Turnoff;
    int n,p;cin>>n>>p;
    for(int i=1;i<=n;i++)cin>>data[i];

    sort(data+1,data+n+1);
    for(ll x=1;x<=data[n];x++){
        ll now=x,pos=1,temp=1;
        for(ll eatten=0;eatten<n;){
            while(pos<=n&&data[pos]<=now)pos++;
            temp=(pos-eatten-1)%p;
            if(!temp)break;
            //f=(f*temp)%p;
            eatten++;now++;
        }
        //cout<<x<<" "<<f<<endl;
        if(temp)ans.push_back(x);
    }
    cout<<ans.size()<<endl;
    for(auto i:ans)cout<<i<<" ";
    cout<<endl;
}