圖論測資生成器

最近寫了一個 GRAPH_GEN.h 檔,想說可以方便生成測資。

簡介

  • 4~5 行是防禦性程式設計,避免多次引用標頭檔時發生編譯錯誤
  • 7~19 行用來生成隨機數
  • 21~32 行是帶有建構式的 edge 物件
  • 底下就是生成測資的物件

具體使用

  • GenTree(n) -> 生成一個有 n 個點,且無邊權的無根樹
  • GenConnectedGraph(n,m) -> 生成一個有 n 個點, m 條邊,且無邊權的連通圖
  • GenGraph(n,m) -> 生成一個有 n 個點, m 條邊,且無邊權的不保證連通圖
  • GenTree(n,k) -> 生成一個有 n 個點,且邊權介於 1~k 的無根樹
  • GenConnectedGraph(n,m,k) -> 生成一個有 n 個點, m 條邊,且邊權介於 1~k 的連通圖
  • GenGraph(n,m,k) -> 生成一個有 n 個點, m 條邊,且邊權介於 1~k 的不保證連通圖

前三個會回傳 vector<pair<int,int>> 每個皆有保證沒有自環,後三個則會回傳 vector<edge> ,以節省重複打 firstsecond 的時間

程式碼

#include<bits/stdc++.h>
using namespace std;

#ifndef GRAPH_GEN
#define GRAPH_GEN

unsigned seed=chrono::steady_clock().now().time_since_epoch().count();
mt19937_64 rng(seed);

using ll=long long;

ll Rand(ll a,ll b){
    uniform_int_distribution<ll> dis(a,b);
    return dis(rng);
}

ll Rand(ll a){
    return Rand(1,a);
}

struct edge{
    int from,to;
    long long dis;

    edge(){}

    edge(int f,int t,long long d){
        from=f;
        to=t;
        dis=d;
    }
};

class GraphGen{
    private :
        struct DSU{
            vector<int> dsu,rk;

            DSU(int n){
                dsu.resize(n+10);
                rk.resize(n+10);
                init();
            }

            void init(){
                for(int i=0;i<dsu.size();++i){
                    dsu[i]=i;
                }
            }

            int find(int a){
                if(dsu[a]==a){
                    return a;
                }else{
                    return dsu[a]=find(dsu[a]);
                }
            }

            bool same(int a,int b){
                return find(a)==find(b);
            }

            void uni(int a,int b){
                if(same(a,b)){
                    return;
                }

                if(rk[find(a)]==rk[find(b)]){
                    dsu[find(b)]=find(a);
                    rk[a]++;
                }else if(rk[find(a)]>rk[find(b)]){
                    dsu[find(b)]=find(a);
                }else{
                    dsu[find(a)]=find(b);
                }
            }
        };
    public :
//      nodes 1~n
        static vector<pair<int,int>> GenTree(int n){
            DSU dsu(n);
            vector<pair<int,int>> result;

            while(result.size()<n-1){
                int a=Rand(n),b=Rand(n);
                if(!dsu.same(a,b)){
                    result.emplace_back(a,b);
                    dsu.uni(a,b);
                }
            }

            return result;
        }
//      n nodes m edges, m need to bigger than n-1
        static vector<pair<int,int>> GenConnectedGraph(int n,int m){
            vector<pair<int,int>> result=GenTree(n);

            for(int i=0;i<m-n+1;++i){
                int a,b;
                do{
                    a=Rand(n);
                    b=Rand(n);
                }while(a==b);

                result.emplace_back(a,b);
            }

            return result;
        }
//      n nodes m edges, m need to bigger than n-1
        static vector<pair<int,int>> GenGraph(int n,int m){
            vector<pair<int,int>> result;

            for(int i=0;i<m;++i){
                int a,b;
                do{
                    a=Rand(n);
                    b=Rand(n);
                }while(a==b);

                result.emplace_back(a,b);
            }

            return result;
        }
//      nodes 1~n, and weight in 1~k
        static vector<edge> GenTree(int n,int k){
            DSU dsu(n);
            vector<edge> result;

            while(result.size()<n-1){
                int a=Rand(n),b=Rand(n),c=Rand(k);
                if(!dsu.same(a,b)){
                    result.emplace_back(a,b,c);
                    dsu.uni(a,b);
                }
            }

            return result;
        }

