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

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();
}

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