[UVa] 839 - Not so Mobile

輸入是以遞迴方式進行
判斷輸入的天平兩邊重量是否為零，來決定下一個輸入是否為子天平
也是參考《入門經典》和其他人的程式碼所提供的解法

#include <stdio.h>
#include <stdlib.h>
int eq;
int sol(){
    int W1,D1,W2,D2;
    scanf("%d %d %d %d",&W1,&D1,&W2,&D2);
    if(!W1){
        W1 = sol();
    }
    if(!W2){
        W2 = sol();
    }
    if(W1*D1!=W2*D2)eq=0;
    return W1+W2;
}
int main(){
    freopen("input.txt","r",stdin);
    int W,kase;
    scanf("%d",&kase);
    while(kase--){
        eq = 1;
        sol();
        if(eq==1)printf("YES\n"); else printf("NO\n");
        if(kase)printf("\n");
    }
   
    return 0;
}

[UVa] 548 - Tree

參考入門經典一書的程式碼
改以struct建構樹的方式進行改寫
許多細節需要注意

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <vector>
#include <string>
#include <cstdio>
#include <iostream>
#include <sstream>
using namespace std;
bool failed;
const int maxn = 10010;
int i=0,inorder[maxn], postorder[maxn];

struct Node{
    bool have_value;
    int v;
    Node *left, *right;
    Node():have_value(false),left(NULL),right(NULL){};
};
Node *root;

Node* newnode(){
    return new Node();
}

void remove_tree(Node* u){
    if(u==NULL)return;
    remove_tree(u->left);
    remove_tree(u->right);
    delete u;
}

Node* buildtree(int L1, int R1, int L2, int R2){
    if(L1>R1)return NULL;
    Node* u = newnode();
    u->v = postorder[R2];
    u->have_value = true;
    int p = L1;
    while(inorder[p] != u->v)p++;
    int count = p-L1; //nodes of left tree

    u->left = buildtree(L1,p-1,L2,L2+count-1);
    u->right = buildtree(p+1,R1,L2+count,R2-1);
    return u;
}

int best_sum, best;
void dfs(Node* u, int sum){
    sum = sum + u->v;
    if(u->right==NULL && u->left==NULL)
        if(sum<best_sum || (sum==best_sum && u->v < best)){
            best_sum = sum;
            best = u->v;
        }
    if(u->right){
        dfs(u->right, sum);
    }
    if(u->left){
        dfs(u->left, sum);
    }

}

/*
//顯示樹有無建立成功使用
int n=0;
vector<int> ans;
bool bfs(){
    queue<Node*> q;
    ans.clear();
    q.push(root);
    while(!q.empty()){
        Node* u = q.front(); q.pop();
        if(!u->have_value) return false;
        ans.push_back(u->v);
        n++;
        if(u->left != NULL)q.push(u->left);
        if(u->right != NULL)q.push(u->right);
    }
    return true;
}
*/

int main(){
    string line;
    while(getline(cin,line)){
        i=0;
        int x;
        stringstream ss(line);
        while(ss>>x){
            inorder[i]=x;
            i++;
        }
        int L1=0,R1=i-1;
        //for(int k=0;k<i;k++)printf("%d\n",inorder[k]);
        i=0;
        getline(cin,line);
        stringstream ss2(line);
        while(ss2>>x){
            postorder[i]=x;
            i++;
        }
        int L2=0,R2=i-1;
        //for(int k=0;k<i;k++)printf("%d\n",postorder[k]);
       
        root = buildtree(L1,R1,L2,R2);
        best_sum = 10000000;

        dfs(root,0);
        printf("%d\n",best);
        remove_tree(root);
        /*
        bfs();
        for(int j=0;j<ans.size()-1;j++){
            printf("%d ",ans[j]);
        }
        */
    }

    return 0;
}

[UVa] 122 - Trees on the level

