[UVA] 10305 - Ordering Tasks

題意:
輸入節點數和有向邊的數量，
接下來輸入節點 A 指向節點 B ，
最後要輸出的是一拓樸排序，
當 A 指向 B ，就要先輸出 A 再輸出 B ，
範例輸入
5 4
1 2
2 3
1 3
1 5
只要滿足節點 1 在 2 3 5 之前輸出以及 2 在 3 之前輸出即可，
所以也可以輸出
4 1 5 2 3
--------------------------------------------------

方法:
拓樸排序，
先利用 DFS 到最深層的節點，
表示該節點一定可以先輸出，
那麼有指向其他節點的一定會比較後面輸出，
根節點也會最後輸出~
--------------------------------------------------

/* 20150827
 * hanting
 * UVa 10305 - Ordering Tasks
 * C++
 */
#include <iostream>
#include <vector>
#include <cstring>//memset
using namespace std;
vector<int> ans;
void Topology(vector<int> *vec,int *visit,int cur)
{
    static int flag=1;
    visit[cur]=flag++;
    for(int i=0;i<vec[cur].size();i++)
    {
        int t=vec[cur][i];
        if(!visit[t])
        {
            Topology(vec,visit,t);
        }
    }
    ans.push_back(cur);
}
int main()
{
    int N,messageN;
    while(cin>>N>>messageN and N+messageN)
    {
        ans.clear();
        vector<int> vec[N+1];
        for(int i=0;i<messageN;i++)
        {
            int a,b;
            cin>>a>>b;
            vec[a].push_back(b);
        }
        int visit[N+1];
        memset(visit,0,sizeof(visit));
        for(int i=1;i<N+1;i++)
        {
            if(!visit[i])
            {
                Topology(vec,visit,i);
            }
        }
        for(int i=ans.size()-1;i>0;i--)
        {
            cout<<ans[i]<<" ";
        }
        cout<<ans[0]<<endl;
    }
    return 0;
}

[UVA] 699 - The Falling Leaves

題意:
遞迴輸入一棵二元樹，
若子節點是葉子則輸入-1，
最後輸出由左到右的垂直節點的權值和，

輸入: 9 5 3 -1 7 -1 -1 4 -1 -1 8 1 -1 6 -1 -1 -1
就會建出像這樣一棵二元樹，
最後由左邊開始輸出每一垂直線的加總，
3 (5+7) (9+4+1) (8+6)
所以是3 12 14 14

每一個測資後面要一個空行(最後一筆也要)。


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

方法:
若子節點不是葉子表示還有子樹要輸入，
所以再進去遞迴，
我以位置10000為根節點，
輸入左節點就在位置9999加上左節點的數字，
輸入右節點就在位置10001加上右節點的數字，
最後再從0開始去找第一個非零的數字開始去輸出~

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

/* 20150826
 * hanting
 * UVa 699 - The Falling Leaves
 * C++
 */
#include <iostream>
#include <cstring>//memset
using namespace std;
int sum[20000];
void input(int cur)
{
    int L,R;
    cin>>L;
    if(L!=-1)
    {
        sum[cur-1]+=L;
        input(cur-1);
    }
    cin>>R;
    if(R!=-1)
    {
        sum[cur+1]+=R;
        input(cur+1);
    }
}
int main()
{
    int caseN=1;
    int root;
    while(cin>>root and root != -1)
    {
        memset(sum,0,sizeof(sum));
        sum[10000]=root;
        input(10000);
        cout<<"Case "<<caseN++<<":"<<endl;

        int i=0;
        for(;i<20000;i++)
        {
            if(sum[i]!=0)
            {
                cout<<sum[i];
                i++;
                break;
            }
        }
        for(;i<20000;i++)
        {
            if(sum[i]==0) break;
            cout<<" "<<sum[i];
        }
        cout<<endl<<endl;
    }
    return 0;
}

[UVA] 839 - Not so Mobile

題意:
要問這個天平是否是平衡的，

注意!題目是遞迴輸入喔!
--------------------------------------------------

方法:
建立一個遞回函式進行輸入，
在輸入的時候就順便做判斷，
並回傳總重量(該天平的左+右)。

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

/* 20150826
 * hanting
 * UVa 839 - Not so Mobile
 * C++
 */
