#UVa:10338-Mischievous Children

排列組合的問題。有 n 個字母的總共排列方式是 n! ,而其中某個文字若是有重複 m 個的話則必須將結果除以 m! ,將所有重複的文字的排列數除掉後即是答案。

C++(0.040)

/*******************************************************/
/* UVa 10338 Mischievous Children                      */
/* Author: Maplewing [at] knightzone.org               */
/* Version: 2018/05/21                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;

void makeFactorial(long long int f[], long long int n){
  for(int i = 0 ; i <= n ; ++i){
    if(i == 0 || i == 1){
      f[i] = 1;
      continue;
    }

    f[i] = f[i-1] * i;
  }
}

int main(){
  long long int factorial[25];
  makeFactorial(factorial, 20);

  int caseCount;
  while(scanf("%d", &caseCount) != EOF){
    for(int caseNumber = 1 ; caseNumber <= caseCount ; ++caseNumber){
      string word;
      cin >> word;

      int totalWordCount = word.length();
      long long int result = factorial[totalWordCount];
      int charCount[26] = {0};
      for(int i = 0 ; i < word.length() ; ++i){
        ++charCount[word[i] - 'A'];
      }

      for(int i = 0 ; i < 26 ; ++i){
        result /= factorial[charCount[i]];
      }

      printf("Data set %d: %lld\n", caseNumber, result);
    }
  }

  return 0;
}

#UVa:11723-Numbering Roads

計算有這麼多可以用的數字上,能夠用幾種方式分別所有的道路,如果超過 26 + 1 ( 26 個字母加上不加字母)種的話,就表示不可能。

C++(0.000)

/*******************************************************/
/* UVa 11723 Numbering Roads                           */
/* Author: Maplewing [at] knightzone.org               */
/* Version: 2018/05/20                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int main(){
  int N, R;
  int caseNumber = 1;
  while(scanf("%d%d", &N, &R) != EOF &&
        N != 0 && R != 0){
    int group = (int)ceil((double)N / R);

    printf("Case %d: ", caseNumber++);
    if( group > 27 ){
      printf("impossible");
    }
    else{
      printf("%d", group - 1);
    }
    printf("\n");

  }
  return 0;
}

#UVa:11715-Car

利用計算速度的物理公式以及僅知的參數去求出答案即可。我是用其中的兩個公式再去推導的:
\(
\begin{align}
v & = u + a \times t \newline
S & = u \times t + \frac{1}{2} \times a \times t^{2}
\end{align}
\)

關鍵字:等加速度直線運動

C++(0.000)

/*******************************************************/
/* UVa 11715 Car                                       */
/* Author: Maplewing [at] knightzone.org               */
/* Version: 2018/05/18                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int main(){
  int type;
  int caseNumber = 1;
  while(scanf("%d", &type) != EOF && type != 0){
    printf("Case %d: ", caseNumber++);
    double u, v, t, a, s;
    switch(type){
      case 1:
        scanf("%lf%lf%lf", &u, &v, &t);
        a = (v - u) / t;
        s = (u + v) * t / 2;
        printf("%.3lf %.3lf", s, a);
        break;
      case 2:
        scanf("%lf%lf%lf", &u, &v, &a);
        t = (v - u) / a;
        s = (u + v) * t / 2;
        printf("%.3lf %.3lf", s, t);
        break;
      case 3:
        scanf("%lf%lf%lf", &u, &a, &s);
        v = sqrt(u * u + 2 * a * s);
        t = (v - u) / a;
        printf("%.3lf %.3lf", v, t);
        break;
      case 4:
        scanf("%lf%lf%lf", &v, &a, &s);
        u = sqrt(v * v - 2 * a * s);
        t = (v - u) / a;
        printf("%.3lf %.3lf", u, t);
        break;
    }
    printf("\n");
  }

  return 0;
}

#UVa:507-Jill Rides Again

找出最大連續和即可。從頭開始當作範圍的頭去加總,遇到總和變成負數之後將加總歸零再從此處當作範圍的頭開始加總,因為從此處歸零開始選會比包含前面加總的結果更好。整段做完的最後看哪段範圍總和最大、範圍最大且出現在比較前面即是答案。

C++(0.060)

/*******************************************************/
/* UVa 507 Jill Rides Again                            */
/* Author: Maplewing [at] knightzone.org               */
/* Version: 2018/05/17                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

int main(){
  int b;
  while(scanf("%d", &b) != EOF){
    for(int r = 1 ; r <= b ; ++r){
      int s;
      scanf("%d", &s);

      vector<int> routes;
      for(int i = 0 ; i < s - 1 ; ++i){
        int n;
        scanf("%d", &n);
        routes.push_back(n);
      }

      int i = -1, sum = 0;
      int maxI = -1, maxJ = -1, maxSum = 0;
      for(int j = 0 ; j < s - 1 ; ++j){
        sum += routes[j];
        if(i == -1) i = j;

        if(sum > maxSum || (sum == maxSum && j - i > maxJ - maxI)){
          maxSum = sum;
          maxI = i;
          maxJ = j;
        }

        if(sum < 0){
          sum = 0;
          i = -1;
        }
      }

      if(maxSum <= 0){
        printf("Route %d has no nice parts\n", r);
      }
      else{
        printf("The nicest part of route %d is between stops %d and %d\n", r, maxI+1, maxJ+2);
      }
    }
  }
  return 0;
}

#UVa:1197-The Suspects

利用 DFS 檢查從 0 號學生開始可以連到多少學生即可得解。建圖時,每個群組可以將群組裡面的其他學生全部連到群組中的特定學生(例如:第一個學生)即可。

C++(0.000)

/*******************************************************/
/* UVa 1197 The Suspects                               */
/* Author: Maplewing [at] knightzone.org               */
/* Version: 2018/05/17                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

int getDFSNodeCount(const vector<vector<int>> &graph, vector<bool> &isVisited, int startPoint){
  isVisited[startPoint] = true;

  int count = 1;
  for(int i = 0 ; i < graph[startPoint].size() ; ++i){
    if(!isVisited[graph[startPoint][i]]){
      count += getDFSNodeCount(graph, isVisited, graph[startPoint][i]);
    }
  }

  return count;
}

int main(){
  int n, m;
  while(scanf("%d%d", &n, &m) != EOF &&
        (n != 0 || m != 0)){

    vector<vector<int>> studentConnectGraph(n, vector<int>());
    for(int i = 0 ; i < m ; ++i){
      int k;
      scanf("%d", &k);

      int rootStudent = 0;
      for(int j = 0 ; j < k ; ++j){
        int currentStudent;
        scanf("%d", &currentStudent);

        if(j == 0){
          rootStudent = currentStudent;
          continue;
        }
        studentConnectGraph[rootStudent].push_back(currentStudent);
        studentConnectGraph[currentStudent].push_back(rootStudent);
        rootStudent = currentStudent;
      }
    }

    vector<bool> isVisited(n, false);
    printf("%d\n", getDFSNodeCount(studentConnectGraph, isVisited, 0));  
  }
  return 0;
}

#UVa:1185-Big Number

對數字取以 10 為底的 log 即可得其位數,故要求 n 階層的位數有多少為:
\(
\begin{align}
GetDigit(n!) & = \lfloor {\log (n!)} \rfloor + 1 \newline
& = \lfloor {\log (n \times (n-1) \times (n-2) \times \dots 1)} \rfloor + 1 \newline
& = \lfloor {\log n} + {\log (n-1)} + {\log (n-2)} + \dots + {\log 1} \rfloor + 1 \newline
\end{align}
\)

透過公式了解可以對各項取 Log 再加總後,就利用 DP 解決即可。

C++(0.330)

/*******************************************************/
/* UVa 1185 Big Number                                 */
/* Author: Maplewing [at] knightzone.org               */
/* Version: 2018/05/17                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int main(){
  int caseCount;
  scanf("%d", &caseCount);

  double logValue[10000005] = {0};
  int maxNumber = 0;
  for(int caseNumber = 0 ; caseNumber < caseCount ; ++caseNumber){
    int n;
    scanf("%d", &n);

    if( n > maxNumber ){
      for(int i = maxNumber + 1 ; i <= n ; ++i ){
        logValue[i] = logValue[i-1] + log10(i);
      }
    }

    printf("%d\n", (int)logValue[n] + 1);
  }

  return 0;
}

#UVa:1121-Subsequence

找出最短長度的數列可以比指定的數 S 大。

利用記住連續數列的最前端和最後端,慢慢從後面增長。如果總和超過了指定數 S ,則從最前端縮回來,直到數列總和比 S 小為止。

P.S. 記得處理總和沒辦法超過 S 的狀況。

C++(0.020)

/*******************************************************/
/* UVa 1121 Subsequence                                */
/* Author: Maplewing [at] knightzone.org               */
/* Version: 2018/05/16                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;

int main(){
  int N, S;
  while(scanf("%d%d", &N, &S) != EOF){
    vector<int> sequence;
    for(int i = 0 ; i < N ; ++i){
      int number;
      scanf("%d", &number);
      sequence.push_back(number);
    }

    int sum = 0, minLength = N+1, front = 0;
    for(int i = 0 ; i < N ; ++i ){
      sum += sequence[i];

      while(sum >= S){
        minLength = min(minLength, i - front + 1);
        sum -= sequence[front];
        ++front;
      }
    }

    printf("%d\n", (minLength == N+1)? 0 : minLength);
  } 
  return 0;
}

#UVa:1112-Mice and Maze

將輸入的邊反過來,從終點求對每個點的最短路徑(可用 SPFA ),再計算有哪些點所耗費的時間在 T 以內即可得解。

C++(0.010)

/*******************************************************/
/* UVa 1112 Mice and Maze                              */
/* Author: Maplewing [at] knightzone.org               */
/* Version: 2018/05/16                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

const int MAX_DISTANCE = 1e+6;

struct Edge{
  int from;
  int to;
  int timeCost;
};

void getShortestPath(int startPoint, const vector<vector<Edge>> &edges, vector<int> &shortestPath){
  queue<int> checkPoint;
  vector<bool> inQueue(shortestPath.size(), false);
  checkPoint.push(startPoint);

  while(!checkPoint.empty()){
    int currentPoint = checkPoint.front();
    checkPoint.pop();
    inQueue[currentPoint] = false;

    for(int i = 0 ; i < edges[currentPoint].size() ; ++i){
      Edge edge = edges[currentPoint][i];
      if(shortestPath[edge.from] + edge.timeCost < shortestPath[edge.to]){
        shortestPath[edge.to] = shortestPath[edge.from] + edge.timeCost;
        if(!inQueue[edge.to]){
          checkPoint.push(edge.to);
          inQueue[edge.to] = true;
        }
      }
    }
  }
}

int main(){
  int caseCount;
  while(scanf("%d", &caseCount) != EOF){
    for(int caseNumber = 0 ; caseNumber < caseCount ; ++caseNumber){
      int N, E, T, M;
      scanf("%d%d%d%d", &N, &E, &T, &M);

      vector<vector<Edge>> edges(N+5, vector<Edge>());
      for(int i = 0 ; i < M ; ++i){
        Edge edge;
        scanf("%d%d%d", &edge.to, &edge.from, &edge.timeCost);
        edges[edge.from].push_back(edge);
      }

      vector<int> shortestPathFromExit(N+5, MAX_DISTANCE);
      shortestPathFromExit[E] = 0;
      getShortestPath(E, edges, shortestPathFromExit);

      int mouseCount = 0;
      for(int i = 1 ; i <= N ; ++i){
        if(shortestPathFromExit[i] <= T){
          ++mouseCount;
        }
      }    

      if(caseNumber > 0) printf("\n");
      printf("%d\n", mouseCount);
    }
  }
  return 0;
}

#UVa:481-What Goes Up

經典的 LIS (Longest Increasing Subsequence) 題目,利用解 LIS 的演算法即可得解。

參考:演算法筆記 – Longest Increasing Subsequence

C++(0.010)

/*******************************************************/
/* UVa 481 What Goes Up                                */
/* Author: Maplewing [at] knightzone.org               */
/* Version: 2018/05/16                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;

int getLIS(const vector<int> &sequence, vector<int> &position){
  if(sequence.size() == 0) return 0;

  vector<int> subsequence;
  for(int i = 0 ; i < sequence.size() ; ++i ){
    vector<int>::iterator lowerBound = lower_bound(subsequence.begin(), subsequence.end(), sequence[i]);
    if(lowerBound == subsequence.end()){
      position[i] = subsequence.size();
      subsequence.push_back(sequence[i]);
    }
    else{
      position[i] = lowerBound - subsequence.begin();
      *lowerBound = sequence[i];
    }
  }

  return subsequence.size();
}


int main(){
  vector<int> sequence;
  int n;
  while(scanf("%d", &n) != EOF){
    sequence.push_back(n);
  }

  vector<int> position(sequence.size(), 0);
  int length = getLIS(sequence, position);
  printf("%d\n", length);
  printf("-\n");

  stack<int> increasingSubsequence; 
  int currentPosition = length - 1;
  for(int i = sequence.size() - 1 ; i >= 0 ; --i){
    if(currentPosition == position[i]){
      increasingSubsequence.push(sequence[i]);
      --currentPosition;
    }
  }

  while(!increasingSubsequence.empty()){
    printf("%d\n", increasingSubsequence.top());
    increasingSubsequence.pop();
  }

  return 0;
}

#UVa:821-Page Hopping

利用計算 All-Pairs Shortest Path 的演算法(例如: Floyd-Warshall Algorithm)即可得解。

由於輸入的數字不一定連續,也不一定會從 0 或 1 開始,故要把它們做個編號,編成連續且從 0 開始的數字。

參考:高中資訊科技概論教師黃建庭的教學網站 – uva-821-PageHopping-Floyd

C++(0.030)

/*******************************************************/
/* UVa 821 Page Hopping                                */
/* Author: Maplewing [at] knightzone.org               */
/* Version: 2018/05/15                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <map>
using namespace std;

const int MAX_DISTANCE = 1e+6;
const int MAX_NODE = 105;

void addToNumberMap(map<int, int> &numberMap, int x){
  if(numberMap.find(x) == numberMap.end()){
    int size = numberMap.size();
    numberMap[x] = size;
  }
}

void findAllPairsShortestPath(int path[][105], int maxSize){
  for(int k = 0 ; k < maxSize ; ++k){
    for(int i = 0 ; i < maxSize ; ++i ){
      for(int j = 0 ; j < maxSize ; ++j ){
        path[i][j] = min(path[i][j], path[i][k] + path[k][j]);
      }
    }
  }
}

int main(){
  int caseNumber = 1;

  while(true){
    map<int, int> numberMap;

    int path[MAX_NODE][MAX_NODE] = {0};
    fill_n(&path[0][0], MAX_NODE * MAX_NODE, MAX_DISTANCE);
    for(int i = 0 ; i < MAX_NODE ; ++i ) path[i][i] = 0;

    int a, b;
    while(scanf("%d%d", &a, &b) != EOF &&
          a != 0 && b != 0){
      addToNumberMap(numberMap, a);
      addToNumberMap(numberMap, b);

      int aNumber = numberMap[a];
      int bNumber = numberMap[b];
      path[aNumber][bNumber] = 1;
    }

    if(numberMap.empty()){
      break;
    }

    int maxSize = numberMap.size();
    findAllPairsShortestPath(path, maxSize);

    int sum = 0;
    for(int i = 0 ; i < maxSize ; ++i){
      for(int j = 0 ; j < maxSize ; ++j ){
        sum += path[i][j];
      }
    }

    printf("Case %d: average length between pages = %.3lf clicks\n", caseNumber++, ((double)sum) / (maxSize * (maxSize - 1)));
  }

  return 0;
}
共 36 頁1 2 3 36