        static vector<edge> GenConnectedGraph(int n,int m,int k){
            vector<edge> result=GenTree(n,k);

            for(int i=0;i<m-n+1;++i){
                int a,b;
                do{
                    a=Rand(n);
                    b=Rand(n);
                }while(a==b);

                int c=Rand(k);

                result.emplace_back(a,b,c);
            }

            return result;
        }

        static vector<edge> GenGraph(int n,int m,int k){
            vector<edge> result;

            for(int i=0;i<m;++i){
                int a,b;
                do{
                    a=Rand(n);
                    b=Rand(n);
                }while(a==b);

                int c=Rand(k);

                result.emplace_back(a,b,c);
            }

            return result;
        }
};

#endif

使用範例 :

#include<bits/stdc++.h>
#include "GRAPH_GEN.h"
using namespace std;

int main(){
    vector<pair<int,int>> edges=GraphGen::GenTree(100000);
}

2021 資訊之芽入芽考 E. 大整數

題目連結:Sprout Online Judge No. 840

題目敘述

你有一個大整數 012345678910111213141516171819202122…

也就是說,這個大整數是把所有非負整數依序串在一起。

現在,給你 n、k,請你輸出,在這個大整數中,由左至右第 n 次出現數字 k,是出現在第幾個位置?

位置從 1 開始算,並保證 k 是介於 0 到 9 之間的整數。

注意到,因為這個大整數太特別了,你定義這個大整數的第一位是 0 。

n≤10^12,0≤k≤9

想法

數字這麼大,一定是二分搜尋,找出最後一個含有數字 k 小於 n 的數字。

而求在 num 之前有多少數字 k 的方法則放在 HackMD(因為比較好寫數學式)。

#include<bits/stdc++.h>
using namespace std;

using ll=long long;

// just for 0
ll countDigit(ll n){
    if(n<1) return 1;
    ll high=n,tp=0,cur=0,low=0,base=1,ret=0;
    while(high>0){
        high=n/(10*base);
        tp=n%(10*base);
        cur=tp/base;
        low=tp%base;
        if(cur==0){
            ret+=(high-1)*base+low+1;
        }else{
            ret+=high*base;
        }
        base*=10;
    }
    return ret+1;
}

// only for 1~9
ll countDigit(ll n,ll k){
    if(k==0) return countDigit(n);
    ll high=n,tp=0,cur=0,low=0,base=1,ret=0;
    while(high>0){
        high=n/(10*base);
        tp=n%(10*base);
        cur=tp/base;
        low=tp%base;
        if(cur==k){
            ret+=high*base+low+1;
        }else if(cur<k){
            ret+=high*base;
        }else{
            ret+=(high+1)*base;
        }
        base*=10;
    }
    return ret;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    ll n,k;
    cin>>n>>k;

    ll l=0,r=1000000000000000000;
    while(r-l>1){
        ll mid=l+r>>1;
        if(countDigit(mid,k)>=n){
            r=mid;
        }else{
            l=mid;
        }
    }

    ll ans=countDigit(l);
    for(int i=1;i<=9;++i){
        ans+=countDigit(l,i);
    }

    ll ctd=countDigit(l,k);
    l++;
    vector<int> ns;
    while(l>0){
        ns.emplace_back(l%10);
        l/=10;
    }
    reverse(ns.begin(),ns.end());

//  search the nth k
    for(int i=0;i<ns.size();++i){
        if(ctd==n) break;
        if(ns[i]==k) ctd++;
        ans++;
    }

    cout<<ans<<"\n";
}

APCS 2022/1/9

Q1. 程式交易

題目連結:h081: 1. 程式交易 – 高中生程式解題系統

想法

第一天先買,維護一個 bool 變數,分為有持股與無持股兩種情況。

  1. 有持股->若當前價格>=當初買的價格(tp)+D,賣掉,tp 改為當前股價
  2. 無持股->若當前價格<=當初賣的價格(tp)-D,買起來,tp 改為當前股價

細節

若交易結束仍持有股票,則不考慮該股票買進的成本 -> 賣掉的時候再加上獲利

實作

#include<bits/stdc++.h>
using namespace std;

bool iss=true;
int n,sum,d,tp;

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    cin>>n>>d>>tp;

    for(int i=1;i<n;++i){
        int now;
        cin>>now;
        if(iss && tp+d<=now){
            sum+=now-tp;
            tp=now;
            iss=false;
        }else if(!iss && tp-d>=now){
            tp=now;
            iss=true;
        }
    }

    cout<<sum<<"\n";
}

Q2. 贏家預測

題目連結:h082. 2. 贏家預測 – 高中生程式解題系統