#include <iostream>
using namespace std;
bool balance;
int input()
{
    int w1,d1,w2,d2;
    cin>>w1>>d1>>w2>>d2;
    if(w1==0) w1=input();
    if(w2==0) w2=input();
    if(w1*d1!=w2*d2) balance=false;
    return w1+w2;
}
int main()
{
    int caseN;
    cin>>caseN;
    while(caseN--)
    {
        balance=true;
        input();
        if(balance)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;

        if(caseN)
            cout<<endl;
    }
    return 0;
}

[UVA] 531 - Compromise

題意:
輸入兩個字串，輸出最長共同子序列(Longest Common Subsequence)。

最長共同子序列就是指兩序列在相同順序下的相同元素，不一定要連續!
舉個例子，
1 2 3 5 7 6
1 3 6 5 7
最長共同子序列就是:
1 3 5 7

1 3 5 7是兩個序列的相同元素，而且都以相同順序出現 1->3->5->7，
像是 1 3 5 6 就不是，因為第二個序列找不到依序出現1 3 5 6的

這一題就是把數字換成字串去找LCS而已。

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

方法:
動態規劃，以先前已經計算好的結果來做下一次的計算，
我先做預處理，將字串先以數字代替，以加快之後在字串上的比較。
我這裡將到目前為止最長的子序列以vector存取，
所以最後直接輸出最後一個vector，
但是其實每計算一次就複製一個vector效率並不高。

在計算過程做標記，最後再循著標記走回來輸出也是一個方法。

Longest Common Subsequence: Dynamic Programming
這個網站寫的蠻好懂得可以參考看看!

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

/* 20150825
 * hanting
 * UVa 531 - Compromise
 * C++
 */
#include <iostream>
#include <vector>
#include <map>
#include <cstring>//memset
using namespace std;
map<string,int> id;
vector<string> store;
int ID(string str)
{
    if(id.count(str)) return id[str];
    else
    {
        store.push_back(str);
        return id[str]=store.size()-1;
    }
}
bool input(vector<int> &a,vector<int> &b)
{
    a.resize(1);
    b.resize(1);

    string str;
    bool chk=false;
    while(cin>>str and str!="#")
    {
        chk=true;
        a.push_back(ID(str));
    }

    while(cin>>str and str!="#")
    {
        b.push_back(ID(str));
    }
    return chk;
}
vector<int> operator+(vector<int>& vec,int c)
{
    vec.push_back(c);
    return vec;
}
vector<int> Max(vector<int> &a,vector<int> &b)
{
    return a.size()>b.size() ? a : b;
}
int main()
{
    vector<int> a,b;
    while(input(a,b))
    {
        vector<int> LCS[a.size()+1][b.size()+1];
        for(int i=1;i<a.size();i++)
        {
            for(int j=1;j<b.size();j++)
            {
                if(a[i]==b[j])
                {
                    LCS[i][j]=LCS[i-1][j-1]+a[i];
                }
                else
                {
                    LCS[i][j]=Max(LCS[i-1][j],LCS[i][j-1]);
                }
            }
        }
        vector<int> ans=LCS[a.size()-1][b.size()-1];
        for(int i=0;i<ans.size()-1;i++)
        {
            int t=ans[i];
            cout<<store[t]<<" ";
        }
        cout<<store[ans.back()]<<endl;
    }
    return 0;
}

[UVA] 679 - Dropping Balls

題意:
有一棵full binary tree，
從根節點開始，
從左到右，由上到下，
編號1到n，
且每一個節點都為開關都為false。

現在從根節點每放一顆球，
如果求經過該節點開關為false則往左子節點去，若為true則往右子節點去，
而該節點的開關就會相反，
球跑到葉子節點停止。

輸入樹的深度 d 與 i 顆球，
輸出第 i 顆球落在編號多少。

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

方法:
模擬操作會超時，
我是推出規律，
直接在輸入前建表，
再依照輸入去查表，

應該有更直覺的方法!

另外一個小發現! 若 i 為奇數則必會落在左子樹，若為偶數必會落在右子樹。
--------------------------------------------------

