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

#UVa:10583-Ubiquitous Religions

先讓大家每個人各自是不同的 Group ,再透過兩人兩人相同的關係讓他們變成同樣的 Group ,再計算總共有幾個不同的 Group 即可得解。

作法參考:Programming學習筆記-UVa 10583 Ubiquitous Religions

C++(0.060)

/*******************************************************/
/* UVa 10583 Ubiquitous Religions                      */
/* Author: Maplewing [at] knightzone.org               */
/* Version: 2018/05/14                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;

int findRootGroup(vector<int> &groups, int x){
  if(x == groups[x]){
    return x;
  }

  return groups[x] = findRootGroup(groups, groups[x]);
}

bool unionGroups(vector<int> &groups, int x, int y){
  int rootX = findRootGroup(groups, x);
  int rootY = findRootGroup(groups, y);

  if(rootX == rootY){
    return false;
  }

  groups[rootX] = groups[rootY];
  return true;
}

int main(){
  int caseNumber = 1;
  int n, m;
  while(scanf("%d%d", &n, &m) != EOF &&
      n != 0 && m != 0){
    vector<int> groups(n+1, 0);
    for(int i = 1 ; i <= n ; ++i){
      groups[i] = i;
    }

    int groupCount = n;
    for(int religionCase = 0 ; religionCase < m ; ++religionCase){
      int i, j;
      scanf("%d%d", &i, &j);

      if(unionGroups(groups, i, j)) --groupCount;
    }

     printf("Case %d: %d\n", caseNumber++, groupCount);
  }

  return 0;
}

#UVa:11849-CD

比較兩個已排序的序列其共同的部分有多少即可得解。

C++(0.470)

/*******************************************************/
/* UVa 11849 CD                                        */
/* Author: Maplewing [at] knightzone.org               */
/* Version: 2018/05/14                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

int main(){
  int N, M;
  while (scanf("%d%d", &N, &M) != EOF &&
       N != 0 && M != 0){
    vector<int> nCDs(N, 0);
    vector<int> mCDs(M, 0);

    for (int i = 0 ; i < N ; ++i ){
      scanf("%d", &nCDs[i]);
    }

    for (int i = 0 ; i < M ; ++i ){
      scanf("%d", &mCDs[i]);
    }

    int bothOwnCount = 0;
    for (int i = 0, j = 0 ; i < N && j < M ; ){
      if(nCDs[i] == mCDs[j]){
        ++bothOwnCount;
        ++i;
        ++j;
      }
      else if(nCDs[i] > mCDs[j]) ++j;
      else ++i;
    }

    printf("%d\n", bothOwnCount);
  }
  return 0;
}

#UVa:820-Internet Bandwidth

Maximum Flow 的經典題型。可以使用 Maximum Flow 的演算法(像是 Ford-Fulkerson Algorithm 或是 Edmonds-Karp Algorithm)解決。

P.S. 題目中,給予 a 到 b 的 bandwidth 的部分 a b bandwidth 有可能會給予好幾組相同的 a, b ,故要全部加總起來去做運算。

參考:Programming學習筆記 – UVa 820 Network Bandwidth

C++(0.010)

/*******************************************************/
/* UVa 820 Internet Bandwidth                          */
/* Author: Maplewing [at] knightzone.org               */
/* Version: 2018/05/14                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <queue>
using namespace std;

const int FLOW_MAX_VALUE = 10000000;

int getMaxFlow(const vector<vector<int>> &capacity, int s, int t, int n){
  int result = 0;
  vector<vector<int>> flow(n+1, vector<int>(n+1, 0));
   while(true){
     vector<int> bottleneck(n+1, 0);
     bottleneck[s] = FLOW_MAX_VALUE;
     queue<int> bfsQueue;
     bfsQueue.push(s);

     vector<int> previousNode(n+1, 0);

     while(!bfsQueue.empty() && bottleneck[t] == 0){
       int current = bfsQueue.front();
       bfsQueue.pop();
       for(int next = 1; next <= n ; ++next){
         if(bottleneck[next] == 0 && capacity[current][next] > flow[current][next]){
           bfsQueue.push(next);
           previousNode[next] = current;
           bottleneck[next] = min(bottleneck[current], capacity[current][next] - flow[current][next]);
         }
       }
     }

    if(bottleneck[t] == 0) break;   
     for(int current = t; current != s; current = previousNode[current]){
       flow[previousNode[current]][current] += bottleneck[t];
       flow[current][previousNode[current]] -= bottleneck[t];
     }

     result += bottleneck[t];
   }

   return result;
}

int main(){
  int testcase = 1;
  int n;
  while(scanf("%d", &n) != EOF && n != 0){
    vector<vector<int>> capacity(n+1, vector<int>(n+1, 0));

    int s, t, c;
    scanf("%d%d%d", &s, &t, &c);

    int a, b, bandwidth;
    for(int i = 0 ; i < c ; ++i){
      scanf("%d%d%d", &a, &b, &bandwidth);
      capacity[a][b] += bandwidth;
      capacity[b][a] += bandwidth;
    }

    printf("Network %d\n", testcase++);
    printf("The bandwidth is %d.\n\n", getMaxFlow(capacity, s, t, n));
  }

  return 0;
}

#UVa:10613-Mushroom Misery

將方格以 y 軸整數窮舉,對於每一個 y 找出每個圓在此 y 上所佔的 x 範圍為多少,得到所有 x 範圍後合併出來並計數即可得到該 y 行方格被佔掉幾格,窮舉完後再加總就可以得到全部所佔的方格數。

至於如何算出該圓對於 y 行方格到底佔了 x 多少,可以利用圓心離 y 行方格最近的距離半徑去求得與 x 平行軸所圍成的三角形的 x 部分的長度(如圖)。

算法圖示

C++(0.060)

/*******************************************************/
/* UVa 10613 Mushroom Misery                           */
/* Author: Maplewing [at] knightzone.org               */
/* Version: 2017/12/29                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

struct Circle{
  double x;
  double y;
  double r;
};

struct Range{
  int min;
  int max;
};

bool cmp(Range a, Range b){
  return a.min < b.min || (a.min == b.min && a.max < b.max);
}

Range getCircleRangeX(Circle c, int y, int size){
  Range r;
  if( y + 1 < c.y && c.y - c.r <= y + 1 ){
    double deltaY = c.y - (y+1);
    double deltaDistance = sqrt( c.r * c.r - deltaY * deltaY );

    r.min = max(0, (int)(c.x - deltaDistance));
    r.max = min(size-1, (int)(c.x + deltaDistance));
    return r;
  }
  else if( y > c.y && c.y + c.r >= y ){
    double deltaY = y - c.y;
    double deltaDistance = sqrt( c.r * c.r - deltaY * deltaY );

    r.min = max(0, (int)(c.x - deltaDistance));
    r.max = min(size-1, (int)(c.x + deltaDistance));
    return r;
  }
  else if( c.y >= y && c.y <= y+1 ){
    r.min = max(0, (int)(c.x - c.r));
    r.max = min(size-1, (int)(c.x + c.r));
    return r;
  }
  else{
    r.min = -1;
    r.max = -1;
    return r;
  }
}

int main(){
  int N;
  while( scanf("%d", &N) != EOF ){
    for( int testCase = 0 ; testCase < N ; ++testCase ){
      int size, n;
      scanf("%d%d", &size, &n);

      vector<Circle> circles;
      for( int i = 0 ; i < n ; ++i ){
        Circle c;
        scanf("%lf%lf%lf", &(c.x), &(c.y), &(c.r));
        circles.push_back(c);
      }

      int totalAffectedSquares = 0;
      for( int i = 0 ; i < size ; ++i ){
        vector<Range> ranges;
        for( int j = 0 ; j < n ; ++j ){
          Range range = getCircleRangeX(circles[j], i, size);
          if( range.min != -1 && range.max != -1 ){
            ranges.push_back(range);
          }
        }

        if( ranges.size() > 0 ){
          sort(ranges.begin(), ranges.end(), cmp);
          Range range = ranges[0];
          for( int j = 1 ; j < ranges.size() ; ++j ){
            if( range.max >= ranges[j].min ){
              range.max = max( range.max, ranges[j].max );
            }
            else{
              totalAffectedSquares += range.max - range.min + 1;
              range = ranges[j];
            }
          }
          totalAffectedSquares += range.max - range.min + 1;
        }
      }

      printf("%d\n", totalAffectedSquares);
    }
  }

  return 0;
}

#UVa:11988-Broken Keyboard (a.k.a. Beiju Text)

利用 List 模擬實際行為即可得解。

C++(0.170)

/*******************************************************/
/* UVa 11988 Broken Keyboard (a.k.a. Beiju Text)       */
/* Author: Maplewing [at] knightzone.org               */
/* Version: 2017/12/21                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <list>
using namespace std;

int main(){
  string input;
  while(getline(cin, input)){
    list<char> text;
    list<char>::iterator textIterator;
    textIterator = text.begin();

    for( int i = 0 ; i < input.length() ; ++i ){
      switch(input[i]){
        case '[':
          textIterator = text.begin();
          break;
        case ']':
          textIterator = text.end();
          break;
        default:
          text.insert(textIterator, input[i]);
          break;
      }  
    }

    for(textIterator = text.begin() ; textIterator != text.end() ; ++textIterator){
      printf("%c", *textIterator);
    }
    printf("\n");
  }

  return 0;
}

#UVa:725-Division

羅列所有可能的分母出來,與N相乘找到分子,再檢查分母和分子是否剛好用完0~9的數字,即可得解。

C++(0.040)

/*******************************************************/
/* UVa 725 Division                                    */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2016/10/19                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

