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

#UVa:11455-Behold my quadrangle

根據所給的邊長去判斷是哪種四邊形,唯一比較難的應該是quadrangle的判斷,其判斷為:\(最長的邊長 \leq 其餘三邊長之和\)。

C++(0.000)

/*******************************************************/
/* UVa 11455 Behold my quadrangle                      */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2016/08/03                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int main(){
  int numTestcase;
  while( scanf("%d", &numTestcase) != EOF ){
    for( int testcase = 0 ; testcase < numTestcase ; ++testcase ){
      int sides[4];
      for( int i = 0 ; i < 4 ; ++i ){
        scanf("%d", &sides[i]);
      }
      sort(sides, sides+4);

      if( sides[0] == sides[3] ){ // Four sides are the same.
        printf("square\n");
      }
      else if( sides[0] == sides[1] && sides[2] == sides[3] ){
        printf("rectangle\n");
      }
      else if( sides[0] + sides[1] + sides[2] >= sides[3] ){
        printf("quadrangle\n");
      }
      else{
        printf("banana\n");
      }
    }
  }

  return 0;
}

#UVa:392-Polynomial Showdown

依照題目的規則去寫判斷式決定輸出的格式長相即可。

C++(0.050)

/*******************************************************/
/* UVa 392 Polynomial Showdown                         */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2016/08/03                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
using namespace std;

int main(){
  int coefficients[9];
  while( scanf("%d", &coefficients[0]) != EOF ){
    for( int i = 1 ; i < 9 ; ++i ){
      scanf("%d", &coefficients[i]);
    }

    bool firstTerm = false;
    for( int i = 0 ; i < 9 ; ++i ){
      if( coefficients[i] != 0 ){
        int coefficientTemp = coefficients[i];
        if( firstTerm ){
          coefficientTemp = abs(coefficientTemp);
          if( coefficients[i] > 0 ){
            printf(" + ");
          }
          else{
            printf(" - ");
          }
        }

        if( 8 - i == 0 ){
          printf("%d", coefficientTemp);
        }
        else{
          if( abs( coefficientTemp ) != 1 ){
            printf("%d", coefficientTemp);
          }
          else if( coefficientTemp == -1 ){
            printf("-");
          }
          printf("x");
          if( 8 - i > 1 ){
            printf("^%d", 8-i);
          }
        }

        firstTerm = true;
      }
    }

    if( !firstTerm ){
      printf("0");
    }
    printf("\n");
  }

  return 0;
}

#UVa:10487-Closest Sums

將數字兩兩相加看看哪對離所求之數字最近即是解。

P.S. 其實最後搜尋部分可用二分搜尋加速,不過這題的數量小可以不用。

C++(0.010)

/*******************************************************/
/* UVa 10487 Closest Sums                              */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2016/08/02                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;

int main(){
  int n;
  int testcase = 1;
  while( scanf("%d", &n) != EOF && n != 0 ){
    int num[1005];
    for( int i = 0 ; i < n ; ++i ){
      scanf("%d", &num[i]);
    }
    sort(num, num+n);

    int m;
    scanf("%d", &m);

    printf("Case %d:\n", testcase++);
    int query;
    for( int i = 0 ; i < m ; ++i ){
      scanf("%d", &query);

      int closetSum = num[0] + num[1];
      for( int j = 0 ; j < n ; ++j ){
        for( int k = j+1 ; k < n ; ++k ){
          int sum = num[j] + num[k];
          if( abs( sum - query ) < abs( closetSum - query ) ){
            closetSum = sum;
          }
          else if( sum - query > abs(closetSum - query) ){
            break;
          }
        }
      }

      printf("Closest sum to %d is %d.\n", query, closetSum);
    }


  }

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