专栏首页ypwAtCoder Beginner Contest 177 A ~ E

AtCoder Beginner Contest 177 A ~ E

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;
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • P1036 选数

    用户7727433
  • 牛客小白月赛22 A~~J

    A.链接:https://ac.nowcoder.com/acm/contest/4462/A 来源:牛客网

    用户7727433
  • 快乐AC三道题---第一周

    我们要解决的无非是是否把下一个元素加入,是否开始维护一个新的子段。我们开一个数组b[] , 记录b[i],表示以a[i]结尾的全部子段中 最大的那个的 和。 这...

    用户7727433
  • P2015 二叉苹果树 树状dp

    用户2965768
  • P1036 选数

    用户7727433
  • 2013年第四届蓝桥杯C/C++B组省赛题目解析

    Zoctopus
  • BUPT2017 wintertraining(15) #2 题解

    ​ 因为2520%pre_lcm0,所以x%pre_lcm(x%2520)%pre_lcm

    饶文津
  • 洛谷P2765 魔术球问题(贪心 最大流)

    attack
  • HDU 5157 Harry and magic string(回文树)

    Harry and magic string Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: ...

    ShenduCC
  • Day3上午解题报告

    预计分数:100+40+50=190 实际分数:100+40+50=190 T1 https://www.luogu.org/problem/show?pid=...

    attack

扫码关注云+社区

领取腾讯云代金券