[UVa] 514 - Rails

卡了很久
因為輸出的 "Yes" 寫成 "YES" ...

Stack基本題
已有通盤的瞭解

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <iostream>
#include <stack>
using namespace std;
int main(){
  freopen("input.txt","r",stdin);
  int n, B[1001];
  int tmp=0;
  while(scanf("%d",&n)==1){
    if(n==0)break;
    while(1){
      memset(B,0,sizeof(B));
      stack<int> s;
      for(int i=0;i<n;i++){
        scanf("%d",&B[i]);
        if(B[i]==0)break;
      }
      if(B[0]==0){
        puts("");
        break;
      }
      int flag=0,A=1,ok=1; 
      while(flag<n){ 
        if(A==B[flag]){
          A++;
          flag++;
        }
        else if(!s.empty() && s.top()==B[flag]){
          flag++;
          s.pop();
        }
        else if(A<n){
         s.push(A);
         A++;
        }else {
          break;
        }
      }
      if(s.empty())printf("Yes");else printf("No");
      puts("");
    }

  }
  return 0;
}

[UVa] 101 - The Blocks Problem

參考算法競賽入門經典ㄧ書

運用STL中vector的一些特性

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <iostream>
#include <cctype>
#include <set>
#include <map>
#include <vector>
#include <sstream>
using namespace std;
int n;
vector<int> pile[30];
void find_block(int a, int& p, int& h){
  for(p=0;p<n;p++){
    for(h=0;h<pile[p].size();h++){
      if(pile[p][h]==a)return; //找到後回傳p及h之位址
    }
  }
}
void clear_above(int p, int h){
  for(int i=h+1; i<pile[p].size();i++){
    int b = pile[p][i];
    pile[b].push_back(b); //put b back
  }
  pile[p].resize(h+1); //改變大小，只保留h以下
}
void pile_onto(int p, int h, int p2){
  for(int i=h; i<pile[p].size(); i++)
    pile[p2].push_back(pile[p][i]); //p堆高度h以上的移到p2
  pile[p].resize(h); //h-1以上的去除
}

int main(){
  scanf("%d",&n);
  int a,b;
  string s1,s2;
  for(int i=0;i<n;i++) pile[i].push_back(i) ; 
  while(cin >> s1){
    if(s1=="quit")break;
    cin >> a >> s2 >> b; 
    int pa,pb,ha,hb;
    find_block(a, pa, ha);
    find_block(b, pb, hb);
    if(pa == pb)continue; //ignore
    if(s2 == "onto")clear_above(pb,hb); //遇onto則b上方木塊全部歸位
    if(s1 == "move")clear_above(pa,ha); //遇move則a上方木塊全部歸位
    pile_onto(pa, ha, pb);
  }
  for(int i=0;i<n;i++){
    printf("%d:", i);
    for(int j=0;j<pile[i].size();j++)printf(" %d", pile[i][j]);
    printf("\n");
  }
  return 0;
}

[UVa] 10194 - Football (aka Soccer)

這題卡了挺久的，拿了不少WA

待有空debug完再放上來

沒有完成真的無心往下繼續...

[UVa] 123 - Searching Quickly

這次算是STL的實習

運用了一些功能強大的函式

在此作個簡介

set : 集合，不會包含相同元素的集合

map : 可作一對一映射，兩者的資料型態可以不同

multimap : 可作一對多的映射

本題的作法，因為multimap在建立之時，就已經以前者元素作排序

getline讀入的一行也因為先後順序不同，在插入map時也排序好了

所以在map建立後直接輸出即可

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cctype>
#include <set>
#include <map>
using namespace std;
int main(){
  freopen("input.txt", "r", stdin);
  set<string> igwords;
  set<string>::iterator it; 
  string input;
  while(1){ //insert ignore words into igwords set
    cin >> input;
    if(input=="::")break;
    else {
      igwords.insert(input);
      input.erase();
    }
  }
  string title;
  multimap<string,string> titles;
  map<string,string>::iterator it_map =titles.begin();
  while(getline(cin,input)){ //getline(input_stream,destination_string)
    title.erase();
    for(int i=0;i<=input.size();i++)input[i] = tolower(input[i]); 
    for(int i=0;i<=input.size();i++){
      if(!isalpha(input[i])){
        if(igwords.count(title)==0 && isalpha(title[0])){ //如果和igwords都不相符
          string input_tmp = input; //開始將input中的單字轉為大寫存入input_tmp
          int tmp = i - title.length(); //
          for(int k = tmp; k < tmp+title.length(); k++) input_tmp[k]=toupper(input[k]); 
          titles.insert(it_map,pair<string,string>(title,input_tmp)); //存入titles中
        }
        title.erase();
        continue;
      }
      title+=input[i];
    }
    input.erase();
  }
  //print set
//  for(it=igwords.begin();it!=igwords.end();it++)cout << *it << '\n';
//  cout << "\n";
  for(it_map=titles.begin();it_map!=titles.end();it_map++)cout << it_map->second << '\n';
  return 0;

}

