圖論測資生成器

最近寫了一個 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";
}

一個非常暴力的常數優化

就是下面這一行

#pragma GCC optimize ("O3,unroll-loops")

可以做到什麼效果呢?在某些情況下可以讓O(n^2)硬解10^5的測資。

int a[100010];

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

for(int i=0;i<q;++i){
    int l,r;
    cin>>l>>r;

    int ret=0;
    for(int j=l;j<r;++j){
        ret+=a[j];
    }
    cout<<ret<<"\n";
}

原本要用前綴和,變爆搜就會過。

以C++內建隨機演算法討論在規模為K之下的隨機次數之機率準確度

最近好像有關於遊戲抽獎機率問題的爭議。

雖然知道隨機有時是不準的,但我仍想用C++(僅梅克森旋轉演算法)親自嘗試。

以下為測試用程式碼。

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

//隨機樹使用參數為時間(毫秒)
unsigned seed = chrono::steady_clock::now().time_since_epoch().count();
mt19937_64 rng(seed);
//平均分布
uniform_int_distribution<int> dis(1,100);

long long RandomNumber(){
    return dis(rng);
}

void TestRamdon(int K){
    int mx=0,mn=100000000;
    for(int i=0;i<100000;++i){
        int ct=0;
        for(int j=0;j<K;++j){
            int tp=RandomNumber();
//          1~100 理論隨機 <=10 機率為 0.1(10%)
            if(tp<=10){
                ct++;
            }
        }
        mx=max(ct,mx);
        mn=min(ct,mn);
    }

    long double maxRate=1.0*mx/K;
    long double minRate=1.0*mn/K;

    cout<<"Max Rate In 10^5 Times "<<K<<" Times Random : "<<maxRate<<"\n";
    cout<<"Min Rate In 10^5 Times "<<K<<" Times Random : "<<minRate<<"\n";
    cout<<endl;
}

int main(){
    // test if random K times is enough to get reality rate

    const int K=400;
    const int TestTime=10;

    for(int i=0;i<TestTime;++i){
        TestRamdon(K);
    }
}

經過我實測,在理論機率為 10% 時,測試400次最悽慘的機率約莫落在 0.04(4%) ,而最佳機率則約為 0.17 (17%)

測試結果 K=400

Max Rate In 10^5 Times 400 Times Random : 0.17
Min Rate In 10^5 Times 400 Times Random : 0.0375 

Max Rate In 10^5 Times 400 Times Random : 0.1775
Min Rate In 10^5 Times 400 Times Random : 0.0425 

Max Rate In 10^5 Times 400 Times Random : 0.17
Min Rate In 10^5 Times 400 Times Random : 0.04   

Max Rate In 10^5 Times 400 Times Random : 0.1675
Min Rate In 10^5 Times 400 Times Random : 0.0325 

Max Rate In 10^5 Times 400 Times Random : 0.165
Min Rate In 10^5 Times 400 Times Random : 0.0375 

Max Rate In 10^5 Times 400 Times Random : 0.17
Min Rate In 10^5 Times 400 Times Random : 0.0375 

Max Rate In 10^5 Times 400 Times Random : 0.17
Min Rate In 10^5 Times 400 Times Random : 0.0425 

Max Rate In 10^5 Times 400 Times Random : 0.17
Min Rate In 10^5 Times 400 Times Random : 0.045  

Max Rate In 10^5 Times 400 Times Random : 0.165
Min Rate In 10^5 Times 400 Times Random : 0.0425 

Max Rate In 10^5 Times 400 Times Random : 0.17
Min Rate In 10^5 Times 400 Times Random : 0.0375

而到底應該要幾次以上才會到min=0.09(9%)呢?歡迎各位親自嘗試。以下是關於我有測試的次數

K=10

Max Rate In 10^5 Times 10 Times Random : 0.6
Min Rate In 10^5 Times 10 Times Random : 0  

Max Rate In 10^5 Times 10 Times Random : 0.7
Min Rate In 10^5 Times 10 Times Random : 0  

