首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >AtCoder Beginner Contest 177 A ~ E

AtCoder Beginner Contest 177 A ~ E

作者头像
杨鹏伟
发布2020-09-10 23:46:47
3510
发布2020-09-10 23:46:47
举报
文章被收录于专栏:ypwypw

A - Don’t be late

签到:

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int main(){
	double d,t,s;
	cin>>d>>t>>s;
	double ans = d / s;
	if(ans <= t) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
} 

B 签到

思路:由于数据范围比较小,所以暴力即可。数据大的话我们可以考虑KMP算法

#include<iostream>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
 
int main(){
	string s,t;
	cin>>s>>t;
	
	int lens = s.length();
	int lent = t.length();
	int ans = inf;	
	for(int i=0;i+lent <= lens ;i++){
		int res = 0;
		for(int j=0;j<lent;j++){
			if(s[i+j]!=t[j]){
				res++;
			}
		}
		ans = min(ans,res);
	}
    cout<<ans<<"\n";
    
	return 0;
} 

C 思路:数据范围比较大,O(n^n)的复杂度肯定不可以,那么我们要分析式子 假设有一组数据:

4 1 3 4 5

那么原式 =1×3+1×4+1×5+3×4+3×5+4×5=1×3+1×4+1×5+3×4+3×5+4×5

=1×3+1×4+3×4+1×5+3×5+4×5=1×3+1×4+3×4+1×5+3×5+4×5

=1×3+(1+3)×4+(1+3+4)×5=1×3+(1+3)×4+(1+3+4)×5

所以我们可以得到可以对数组从小到大进行排序,然后每次用前i-1的前缀和乘以当前这个数就行了

#include<iostream>
#include<algorithm>
#define maxn 200005
using namespace std;
typedef long long ll;
ll n,a[maxn],s[maxn];
ll ans,res;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	
	sort(a+1,a+1+n);
	ans = 0;
	
	s[1] = a[1];
	for(int i=2;i<=n;i++){
		s[i] = s[i-1] + a[i];
		s[i] %= 1000000007;
	}
	for(int i=2;i<=n;i++){
		ans = (ans+a[i] * s[i-1])%1000000007; 
	}
	cout<<ans<<endl;
	return 0;
}

D

思路:题意很直观,就是让我们求最大分组数。条件是组内所有人不是朋友关系。

思路:并查集板子题。我们可以对数据预处理后然后对其进行分块,然后其中哪块元素最多的那个个数就是最大组数。

#include<iostream>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
 
int f[200005];
int fa[200005];
int find(int x){
	return x != f[x]?f[x]=find(f[x]):x;
}
 
void join(int x,int y){
	int fx = find(x);
	int fy = find(y);
	if(fx != fy) f[fx] = fy;
}
 
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) f[i] = i;
	
	for(int i=1;i<=m;i++){
		int aa,bb;
		cin>>aa>>bb;
		join(aa,bb);	
	}
	
    for(int i=1;i<=n;i++) fa[i] = find(f[i]);
	int ans = -inf;
	sort(fa+1,fa+1+n);
	int num = 1;
	for(int i=2;i<=n;i++){
		if(fa[i] == fa[i-1]) ++num;
		else ans = max(ans,num),num=1;
	}
	cout<<max(ans,num)<<endl;
	return 0;
}

E 思路:判断两两互质:分解质因子,如果一个因子同时含有多个数,那么这个序列不是互质的。 判断所有数互质:取第一个数,然后在取其余剩余数的最大值,两者gcd为一则说明所有数互质。

#include <cstdio>
int n,a,d,t[1000003],maxa=-(1<<30);
//maxa保存a的最大值,也是因子的最大值,t[i]表示因子i有多少个,d为n个数的最大公因数
int gcd(int x,int y){
    if(!y) return x;
    return gcd(y,x%y);
}
void fj(int x){//分解质因数
    for(int i=2;i*i<=x;){
        if(!(x%i)){
            ++t[i];//用桶记下来
            while(!(x%i)) x/=i;
        }
        else ++i;
    }
    if(x>1) ++t[x];//不要忘了这一句
}
int main(){
    scanf("%d%d",&n,&a);
    d=a;//d初始值为a
    for(int i=2;i<=n;i++){
        scanf("%d",&a);
        if(maxa<a) maxa=a;//更新maxa
        d=gcd(d,a);//求n个数的公因数可以这么做
        fj(a);//对a分解质因数
    }
    if(d==1){
        for(int i=2;i<=maxa;i++)
            if(t[i]>1) return puts("setwise coprime"),0;
            //t[i]>1说明有几个数有相同的因子,则肯定有一对数不互质
        return puts("pairwise coprime"),0;
    }
    else return puts("not coprime"),0;
    return 0;
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2020-09-06 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档