[UVa] 400 - Unixls

奇怪的是，題目說最右邊欄的寬度是最大檔名長，但輸出時卻都要+2才會過...

/*-----------------------------------------------------*/
/*參考程式競賽與演算法入門經典P.5-32內容               */
/*-----------------------------------------------------*/
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int max_col = 60; //最大行數
const int maxn = 105; //檔案名稱最大長度
string filenames[maxn];

int main(){
  freopen("input.txt", "r", stdin);
  int n=0;
  while(cin >> n){
    int M = 0;  //檔案名稱最長長度
    for(int i=0;i<n;i++){
      cin >> filenames[i];
      if((int)filenames[i].length()>M) M = filenames[i].length();
    }
    sort(filenames, filenames+n); //sort
    for(int i=0;i<60;i++)printf("-");
    printf("\n");    
    //行數=最大行數減最大檔名，除上最大檔名加2(得到除最後一行的行數)
    //再把最後一行加回來的數即是
    int cols = (max_col-M)/(M+2) + 1;
    int rows = n/cols; 
    if(n%cols==0); else rows++; //無條件進位

    int flag;
    for(int r=0;r<rows;r++){
      for(int c=0;c<cols;c++){
        flag = c*rows+r; //直接計算出位置
        if(flag < n)cout << filenames[flag];
        for(int i=0; i<M-(int)filenames[flag].length() ;i++)cout << " ";
        cout << "  ";
      }
      cout << "\n"; 
    }
  }


  return 0;
}

[UVa] 156 - Ananagrams

要注意的點很多

主要流程：換小寫，字串內排序，比對抽出原字串，原字串互相排序，輸出

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <cstdio>
#include <cstring
#include <iostream>
using namespace std;
int main(){
  //freopen("input.txt", "r", stdin);
  char words[1500][30]; //up to 1000 words and 20 letters.
  char input[30];
  int count=0; //count the number of words
  memset(input,'\0',sizeof(input));
  memset(words,'\0',sizeof(words));

  while(scanf("%s",input)!=EOF){
    if(input[0]=='#'){
        count--;
        break;
    }
    strcpy(words[count],input);
    count++;
    memset(input,'\0',sizeof(input));
  }

  //換小寫
  char words_s[1500][30]={'\0'};
  for(int i=0;i<=count;i++){
    for(int j=0;j<30;j++){
      words_s[i][j]=tolower(words[i][j]);
    }
  }

  //排序
  int flag = 0;
  for(int i=0;i<=count;i++){
    for(int j=0;words_s[i][j]!='\0';j++){
      for(int k=j+1;k<strlen(words[i]);k++){
        if(words_s[i][k]<=words_s[i][j]){ //exchange
          char tmp;
          tmp = words_s[i][k];
          words_s[i][k] = words_s[i][j];
          words_s[i][j] = tmp;
        }
      }
    }
  }    
  //檢查相同
  char words_ok[1500][30];
  int is_ananagram;
  flag=0;
  memset(words_ok,'\0',sizeof(words_ok));
  for(int i=0;i<=count;i++){
    is_ananagram=1;
    for(int j=0;j<=count;j++){
      if(strcmp(words_s[i],words_s[j])==0 && i!=j){
        is_ananagram=0;
        break;
      }
    }
    if(is_ananagram==1 || strlen(words_ok[flag])==1){ //是獨立字或為個別字母
      strcpy(words_ok[flag],words[i]);
      flag++;
    }
  }
  int ok_count = flag; 
  //檢查出來的陣列 words_ok 按照字母排序
  for(int i=0;i<ok_count;i++){
    for(int j=i+1;j<ok_count;j++){
      if(strcmp(words_ok[i],words_ok[j])>0)
      {   char tmp[30];
          strcpy(tmp,words_ok[i]);
          strcpy(words_ok[i],words_ok[j]);
          strcpy(words_ok[j],tmp);
      }
    }
  }


  /*
  for(int i=0;i<=count;i++){
    for(int j=0;words_s[i][j]!='\0';j++)printf("%c",words_s[i][j]);
    printf("\n");
  }
  */

  for(int i=0;i<ok_count;i++){
    //for(int j=0;words_ok[i][j]!='\0';j++)
      printf("%s",words_ok[i]);
    printf("\n");
  }
  return 0;

}