UVa 389
http://domen111.github.io/UVa-Easy-Viewer/?389
給一個字串 $S$ 以及兩個數字 $n, m$ ，表示 $S$ 是 $n$ 進位底下的表示方式，求轉成 $m$ 進位制的樣子。
想法
- 先將 $S$ 想辦法換成我們熟悉的數字表示方式十進位
- 統一從十進位轉換為其他進位制
Zerojudge a020
發表於
分類於
Zerojudge
ZJ a020
題目
https://zerojudge.tw/ShowProblem?problemid=a020
給一個身分證字號，求是否符合身份證字號的規則，其規則如下:
- 先依照表格，將英文字母對應到數字
1
2
3
4
5
6
7
8
9A=10 台北市 J=18 新竹縣 S=26 高雄縣
B=11 台中市 K=19 苗栗縣 T=27 屏東縣
C=12 基隆市 L=20 台中縣 U=28 花蓮縣
D=13 台南市 M=21 南投縣 V=29 台東縣
E=14 高雄市 N=22 彰化縣 W=32 金門縣
F=15 台北縣 O=35 新竹市 X=30 澎湖縣
G=16 宜蘭縣 P=23 雲林縣 Y=31 陽明山
H=17 桃園縣 Q=24 嘉義縣 Z=33 連江縣
I=34 嘉義市 R=25 台南縣 - 將第 1 步得到的數字的十位數以及個位數乘上 9 的值記錄下來為 $n$
- 數字從最左邊到最右邊依序乘上 8, 7, 6, … ,2, 1 ，並相加記錄下來為 $m$
- 若 $n+m$ 是 10 的倍數，表示正確，否則錯誤
Zerojudge b266
發表於
分類於
Zerojudge
Zerojudge b840
發表於
分類於
Zerojudge
UVa10583
發表於
分類於
UVa
UVa 10583
題目
http://domen111.github.io/UVa-Easy-Viewer/?10583
有 $n$ 個人，每個人至多有 $1$ 個宗教信仰，現在給你 $m$ 對數字 $i, j$ ，表示 $i, j$ 擁有相同的宗教信仰。求在這 $n$ 個人當中最多有多少不同的宗教信仰?
想法
這裡可以想到並查集的概念
我們可以將這 $n$ 個人分成幾個集合，而每個集合都有一個老大，並且該集合內的所有人都會指向老大
這樣一來，當我們要判定一個人所在的群組是否已經被算過的話，就可以透過遞迴的方式找到群組的老大，看看老大有沒有被算過即可，也就是將集合以老大表示。
TOJ 474
TOJ 474
題敘
https://toj.tfcis.org/oj/pro/474/
給定一個長方形的長與寬，以及一個整數 $k$
求在長方形中能以連續 $k$ 個格子連線的數量有多少
想法
依序找出橫向、直向、斜向的答案相加即可，數學題
TIOJ 2054
TIOJ 2054
題敘
https://tioj.ck.tp.edu.tw/problems/2054
二維 slide window 問題
給定一個長方形的寬與高，以及一個平面座標上的多個點座標
問該長方形最多能涵蓋多少點座標
想法
如果是一維的，也就是長方形的高是無限大的情況
我們只需要維護左界與右界，每次看看下一個點加入後右界與左界的距離有沒有超過寬
只需要 $O(N)$ 就可以知道最多有多少點了
TOJ 475
TOJ 475
題敘
https://toj.tfcis.org/oj/pro/475/
LCA 模板題
給一個樹，求多點之間的最低共同祖先
想法
每兩個點做一次 LCA 後，將答案再與下一個點做 LCA ，一直到每個查詢都遍歷過
POJ 1330
POJ 1330
題敘
https://vjudge.net/problem/POJ-1330
LCA 模板題
給一棵樹，有 $T$ 筆詢問，求點 $u$ 與 $v$ 的最低共同祖先
想法
使用倍增法爬行
先將兩點維持到相同的深度
如果兩點相同，則這個點就是答案
否則爬行直到兩者的祖先是相同的
TIOJ 1080
TIOJ 1080
題敘
https://tioj.ck.tp.edu.tw/problems/1080
逆敘數對模板題
對於一個數列 $S$ 若 $S$ 的第 $i$ 項 $s_i$ 與第 $j$ 項 $s_j$ 符合 $s_i>s_j$ ，並且 $i<j$ ，那麼我們說 $(i,j)$ 是一個逆序數對。請問給定 $S$ ，總共有多少個逆序數對
想法
對於一個元素來說，他的逆敘數對數量會跟在這個元素之後比該元素還小的數量相同
也就是說，我們的目的是要每個元素找到符合這樣條件的數量總和