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++ 彰雲嘉區複賽106-5 回文日期問題

題目連結:e525: 106 彰雲嘉區複賽 – Q5 回文日期問題

窮舉法

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;

int dom[15]={0,31,28,31,30,31,30,31,31,30,31,30,31,0,0};
int pro[700],nt,ct=0;

void check(int y){
    if(y%400==0 || (y%4==0 && y%100!=0)){
        dom[2]=29;
    }else dom[2]=28;
}

void isv(int a){
    string s;
    int b=a;
    while(a>0){
        s+=char(a%10+'0');
        a/=10;
    }
    for(int i=0;i<=s.size()/2;i++){
        if(s[i]!=s[s.size()-1-i]){
            return;
        }
    }
    pro[nt++]=b;
    return;
}

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

    int n;
    cin>>n;
    while(n--){
        int y;
        nt=ct=0;
        cin>>y;
        check(y);
        for(int i=1;i<=12;i++){
            int tmp=i;
            for(int j=1;j<=dom[i];j++){
                if(i<10){
                    if(j<10){
                        isv(y*100+i*10+j);
                        isv(y*1000+i*10+j);
                        isv(y*1000+i*100+j);
                        isv(y*10000+i*100+j);
                    }else{
                        isv(y*1000+i*100+j);
                        isv(y*10000+i*100+j);
                    }
                }else{
                    if(j<10){
                        isv(y*1000+i*10+j);
                        isv(y*10000+i*100+j);
                    }else{
                        isv(y*10000+i*100+j);
                    }
                }
            }
            i=tmp;
        }
        cout<<nt<<" ";
        sort(pro,pro+nt);
        for(int i=0;i<nt;i++){
            cout<<pro[i]<<" ";
        }
        cout<<"\n";
    }
    return 0;
} 

C++ 彰雲嘉區複賽106-4 變位字判斷

題目連結:e524: 106 彰雲嘉區複賽 – Q4 變位字判斷

用map很方便(如果是C++11更方便)

#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<string>
#include<cstdlib>
using namespace std;

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

    string a,b;
    int n;
    cin>>n;
    getline(cin,a);
    while(n--){
        getline(cin,a);
        getline(cin,b);
        map<char,int> ma,mb;

        for(int i=0;i<a.size();i++){
            char c=a[i];
            if(islower(c)){
                ma[c]++;
            }else if(isupper(c)){
                ma[tolower(c)]++;
            }
        }

        for(int i=0;i<b.size();i++){
            char c=b[i];
            if(islower(c)){
                mb[c]++;
            }else if(isupper(c)){
                mb[tolower(c)]++;
            }
        }

        bool isv=true;
        map<char,int>::iterator ta=ma.begin(),tb=mb.begin();
        for(ta=ma.begin();ta!=ma.end() && tb!=mb.end();ta++){
            pair<char,int> pa=(*ta),pb=(*tb);
            if(pa!=pb){
                isv=false;
            }
            tb++;
        }
        if(ma.size()!=mb.size()) isv=false;
        cout<<isv<<"\n";
    }
    return 0;
}

C++ 彰雲嘉區複賽106-3 費波南希數列

題目連結:e523: 106 彰雲嘉區複賽 – Q3 費波南希數列

用到最簡單DP和二分搜(都可以不用)

#include<iostream>
#include<algorithm>
using namespace std;

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

    int n,f[200];
    cin>>n;

    f[0]=-1;f[1]=1;f[2]=1;
    for(int i=3;i<100;i++){
        f[i]=f[i-1]+f[i-2];
        if(f[i]<0) f[i]=0x3f3f3f3f;
    }

    while(n--){
        int a;
        cin>>a;
        int it=lower_bound(f,f+100,a)-f;
        if(f[it]==a){
            cout<<it;
        }else{
            cout<<-1;
        }
        cout<<"\n";
    }
    return 0;
}

C++ 彰雲嘉區複賽106-2 跑長編碼與資料壓縮

題目連結:e522: 106 彰雲嘉區複賽 – Q2 跑長編碼與資料壓縮

字串基本應用

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;

string num[10]={"000","001","010","011","100","101","110","111"};