想法

將輸贏判斷抽象化,方便除錯。其餘依照題目用 vector 模擬即可。

實作

#include<bits/stdc++.h>
using namespace std;

#define siz(v) ((int)v.size())
using ll=long long;

struct player{
//  s, t, fail times
    ll s,t,f;
};

player ps[1005];
int n,m;

bool battle(int a,int b){
    bool ret=(ps[a].s*ps[a].t)>=(ps[b].s*ps[b].t);
    if(ret){
        ll tps=ps[a].s+(ps[b].s*ps[b].t)/(2*ps[a].t);
        ll tpt=ps[a].t+(ps[b].s*ps[b].t)/(2*ps[a].s);
        ps[a].s=tps;
        ps[a].t=tpt;

        ps[b].s+=ps[b].s>>1;
        ps[b].t+=ps[b].t>>1;
        ps[b].f++;
    }else{
        ll tps=ps[b].s+(ps[a].s*ps[a].t)/(2*ps[b].t);
        ll tpt=ps[b].t+(ps[a].s*ps[a].t)/(2*ps[b].s);
        ps[b].s=tps;
        ps[b].t=tpt;

        ps[a].s+=ps[a].s>>1;
        ps[a].t+=ps[a].t>>1;
        ps[a].f++;
    }
    return ret;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    cin>>n>>m;
    for(int i=1;i<=n;++i) cin>>ps[i].s;
    for(int i=1;i<=n;++i) cin>>ps[i].t;

    vector<int> bt(n);
    for(int i=0;i<n;++i) cin>>bt[i];

    while(siz(bt)>1){
        vector<int> vt,fl;
        for(int i=0;i<siz(bt);i+=2){
            if(i==siz(bt)-1){
                vt.emplace_back(bt[i]);
            }else{
                if(battle(bt[i],bt[i+1])){
                    vt.emplace_back(bt[i]);
                    if(ps[bt[i+1]].f<m) fl.emplace_back(bt[i+1]);
                }else{
                    if(ps[bt[i]].f<m) fl.emplace_back(bt[i]);
                    vt.emplace_back(bt[i+1]);
                }
            }
        }

        while(bt.size()) bt.pop_back();

        for(auto i:vt) bt.emplace_back(i);
        for(auto i:fl) bt.emplace_back(i);
    }

    cout<<bt.front();
}

Q3. 數位占卜

題目連結:h083. 3. 數位占卜 – 高中生程式解題系統

前言

這是我唯一沒有滿分的題目,要用 set<long long> 陣列,還要 rolling hash 。
參考資料:2022 01/09 APCS 題解 – HackMD

實作

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
const ll MOD=2147483647;
const ll X=29;

// pwt[i]=29^i%MOD
// inv[i]=pwt[i] 在 MOD 的反元素
ll pwt[105],inv[105];
// hash value
ll h[50010][105];
// 原始資料
string s[50010];
// 對於長度為 i 的字串的 hash 值
set<ll> ss[105];

// 快速冪
ll POW(ll a,ll x){
    ll ret=1;
    while(x>0){
        if(x&1) ret=ret*a%MOD;
        a=a*a%MOD;
        x>>=1;
    }
    return ret;
}

void build(){
    pwt[0]=inv[0]=1;
    for(int i=1;i<=101;i++){
//      X^i%MOD
        pwt[i]=X*pwt[i-1]%MOD;
//      模逆元
        inv[i]=POW(pwt[i],MOD-2);
    }
}

void hah(string &tp,ll p){
    int m=tp.size();
//  不加 1 的話 a, aa, aaa 會被視為相同
    h[p][0]=tp[0]-'a'+1;
    for(int i=1;i<m;++i){
        h[p][i]=(h[p][i-1]+(tp[i]-'a'+1)*pwt[i])%MOD;
    }
    ss[m].insert(h[p][m-1]);
}

// 第 p 個字串的 [l,r] hash 前綴和的值
ll query(ll p,ll l,ll r){
    return l==0 ? h[p][r] : (h[p][r]-h[p][l-1]+MOD)%MOD*inv[l]%MOD;
}

