CodeforcesGlobalRound24(11.28补题)-创新互联

Dashboard - Codeforces Global Round 24 - Codeforces

成都创新互联公司的客户来自各行各业,为了共同目标,我们在工作上密切配合,从创业型小企业到企事业单位,感谢他们对我们的要求,感谢他们从不同领域给我们带来的挑战,让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。专业领域包括成都网站制作、成都做网站、电商网站开发、微信营销、系统平台开发。

A. Doremy's Paint

题意:给定一个长度为n的序列,定义 c(l,r)为 l~r 之间不同的序列的个数,确定一组 l,r 使得

l-r-c(l,r) 的值大

思路:可以发现当多加一个数时并不会影响答案的大小(如l-- 或r++ ,l-r减小或增大的同时,c(l,r) 会同步 增大或减小),故让l,r之间的相同的数的个数尽可能的大即可,也就是输出1,n即可。

#include// #define int long long
#define PII pair#define ios ios::sync_with_wtdio(false);cin.tie(0);cin.tie(0)

using namespace std;

const int N=1e5+10;
int a[N];
int n;

void solve(){
	cin >>n;
	for(int i=0;i>a[i];
	cout<< "1 n"<< endl;
}

int main(){
	int t=1;
	cin >>t;
	while(t--){
		solve();
	}
	return 0;
}

B. Doremy's Perfect Math Class

题意:给定一个大小为n的集合(不含有重复元素),我们可以选定集合中的两个元素做差,将差加入集合中,问集合中的数最多有多少个

思路:猜结论,如若一组数的gcd为1,那么max{1...n}中的任意一个数都可以构造出来,如({16,6},gcd=2,16-6=8,8-6=2,则可构造出{2,4,6,8,10,12,14,16})。一个集合能构造出的数就是集合内大的值除gcd,如(gcd为3 {3,6,.....,max})。

故结论为                    ans=\frac{max}{gcd}

#include// #define int long long
#define PII pair#define ios ios::sync_with_wtdio(false);cin.tie(0);cin.tie(0)

using namespace std;

const int N=1e5+10;
int a[N];
int n,m;

void solve(){
	cin >>n;
	int res=0;
	int mx=0;
	for(int i=0;i>a[i];
		mx=max(mx,a[i]);
		res=__gcd(res,a[i]);
	}
	cout<< mx/res<< endl;
}

int main(){
	int t=1;
	cin >>t;
	while(t--){
		solve();
	}
	return 0;
}

C. Doremy's City Construction

题意:给定n个带权点,在点中添加若干条无向边,使得途中不存在连续非下降的路径(即连续非下降的路径大于等于3不符合)

思路:将点的依据权排序之后,可以将点分为两个集合,小点集合和大点集合,集合中的每一个点都可以连接另一个集合中的所有点,故可以枚举两个集合的边界,取大值即可。

#include#define int long long
#define PII pair#define ios ios::sync_with_wtdio(false);cin.tie(0);cin.tie(0)

using namespace std;

const int N=2e5+10;
int a[N];
int n;

void solve(){
	cin >>n;
	mapmp;
	for(int i=0;i>a[i];
		mp[a[i]]++;
	}
	sort(a,a+n);
	if(a[0]==a[n-1]){
		cout<< n/2<< endl;
		return ;
	}
	int ans=0,num=0;
	for(int i=0;i>t;
	while(t--){
		solve();
	}
	return 0;
}

D:D. Doremy's Pegging Game(理解不了,贴个题解)

题意:存在 n 个点的钉子,绕成一个环。其中环内部有一个特殊的钉子,这个钉子比环上的钉子都要短。刚开始一个橡皮绳绕在环上,每次可以取走一个环上的钉子。钉子被取走后橡皮筋会收缩。一旦其中一个点被挂在了中间特殊的钉子上,游戏结束。求删除序列的方案数。

思路:

#include#define LL long long 
using namespace std;

const int MX = 5000 + 233;
LL C[MX][MX] ,n ,p ,fac[MX];

void init(){
	for(int i = 0 ; i< MX ; ++i) C[i][0] = 1;
	for(int i = 1 ; i< MX ; ++i)
		for(int j = 1 ; j< MX ; ++j)
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % p;
	fac[0] = fac[1] = 1 % p;
	for(int i = 2 ; i< MX ; ++i) fac[i] = fac[i - 1] * i % p;
}

int main(){
	cin >>n >>p;
	init();
	int t = n / 2;
	LL Ans = 0;
	for(int i = t ; i<= n - 1 ; ++i){
		if((n & 1) && i == n - 1) break;
		int upper = (i == n - 1) ? n - i - 1 : n - i - 2;
		for(int j = 0 ; j<= upper ; ++j){
			Ans = (Ans + n * (2 * t - i) * C[upper][j] % p * fac[j + i - 1]) % p;
		}
	}
	cout<< Ans<< endl;
	return 0;
}

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


网站栏目:CodeforcesGlobalRound24(11.28补题)-创新互联
网站链接:http://pwwzsj.com/article/dpohes.html