USACO 1.2

Brief

本章節的題目也是沒有什麼特定演算法，有些可以使用DP來處理，有些則是根據題目敘述來解即可

Milking Cows

此提使用DP來解，思考過程如下

• 將所有farmers的工作時間依據其起點由早到晚排序

      for(int i=0;i<n;i++){
          farmers* f = new farmers();
          fin >> f->low >> f->high;
          data.push_back(f);
      }
      sort(data.begin(),data.end(),compare);

• 掃過所有farmers的工作時間，判斷當前的farmers是否有跟上一個farmers的時間有重疊，如果有重疊，就更新當前紀錄的工作時間，如果沒有重疊，就代表此時需要閒置，因此就要更新當前閒置時間，每次更新的同時，也順便紀錄最大值

      currLow = data[0]->low;
      currHigh= data[0]->high;
      maxMilked = currHigh - currLow;
      maxNotMilked = 0;
      for(int i=1;i<data.size();++i){
          if(data[i]->low > currHigh){ //沒有重疊
              maxNotMilked = max(maxNotMilked,data[i]->low - currHigh);
              currLow = data[i]->low;
              currHigh = data[i]->high;
              maxMilked = max(maxMilked,currHigh-currLow);
          }
          else if (data[i]->high > currHigh){ //有重疊
              currHigh = data[i]->high;
              maxMilked = max(maxMilked,(currHigh - currLow));
          }
      }

• 全部掃過一遍及可找到答案

Transformations

• 此題不難，只要想好如何將一個矩陣給順時針旋轉90即可

void turn90(char* data,int n){
    char *tmp = new char[n*n];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            tmp[j*n+(n-i-1)] =  data[i*n + j];
        }
    }
    memcpy(data,tmp,n*n);
    delete tmp;
    return ;
}

• 根據題目所規定的順序，每種都去嘗試，若符合就印出答案，不合就繼續嘗試下一種即可。

    //#1
    turn90(src,n);
    if( 0 == memcmp(src,dst,n*n)){
        fout <<"1"<<endl;
        return 0;
    }
    //#2
    turn90(src,n);
    if( 0 == memcmp(src,dst,n*n)){
        fout <<"2"<<endl;
        return 0;
    }
    //#3
    turn90(src,n);
    if( 0 == memcmp(src,dst,n*n)){
        fout <<"3"<<endl;
        return 0;
    }
    //#4
    turn90(src,n);
    reflect(src,n);
    if( 0 == memcmp(src,dst,n*n)){
        fout <<"4"<<endl;
        return 0;
    }
    //#5
    for(int i=0;i<3;i++){
        turn90(src,n);
        if( 0 == memcmp(src,dst,n*n)){
            fout <<5<<endl;
            return 0;
        }
    }
    //#6
    turn90(src,n);
    reflect(src,n);
    if( 0 == memcmp(src,dst,n*n)){
        fout <<"6"<<endl;
        return 0;
    }
    //#7
    fout<<"7"<<endl;

Name That Number

• 一開始先讀取dict.txt，只將長度符合題目要求的單字給存起來

while(din >> tmp){
  if(tmp.size() == input.size())
  data.push_back(tmp);
}

• 接下來依據位數來一個一個檢查。先針對單字內所有的第一位進行檢查是否符合規則，若不合就將其從字典內刪除，以此往下即可找到所有符合的答案

    for(int i=0;i<input.size();++i){
          for(list<string>::iterator itr = data.begin(); itr != data.end() ; ){
              if(check(input[i]-'0',(*itr)[i])){
                  ++itr;
              }
              else{
                  itr = data.erase(itr);
              }

          }
      }

Palindromic Squares

• 對於1~300之間的每個數字都去進行驗證
• 首先將先該數字給平方，接者去判斷是否迴文，若是就印出答案即可

 void PalindromesSquare(int n,int base){
      string baseString;
      string squareString;
      int tmp = n;
      n = n *n;
      while(n){ //計算平方後的字串
          squareString.push_back(getBaseChar(n%base));
          n/=base;
      }
      while(tmp){ //計算當前的字串
          baseString.push_back(getBaseChar(tmp%base));
          tmp/=base;
      }
      if ( checkPalin(squareString) ){
          n = baseString.size();
          for(int i=0;i<baseString.size();++i)
              fout<<baseString[n-i-1];
          fout<<" "<<squareString<<endl;
      }

  }

Dual Palindromes

• 這題跟 Dual Palindromes非常類似，先根據題目的需求對每個數字去做處理
• 每次處理都以2~10進位去試試看有沒有迴文，若能夠產生迴文的base數量超過兩個就直接印出結果，直接測是下一個數字即可

  int main() {
      ifstream fin ("dualpal.in");
      int limit;
      int start;
      int count;
      fin >> limit >> start;
      while(limit){
          ++start;
          count =0;
          for(int i=2;i<=10;++i){
              if( PalindromesSquare(start,i)){
                  ++count;
                  if( 2 == count){
                      fout<<start<<endl;
                      --limit;
                      break;
                  }
              }
          }
      }
      return 0;
  }