string print(int sum,char bit){
    string re(1,bit);
    re+=num[sum];
    re+=" ";
    return re;
}

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

    int iptNum=0;
    cin>>iptNum;

    string bit,out;
    getline(cin,bit);

    while(iptNum--){
        out="";
        getline(cin,bit);
        int j,sum=1;
        long long rate=0;
        for(j=1;j<bit.size();j++){
            if(bit[j]!='0' && bit[j]!='1'){
                cout<<"-1\n";
                j++;
                break;
            }

            if(bit[j-1]==bit[j] && sum<7){
                sum++;
            }else{
                out+=print(sum,bit[j-1]);
                rate+=4;
                sum=1;
            }
        }
        out+=print(sum,bit[j-1]);
        rate+=4;
        rate*=1000;
        rate/=bit.size();
        rate=(rate+5)/10;

        if(bit[j-1]=='0' || bit[j-1]=='1'){
            cout<<out<<rate<<"\n";
        }
    }
    return 0;
}

C++ 彰雲嘉區複賽106-1 三角形

題目連結:e521: 106 彰雲嘉區複賽 – Q1 三角形

簡單的三角形判別

#include<iostream>
#include<algorithm>
using namespace std;

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

    int n;
    cin>>n;
    while(n--){
        int d[3];
        for(int i=0;i<3;i++) cin>>d[i];
        sort(d,d+3);
        if(d[0]+d[1]<=d[2]){
            cout<<0<<"\n";
        }else{
            cout<<1<<" ";
            if(d[0]==d[1] || d[1]==d[2]) cout<<1;
            else cout<<0;
            cout<<"\n";
        }
    }
    return 0;
}

C++ 106 花蓮 一起回家的日子

題目來源:106東區學科能力競賽

gcd轉lcm

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

int dayInM[12]={31,28,31,30,31,30,31,31,30,31,30,31};

void check(int y){
    if((y%4==0 && y%100!=0) || y%400==0){
        dayInM[1]=29;
    }else{
        dayInM[1]=28;    
    }
    return;
}

int gcd(int a,int b){
    if(a%b==0){
        return b;
    }else{
        return gcd(b,a%b);
    }
}

int main(){
    int n;
    scanf("%d",&n);

    int dt[500];
    for(int i=0;i<n;i++){
        scanf("%d",dt+i);
    }

    int y,m,d;
    scanf("%d/%d/%d",&y,&m,&d);
    for(int i=0;i<n-1;i++){
        int d=gcd(dt[i],dt[i+1]);
        int min=d*dt[i]/d*dt[i+1]/d;
        dt[i+1]=min;
    }

    d+=dt[n-1];

    check(y);
    while(d>dayInM[m-1]){
        d-=dayInM[m-1];
        m++;
        if(m>12){
            m=1;
            y++;
        }
        check(y);
    }
    printf("%4d/%02d/%02d",y,m,d);
    return 0;
}

C++ 106全國賽 2. 自戀數

題目連結:c459. 2. 自戀數 – 高中生程式解題系統

直接用字串轉數字配合題目敘述即可

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

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

    int base[15][10];
    for(int i=0;i<12;i++){
        base[i][0]=1;
        for(int j=1;j<10;j++){
            base[i][j]=base[i][j-1]*i;
        }
    }

    string N;
    int b,n=0,sum=0;
    cin>>b>>N;
    for(int i=0;i<N.size();i++){
        n*=b;
        n+=N[i]-'0';
        sum+=base[(N[i]-'0')][N.size()];
    }
    string ans=(n==sum)?"YES":"NO";
    cout<<ans<<"\n";
    return 0;
}

C++ 106全國賽 1. 連號或不連號

題目連結:c299. 1. 連號或不連號 – 高中生程式解題系統

排序後檢查即可

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

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

    int n;
    cin>>n;
    int dt[105];
    for(int i=0;i<n;i++){
        cin>>dt[i];
    }
    sort(dt,dt+n);

    bool ans=true;
    cout<<dt[0]<<" "<<dt[n-1];
    for(int i=1;i<n;i++){
        if(dt[i]!=dt[i-1]+1) ans=false;
    }
    if(ans){
        cout<<" yes";
    }else{
        cout<<" no";
    }

    return 0;
}