ll solve(int n){
    ll ans=0;
    for(int i=0;i<n;++i){
        ll m=s[i].size();
        for(int j=1;j<m;++j){
//          從中間開始
            if(j*2<=m) continue;
//          若第 i 個字串的 [0,m-j-1] 與 [j,m-1] 相同
            if(query(i,0,m-j-1)==query(i,j,m-1)){
//              尋找匹配字串,(j*2-m) 補齊字串長度
                if(ss[j*2-m].count(query(i,m-j,j-1)))
                    ans++;
            }
        }
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    int n;
    cin>>n;
    build();
    for(int i=0;i<n;++i){
        cin>>s[i];
        hah(s[i],i);
    }

    cout<<solve(n)<<"\n";
}

Q4. 牆上海報

題目連結:h084. 4. 牆上海報 – 高中生程式解題系統

想法

Greedy + 二分搜。避免有人不知道要搜什麼,是搜尋高度。因為從題目中我們可以發現 -> 越高的地方可以放東西的區間越來越破碎,也越來越少。且若 x 是可以放的下的高度,選 x\'< x 都不會更好(題目要求越高越好)。這樣就可以一次刪除一半的區間。

那 Greedy 呢?因為有規定擺放順序,因此能放就放,這個區間放不下就移至下個區間。沒有區間可以放就表示這個高度不合法。

實作

#include<bits/stdc++.h>
using namespace std;

int n,k;
int h[200010],bd[50010];

bool check(int x){
    int psum=0;
    vector<int> len;
    for(int i=1;i<=n;++i){
        if(h[i]>=x){
            psum++;
        }else{
            len.emplace_back(psum);
            psum=0;
        }
    }
//  0也無所謂
    len.emplace_back(psum);

    for(int i=1,j=0;i<=k;++i){
        while(len[j]<bd[i]){
            j++;
            if(j==len.size()) return false;
        }
        len[j]-=bd[i];
    }
    return true;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    cin>>n>>k;
    for(int i=1;i<=n;++i) cin>>h[i];
    for(int i=1;i<=k;++i) cin>>bd[i];

    int l=0,r=1073741824;
    while(r-l>1){
        int mid=l+r>>1;
        if(check(mid)){
            l=mid;
        }else{
            r=mid;
        }
    }

    cout<<l<<"\n";
}

AtCoder ABC 215 D

題目連結:AtCoder Beginner Contest 215: D – Coprime 2

題目敘述 :

給定 n, m 下一行會有 n 個數字,輸出所有k in 1~m,k是與所有數字皆互質的數。

範例輸入 1 :

3 12
6 1 5

範例輸出 1 :

3
1
7
11

題解 :

用埃氏篩法在log(n)的時間內做質因數分解,接著將所有數字的質因數聯集存在bitset中,最後判斷1~m的所有數字的質因數之中有無存於bitset中。

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
const ll N=100010;
#define IO_SPEEDUP ios::sync_with_stdio(0);cin.tie(0);
#define IO_INIT cout<<fixed<<setprecision(6);

int n,m;
int pri[N];
bitset<N> bt;

void init(){
    pri[1]=0;
    for(int i=2;i<N;++i){
        if(pri[i]==0){
            pri[i]=i;
            for(ll k=(ll)i*i;k<N;k+=i)
                pri[k]=i;
        }
    }
}

void div(int n){
    while(pri[n]>0){
        bt[pri[n]]=true;
        n/=pri[n];
    }
}

bool check(int n){
    while(pri[n]>0){
        if(bt[pri[n]]){
            return false;
        }
        n/=pri[n];
    }
    return true;
}

int main(){
    IO_SPEEDUP; IO_INIT;

    cin>>n>>m;
    init();

    for(int i=0;i<n;++i){
        int a;
        cin>>a;
        div(a);
    }

    vector<int> ans;
    for(int i=1;i<=m;++i){
        if(check(i)){
            ans.emplace_back(i);
        }
    }

    cout<<ans.size()<<"\n";
    for(auto i:ans){
        cout<<i<<"\n";
    }
}

AtCoder ABC 215 C

題目連結:AtCoder Beginner Contest 215: C – One More aab aba baa

題目敘述 :

輸出 S 中字典順序第 K 大的排列.

範例輸入 1 :

aab 2

範例輸出 1 :

aba

範例輸入 2 :

ydxwacbz 40320

範例輸出 2 :

zyxwdcba

題解 :

用內建函式next_permutation()可以生成字典序大一點的排列。

#include<bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);cin.tie(0);

    string str;
    int n;

    cin>>str>>n;

//  因為沒有說輸入的會是字典序最小的,因此要先排序
    sort(str.begin(),str.end());
//  會是n-1是因為還沒進行前就是最小(第k=1小)
    for(int i=0;i<n-1;++i){
        next_permutation(str.begin(),str.end());
    }
    cout<<str;
}