也是參考《入門經典》一書的方法
用結構和指標去建立樹的節點

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <vector>
#include <string>
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 300;
bool failed;
char s[maxn];
struct Node{
    bool have_value; //是否已建立
    int v; //值
    Node *left, *right; //left and right node
    Node():have_value(false),left(NULL),right(NULL){}; //建構函數
};
Node *root; //root of tree

//申請新節點的函數
Node* newnode(){
    return new Node();
}

void addnode(int v, char* s){
    int n = strlen(s);
    Node* u = root; // u 從根節點往下
    for(int i=0;i<n;i++){
        if(s[i]=='L'){
            if(u->left==NULL)u->left = newnode(); //不存在則建立新節點
            u = u->left; //往左
        }else if(s[i]=='R'){
            if(u->right==NULL)u->right = newnode();
            u = u->right;
        }
    }
    if(u->have_value)failed = true;
    u->v = v;
    u->have_value = true;
}

void remove_tree(Node* u){
    if(u==NULL) return;
    remove_tree(u->left);
    remove_tree(u->right);
    free(u);
}






//讀取資料
bool read_input(){
    failed = false;
    remove_tree(root);
    root = newnode(); //建立根節點
    while(1){
        if(scanf("%s", s)!=1) return false;
        if(!strcmp(s,"()"))break; // End
        int v;
        sscanf(&s[1], "%d", &v); //讀入節點值(數字)
        addnode(v, strchr(s,',')+1);
    }
    return true;
}

int n=0;
vector<int> ans;
bool bfs(){
    queue<Node*> q;
    ans.clear();
    q.push(root);
    while(!q.empty()){
        Node* u = q.front(); q.pop();
        if(!u->have_value) return false; //錯誤
        ans.push_back(u->v); //增加到輸出尾部
        n++;
        if(u->left != NULL)q.push(u->left);
        if(u->right != NULL)q.push(u->right);
    }
    return true;
}

int main(){
    while(read_input()){
        if(!bfs())failed=1;
        if(failed)printf("not complete\n");
        else {
            for(int i=0;i<ans.size()-1;i++){
                printf("%d ",ans[i]);
            }
            printf("%d",ans[ans.size()-1]);
            printf("\n");
        }
    }
    return 0;
}

[UVa] 679 - Dropping Balls

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(){
    int kase;
    while(1){
        scanf("%d",&kase);
        if(kase==-1)break;
        for(int i=0;i<kase;i++){
            int D,I,P=1;
            scanf("%d %d",&D,&I);
            while(D--){
              //if(D==1)break;
              if(I%2!=0){
                    I=I/2+1;
                    P=P*2;
                }
                else{
                     P = P*2+1;
                    I = I/2;
                }
            }
            printf("%d\n",P/2);
        }
    }
    return 0;
}

[UVa] 12657 - Boxes in a Line

參考書上的經典鏈結串列題目
有點複雜，花點腦筋想即可
STL會TLE，所以書上用陣列操作

2015/1/16 做了些改良，在書中 swap(x,y) 可拿掉，在後面直接作判斷

if (right[y]==x) {
   link(ly,x); link(x,y); link(y,rx);
}

可達到相同效果
用陣列操作鍊結串列，本就有許多不方便的地方

//STL會TLE，所以改用陣列模擬
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <algorithm>
using namespace std;

