AtCoder Beginner Contest 214 題解(A-E)

AtCoder Beginner Contest 214 題解(A-E)

A. New Generation ABC

題目大意：

根據數的范圍輸出答案，

解題思路：

簽到題，

代碼：

#include<bits/stdc++.h>
using namespace std;
int n;
int main()
{
    cin>>n;
    if(n<=125) puts("4");
    else if(n<=211) puts("6");
    else puts("8");       
    return 0;
}

B. How many?

題目大意：

問有多少個三元組 ( a , b , c ) (a,b,c) (a,b,c)滿足 a + b + c ≤ S , a × b × c ≤ T a+b+c\le S,a\times b\times c\le T a+b+c≤S,a×b×c≤T，

解題思路：

因為資料比較小，直接 O ( S 3 ) O(S^3) O(S3)暴力就行，

代碼：

#include<bits/stdc++.h>
using namespace std;
int S,T;
int main()
{
    cin>>S>>T;
    int res=0;
    for(int i=0;i<=S;i++)
        for(int j=0;j+i<=S;j++)
            for(int k=0;k+i+j<=S;k++)
                    if(i*j*k<=T) res++;

    cout<<res<<endl;
    return 0;
}

C. Distribution

題目大意：

n n n個人站成一個圈，第 i i i個人會在 t i t_i ti?的時間得到一顆寶石，并且在 s i s_i si?秒后將石頭遞給下一個人，問每個人第一次得到的寶石的時間是多少，

解題思路：

每個人只能從前一個人手上得到寶石或者到了 t i t_i ti?時間得到寶石，

所以我們就從最早得到寶石的那個人列舉一圈， a n s [ i ] = min ? ( t [ i ] , a n s [ i ? 1 ] + s [ i ? 1 ] ) ans[i]=\min(t[i],ans[i-1]+s[i-1]) ans[i]=min(t[i],ans[i?1]+s[i?1])，

時間復雜度 O ( n ) O(n) O(n)

代碼：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5+10;
LL a[N],s[N],t[N];
int n;
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%lld",&s[i]);
    for(int i=0;i<n;i++) scanf("%lld",&t[i]);
    int p=0,Min=2e9;
    for(int i=0;i<n;i++)
        if(t[i]<Min){
            p=i;
            Min=t[i];
        }
    a[p]=t[p];
    for(int i=1;i<n;i++){
        int cur=(p+i)%n,pre=(p+i-1+n)%n;
        a[cur]=min(t[cur],a[pre]+s[pre]);
    }
    for(int i=0;i<n;i++) printf("%lld\n",a[i]);
    return 0;
}

D. Sum of Maximum Weights

題目大意：

給出一顆 n n n個頂點的樹， n ? 1 n-1 n?1條無向邊都有相應的邊權，設 f ( u , v ) f(u,v) f(u,v)為 u u u和 v v v之間路徑上的最長邊，求 ∑ i = 1 n ? 1 ∑ j = i + 1 n f ( i , j ) \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n}f(i,j) i=1∑n?1?j=i+1∑n?f(i,j)，

解題思路：

我們假設連接 u u u和 v v v的邊 e e e是最長的一條邊，權重是 w w w，那么這條邊就相當于一條獨木橋，將 u u u和 v v v分割成兩個連通塊，如果要從一個連通塊到另一個連通塊必須要經過 e e e,設兩個連通塊的大小分別是 u . s i z e u.size u.size和 v . s i z e v.size v.size，那么這條邊在最終答案中一定貢獻了 u . s i z e × v . s i z e u.size\times v.size u.size×v.size次，

通過上述分析，我們發現可以將所有的邊按照權重從小到大排序，同時對于每個頂點維護一個并查集，每條邊的貢獻次數就是這條邊所連接的兩個連通塊大小的乘積，每次加邊就相當于將兩個連通塊合并成一個更大的連通塊，

時間復雜度 O ( n l o g n ) O(nlogn) O(nlogn)，

代碼：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct Edge{
    int a,b,w;
    bool operator <(const Edge &t)const{
        return w<t.w;
    }
}e[N];
int f[N],sz[N];
int n,m;
int find(int x){
    if(f[x]!=x) f[x]=find(f[x]);
    return f[x];
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n-1;i++) scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].w);
    sort(e,e+n-1);
    for(int i=1;i<=n;i++) f[i]=i,sz[i]=1;
    long long res=0;
    for(int i=0;i<n-1;i++){
        int a=e[i].a,b=e[i].b,w=e[i].w;
        int fa=find(a),fb=find(b);
        res+=(long long)w*sz[fa]*sz[fb];
        sz[fa]+=sz[fb];
        f[fb]=fa;
    }
    printf("%lld\n",res);
    return 0;
}

E. Packing Under Range Regulations

題目大意：

有 1 0 9 10^9 109個箱子編號為 [ 1 , 1 0 9 ] [1,10^9] [1,109]和 n n n個球編號是 [ 1 , n ] [1,n] [1,n]，每個箱子最多只能放一個球，其中第 i i i個球要求放在 [ l i , r i ] [l_i,r_i] [li?,ri?]這個區間的箱子中，問能否存在一個方案滿足要求，

解題思路：

做法的核心就是對于第 j j j個箱子，所有 l i ≥ j l_i\ge j li?≥j的球中，我們要優先選擇 r i r_i ri?最小的球，這個貪心的原因是很直觀的，

如果是暴力考慮所有的箱子，肯定是會 T L E TLE TLE的，所以我們考慮只考慮那些有效的區間，通過球來列舉會極大優化時間，是學習官方題解的做法，具體做法看代碼，

時間復雜度 O ( n l o g n ) O(nlogn) O(nlogn)，

代碼：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=2e5+10;
PII a[N];
int n;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d%d",&a[i].first,&a[i].second);
        priority_queue<int,vector<int>,greater<int> > heap;
        sort(a+1,a+1+n);
        a[n+1].first=2e9;
        int cur=0;
        bool flag=true;
        for(int i=1;i<=n&&flag;i++){
            if(cur<a[i].first) cur=a[i].first;
            heap.push(a[i].second);
            while(i<n&&a[i+1].first==a[i].first){
                 heap.push(a[i+1].second);
                 i++;
            }
            while(!heap.empty()&&cur<a[i+1].first){
                int t=heap.top();heap.pop();
                if(cur<=t) cur++;
                else{
                    flag=false;
                    break;
                }
            }
        }
        puts(flag?"Yes":"No");
    }
    return 0;
}