/* 20150824
 * hanting
 * UVa 679 - Dropping Balls
 * C++
 */
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
vector<int> table[21];
vector<int> ans[21];
vector<int> ID[21];
void initial()
{
    int id=1;
    for(int i=0;i<20;i++)
    {
        table[i].resize(1<<i);
        ans[i].resize(1<<i);
        ID[i].resize(1<<i);
        for(int j=0;j<ID[i].size();j++)
        {
            ID[i][j]=id++;
        }
    }
    ans[0][0]=ID[0][0];
    for(int i=1;i<20;i++)
    {
        for(int j=0;j<table[i].size();j++)
        {
            if(j&1)
            {
                table[i][j]=table[i][j-1]+(1<<i-1);
            }
            else
            {
                table[i][j]=table[i-1][j/2];
            }
            ans[i][table[i][j]]=ID[i][j];
        }
    }
}
int main()
{
    initial();
   // freopen("1.txt","r",stdin);
    int N;
    while(cin>>N and N!=-1)
    {
        int depth,ballN;
        for(int i=0;i<N;i++)
        {
            cin>>depth>>ballN;
            cout<<ans[depth-1][ballN-1]<<endl;
        }
    }
    return 0;
}

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

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

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

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

[UVA] 11988 - Broken Keyboard

題意:
一個字元一個字元輸入，
若輸入'['，就跑回起點，
若輸入']'，就跑到終點，

