专栏首页wymCodeforces Round #561 (Div. 2)

Codeforces Round #561 (Div. 2)

A.老老实实用组合数做的。

//A
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 202020;
const int MOD = 998244353;
ll fac[MAXN],favin[MAXN];
ll quic(int a,int b){
	ll  ans = 1;
	for(;b;b>>=1,a=(ll)a*a%MOD){
		if((b&1)){
			ans=ans*a%MOD;
		}
	}
	return ans;
}
void init(){
	fac[0]=1;
	for(int i=1;i<=MAXN;i++)
		fac[i]=fac[i-1]*i%MOD;
	favin[MAXN]=quic(fac[MAXN],MOD-2);
	for(int i=MAXN;i>0;i--)
		favin[i-1] = favin[i]*i%MOD; 
	//1/(i-1)! =  1/(i!) * i;
}
ll C(int n,int m){
	if(n<0||m<0||m>n)return 0;
	return fac[n]*favin[m]%MOD*favin[n-m]%MOD; 
}
int main()
{
	init();
	int n;
	int q[400];
	memset(q,0,sizeof(q));
	cin>>n;
	while(n--){
		string s;
		cin>>s;
		q[s[0]]++;
	}
	ll ans = 0;
	for(char i = 'a';i<='z';i++ ){
		int nn = q[i]/2;
		ans+=C(nn,2);
		ans+=C(q[i]-nn,2);
	}
	cout<<ans<<endl;
	return 0;
}

B.保证行列都大于等于5,构造出来就行。

//B
#include <bits/stdc++.h>
using namespace std;
char c[6] = {'a','e','i','o','u'};
int main()
{
	int k,n=-1,m=-1;
	scanf("%d",&k); 
	for(int i=5;i<=k/5;i++)
		for(int j=5;j<=k/5;j++)
		{
			if(i*j==k){
				n = i; m = j;
				break;
			}	
		}
	if(n<0&&m<0){
		printf("-1");return 0; 
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			printf("%c",c[(i+j)%5]);	
		}
	
	}
	return 0;
}

C. 求min(|X-Y|,|X+Y|) <= min(X,Y) <= max(X,Y) <= max(|X-Y|,|X+Y|)

然后分类x>y>0,x>0>y,0>x>y,很快发现若有序且负数转换为绝对值没影响,且此时X<=2*Y才行。

于是二分求解。

//C
#include <algorithm>
#include <iostream>
using namespace std;
int a[200005];
#define ll long long
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		int t;
		scanf("%d",&t);
		a[i] = abs(t);
	}
	sort(a,a+n);
	ll ans = 0;
	for(int i=0;i<n-1;i++){
		int add = lower_bound(a,a+n,2*a[i])- a;
		if(a[add]>2*a[i]){
			add=add-i-1;
		}else {
			while(a[add]==2*a[i]&&add<n){
				add++;
			}
			add--;
			add = add - i;
		}
		ans+=(ll)add;
	}
	cout<<ans;
 	return 0;	
} 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 区间更新与点值

    用户2965768
  • [LightOJ-1356] Prime Independence 二分图+素数分解

    数据大,需要用优化的二分图,对每个数求出素因数,不独立的两个数之间就差一个素因数,若 a 去掉这个素因数得到b

    用户2965768
  • Educational Codeforces Round 67 (Rated for Div. 2) A~E 贪心,构造,线段树,树的子树

    Educational Codeforces Round 67 (Rated for Div. 2)

    用户2965768
  • HDU 3488 Tour(拆点+二分图最大权匹配--KM)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3488

    Ch_Zaqdt
  • 1065. 单身狗(25)

    “单身狗”是中文对于单身人士的一种爱称。本题请你从上万人的大型派对中找出落单的客人,以便给予特殊关爱。

    AI那点小事
  • 【USACO 1.2】Palindromic Squares

    饶文津
  • 2017年中国大学生程序设计竞赛-中南地区赛暨第八届湘潭市大学生计算机程序设计大赛题解&源码(A.高斯消元,D,模拟,E,前缀和,F,LCS,H,Prim算法,I,胡搞,J,树状数组)

    A-------------------------------------------------------------------------------...

    Angel_Kitty
  • 1035. 插入与归并(25)

    插入排序是迭代算法,逐一获得输入数据,逐步产生有序的输出序列。每步迭代中,算法从输入序列中取出一元素,将之插入有序序列中正确的位置。如此迭代直到全部元素有序。

    AI那点小事
  • 【C语言笔记】函数参数压栈的顺序?

    按照日常习惯来看,C语言的函数参数压栈顺序是从左到右吧?但是事实却是相反的,C语言函数参数压栈顺序是从右到左的。下面看一个程序:

    正念君
  • 图论--拓扑排序--模板

    风骨散人Chiam

扫码关注云+社区

领取腾讯云代金券