CodeforcesGlobalRound24(11.28补题)-创新互联-乐山大橙子建站

新闻中心

这里有您想知道的互联网营销解决方案

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://lswzjz.com/article/dpohes.html

新闻中心

其他资讯