【题解】ABC177

A

语法题

#include<bits/stdc++.h>
using namespace std;
const int inf=1e9+7;
int main(){
    double d,t,s;
    cin>>d>>t>>s;
    if(s*t>=d)cout<<"Yes";
    else cout<<"No";
    return 0;
}

B

暴力枚举

#include<bits/stdc++.h>
using namespace std;
const int inf=1e9+7;
string s;
string t;
int main(){
    cin>>s;
    cin>>t;
    int slen=s.length();
    int tlen=t.length();
    int ans=999999;
    for(int i=0;i<=slen-tlen;i++){
        int cnt=0;
        for(int j=0;j<tlen;j++){
            if(s[i+j]!=t[j]){
                cnt++;
            }
        }
        ans=min(ans,cnt);
    }
    cout<<ans<<endl;
    return 0;
}

C

可以用后缀和加速求和。

#include<bits/stdc++.h>
using namespace std;
const long long inf=1e9+7;
int n;
long long a[200005];
long long lsum[200005];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=n;i>=1;i--){
        lsum[i]=a[i]+lsum[i+1];
        lsum[i]%=inf;
    }
    long long ans=0;
    for(int i=1;i<=n;i++){
        ans+=a[i]*lsum[i+1];
        ans%=inf;
    }
    cout<<ans<<endl;
    return 0;
}

D

非常裸的找最大并查集

#include<bits/stdc++.h>
using namespace std;
const long long inf=1e9+7;
int n,m;
int father[200005];
int find(int x){
    if(father[x]==x){
        return x;
    }
    return father[x]=find(father[x]);
}
void unite(int x,int y){
    int fx=find(x),fy=find(y);
    if(fx!=fy){
        father[fx]=fy;
    }
}
int siz[200005];
int main(){
    cin>>n>>m;
    int u,v;
    for(int i=0;i<200005;i++)father[i]=i; 
    for(int i=1;i<=m;i++){
        cin>>u>>v;
        unite(u,v);
    }
    for(int i=1;i<=n;i++){
        siz[find(i)]++;
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans=max(ans,siz[i]);
    }
    cout<<ans<<endl;
    return 0;
}

E

很水的E,可是我脑子一抽竟然用筛法找每个质数,然后用再求每个数的质因数。。。卡了40min QAQ
判断pairwise coprime:将所有数字分解质因数,如果不同的数字出现同一个质因数就代表不是。否则就是。
判断setwise coprime:直接gcd即可.

#include<bits/stdc++.h>
using namespace std;
const long long inf=1e9+7;
const int maxn=1e6;
int n;
int a[maxn+5];
int gcd(int a,int b){
    if(a%b==0)return b;
    return gcd(b,a%b);
}
int tot=0;
bool used[maxn+5];
int fen(int x){
    int sqr=sqrt(x);
    for(int i=2;i<=sqr;i++){
        if(x%i==0){
            if(used[i])return 0;
            used[i]=1;
        }
        while(x%i==0){
            x/=i;
        }
    }
    if(x!=1){
        if(used[x])return 0;
        used[x]=1;
    }
    return 1;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    int ans=1;
    for(int i=1;i<=n;i++){
        if(!fen(a[i])){
            ans=0;
            break;
        }
    }
    if(ans==1){
        printf("pairwise coprime");
        return 0;
    }
    ans=a[1];
    for(int i=2;i<=n;i++){
        ans=gcd(ans,a[i]);
    }
    if(ans==1){
        printf("setwise coprime");
        return 0;
    }
    printf("not coprime");
    return 0;
}

F

简化一下题目其实就是 知道每一行都有一个i,j是以i开头,j结尾的线段,要求不在这些线段的集合中的最大行数以及位置。并且i,j是可改变的。
最后贪心一下。
但是前者我并不知道如何维护。
所以,
我不会。

本文链接:http://kaispace.com.cn/index.php/archives/707/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者