bool iterateAllPossibleAnswer(int N, bool digitsUsed[], int digit, int denominator){
  if( digit == 5 ){
    int numerator = denominator * N;
    if( numerator >= 100000 ) return false;

    bool checkAllDigitUsed[10];
    memcpy( checkAllDigitUsed, digitsUsed, sizeof(checkAllDigitUsed) );

    for( int checkDigit = 10; checkDigit <= 100000 ; checkDigit *= 10 ){
      int numeratorDigit = numerator % checkDigit / (checkDigit / 10);
      if( checkAllDigitUsed[numeratorDigit] ) return false;
      checkAllDigitUsed[numeratorDigit] = true;
    }

    printf("%05d / %05d = %d\n", numerator, denominator, N);

    return true;
  }

  bool haveAnswer = false;
  for( int i = 0 ; i < 10 ; ++i ){
    if( digitsUsed[i] ) continue;

    digitsUsed[i] = true;
    denominator = denominator * 10 + i;
    haveAnswer |= iterateAllPossibleAnswer(N, digitsUsed, digit + 1, denominator);
    denominator /= 10;
    digitsUsed[i] = false;
  }

  return haveAnswer;
}


int main(){
  int N;
  bool separationLine = false;
  while( scanf("%d", &N) != EOF && N != 0 ){
    if( separationLine ){
      printf("\n");
    }
    separationLine = true;

    bool digitsUsed[10] = {false};
    bool haveAnswer = iterateAllPossibleAnswer(N, digitsUsed, 0, 0);

    if( !haveAnswer ){
      printf("There are no solutions for %d.\n", N );
    }
  }


  return 0;
}

