Codeforces Round #654 (Div. 2)

比赛链接

E2. Asterism (Hard Version)

题意

给定 $n$ 个正整数，代表 $n$ 个敌人，每个敌人有 $a_i$ 颗糖，再给定一个素数 $p(p \le n)$。

定义游戏规则为一开始玩家拥有若干颗糖，每次玩家可以选取一个未挑战且手上糖果数不大于玩家的敌人，打败他获得一颗糖果。

定义 $f(x)$ 为玩家一开始拥有 $x$ 颗糖时可以战胜所有敌人的方案数。

要求输出所有满足 $p\nmid f(x)$ 的 $x$。

题解 $1$

设 $b_i$ 为糖果数不大于 $i$ 的敌人个数，$C_i(x)=b_{x+i}-i$。

有 $f(x)=\prod_{i=0}^{n-1} C_i(x)$。

易知 $C_{n-1}(x)\le 1$ 且 $C_i(x)-C_{i-1}(x)=b_{x+i}-1\ge -1$。

所以 $p\nmid f(x)\iff \forall i(0\le i\lt n \longrightarrow C_i\lt p)$。

由于 $C_i(x)\le C_i(x+1)$，所以答案为一段区间。

考虑 $x$ 的可能范围，记 $A=\max a_i$。若 $x\le A-n$，则 $f(x)= 0$，有 $p\mid f(x)$。若 $x\ge A$，则 $f(x)= n!$，有 $p\mid f(x)$。

所以将区间左端点初值设为 $A-n+1$，右端点初值设为 $A$，暴力枚举 $i=0\sim n-1$ 的情况，维护一下即可，时间复杂度 $O(n)$。

查看代码

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <queue>
#include <cmath>
#define _for(i,a,b) for(int i=(a);i<(b);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define mem(a,b) memset((a),(b),sizeof(a))
using namespace std;
typedef long long LL;
inline int read_int(){
	int t=0;bool sign=false;char c=getchar();
	while(!isdigit(c)){sign|=c=='-';c=getchar();}
	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
	return sign?-t:t;
}
inline LL read_LL(){
	LL t=0;bool sign=false;char c=getchar();
	while(!isdigit(c)){sign|=c=='-';c=getchar();}
	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
	return sign?-t:t;
}
inline void write(LL x){
	register char c[21],len=0;
	if(!x)return putchar('0'),void();
	if(x<0)x=-x,putchar('-');
	while(x)c[++len]=x%10,x/=10;
	while(len)putchar(c[len--]+48);
}
inline void space(LL x){write(x),putchar(' ');}
inline void enter(LL x){write(x),putchar('\n');}
const int MAXN=1e5+5;
int a[MAXN],b[MAXN<<1];
int main()
{
	int n=read_int(),p=read_int(),A=0;
	_for(i,0,n){
		a[i]=read_int();
		A=max(A,a[i]);
	}
	_for(i,0,n)
	b[max(0,a[i]-(A-n))]++;
	_for(i,1,n<<1)
	b[i]+=b[i-1];
	int st=1,en=n;
	_rep(i,1,n){
		while(b[st+(i-1)]<i)
		st++;
	}
	_for(i,0,n){
		while(b[en+i]-i>=p)
		en--;
	}
	st+=(A-n),en+=(A-n);
	if(st<=en){
		enter(en-st+1);
		_rep(i,st,en){
			if(i!=st)
			putchar(' ');
			write(i);
		}
	}
	else
	enter(0);
	return 0;
}

CVBB ACM Team

目录

Codeforces Round #654 (Div. 2)

E2. Asterism (Hard Version)

题意

题解 $1$

F. Raging Thunder

题意

题解

CVBB ACM Team

用户工具

站点工具

目录

Codeforces Round #654 (Div. 2)

E2. Asterism (Hard Version)

题意

题解 $1$

F. Raging Thunder

题意

题解

页面工具