例如
輸入123[4
就會輸出4123

輸入1[23]4
就會輸出2314

方法:
如果使用陣列儲存，
若很多'['或']'就會超時，
使用linked list一個串一個，
紀錄起點和終點~


/* 20150817
 * hanting
 * UVa 11988 - Broken Keyboard
 * C++
 */
#include <iostream>
using namespace std;
#define head 100001
#define last 100002
int Left[100003];
int Right[100003];

void Link(int L,int R)
{
    Left[R]=L;
    Right[L]=R;
}
int main()
{
    string str;
    while(getline(cin,str))
    {
        int cur=head;
        Link(head,last);
        Right[last]=-1;
        for(int i=0;i<str.size();i++)
        {
            if(str[i]=='[')
            {
                cur=head;
            }
            else if(str[i]==']')
            {
                cur=Left[last];
            }
            else
            {
                Link(i,Right[cur]);
                Link(cur,i);
                cur=Right[cur];
            }
        }
        int now=Right[head];
        while(now!=last)
        {
            cout<<str[now];
            now=Right[now];
        }

        cout<<endl;
    }
    return 0;
}

[UVA] 514 - Rails

題意:
火車有n節車廂，
每個車廂都有依序的編號1...n，
現在這些車廂要從A到B，這個火車可以重組，
重組的方法如下:
車廂是一個一個到車站，
來到車站後可以往B方向去，也可以先暫放在車站。
輸入往另一個方向的車廂編號，
問是否可以藉由重組，
往另一個方向去。
範例輸入:
5           //5節車廂
1 2 3 4 5
5 4 1 2 3
0           //結束
問是否可以以1 2 3 4 5的順序往B方向，
一開始從A方向也是1 2 3 4 5
所以1先進車站，直接往B去，
接著2進車站，直接往B去，
接著3進車站，直接往B去，
接著4進車站，直接往B去，
接著5進車站，直接往B去，
就可以以1 2 3 4 5的順序往B方向去，
所以輸出Yes
而5 4 1 2 3，
1先進車站，先暫放，
2進車站，先暫放，
3進車站，先暫放，
4進車站，先暫放，
5進車站，往B方向去，
接著4往B方向去，
再來車站只能把3往B送，不能送1 2(因為3還沒出)，
不可能以5 4 1 2 3的順序重組輸出，
所以輸出No

方法:
車站是一個stack
直接模擬操作，使用一個queue儲存輸入，
依序將1 2 ...n送入stack，
若stack.top==queue.front，那就pop
若stack最後不為空就是No，反之就是Yes



/* 20150814
 * hanting
 * UVa 514 - Rails
 * C++
 */
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
bool CanRestructure(queue<int> &que)
{
    vector<int> from(que.size());
    for(int i=0;i<from.size();i++)
    {//給予from初始值1 2 ...n
        from[i]=i+1;
    }
    stack<int> stk;
    for(int i=0;i<from.size();i++)
    {
        stk.push(from[i]);//車廂一個個進車站
        while(stk.size() and que.front()==stk.top())
        {//若與B的頭一樣就輸出，也就是pop車站的車廂
            stk.pop();
            que.pop();
        }
    }
    if(stk.size()) return false;
    else return true;
}
int main()
{
    int N;
    while(cin>>N and N)
    {
        while(true)
        {
            queue<int> que;
            int num;
            cin>>num;
            if(!num) break;//0跳出
            que.push(num);
            for(int i=1;i<N;i++)
            {
                cin>>num;
                que.push(num);
            }
            if(CanRestructure(que))
                cout<<"Yes"<<endl;
            else
                cout<<"No"<<endl;
        }
        cout<<endl;
    }
    return 0;
}



[UVA] 221 - Urban Elevations

題意:
給你一個城市的俯視圖，
輸入每一棟建築物的
。x 座標
。y 座標
。寬
。長
。高
每一個資訊都是實數，(不是整數)
建築物編號為輸入順序，
例如第一個輸入的編號為1
問正視圖中可見的建築物有哪些，
輸出建築物編號，
以建築物的 x 座標由小到大輸出，
注意!若 x 座標相同以建築物 y 座標由小到大輸出!
例如:
輸入
3//三個建築物
0 0 10 1 50
0 1 11 1 20
0 2 10 1 100

建築物1 2 3都可看到，
但要依照 x 座標案 y 座標輸出，
所以輸出1 2 3。


方法:
離散化
可以列舉每一個x座標，然後看該 x 座標有哪些建築物可見，
但是問題在於，x 座標有無限個，不可能全部列舉，
所以用離散化的方式，將無限變有限。
作法是將每一個建築物的頭和尾的 x 座標紀錄起來排序後做unique，
然後去列舉這些 x 座標就好，
判斷在 x 座標為 i 時該建築物可不可見，
先判斷該建築物是否有覆蓋到 i (頭<=i<=尾)，
然後再判斷該建築物前面是否有比他高的，
也就是 y 座標比該建築物小的也覆蓋到 i ，是否有比他高!

注意!每一筆測資之間需空一行，最後一筆測資後面不需要空行。



/* 20150812
 * hanting
 * UVa 221 - Urban Elevations
 * C++
 */
#include <iostream>
#include <vector>
#include <algorithm>//sort,unique
using namespace std;
struct Building
{
    int id;
    double x,y,width,depth,height;
    friend istream& operator>>(istream& in,Building &b)
    {
        in>>b.x>>b.y>>b.width>>b.depth>>b.height;
        return in;
    }
    bool operator<(const Building &B)const
    {
        return (x<B.x) or (x==B.x and y<B.y);
    }
    bool cover(double t)
    {
        return t>=x and t<=x+width;
    }
    bool visible(double x,Building *b,int n)
    {
        for(int i=0;i<n;i++)
        {
            if(b[i].cover(x) and b[i].y<y and b[i].height>=height) return false;
        }
        return true;
    }
};
int main()
{
    int buildingN;
    int Case=1;
    int blank=0;
    while(cin>>buildingN and buildingN)
    {
        if(blank++) cout<<endl;
        Building building[buildingN];
        double xCoor[buildingN*2];
        for(int i=0;i<buildingN;i++)
        {
            cin>>building[i];
            building[i].id=i+1;//編號從1開始
            xCoor[i*2]=building[i].x;
            xCoor[i*2+1]=building[i].x+building[i].width;
        }
        sort(building,building+buildingN);
        sort(xCoor,xCoor+buildingN*2);
        int m=unique(xCoor,xCoor+buildingN*2)-xCoor;
        vector<int> ans;
        ans.push_back(0);

        for(int i=1;i<buildingN;i++)
        {
            for(int j=0;j<m-1;j++)
            {
                double x=(xCoor[j]+xCoor[j+1])/2;
                if(building[i].cover(x) and building[i].visible(x,building,buildingN))
                {
                    ans.push_back(i);
                    break;
                }
            }
        }

        cout<<"For map #"<<Case++<<", the visible buildings are numbered as follows:"<<endl;

        for(int i=0;i<ans.size()-1;i++)
        {
            cout<<building[ans[i]].id<<" ";
        }
        cout<<building[ans.back()].id<<endl;
    }
    return 0;
}

[UVA] 1592 - Database

題意:
輸入列數和行數，
表示有一個列*行個欄位的字串表，
每個欄位一個字串，
問說能不能找到r1,r2,c1,c2
使得字串(r1,c1)==字串(r2,c1) and 字串(r1,c2)==字串(r2,c2)，
如果有就輸出NO，並輸出哪兩列的哪兩行
如果沒有就輸出YES
範例輸入:

所以輸出
2 3
2 3

方法:
這題要先做預處理喔，
將字串都以編號代替，
不然除了會TLE外，
還會TLE。
再來不需要一個一個列舉，
只需要枚舉行就好，(因為題目有說行數<=10)
 再把每一列的兩個字串編號和列數以二元組存取，
例如該列有兩個字串編號:15和23，
那就將10和23合體當first，該列數當second，
(1500023,2)，表示第二列有字串10和字串23，
如果該二元組已經存在，
表示找到題目所求，即可輸出!
注意只要找到一組就好哦!

/* 20150803
 * hanting
 * UVa 1592 - Database
 * C++
 */
#include <iostream>
#include <map>
#include <cstring>//strtok
using namespace std;
map<string,int> ID;
int sum=0;
int idx=1;
int StrID(string str)
{
    if(ID[str]) return ID[str];
    return ID[str]=idx++;
}
int main()
{
    int row,col;
    while(cin>>row>>col)
    {
        cin.get();
        string table[row+2][col+2];
        string tmp;
        for(int i=1;i<=row;i++)
        {
            getline(cin,tmp);//注意要讀一整行再做切割
            char *pch=strtok((char*)tmp.c_str(),",");

            int j=1;
            while(pch)
            {
                table[i][j++]=pch;
                pch=strtok(NULL,",");
            }
        }
        int IDtable[row+2][col+2];//預處理,將字串予編號
        for(int i=1;i<=row;i++)
        {
            for(int j=1;j<=col;j++)
            {
                IDtable[i][j]=StrID(table[i][j]);
            }
        }
        bool Yes=true;//找到一項即可
        for(int i=1;i<=col and Yes;i++)
        {
            for(int j=i+1;j<=col and Yes;j++)
            {
                map<int,int> Map;//Map[idx]=列
                for(int k=1;k<=row and Yes;k++)
                {
                    int idx=IDtable[k][i]*100000+IDtable[k][j];
                    if(Map.count(idx))
                    {
                        cout<<"NO"<<endl;
                        cout<<Map[idx]<<" "<<k<<endl;
                        cout<<i<<" "<<j<<endl;
                        Yes=false;
                    }
                    else
                    {
                        Map[idx]=k;
                    }
                }
            }
        }
        if(Yes) cout<<"YES"<<endl;

    }
    return 0;
}

[UVA] 400 - Unix ls

題意:
輸入多個字串，
以最長字串的格子數+2為每一個字串可輸出的格子數，
以字典序先由上而下再從左到右輸出，
也就是以行為主!
每一列最長60字元。

方法:
先找出最長字串，
因為每個字串的格子數固定，
所以可以算出每一列最多可以放幾個字串，
再把它一個一個放進一個二維陣列，
注意是以行為主喔!
再以列為主輸出二維陣列的字串就好。

/* 20150803
 * hanting
 * UVa 400 - Unix ls
 * C++
 */
#include <iostream>
#include <vector>
#include <algorithm>//sort
#include <iomanip>//setw
using namespace std;
int main()
{
    int N;
    while(cin>>N)
    {
        cout<<"------------------------------------------------------------"<<endl;
        vector<string> vec(N);
        int maxi=0;
        for(int i=0;i<N;i++)
        {
            cin>>vec[i];
            if(maxi<vec[i].size()) maxi=vec[i].size();
        }
        sort(vec.begin(),vec.end());
        int w;//欄位
        int h;//列
        w=(60-maxi)/(maxi+2)+1;
        h=N/w+(N%w ? 1 : 0);
        string output[h][w];
        int x=0;
        for(int i=0;i<w and x<vec.size();i++)
        {
            for(int j=0;j<h and x<vec.size();j++)
            {
                output[j][i]=vec[x++];
            }
        }

        for(int i=0;i<h;i++)
        {
            for(int j=0;j<w;j++)
            {
                cout<<setw(j!=w-1 ? maxi+2 : maxi)<<left<<output[i][j];
            }cout<<endl;
        }
    }
    return 0;
}

[UVA] 12096 - The SetStack Computer

題意:
有一個裝set的stack，
五種操作:
PUSH:裝一個空集合進去stack
DUP:複製stack 最頂端的set再push進去stack
UNION:拿stack最頂端兩個set做聯集再push進去stack
INTERSERT:拿stack最頂端兩個set做交集再push進去stack
ADD:將stack最頂端的set拿出來後insert進去stack最頂端的set
每一次操作都要輸出stack最頂端的set的size
範例輸入的示意圖:(藍色數字就是輸出目前stack最頂端的set的size)




















方法:
如果直接操作會超時，
先將set做編號，
例如{}編號為0，
那麼PUSH時就可以PUSH 0進去stack，
這樣stack可以用stack<int>做儲存，
set也可以用set<int>做儲存，
接下來就可以做五種操作了，
在取top跟pop時要注意有沒有少pop!

/* 20150803
 * hanting
 * UVa 12096 - The SetStack Computer
 * C++
 */
#include <iostream>
#include <map>
#include <vector>
#include <stack>
#include <set>
#include <algorithm>//set_union,set_intersection
using namespace std;
stack<int> stk;
map<set<int>,int> Map;
vector<set<int> > vec;
int SetID(set<int> &s)
{
    if(Map.count(s)) return Map[s];
    vec.push_back(s);
    return Map[s]=vec.size()-1;
}
set<int> Empty;
void PUSH()
{
    stk.push(SetID(Empty));
}
void DUP(int t)
{
    stk.push(t);
    stk.push(t);
}
void UNION(int t)
{
    int t2=stk.top();
    stk.pop();
    set<int> un;
    set_union(vec[t].begin(),vec[t].end(),vec[t2].begin(),vec[t2].end(),inserter(un,un.begin()));
    stk.push(SetID(un));
}
void INTERSECT(int t)
{
    int t2=stk.top();
    stk.pop();
    set<int> in;
    set_intersection(vec[t].begin(),vec[t].end(),vec[t2].begin(),vec[t2].end(),inserter(in,in.begin()));
    stk.push(SetID(in));
}
void ADD(int t)
{
    set<int> s(vec[stk.top()].begin(),vec[stk.top()].end());
    stk.pop();
    s.insert(t);
    stk.push(SetID(s));
}
int main()
{
    int N;
    cin>>N;
    while(N--)
    {
        while(stk.size()) stk.pop();//initial
        int cmdN;
        cin>>cmdN;
        for(int i=0;i<cmdN;i++)
        {
            string cmd;
            cin>>cmd;
            if(cmd=="PUSH")
            {
                PUSH();
            }
            else
            {
                int top=stk.top();
                stk.pop();
                if(cmd=="DUP")
                {
                    DUP(top);
                }
                else if(cmd=="UNION")
                {
                    UNION(top);
                }
                else if(cmd=="INTERSECT")
                {
                    INTERSECT(top);
                }
                else//ADD
                {
                    ADD(top);
                }
            }
            cout<<vec[stk.top()].size()<<endl;
        }
        cout<<"***"<<endl;
    }
    return 0;
}

[UVA] 136 - Ugly Numbers

題意:
醜數:質因數只有2 3 5，
1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40...這些都是醜數
求第1500個醜數。

方法:
醜數一定是2a*3b*5c，其中 a,b,c >= 0，
所以先把2 3 5放進優先佇列，一個一個pop，
取出後分別將*2和*3和*5的數再push進去佇列，
pop第1500次就是答案囉
(答案:859963392)


/* 20150801
 * hanting
 * UVa 136 - Ugly Numbers
 * C++
 */
#include <iostream>
#include <map>
#include <queue>
using namespace std;

int main()
{
    long long init[]={5,3,2,1};
    priority_queue<long long,vector<long long>,greater<long long> > prq(init,init+4);
    map<long long,long long> Map;
    Map[1]=Map[2]=Map[3]=Map[5]=1;
    for(long long i=0;i<1500-1;i++)
    {
        long long x2,x3,x5;
        long long top=prq.top();
        prq.pop();
        x2=top*2;
        x3=top*3;
        x5=top*5;
        if(Map[x2]==0)
        {
            prq.push(x2);
            Map[x2]=1;
        }
        if(Map[x3]==0)
        {
            prq.push(x3);
            Map[x3]=1;
        }
        if(Map[x5]==0)
        {
            prq.push(x5);
            Map[x5]=1;
        }
    }
    cout<<"The 1500'th ugly number is "<<prq.top()<<"."<<endl;
    return 0;
}