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

#HTML(HTML5):具有摘要與詳細兩種資訊的折疊呈現

在 HTML5 中,對於某段內容具有摘要資訊與詳細資訊兩種資訊需要呈現,並且希望能夠先折疊起來只顯示摘要資訊,等使用者按下去再開啟詳細資訊的這種狀況,我們可以使用 <details><summary> 這兩個標籤來呈現,具體用法是:

<details>
  <summary>{摘要資訊}</summary>
  {詳細資訊}
</details>

舉個例子,例如我現在想要介紹雷亞即將在 2018 年 1 月上市的 Cytus2 ,我可能就會這麼做:

<details>
  <summary>音樂遊戲 Cytus2</summary>
  <p>Cytus2 是一款由雷亞遊戲即將於 2018 年 1 月出品的遊戲,根據目前釋出的 Trailer 影片即將會有五隻角色在劇情之中。</p>
  <p>相關連結:
     <ul>
        <li><a href="https://www.youtube.com/watch?v=IAS52XC2pto" target="_blank">Trailer 連結</a></li>
        <li><a href="https://www.rayark.com/g/cytus2/" target="_blank">官網連結</a></li>
     </ul>
  </p>
</details>

呈現效果大概會是這樣,僅出現摘要內容,並且前面會出現折疊符號:
details1

按下去之後可以展開詳細的資訊:
details2

如果你希望一開始就要是展開的樣貌的話,就在 <details> 標籤裡面加上 open 屬性:

  <details open> ...... 內容省略 ...... </details>

P.S. 利用教學來工商我目前工作的專案也是萬萬沒想到wwwwwwwwww

參考資料

  1. DevDocs:http://devdocs.io/html/
  2. w3schools.com > HTML <details> Tag:https://www.w3schools.com/tags/tag_details.asp
  3. w3schools.com > HTML <summary> Tag:https://www.w3schools.com/tags/tag_summary.asp

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

#HTML:文章中的表意標籤

在 HTML 當中,有很多標籤是用來表達其內容代表的意義是什麼,例如當遇到一段文字描述的是聯絡方式的時候,我們可以利用<address>標籤將這段內容標起來,代表這段內容是個地址。

這類標籤非常多,原本的用途應該是讓瀏覽器可以根據不同種類的內容可以做相對應的事情,例如上述利用<address>標籤標起來後,可能瀏覽器就可以提供你將這段內容給備註成聯絡方式之類的。但由於目前瀏覽器並沒有特別為這類標籤提供特殊的功能,故其實也沒有很多人真的活用這類標籤,再加上其內容繁多,真的要在寫網頁的時候想到有哪個可以用也是蠻困難的一件事情。

雖然如此,這裡還是整理一下有哪些標籤,以便真的在做網站的時候可以稍微想到可以用哪些標籤,不過內容可能還會新增或有遺漏,有看到我會慢慢再更新。另外,大部分的標籤沒有預設樣式,相關樣式的設計可以另外撰寫 CSS 來做。