AtCoder ABC 215 B

題目連結:AtCoder Beginner Contest 215: B – log2(N)

題目敘述 :

輸入正整數 N, 輸出最大整數 k 使 2^k≤N.

範例輸入 1 :

1000000000000000000

範例輸出 1 :

59

範例輸入 2 :

6

範例輸出 2 :

2

題解 :

用迴圈循環計算。 在整數運算時 ans<<=1 相當於 ans*=2

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    long long n;
    cin>>n;

    int ct=0;
    long long ans=1;
    while(ans*2<=n){
        ans<<=1;
        ct++;
    }
    cout<<ct;
}

注意!

用內建函式log2(n)式不會過的喔!

AtCoder ABC 215 A

題目連結:AtCoder Beginner Contest 215: A – Your First Judge

題目敘述 :

給定一個字串 S, 輸出 AC 若 S=="Hello,World!" 否則輸出 WA.

輸入說明 :

輸⼊一行字串

範例輸入 1 :

Hello,World!

範例輸出 1 :

AC

範例輸入 2 :

Hello,world!

範例輸出 2 :

WA

題解 :

直接判斷即可(s == "Hello,World!")

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    string ipt;
    cin>>ipt;
    if(ipt=="Hello,World!"){
        cout<<"AC";
    }else{
        cout<<"WA";
    }
}

2021全國學科能力競賽模擬賽 : 2.BGP

前言

我發現,全國能力競賽的難度似乎與我預期的有落差,這一題也是我唯一一個完全解開的題目。真的好難!

題目敘述 :

「BGP 劫持(BGP Hijacking)」是⼀種透過「邊界閘道器協定(Border Gateway Protocol,BGP)」 的性質進⾏攻擊的⼿段。簡單來說,每個伺服器會宣稱⾃⼰擁有⼀段 IP,並將這個訊息傳遞給周遭的伺服器,來更新他們的路由表。周遭的伺服器也會將這個更新繼續往外傳遞,使伺服器知道要如何將封包傳遞到指定的IP。而 BGP 劫持這個攻擊⼿法,就是透過錯誤地宣稱⾃⼰擁有某⼀段 IP,或者是⾃⼰通往擁有該 IP 的伺服器路徑更短,來使得其他路由器將 IP 往他傳遞。並透過 BGP 更新路由表的特性進⾏⼤規模的流量轉移,使得使⽤者無法存取特定的服務,或者是拿到封包之後拆解其中的內容以獲得敏感資訊。

現在,全國資訊安全能⼒競賽模擬賽要進⾏⼀場 BGP 劫持的攻防⼤賽。這場⽐賽⼀共有 N ⽀隊伍參加,每⽀隊伍會維護⼀台伺服器,之後主辦⽅每次會把⼀個封包丟給⼀個伺服器,並指定他要傳向哪個伺服器。接著每台伺服器會根據他的路由表,選擇⼀個伺服器傳遞封包,而參賽者要做的就是盡可能讓不相關的封包經過⾃⼰,從而破解其中的資訊,而封包的傳遞⽅和接收⽅則要負責保護傳遞的路徑不要被攻擊。作為全國資安第⼀把交椅,翔哥也有關注全國資訊安全能⼒競賽模擬賽,但是翔哥真的太強了,這種⽐賽的勝敗他並不放在⼼上,他關⼼的是有沒有可能⼤家都享受到⽐賽的過程。雖然傳遞的路徑會根據路由表以及接收者而異,可是這對翔哥來說是 a piece of cake。他已經預測出了 M 個封包潛在被劫持的⽅式。根據封包傳遞的性質,這些路徑必定不會讓封包在數個隊伍之間循環傳遞。

現在,翔哥想知道是否存在⼀種 BGP 劫持的狀況,使得封包會經過每⽀隊伍恰好⼀次。

輸入說明 :

輸⼊的第⼀⾏包含兩個⾮負整數 N 、M ,代表全國資訊安全能⼒競賽模擬賽⼀共有 N 個隊伍參加,且 有 M 個可能的封包劫持狀況。 接下來的 M ⾏,每⾏包含兩個正整數 si、ti,代表第 si 個隊伍拿到的封包有可能被第 ti 個隊伍劫持。 保證不存在⼀種劫持路徑使得⼀個封包可以在數個隊伍之間循環傳遞。

輸出說明 :

