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