標籤 含義 用法 簡易範例
<abbr> 縮寫 將縮寫部分包起來,可利用 title 屬性撰寫全稱。 <abbr title="World Wide Web">WWW</abbr>
<address> 聯絡方式 將聯絡方式包起來。 <address>可寄信至台北市新生北路X段X號,或是寄信至<a href="mailto:xxx@xxx.xxx">xxx@xxx.xxx</a></address>
<b> 關鍵字或專有名詞等之類文字內容 可將關鍵字或專有名詞包起來去凸顯出來,預設樣式為粗體。 <b>索尼克力量</b>是個不錯的遊戲。
<bdi> 閱讀方向未知的文字 將閱讀方向不知道的文字包起來。
<bdo> 需覆蓋目前閱讀方向的文字 將閱讀方向不一樣的文字直接包起來,用 dir 屬性可以強制覆蓋其閱讀相反是左到右還是右到左。
<blockquote> 多行引用內容 將引用到的別人的多行內容包起來,另外可用 cite 屬性來描述從哪裡引用過來的。(單行內容利用 <q>)
<cite> 其他相關內容的資訊 將與本文章相關內容的標題或連結等等資訊包起來。
<code> 程式碼 可將程式碼包起來。
<data> 資料名稱 將資料名稱利用此標籤包起來,再利用 value 屬性來標示此資料的值為何。
<del> 文章編輯內容上標明已被刪除的資料 將文章中已被刪除的資料標出來,預設樣式會有刪除線。
<details> & <summary> 具有詳細資料的內容與摘要 詳細用法:#HTML(HTML5):具有摘要與詳細兩種資訊的折疊呈現
<dfn> 被詮釋的資料名稱 將被解釋的資料名稱包起來,其被解釋的內容會與其同在同一個文章結構標籤內或解釋清單中,並且在其附近。 <p><dfn>Sonic the Hedgehog</dfn>是 SEGA 著名的動作跑酷遊戲,主角為索尼克,設定上是一隻刺蝟。</p>
<em> 想要強調的文字內容 將文句中特別想強調的地方標示出來的標籤,預設樣式為斜體。 <em>努力不懈的精神</em>正是那個人成功的關鍵。
<ins> 文章編輯內容上標明加入的文字內容 將被加入的文字內容標示出來用的標籤。
<kbd> 鍵盤上的按鍵名稱 將文章中出現的鍵盤上的按鍵標示出來,字體會變成 monospace 的字體。 複製的快捷鍵是 <kbd>Ctrl</kbd> + <kbd>C</kbd>
<mark> 特別標明的文字內容,通常代表具相關性 將相關內容標示出來,例如搜尋引擎搜完會在搜尋到的文章中將你打的關鍵字利用此標籤標註出來。
<meter> 已知範圍內的數量值 將已知範圍內的數量值標示出來,利用 minmax 屬性表明範圍,再利用 value 屬性表示大小,預設會用長條來代替被包住的內容。
<progress> 進度值 將進度標明出來,最小固定為 0 ,最大值可利用 max 屬性表明,進度值可利用 value 屬性,預設會用進度條來代替被包住的內容。 (像是 <meter> 但含義不同。) 目前進度:<progress max="100" value="85">85%</progress>
<q> 短引用內容 將引用到的別人的單行內容包起來,另外可用 cite 屬性來描述從哪裡引用過來的。(多行內容利用 <blockquote>)
<s> 不再正確的內容 將不再正確的內容標明出來,例如東西售完了就將項目利用 <s> 標起來,預設樣式為刪除線。 <s>學院制服</s> 已售完!
<samp> 電腦程式的範例輸出 將電腦程式跑出來的範例輸出標注出來,字體會變成 monospace 的字體。
<small> 小註解或是印刷品的版權聲明或是法律條文 將小註解或是印刷品的版權聲明或是法律條文表明出來。
<strong> 重要性高的文章內容 將非常重要的內容標示出來,預設樣式為粗體。 明天開會,<strong>千萬不可以遲到!</strong>
<sub> 下標文字 表示文字內容會位於下標位置。 水的化學式是 H<sub>2</sub>O
<sup> 上標文字 表示文字內容會位於上標位置。 3 的 2 次方是 3<sup>2</sup>
<time> 時間或是日期內容 將時間或是日期內容標示出來,可用 datetime 放入電腦可解讀的時間格式。 <time datetime="2017-12-23T01:42">今天</time>我撰寫了這篇文章。
<u> 文章上會用底線裝飾的內容 將實際文章上會用底線裝飾的內容標示出來,例如中文的人名或是拼錯的文字。 <u>曹又霖</u>就是<u>灆洢</u>
<var> 數學上的代數或是程式上的變數 可用來標示數學上的代數或是程式上的變數。 <var>a</var> = <var>b</var> + 20

參考資料

  1. DevDocs:http://devdocs.io/html/
  2. How to use the Meter & Progress Elements – Treehouse Blog:http://blog.teamtreehouse.com/use-meter-progress-elements

#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;
}
共 40 頁 1 2 3 4 40