如果存在⼀種劫持封包的⽅式,使得每個隊伍會接⼿那個封包恰好⼀次,請輸出 N 個正整數於⼀⾏,代表封包可以依序經過哪些隊伍的伺服器,否則請輸出 −1。如果有很多種封包傳遞路徑都滿⾜條件,輸出任意⼀個都可以獲得 Accepted。

範例輸入 1 :

5 8
5 2
3 1
2 4
5 1
3 2
5 2
1 2
3 5

範例輸出 1 :

3 5 1 2 4

範例輸入 2 :

5 5
1 4
3 4
5 2
2 1
5 3

範例輸出 2 :

-1

題解 :

剛看到題目可能會以為是漢米頓路徑。然而實際上仔細閱讀後應該會發現,他保證圖是一個DAG,也因此可以主張一個貪婪法性質,必須由入度為0的點開始。並且,因為入度為0的點沒有進入的邊,所以兩個或以上的點入度為0時保證沒有路徑。如下圖

BGP_1必定是依照 1 -> 2 -> 3 的順序拔點,而下圖是一個沒有路徑的範例

BGP_2因為拔完1之後有兩個點入度為0,所以無解。

實作程式碼如下(因為比賽所以含有比較多巨集和一些其他的簡化技巧,我會在使用時加上註解)

#include<bits/stdc++.h>
using namespace std;

//縮短long long變數宣告以及常用常數
using ll=long long;
const ll MOD=1e9+7;
const ll INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const ll N=1000010;
const ll M=1010;
const long double PI=3.14159265358979;

//巨集(競賽縮短程式碼技巧)
#define ALL(v) v.begin(),v.end();
#define siz(v) ((int)v.size())
#define F first
#define S second
#define EB emplace_back
#define PB pop_back
#define EF emplace_front
#define PF pop_front
#define EE emplace
#define rs resize
#define MP make_pair

template<typename T> using prior=priority_queue<T>;
template<typename T> using Prior=priority_queue<T,vector<T>,greater<T>>;
template<typename T> using Stack=stack<T,vector<T>>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;

//N=1000010
vector<int> g[N];
//ind存入度
int ind[N];
int n,m;

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    cin>>n>>m;
    for(int i=0;i<m;++i){
        int f,t;
        cin>>f>>t;
//      EB -> emplace_back
        g[f].EB(t);
        ind[t]++;
    }

    queue<int> bfs;

    int ctind=0;
    for(int i=1;i<=n;++i){
        if(ind[i]==0){
            ctind++;
//          EE -> emplace
            bfs.EE(i);
//          兩個或以上的點入度為0
            if(ctind>1){
                cout<<-1;
                return 0;
            }
        }
    }

    vector<int> ans;
    while(!bfs.empty()){
        int n=bfs.front();
        bfs.pop();
//      EB -> emplace_back
        ans.EB(n);

        int ctind=0;
        for(auto i:g[n]){
            ind[i]--;
            if(ind[i]==0){
                ctind++;
//              EE -> emplace
                bfs.EE(i);
//              兩個或以上的點入度為0
                if(ctind>1){
                    cout<<-1;
                    return 0;
                }
            }
        }
    }

    for(auto i:ans){
        cout<<i<<" ";
    }
}

TIOJ 1143 95_4.靈犬尋寶

題目連結:1143 – 4.靈犬尋寶 | TIOJ INFOR Online Judge

題目敘述 :

正方形(左下角座標為(0,0),右上角座標為(99,99))的格網上,有一隻靈犬要尋找一個寶物,格網上除了靈犬與寶物之外,還有一些障礙物。一般情況下,只要不超出格網的邊界,靈犬的每一步最多有8個方向可供選擇,如圖一;但是必須注意,只有在A點沒有障礙物時才可以選擇方向1或方向2,只有在B點沒有障礙物時才可以選擇方向3或方向4,只有在C點沒有障礙物時才可以選擇方向5或方向6,只有在D點沒有障礙物時才可以選擇方向7或方向8。如果靈犬可以從出發的位置走到寶物的位置,其總共使用的步數,理論上應有一個最小值;但是靈犬也有可能無法走到寶物的位置。過程中,靈犬不可以走到障礙物的位置上。

以圖二為例,有多達4個障礙物介於靈犬與寶物之間,但是靈犬最快只要2步就可以到達寶物的位置。圖三是另一個例子,靈犬的位置靠近角落,雖然只有2個障礙物,靈犬卻無法到達寶物的位置。

請撰寫一個程式,若靈犬可以從最初位置走到寶物的位置時,請列印出其使用之最少步數;若靈犬無法到達寶物的位置,請列印出單字『impossible』。

