天天看點
傳回

2021百度之星初賽第一場部分題解寫在前面1003 鴿子1004 萌新1006 毒瘤的資料結構1008 獵人殺總結

寫在前面

幾個家長要求我寫一些2021百度之星初賽第一場的題解。

1003 鴿子

原題連結

https://acm.hdu.edu.cn/showproblem.php?pid=6998

http://47.110.135.197/problem.php?id=5977

簡單題解

就是有些操作可做可不做。自然想到了01背包。是以可以使用動态規劃。

AC 代碼 

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PLL;
const LL INF=4e18;

const int MAXN=1e5+10;
LL dp[MAXN];//dp[j]為目前枚舉的操作（含之前枚舉過的操作）上，對于第j個位置的最小暗箱操作次數。

void solve(){
    memset(dp, -1, sizeof(dp));

    LL n, m, K, u, v;
    cin>>n>>m>>K;
    dp[K]=0;
    while(m--){
        LL u,v;
        cin>>u>>v;
        if (dp[u]==-1&&dp[v]==-1) {
            //什麼都不用做
            continue;
        } else if (dp[u]==-1&&dp[v]!=-1) {
            dp[u]=dp[v];
            dp[v]+=1;
        } else if(dp[u]!=-1&&dp[v]==-1){
            dp[v]=dp[u];
            dp[u]+=1;
        } else{
            LL t1=dp[v], t2=dp[u];
            dp[v]=min(dp[v]+1, t2);
            dp[u]=min(dp[u]+1, t1); 
        }
    }
    for(LL i=1;i<=n;++i){
        //這裡要特别注意，本題會卡最後一個空格。艹，PE了n次。
        cout<<dp[i];
        if (i!=n) {
            cout<<" ";
        }
    }
    cout<<"\n";
}

int main(){
#if 1
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#endif
    LL T;
    cin>>T;
    while (T--) {
        solve();
    }
    return 0;
}

1004 萌新

題目連結

https://acm.hdu.edu.cn/showproblem.php?pid=6999

http://47.110.135.197/problem.php?id=5974

題解

本題是一個數學題。

求 a   m o d   c = b   m o d   c a\ mod\ c=b\ mod\ c a mod c=b mod c，移項可得 ( a − b )   m o d   c = 0 (a-b)\ mod\ c=0 (a−b) mod c=0。

為了不減少通用性，我們假設 a > b a>b a>b。

是以最大的 c c c 就是 a − b a-b a−b。下面我們需要對 c c c 的最小值進行讨論。

當 a = = b a==b a==b 時候，最小的 c c c 為 2 2 2。

當 a − b = = 1 a-b==1 a−b==1 時候，也就是 a a a 和 b b b 互質，不存在最大和最小的 c c c。

當 a − b > 1 a-b>1 a−b>1 時候，暴力枚舉即可最小的 c c c 即可。如果找不到最小的 c c c，不存在最大和最小的 c c c。

注意我們需要将時間複雜度控制在 O ( T × l o g ( a − b ) ) O(T \times log(a-b)) O(T×log(a−b))。

AC 代碼 

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PLL;
const LL INF=4e18;

int main() {
#if 1
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#endif
    //freopen("00.in", "r", stdin);
    //freopen("00.out", "w", stdout);
    LL T;
    cin>>T;
    while (T--) {
        LL a,b;
        cin>>a>>b;

        //a%c=b%c -> (a-b)%c=0
        LL maxx=abs(a-b);
        if (0==maxx) {
            //a==b
            if (a>1) {
                cout<<"2 "<<a<<"\n";
            } else {
                cout<<"-1 -1\n";
            }
        } else if (1==maxx) {
            cout<<"-1 -1\n";
        } else {
            //暴力枚舉
            bool flag=true;
            for (LL i=2; i*i<=maxx; i++) {
                if (maxx%i==0) {
                    flag=false;
                    cout<<i<<" "<<maxx<<"\n";
                    break;
                }
            }
            if (flag) {
                cout<<maxx<<" "<<maxx<<"\n";
            }
        }

    }

    return 0;
}

1006 毒瘤的資料結構

題目連結

https://acm.hdu.edu.cn/showproblem.php?pid=7001

http://47.110.135.197/problem.php?id=5976

題解

考點資料結構的雙向連結清單。

由于本題的資料比較大，5e6。自然不能去一一周遊。是以本題可以考慮使用雙向連結清單或者并查集來完成。

道歉目前該題處于 TLE 狀态，應該是 5e6 資料讀取問題。已經解決。

我算服了，HDU 伺服器隻能使用 fread() 方式通過，其他方式讀取，全部都是 TLE。

為了這個 TLE，搞了幾天，都要懷疑人生了。不過還是自己對這樣海量資料讀取不了解問題。

AC代碼 

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PLL;
const LL INF=4e18;

const int MAXN=5e6+10;
bool aa[MAXN];
LL nex[MAXN];
LL pre[MAXN];

namespace fastIO {
    static char buf[100000],*h=buf,*d=buf;//緩存開大可減少讀入時間，看題目給的空間
    #define gc h==d&&(d=(h=buf)+fread(buf,1,100000,stdin),h==d)?EOF:*h++//不能用fread則換成getchar
    template<typename T>
    inline void read(T&x) {
        int f = 1;x = 0;
        register char c(gc);
        while(c>'9'||c<'0'){
            if(c == '-') f = -1;
            c=gc;
        }
        while(c<='9'&&c>='0')x=(x<<1)+(x<<3)+(c^48),c=gc;
        x *= f;
    }
    template<typename T>
    void output(T x)
    {
        if(x<0){putchar('-');x=~(x-1);}
        static int s[20],top=0;
        while(x){s[++top]=x%10;x/=10;}
        if(!top)s[++top]=0;
        while(top)putchar(s[top--]+'0');
    }
}
using namespace fastIO;