#UVa:10986-Sending email

求一點到另外一點的最短距離,用SPFA即可得解。

P.S. 記得紀錄每個邊可以對點去分群,這樣在更新最短路徑的速度會比較快,如果沒做很容易TLE。

C++(0.100)

/*******************************************************/
/* UVa 10986 Sending email                             */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2016/10/16                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

const int UNREACHABLE = -1;

struct Edge{
  int from;
  int to;
  int w;

  Edge(){}

  Edge(int _from, int _to, int _w){
    from = _from;
    to = _to;
    w = _w;
  }
};

int main(){
  int N;
  while( scanf("%d", &N) != EOF ){
    int n, m, S, T;
    for( int testcase = 1 ; testcase <= N ; ++testcase ){
      scanf("%d%d%d%d", &n, &m, &S, &T);

      vector<int> shortestPath(n, UNREACHABLE);
      shortestPath[S] = 0;
      vector< vector<Edge> > nodeEdges = vector< vector<Edge> >(n, vector<Edge>());

      int a, b, w;
      for( int i = 0 ; i < m ; ++i ){
        scanf("%d%d%d", &a, &b, &w);
        nodeEdges[a].push_back( Edge(a, b, w) );
        nodeEdges[b].push_back( Edge(b, a, w) );
      }


      queue<int> next;
      vector<bool> inQueue(n, false);
      next.push(S);

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

        for( int i = 0 ; i < nodeEdges[current].size() ; ++i ){
          int toNode = nodeEdges[current][i].to;
          if( shortestPath[toNode] == UNREACHABLE || 
              shortestPath[current] + nodeEdges[current][i].w < shortestPath[toNode] ){
            shortestPath[toNode] = shortestPath[current] + nodeEdges[current][i].w;
            if( !inQueue[toNode] ){
              next.push(toNode);
              inQueue[toNode] = true;
            }
          }
        }
      }

      printf("Case #%d: ", testcase);
      if( shortestPath[T] == UNREACHABLE ){
        printf("unreachable\n");
      }
      else{
        printf("%d\n", shortestPath[T]);
      }
    }
  }

  return 0;
}
共 37 頁 1 2 3 4 37