輸入說明 :

第一行為一個整數n,代表障礙物的個數,0 ≤ n ≤ 1000。接下來的n行,每行表示一個障礙物的座標,其橫座標值與縱座標值間以一個空白隔開。 再下來的一行,表示靈犬的最初位置,其橫座標值與縱座標值間以一個空白隔開。 最後一行,代表寶物的位置,其橫座標值與縱座標值間以一個空白隔開。 注意:輸入之障礙物、靈犬、寶物皆在不同位置。所有橫、縱座標值均為介於0(含)至99(含)之間的整數。

輸出說明 :

依行走之規則,若靈犬可以從其位置走到寶物的位置時,請列印出其使用之最少步數;若靈犬無法到達寶物的位置,請列印出單字『impossible』。

範例輸入 1 :

4
3 6
4 5
5 4
6 3
3 3
7 5

範例輸出 1 :

2

範例輸入 2 :

2
1 1
0 2
0 1
4 3

範例輸出 2 :

impossible

題解 :

這很明顯是圖的BFS,而為何不是DFS呢?因為題目要求輸出最短的路徑,而在DFS的時候,只要下一步能走就一直走,因此不一定會是最短路徑。

在BFS時,要先判斷座標是否存在,再看是否會被阻擋,以及是否已經到過,最後還有目標位置有無障礙物。若以上條件均通過才能將他推入佇列。

實作程式碼如下

#include<bits/stdc++.h>
using namespace std;
//這樣在宣告long long 時可以用ll代替
using ll=long long;
//常數N表示最大地圖長寬,多5以求保險
const ll N=105;

//位置
struct Pos{
    int r,c;

    friend bool operator==(Pos a,Pos b){
        return (a.r==b.r && a.c==b.c);
    }

    void operator+=(Pos b){
        r+=b.r;
        c+=b.c;
    }
};

//位置變化量
struct Deg{
    Pos pos;
    Pos lmt;
};

const Deg d[8]={
    {Pos{ 3, 1},Pos{ 1, 0}},
    {Pos{ 3,-1},Pos{ 1, 0}},
    {Pos{ 1,-3},Pos{ 0,-1}},
    {Pos{-1,-3},Pos{ 0,-1}},
    {Pos{-3, 1},Pos{-1, 0}},
    {Pos{-3,-1},Pos{-1, 0}},
    {Pos{-1, 3},Pos{ 0, 1}},
    {Pos{ 1, 3},Pos{ 0, 1}}
};

int n;

void solve(){
//  mp存那些位置有障礙物
    bitset<N> mp[N];
    int ct[N][N]={0};

    for(int i=0;i<n;++i){
        int r,c;
        cin>>r>>c;
        mp[r][c]=true;
    }

    Pos pos,loot;
    cin>>pos.r>>pos.c;
    cin>>loot.r>>loot.c;

    if((abs(pos.r-loot.r)+abs(pos.c-loot.c)) & 1){
        cout<<"impossible"<<"\n";
        return;
    }

    bool isf=false;
//  初始化
    queue<Pos> bfs;
    bfs.push(pos);
//  用1初始化避免以為沒到過
    ct[pos.r][pos.c]=1;

    while(!bfs.empty()){
        Pos now=bfs.front();
        bfs.pop();

        if(now==loot){
//          因為初始化為1,因此就要將答案-1
            cout<<ct[now.r][now.c]-1<<"\n";
            isf=true;
            break;
        }

        for(int i=0;i<8;++i){
            Pos next=now;
            next+=d[i].pos;
//          座標存在與否
            if(next.r<100 && next.c<100 && next.r>=0 && next.c>=0){
//              目標位置有無障礙物
                if(!mp[next.r][next.c]){
//                  是否會被阻擋
                    if(!mp[now.r+d[i].lmt.r][now.c+d[i].lmt.c]){
//                      是否已經到過
                        if(!ct[next.r][next.c]){
                            bfs.push(next);
                            ct[next.r][next.c]=ct[now.r][now.c]+1;
                        }
                    }
                }
            }
        }
    }

    if(!isf){
        cout<<"impossible"<<"\n";
    }
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
//處理多筆輸入(用於ZeroJudge:b059),但單筆輸入也不會錯
    while(cin>>n){
        solve();
    }
}

TIOJ 1142 95_3.關鍵邏輯閘

題目連結:1142 – 3.關鍵邏輯閘 | TIOJ INFOR Online Judge

