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

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

C++ 最短路徑問題 Dijkstra應用

題目連結:Sprout Online Judge No. 393

這題用 Bellman-Ford 必定 TLE

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int dr[4]{1,0,-1,0},dc[4]{0,1,0,-1};

int dt[2005][2005];
string mp[2005];
bitset<2005> v[2005];

struct position{
    int r,c;
    bool operator==(position a){
        return r==a.r && c==a.c;
    }
};
bool operator<(position a,position b){
    return dt[a.r][a.c]>dt[b.r][b.c];
}

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

    int n,m,ans=INF;
    cin>>n>>m;

    for(int i=0;i<n;i++) for(int j=0;j<m;j++) dt[i][j]=INF;

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

    position ps,pe;
    cin>>ps.r>>ps.c;ps.r--;ps.c--;
    cin>>pe.r>>pe.c;pe.r--;pe.c--;
    dt[ps.r][ps.c]=0;

    priority_queue<position> bfs;
    bfs.push(ps);

    int ct;
    position now,next,mnPos;
    while(!bfs.empty()){
        now=bfs.top();
        bfs.pop();
        v[now.r][now.c]=1;
        for(int i=0;i<4;i++){
            next.r=now.r+dr[i];
            next.c=now.c+dc[i];
            if(next.r>=0 && next.c>=0 && next.r<n && next.c<m){
                ct=dt[now.r][now.c];
                if(mp[next.r][next.c]=='.')
                    ct++;
                if(pe==next)
                    ans=min(ans,ct);
                if(!v[next.r][next.c]){
                    v[next.r][next.c]=1;
                    dt[next.r][next.c]=ct;
                    bfs.push(next);
                }
            }
        }
    }
    cout<<ans<<"\n";
    return 0;
}

HackerRank Sorting 5.Counting Inversions

題目連結:Merge Sort: Counting Inversions | HackerRank

這就是反序數對了(Merge Sort)

vector<long> dt;

long msort(long l,long r){
    if(l>=r-1) return 0;
    long mid=(l+r)/2,j=mid;
    long sum=msort(l,mid)+msort(mid,r);
    long tmp[r-l],k=0;
    for(long i=l;i<mid;i++){
        while(j<r && dt[j]<dt[i]){
            tmp[k++]=dt[j++];
        }
        tmp[k++]=dt[i];
        sum+=j-mid;
    }
    while(j<r){
        tmp[k++]=dt[j++];
    }
    j=0;
    for(long i=l;i<r;i++){
        dt[i]=tmp[j];
        j++;
    }
    return sum;
}

HackerRank Sorting 4.Fraudulent Activity Notifications

題目連結:Fraudulent Activity Notifications | HackerRank

我只想到用 Counting Sort (O(n*exp[i]_range))。

int activityNotifications(vector<int> e, int d) {
    int ct=0;
    vector<int> m(205,0);
    for(int i=0;i<d;i++){
        m[e[i]]++;
    }
    for(int i=d;i<e.size();i++){
        int k=0,p=-1;
        for(int j=0;j<201;j++){
            k+=m[j];
            if(d&1){
                if(k>=d/2+1){
                    if(e[i]>=j*2) ct++;
                    break;
                }
            }else{
                if(k==d/2){
                    p=j;
                }else if(k>d/2){
                    if(p==-1){
                        if(e[i]>=j*2) ct++;
                    }else{
                        if(e[i]>=j+p) ct++;
                    }
                    break;
                }
            }
        }
        m[e[i]]++;
        m[e[i-d]]--;
    }
    return ct;
}