const int maxn = 100010;
int left[maxn], right[maxn]; //儲存左邊和右邊盒子序號的陣列
void link(int l, int r){ //連接 l and r ，l在左,r在右
    left[r] = l; right[l] = r;
}
int main(){
// freopen("input.txt","r",stdin);
    int n,m,c,x,y;
    int cas=0;
    while(scanf("%d %d", &n, &m)!=EOF){
      cas++;
        int inv=0;
        for(int i=1;i<=n;i++){
            left[i]=i-1;
            right[i]=(i+1)%(n+1); //尾數的右邊為1
        }
        right[0] = 1;
        left[0] = n;

        while(m--){ 
            scanf("%d",&c);
            if(c==4)inv = !inv;
            else if(c!=3 && inv)c = 3-c; //反向狀態，換的位子要變
            if(c==1){
              scanf("%d %d",&x,&y);
              if(x==left[y])continue;
                link(left[x],right[x]); link(left[y],x); link(x,y);
            }
            else if(c==2){
              scanf("%d %d",&x,&y);
                if(x==right[y])continue;
                int lx = left[x], rx = right[x], ly=left[y], ry=right[y];
              link(lx,rx); link(y,x); link(x,ry);
            }
            else if(c==3){
              scanf("%d %d",&x,&y);
                int lx = left[x], rx = right[x], ly=left[y], ry=right[y];
                if(right[y]==x){ //相鄰情況
                  link(ly,x); link(x,y); link(y,rx);
                }else if(right[x]==y){ //相鄰情況
                  link(lx,y); link(y,x); link(x,ry);
                }else{
                  link(lx,y); link(y,rx); link(ly,x); link(x,ry);
                }
            }
            /*
            int a=0;
            for(int i=1;i<=n;i++){
              a = right[a];
                printf("%d ",a);
            }
            printf("\n");
            */
        }
        int box=0;
        long long sum=0;
        for(int i=1;i<=n;i++){
          box = right[box];
          if(i%2 == 1) sum += box;
        }
        if(inv && n%2==0) sum = (long long)n*(n+1)/2 - sum;
        printf("Case %d: %lld\n",cas,sum);
       
    }
    return 0;
}

[UVa] 11988 - Broken Keyboard

犯了嚴重錯誤
在迴圈之前應該就要給定strlen值
否則會TLE

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <list> // STL linked list
#include <iostream>
using namespace std;
list<char> text;
list<char>::iterator it=text.begin();
int main(){
  char input[100001];
  while(scanf("%s",input)!=EOF){
    int length = strlen(input); //重點：不在迴圈中呼叫strlen，否則TLE
    text.clear();
    it = text.begin();
    for(int i=0;i<length;i++){
      if(input[i]=='[')it=text.begin();
      else if(input[i]==']')it=text.end();
      else{
        text.insert(it,input[i]);
      }
    } 
    for(it=text.begin();it!=text.end();it++) printf("%c",*it);
    printf("\n");
  }
  return 0;
}

[UVa] 442 - Matrix Chain Multiplication

也是stack的用法
將 Matrix struct 宣告陣列來儲存A~Z的矩陣
遇到字母則push進堆疊，遇右括弧則pop兩個相乘再push

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <iostream>
#include <stack>
using namespace std;
struct Matrix{
    char name;
  int row, col;
};

int main(){
    int n;
    Matrix mat[26]; //存放矩陣結構的陣列
    stack<Matrix> s; //存放矩陣的堆疊

    scanf("%d",&n);
    getchar();
    for(int i=0;i<n;i++){ //Input Matrixs
        char a;
        int r,c;
        scanf("%c %d %d",&a,&r,&c);
    getchar();
        mat[a-'A'].name = a;
        mat[a-'A'].row  = r;
        mat[a-'A'].col  = c;
    }
  
    char input[1000];      
    while(fgets(input,sizeof(input),stdin)){
        int count=0;
    bool error=0;
        for(int i=0;i<=strlen(input);i++){
            if(isalpha(input[i])){ //找到字母則入堆疊
                s.push(mat[input[i]-'A']);
            }
            else if(input[i]==')'){
                Matrix mat_b = s.top(); s.pop();
                Matrix mat_a = s.top(); s.pop();
                if(mat_a.col != mat_b.row){
                    error=1;
                    break;
                }
                count += mat_a.row * mat_a.col * mat_b.col;
        Matrix tmp;
        tmp.row = mat_a.row;
        tmp.col = mat_b.col;
        s.push(tmp);
            }
        }
        if(error==1)printf("error\n"); else printf("%d\n",count);
  }
 
    return 0;
}