題目敘述 :

一個組合電路(combinational circuit)由線路(wires)連接一組邏輯閘(logic gates)而成,並且不包含有向迴路(directed cycle)。一個組合電路的效能決定於最後一個主要輸出(primary output)被算出來的時間。假設每一個邏輯閘所需的運算時間都是固定並且是已知的,而線路的延遲(delay)是0。我們希望把一個組合電路所有的關鍵邏輯閘找出來。若一個邏輯閘的運算時間有任何延長,便會影響到整個電路的效能,它就被稱為關鍵邏輯閘。以圖一的組合電路為例,I1、I2、I3是主要輸入;O1、O2是主要輸出;圓圈代表邏輯閘,箭頭代表線路;每個邏輯閘有自己的編號以及固定的延遲時間。在圖一的例子當中,該組合電路中的O1會因為邏輯閘2、4、5的延遲,在時間400才會收到運算結果;而O2會因為邏輯閘2、4、6的延遲,在時間600才收到運算結果,因此O2是最後一個被算出來的主要輸出。關鍵邏輯閘分別是2、4以及6號邏輯閘,當其中一個關鍵邏輯閘的運算時間有任何延長,O2被算出來的時間也會再往後延遲。相反地,就算1號邏輯閘的運算時間從150延長到160,也不會影響到O2被算出來的時間,因此1號邏輯閘並不是關鍵邏輯閘。

輸入說明 :

第一行為一個整數 n (0 < n < 10000),代表一個組合電路的邏輯閘總數,每個邏輯閘的編號都不同,且範圍是介於 1~n 之間的整數。第二行為一個整數 m (m < 50000),代表線路的總數。接下來的 n 行,依序列出每個邏輯閘的運算時間;每個運算時間的值是介於 0 到 600 之間(含)的整數。最後 m 行,分別列出每一條線路由某個邏輯閘的輸出接到另一個邏輯閘的輸入。 注意:為簡化輸入,我們把主要輸入(primary inputs)與邏輯閘之間的線路,以及邏輯閘與主要輸出(primary outputs)之間的線路省略。(每一個邏輯閘至少都含有一個線路輸出到另一個邏輯閘或主要輸出)

輸出說明 :

列出關鍵邏輯閘的個數。

範例輸入 1 :

5 4
200
200
400
250
200
1 2
3 2
3 5
4 5

範例輸出 1 :

3

題解 :

很明顯,題目是要最長的路徑,因為最後一個完成的才會是關鍵邏輯閘,並且圖是有向無環圖,我的想法是先做出反圖( f->t 存成 t->f ),接著將所有終點接到虛擬點0,並用一次DFS算出所有點的最長路徑。以範測為例。

原圖的邊有 1->2, 3->2, 3->5, 和 4->5。我將它存為下圖

TIOJ1142_p1

可以聲稱一個性質"對於每個點而言,只有反圖上累積路徑最長的那幾條,後面的點才會有可能是關鍵邏輯閘",最後再做一次DFS,知道那些點是關鍵就可以間接算出數量了。

實作程式碼如下

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
const ll N=10010;

int n,m;
//dis存運算時間,dp存到這個點的最長距離
int dis[N],dp[N];
//ind表示indegree,ind[i]為零的都是終點
int ind[N];
//圖的鄰接串列表示法
vector<int> g[N];
//哪些是關鍵
bitset<N> ans;

//第一次DFS
void init(int node){
    dp[node]=0;
    for(auto i:g[node]){
        init(i);
        dp[node]=max(dp[node],dp[i]);
    }
    dp[node]+=dis[node];
}

//第二次DFS
void dfs(int node){
    int mx=0;
    bitset<N> tp;
    for(auto i:g[node]){
        if(dp[i]>mx){
            tp.reset();
            mx=dp[i];
            tp[i]=true;
        }else if(dp[i]==mx){
            tp[i]=true;
        }
    }

    for(auto i:g[node]){
        if(tp[i]){
            dfs(i);
        }
    }
    ans|=tp;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>dis[i];
    }

    for(int i=0;i<m;++i){
        int f,t;
        cin>>f>>t;
        g[t].emplace_back(f);
        ind[f]++;
    }

//  將所有終點用點0連接
    for(int i=1;i<=n;++i){
        if(ind[i]==0){
            g[0].emplace_back(i);
        }
    }

//  最後各跑一次就可以求出答案了
    init(0);
    dfs(0);

    cout<<ans.count();
}