2015年8月22日 星期六

[UVA] 10129 - Play on Words

題意:
輸入多個字串,
問是否可以以某一種排列方式,
使得第一個字串的尾與第二個字串的頭相同,
第二個字串的尾與第三個字串的頭相同,
第N個字串的尾與第N+1個字串的頭相同,
如果可以輸出"Ordering is possible."
不行則輸出"The door cannot be opened."

--------------------------------------------------

方法:
如果將每個字串的頭尾都假設為一個節點,
那麼就會形成一個有向圖,
例如apple,可以變成節點 a 連向節點 e ,
那麼這題所求的就是有沒有存在尤拉路徑(或迴路)。

判斷是否有尤拉路徑或迴路必須滿足三點:
1.將有向邊都看成無向邊的話,此圖必須連通。
2.尤拉路徑只能有一個起點一個終點,
   起點(入度=出度+1),終點(出度=入度+1),
   除了起點終點以外,所有節點出度都等於入度,
   若該節點出度不等於入度且不滿足起點或終點的條件則尤拉路徑不存在。
3.若所有節點出度都等於入度,表示不存在起點和終點=>存在尤拉迴路。


而判斷是否連通的方法可以用DFS或disjoint set,
這裡我使用disjoint set 判斷。
--------------------------------------------------
/* 20150822
 * hanting
 * UVa 10129 - Play on Words
 * C++
 */
#include <iostream>
using namespace std;
int parent[26];
void initial()
{
    for(int i=0;i<26;i++)
    {
        parent[i]=-1;
    }
}
int Find(int x)
{
    if(parent[x]<0) return x;
    else
    {
        return parent[x]=Find(parent[x]);
    }
}
void Union(int x,int y)
{
    int Fx=Find(x);
    int Fy=Find(y);
    if(Fx!=Fy)
    {
        if(parent[Fx]<parent[Fy])
        {
            parent[Fx]+=parent[Fy];
            parent[Fy]=Fx;
        }
        else
        {
            parent[Fy]+=parent[Fx];
            parent[Fx]=Fy;
        }
    }
    else
        parent[Fx]--;
}
int main()
{
    int caseN;
    cin>>caseN;
    while(caseN--)
    {
        int wordN;
        cin>>wordN;
        string word[wordN];
        initial();
        int table[26][26]={};
        for(int i=0;i<wordN;i++)
        {
            cin>>word[i];
            int head=word[i][0]-'a';
            int last=word[i][word[i].size()-1]-'a';
            table[head][last]++;//head connect last
            Union(head,last);
        }


        int cnt=0;
        for(int i=0;i<26;i++)
        {
            if(parent[i]<-1) cnt++;
        }

        bool connected=(cnt==1);//是否為連通圖

        int start=0,End=0;
        bool possible=true;
        for(int i=0;i<26 and connected;i++)
        {
            int indegree=0;
            int outdegree=0;
            for(int j=0;j<26;j++)
            {
                outdegree+=table[i][j];
                indegree+=table[j][i];
            }
            if(indegree!=outdegree)
            {
                if(indegree==outdegree+1)
                    start++;
                else if(indegree+1==outdegree)
                    End++;
                else
                    possible=false;
            }
        }
        possible&=((start==1 and End==1)or(start==0 and End==0));
        if(connected and possible)
        {
            cout<<"Ordering is possible."<<endl;
        }
        else
        {
            cout<<"The door cannot be opened."<<endl;
        }
    }
    return 0;
}

--------------------------------------------------
範例輸入:
input.txt

範例輸出:
output.txt
--------------------------------------------------

[UVA] 572 - Oil Deposits

題意:
輸入一個圖,
計算 '@' 有多少個連接區塊,
只要兩個'@'相鄰或在斜對角就算連接。

--------------------------------------------------

方法:
先用迴圈找出'@',
再用DFS去找相連接的 '@' ,
每連接一個就將其字元改掉,避免重複連接,
DFS做完後,
這樣再繼續迴圈找下一個'@'可以保證不與上一個'@'在同一區塊,
因為上一個'@'所有跟他相連的區塊都被改掉了,
所以可以放心地++

--------------------------------------------------
/* 20150822
 * hanting
 * UVa 572 - Oil Deposits
 * C++
 */