int main(){
    LL n,op,x;
    read(n);
    pre[n+1]=n;nex[0]=1;
    for (LL i=1;i<=n;++i) {
        nex[i]=i+1;
        pre[i]=i-1;
    }
    for (LL i=1;i<=n;++i){
        LL op,x;
        read(op);
        read(x);
        if(op==1){
            //1操作
            if(aa[x]) {
                continue;
            }
            nex[pre[x]]=nex[x];
            pre[nex[x]]=pre[x];
            aa[x]=1;
        } else {
            if(x==nex[0]){
                cout<<nex[nex[0]]<<"\n";
            } else {
                cout<<nex[0]<<"\n";
            }
        }
    }

    return 0;
}

下面代碼是使用并查集。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <utility>

using namespace std;
typedef long long LL;
typedef pair<LL, LL> PLL;
const LL INF=4e18;

namespace fastIO {
    static char buf[100000],*h=buf,*d=buf;//緩存開大可減少讀入時間，看題目給的空間
    #define gc h==d&&(d=(h=buf)+fread(buf,1,100000,stdin),h==d)?EOF:*h++//不能用fread則換成getchar
    template<typename T>
    inline void read(T&x) {
        int f = 1;x = 0;
        register char c(gc);
        while(c>'9'||c<'0'){
            if(c == '-') f = -1;
            c=gc;
        }
        while(c<='9'&&c>='0')x=(x<<1)+(x<<3)+(c^48),c=gc;
        x *= f;
    }
    template<typename T>
    void output(T x)
    {
        if(x<0){putchar('-');x=~(x-1);}
        static int s[20],top=0;
        while(x){s[++top]=x%10;x/=10;}
        if(!top)s[++top]=0;
        while(top)putchar(s[top--]+'0');
    }
}
using namespace fastIO;

const int MAXN=5e6+10;
LL rel[MAXN];
//并查集
LL fa[MAXN];
LL sa[MAXN];

void init(LL n) {
    for (LL i=0; i<=n; i++) {
        fa[i]=i;
        sa[i]=1;
    }
}

LL find(LL x) {
    if (fa[x]!=x) {
        fa[x]=find(fa[x]);
    }
    return fa[x];
}

void merge(LL x, LL y) {
    x=find(x);
    y=find(y);
    if (x==y) {
        return;
    }
    fa[x]=y;
    sa[y]+=sa[x];
}

int main() {
#if 0
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#endif
    //freopen("00.in", "r", stdin);
    //freopen("00.out", "w", stdout);
    int n;
    read(n);
    init(n);
    rel[0]=1;

    for (int i=1; i<=n; i++) {
        int opt, x;
        read(opt);
        read(x);
        if (1==opt) {
            rel[x]=1;
            if (rel[x-1]==1) {
                merge(x-1, x);
            }
            if (rel[x]==rel[x+1]) {
                merge(x, x+1);
            }
        } else {
            int ans=find(1);
            if (ans>=x-1) {
                ans=find(x+1);
                if (ans<=n && rel[ans]==1) {
                    ans++;
                }
            } else {
                ans=ans+rel[ans];
            }
            printf("%d\n", ans);
        }
    }

    return 0;
}

1008 獵人殺

題目連結

https://acm.hdu.edu.cn/showproblem.php?pid=7003

http://47.110.135.197/problem.php?id=5975

題解

模拟題。應該是這次初賽最簡單的一題。見鬼，竟然放在了最後一題。

AC 代碼 

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PLL;
const LL INF=4e18;

const int MAXN = 50+10;
LL a[MAXN];
LL b[MAXN][MAXN];
bool vis[MAXN];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    LL T;
    cin >> T;
    while(T--){
        LL n;
        cin>>n;

        //清資料
        memset(vis,0,sizeof(vis));

        LL cnt = n;
        LL lr = -1;//狼人
        bool flag = 0;
        for(LL i = 1; i <= n; i++){
            cin >> a[i];
            b[i][1] = a[i]; 
            if(a[i] == 1){
                lr = i;//找到狼的位置
            }
        }
        for(LL i = 1; i <= n; i++){
            for(LL j = 2; j <= n + 1; j++){
                cin >> b[i][j];
            }
        }

        LL k = 2;
        LL wz = b[lr][k];//第一晚 狼人殺人(可自刀） 
        while(lr != -1 && cnt > 2){
            if(lr == wz){//狼自殺 
                lr = -1;
                if(lr == -1){
                    cout <<"lieren\n";
                    break;
                }
            } else{//殺獵人 
                while(!vis[wz]){//如果獵人還活着 
                    vis[wz] = 1;//獵人死亡 
                    if(wz == lr){//如果下個死亡的是狼的話 
                        cout << "lieren\n";
                        flag = 1;
                        break;
                    }
                    cnt--;
                    if(cnt <= 2){//如果隻剩下兩個玩家的話 
                        cout <<"langren\n";
                        flag = 1;
                        break;
                    }
                    while(vis[b[wz][k]] == 1){//直到找出第wz行暗殺名單中最靠前且還活着的玩家。 
                        k++;
                    }
                    wz = b[wz][k];//更新 
                    k = 2;//将每個玩家的暗殺名單周遊下标重置。 
                }
                if(flag == 1){//遊戲結束，跳出循環 
                    break;
                }
            }
        }
    }

    return 0;
}

總結

還是太水了，還有些題需要進一步考慮一下。

OJ題解 2021年百度之星初賽第一場 題解 萌新 獵人殺 毒瘤的資料結構
上一篇: 在javaFX中使用java類
下一篇: 病毒侵襲持續中 HDU - 3065 AC自動機 巨坑的題 CSND部落格

繼續閱讀