Max Rate In 10^5 Times 10 Times Random : 0.7
Min Rate In 10^5 Times 10 Times Random : 0

Max Rate In 10^5 Times 10 Times Random : 0.7
Min Rate In 10^5 Times 10 Times Random : 0

Max Rate In 10^5 Times 10 Times Random : 0.7
Min Rate In 10^5 Times 10 Times Random : 0

Max Rate In 10^5 Times 10 Times Random : 0.6
Min Rate In 10^5 Times 10 Times Random : 0

Max Rate In 10^5 Times 10 Times Random : 0.7
Min Rate In 10^5 Times 10 Times Random : 0

Max Rate In 10^5 Times 10 Times Random : 0.8
Min Rate In 10^5 Times 10 Times Random : 0

Max Rate In 10^5 Times 10 Times Random : 0.7
Min Rate In 10^5 Times 10 Times Random : 0

Max Rate In 10^5 Times 10 Times Random : 0.6
Min Rate In 10^5 Times 10 Times Random : 0

K=100

Max Rate In 10^5 Times 100 Times Random : 0.25
Min Rate In 10^5 Times 100 Times Random : 0      

Max Rate In 10^5 Times 100 Times Random : 0.25
Min Rate In 10^5 Times 100 Times Random : 0      

Max Rate In 10^5 Times 100 Times Random : 0.25
Min Rate In 10^5 Times 100 Times Random : 0      

Max Rate In 10^5 Times 100 Times Random : 0.26
Min Rate In 10^5 Times 100 Times Random : 0      

Max Rate In 10^5 Times 100 Times Random : 0.25
Min Rate In 10^5 Times 100 Times Random : 0      

Max Rate In 10^5 Times 100 Times Random : 0.25
Min Rate In 10^5 Times 100 Times Random : 0      

Max Rate In 10^5 Times 100 Times Random : 0.25
Min Rate In 10^5 Times 100 Times Random : 0      

Max Rate In 10^5 Times 100 Times Random : 0.25
Min Rate In 10^5 Times 100 Times Random : 0      

Max Rate In 10^5 Times 100 Times Random : 0.25
Min Rate In 10^5 Times 100 Times Random : 0      

Max Rate In 10^5 Times 100 Times Random : 0.25
Min Rate In 10^5 Times 100 Times Random : 0

K=1000

Max Rate In 10^5 Times 1000 Times Random : 0.148
Min Rate In 10^5 Times 1000 Times Random : 0.061 

Max Rate In 10^5 Times 1000 Times Random : 0.143
Min Rate In 10^5 Times 1000 Times Random : 0.061 

Max Rate In 10^5 Times 1000 Times Random : 0.143
Min Rate In 10^5 Times 1000 Times Random : 0.063 

Max Rate In 10^5 Times 1000 Times Random : 0.147
Min Rate In 10^5 Times 1000 Times Random : 0.063 

Max Rate In 10^5 Times 1000 Times Random : 0.143
Min Rate In 10^5 Times 1000 Times Random : 0.063 

Max Rate In 10^5 Times 1000 Times Random : 0.144
Min Rate In 10^5 Times 1000 Times Random : 0.061 

Max Rate In 10^5 Times 1000 Times Random : 0.146
Min Rate In 10^5 Times 1000 Times Random : 0.055 

Max Rate In 10^5 Times 1000 Times Random : 0.144
Min Rate In 10^5 Times 1000 Times Random : 0.061 

Max Rate In 10^5 Times 1000 Times Random : 0.145
Min Rate In 10^5 Times 1000 Times Random : 0.061 

Max Rate In 10^5 Times 1000 Times Random : 0.142
Min Rate In 10^5 Times 1000 Times Random : 0.061

但是剛剛測測試次數皆為10^5,若換成10^6呢?

Max Rate In 10^6 Times 400 Times Random : 0.1775
Min Rate In 10^6 Times 400 Times Random : 0.03

變成 0.03(3%) !

不得不說,跟我想的好像不一樣。希望大家自己測試,筆者因為電腦不夠好(i5古早版本)只能做到這了。

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