#include <iostream>
#include <cstring>//memset
using namespace std;
const int maxn=100+5;
int grid[maxn][maxn];
void DFS(int i,int j)
{
    grid[i][j]=2;
    if(grid[i][j+1]==1)//Right
    {
        DFS(i,j+1);
    }
    if(grid[i+1][j]==1)//Down
    {
        DFS(i+1,j);
    }
    if(grid[i][j-1]==1)//Left
    {
        DFS(i,j-1);
    }
    if(grid[i-1][j]==1)//Up
    {
        DFS(i-1,j);
    }

    if(grid[i-1][j-1]==1)//Left-Up
    {
        DFS(i-1,j-1);
    }
    if(grid[i-1][j+1]==1)//Right-Up
    {
        DFS(i-1,j+1);
    }
    if(grid[i+1][j-1]==1)//Left-Down
    {
        DFS(i+1,j-1);
    }
    if(grid[i+1][j+1]==1)//Right-Down
    {
        DFS(i+1,j+1);
    }
}
int main()
{
    int row,col;
    while(cin>>row>>col and row+col)
    {
        memset(grid,0,sizeof(grid));
        for(int i=0;i<row;i++)
        {
            for(int j=0;j<col;j++)
            {
                char ch;
                cin>>ch;
                grid[i][j]=(ch=='@' ? 1:0);
            }
        }
        int ans=0;
        for(int i=0;i<row;i++)
        {
            for(int j=0;j<col;j++)
            {
                if(grid[i][j]==1)
                {
                    DFS(i,j);
                    ans++;
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

[UVA] 548 - Tree

題意:
給一棵樹的中序和後序,
求這棵樹的葉子到根節點的路徑權值總合最小的葉子。

--------------------------------------------------

方法:
建樹的過程跟536那題很像,
可以參考看看
536 - Tree Recovery
這題要做葉子的判斷就在於inord或postord的長度==1時就是葉子~
每找到一個子樹的root就去加上父節點的權值,
這樣找到葉子的時候就可以順便找到到root路徑上最小權值和的葉子了!

--------------------------------------------------

/* 20150822
 * hanting
 * UVa 548 - Tree
 * C++
 */
#include <iostream>
#include <vector>
#include <sstream>
#include <algorithm>//find
using namespace std;
istream& operator>>(istream& in,vector<int> &vec)
{
    vec.clear();
    string str;
    getline(in,str);
    stringstream sin(str);
    int num;
    while(sin>>num) vec.push_back(num);
    return in;
}
void FindLeaf(vector<int> &in,vector<int> &post,int &mini,int &ansLeaf,int parWeight)
{
    if(in.size()>1)
    {
        int root=post.back();
        vector<int>::iterator it=find(in.begin(),in.end(),root);//root position

        vector<int> inLeft(in.begin(),it);
        vector<int> inRight(it+1,in.end());
        vector<int> postLeft(post.begin(),post.begin()+inLeft.size());
        vector<int> postRight(post.begin()+inLeft.size(),post.end()-1);

        FindLeaf(inLeft,postLeft,mini,ansLeaf,root+parWeight);
        FindLeaf(inRight,postRight,mini,ansLeaf,root+parWeight);
    }
    else if(in.size()==1)//leaf
    {
        if(mini>in.back()+parWeight)
        {
            mini=in.back()+parWeight;
            ansLeaf=in.back();
        }
        else if(mini==in.back()+parWeight and in.back()<ansLeaf)
        {
            ansLeaf=in.back();
        }
    }
}
int main()
{
    vector<int> inord,postord;
    while(cin>>inord>>postord)
    {
        int mini=0x3fffffff;
        int ansLeaf=0;
        FindLeaf(inord,postord,mini,ansLeaf,0);
        cout<<ansLeaf<<endl;
    }
    return 0;
}

2015年8月20日 星期四

[UVA] 12657 - Boxes in a Line

題意:
輸入N表示1,2,3...,N個數字連接成一條鏈,
現在有四種操作:
1 x y :將 x 移到 y 左邊
2 x y :將 x 移到 y 右邊
3 x y :將 x 和 y 交換位置
4       :反轉整條鏈
最後輸出鏈上奇數位置的數字總和。

--------------------------------------------------

方法:
直接使用vector模擬操作會超時,
這題要用雙向鏈接串列,
一開始先串接這N個數字,
小技巧:先設置一個head和一個last,但要保證不會使用到這兩個數字
例如題目只會用到1~100000的數字,head就可以設為0,last設為100001
那麼一開始串接起來就變成
0-1-2-3-.....-N-100001
因為任何操作都不會動到head和last,
這樣在輸出時比較方便,

操作4的反轉整條鏈比較麻煩,
直接模擬的話要整條鏈都掃一遍,太費時,
所以可以先用一個記號表示目前這條鏈是否有反轉,
如果沒有反轉:
輸出時從head開始輸出,
如果有反轉:
那麼操作1就變成操作2,
操作2就變成操作1,
輸出時從last輸出,

操作3要注意的是 ! 要額外判斷 x y 是否相鄰 ! 不然會被吃掉

--------------------------------------------------

/* 20150820
 * hanting
 * UVa 12657 - Boxes in a Line
 * C++
 */
#include <iostream>
using namespace std;
const int maxn=100000+5;
int Left[maxn],Right[maxn];
#define head 0
#define last 100003
void Link(int L,int R)
{
    Right[L]=R;
    Left[R]=L;
}
void initial(int N)
{
    Link(head,1);
    for(int i=1;i<N;i++)
    {
        Link(i,i+1);
    }
    Link(N,last);
}
int main()
{
    int boxN,cmdN;
    int caseN=1;
    while(cin>>boxN>>cmdN)
    {
        initial(boxN);//串接N個數字
        bool Reverse=false;
        for(int i=0;i<cmdN;i++)
        {
            int cmd,x,y;
            cin>>cmd;
            if(cmd!=4)
            {
                cin>>x>>y;
            }
            else//反轉整條鏈
            {
                Reverse=!Reverse;
            }
            int Lx=Left[x],Rx=Right[x];
            int Ly=Left[y],Ry=Right[y];
            if(Reverse and cmd<3) cmd=3-cmd;
            switch(cmd)
            {
            case 1://把x移動到y左邊
                if(Ly==x) break;//x已經在y左邊
                Link(Ly,x);
                Link(x,y);
                Link(Lx,Rx);
                break;
            case 2://把x移動到y右邊
                if(Ry==x) break;//x已經在y右邊
                Link(y,x);
                Link(x,Ry);
                Link(Lx,Rx);
                break;
            case 3://x與y的位置交換
                if(Lx==y)//y在x左邊
                {
                    Link(Ly,x);
                    Link(x,y);
                    Link(y,Rx);
                }
                else if(Rx==y)//y在x右邊
                {
                    Link(Lx,y);
                    Link(y,x);
                    Link(x,Ry);
                }
                else
                {
                    Link(Lx,y);
                    Link(y,Rx);
                    Link(Ly,x);
                    Link(x,Ry);
                }
                break;
            }
        }
        cout<<"Case "<<caseN++<<": ";
        long long sum=0;
        if(Reverse)
        {
            for(int i=Left[last] ,j=0; i!=head ; i=Left[i],j++)
            {
                if(!(j&1)) sum+=i;
            }
        }
        else
        {
            for(int i=Right[head],j=0 ; i!=last ; i=Right[i],j++)
            {
                if(!(j&1)) sum+=i;
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}

2015年8月18日 星期二

[UVA] 442 - Matrix Chain Multiplication

題意:
計算矩陣相乘需要的計算次數,
若矩陣A是3*4,矩陣B是4*5,矩陣C是4*8,
那麼A乘以B所需的計算次數是3*4*5,
A乘以C的計算次數就是3*4*8,
而B乘以C就不能乘,所以是error。
測資若有兩個矩陣一定會用括弧,
例如:
(AB)
不會有
AB
這樣的測資,所以不用特別判斷。

--------------------------------------
方法:
將矩陣以結構方式儲存,
用一個stack存放矩陣,
若遇到')'就將stack pop兩個出來做相乘並判斷是否可做香腸,
可相乘就將計算次數加進sum裡面。

/* 20150818
 * hanting
 * UVa 442 - Matrix Chain Multiplication
 * C++
 */
#include <iostream>
#include <stack>
#include <map>
using namespace std;
struct Matrix
{
    int row,col;
    int times;
    Matrix(int r=0,int c=0,int t=0):row(r),col(c),times(t){}
    Matrix operator*(Matrix &m)
    {
        int t= (col==m.row ? row*col*m.col:-1);//判斷是否可乘,負數表示不行
        return Matrix(row,m.col,t);
    }
};
stack<Matrix> stk;
map<char,Matrix> Map;
int main()
{
    int N;
    while(cin>>N)
    {
        Map.clear();
        char ch;
        int r,c;
        for(int i=0;i<N;i++)
        {
            cin>>ch>>r>>c;
            Map[ch]=Matrix(r,c);
        }
        string str;
        while(cin>>str)
        {
            while(stk.size()) stk.pop();//initial
            bool valid=true;
            int sum=0;
            for(int i=0;i<str.size() and valid;i++)
            {
                if(str[i]==')')//從stack中pop兩個出來做乘法
                {
                    if(stk.size()<2)
                    {
                        valid=false;
                    }
                    else
                    {
                        Matrix t1=stk.top(); stk.pop();
                        Matrix t2=stk.top(); stk.pop();
                        Matrix result(t2*t1);
                        if(result.times<0) valid=false;
                        else
                        {
                            sum+=result.times;
                            stk.push(result);
                        }
                    }
                }
                else if(str[i]!='(')
                {
                    Matrix tmp=Map[str[i] ];
                    stk.push(tmp);
                }
            }
            if(valid)
            {
                cout<<sum<<endl;
            }
            else
            {
                cout<<"error"<<endl;
            }
        }
    }
    return 0;
}

[UVA] 536 - Tree Recovery

題意:
拜訪樹有幾種方式:
前序(preorder):先拜訪根 再拜訪左子樹 最後拜訪右子樹=>根左右
中序(inorder):先拜訪左子樹 再拜訪根 最後拜訪右子樹=>左根右
後序(postorder):先拜訪左子樹 再拜訪右子樹 最後拜訪根=>左右根

這一題就是給你前序和中序,
要你求出後序。
--------------------------------------------
方法:
使用遞迴,
有前序就可以知道根,
再利用中序求出左子樹與右子樹,
以範例輸入:
前序DBACEGF 
中序ABCDEFG
由前序可以知道根是D,
知道根之後,可以在中序找到左子樹與右子樹的個數,
分別是3個,3個,
所以可以從前序知道根左右分別是D  , BAC  , EGF
分別對左子樹BAC和右子樹EGF做拜訪,
做完左樹與右樹的拜訪最後拜訪根,
就完成後序了。

---------------------------------------

/* 20150818
 * hanting
 * UVa 536 - Tree Recovery
 * C++
 */
#include <iostream>
using namespace std;
void travel(string &preord,string &inord,string &postord)
{
    if(preord.size())
    {
        string PreLeft,PreRight,InLeft,InRight;
        char root=preord[0];
        int FindRootInord=inord.find(root);

        InLeft=inord.substr(0,FindRootInord);
        InRight=inord.substr(FindRootInord+1);
        PreLeft=preord.substr(1,InLeft.size());
        PreRight=preord.substr(InLeft.size()+1);

        travel(PreLeft,InLeft,postord);//left
        travel(PreRight,InRight,postord);//right
        postord+=root;
    }
}
int main()
{
    string preord,inord;
    while(cin>>preord>>inord)
    {
        string postord="";
        travel(preord,inord,postord);
        cout<<postord<<endl;
    }
    return 0;
}

2015年8月17日 星期一

[UVA] 122 - Trees on the level

題意:
給一棵二元樹的節點,
輸入(n,s),
n是該節點的編號,
s是從根結點走到該節點的路徑,(根結點沒有s)
R是右,L是左,
輸入()表示該筆測資結束。
注意! 這題是多筆測資喔!
由左到右,從上到下將樹的節點編號輸出,
如果給重複的節點或該節點沒有父節點,則輸出not complete,
例如:
輸入:(1,R) (2,RR) ()
輸出:not complete//沒有根結點

方法:
判斷路徑s長度,
長度越短越先輸出,
長度相同,L比R先輸出,
依此排序,
排序後,
第一個點必須沒有s,
而後面的所有點都要有父節點,
否則就是not complete

判斷父節點就判斷是否有節點的路徑是該節點的路徑去尾,
例如(1,RRL)和(2,RRR)的父節點就是(n,RR)


/* 20150818
 * hanting
 * UVa 122 - Trees on the level
 * C++
 */
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>//sort
#include <sstream>
using namespace std;
struct Node
{
    int id;
    string route;
    Node(int x,string str):id(x),route(str){}
    bool operator<(const Node &n)const
    {
        if(route.size()<n.route.size()) return true;
        else if(route.size()==n.route.size())return route<n.route;
        else return false;
    }
};
inline string Parent(string &str)
{
    return str.substr(0,str.size()-1);
}
string str;
vector<Node> vec;
map<string,int> Map;
bool Input()
{
    Map.clear();
    vec.clear();
    bool input=false;
    while(cin>>str and str!="()")
    {
        input=true;
        stringstream sin(str);
        char ch;
        int x;
        string tmp;
        sin>>ch>>x>>ch>>tmp;//( 11 , LL)
        tmp.erase(tmp.size()-1);//右括弧
        vec.push_back(Node(x,tmp));
    }
    return input;
}
int main()
{
    while(Input())
    {
        sort(vec.begin(),vec.end());
        bool NO=vec[0].route!="";
        Map[""]=1;
        for(int i=1;i<vec.size() and !NO;i++)
        {
            string par=Parent(vec[i].route);//求父節點
            if(Map.count(par)==0 or Map.count(vec[i].route)!=0)
            {
                NO=true;
                break;
            }
            Map[vec[i].route]++;
        }
        if(NO)
        {
            cout<<"not complete"<<endl;
        }
        else
        {
            for(int i=0;i<vec.size()-1;i++)
            {
                cout<<vec[i].id<<" ";
            }
            cout<<vec.back().id<<endl;
        }
    }
    return 0;
}