題目連結
/* 題目: UVa 706 - LC-Display
* Language: C++
* Created on: 2020年2月1日
* Author: hanting
*/
#include <iostream>
#include <vector>
using namespace std;
#define Char2Num(x) (x-'0')
int LCD[10][7] = { // 7 position can display dash '-'
{1, 0, 1, 1, 1, 1, 1},
{0, 0, 0, 0, 0, 1, 1},
{1, 1, 1, 0, 1, 1, 0},
{1, 1, 1, 0, 0, 1, 1},
{0, 1, 0, 1, 0, 1, 1},
{1, 1, 1, 1, 0, 0, 1},
{1, 1, 1, 1, 1, 0, 1},
{1, 0, 0, 0, 0, 1, 1},
{1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 0, 1, 1}
};
void drawDisplay(vector<string> &display, int j, char symbol)
{
int up = 0;
int middle = display.size()/2;
int down = display.size()-1;
if(j == 0)
{
for(int i = 1; i < display[up].size()-1; i++)
display[up][i] = symbol;
}
else if(j == 1)
{
for(int i = 1; i < display[middle].size()-1; i++)
display[middle][i] = symbol;
}
else if(j == 2)
{
for(int i = 1; i < display[down].size()-1; i++)
display[down][i] = symbol;
}
else if(j == 3)
{
for(int i = 1; i < middle; i++)
display[i][0] = symbol;
}
else if(j == 4)
{
for(int i = middle+1; i < down; i++)
display[i][0] = symbol;
}
else if(j == 5)
{
for(int i = 1; i < middle; i++)
display[i][display[i].size()-1] = symbol;
}
else if(j == 6)
{
for(int i = middle+1; i < down; i++)
display[i][display[i].size()-1] = symbol;
}
}
string operator * (string &str, int mul)
{
string result = "";
while(mul--)
{
result += str;
}
return result;
}
main()
{
int s;
string n;
while(cin >> s >> n && s)
{
vector<string> output(3+s*2);
for(int i = 0; i < n.size(); i++)
{
int num = Char2Num(n[i]);
string space = " ";
vector<string> display(3+s*2, space*(s+2));
for(int j = 0; j < 3; j++)
{
if(LCD[num][j])
{
drawDisplay(display, j, '-');
}
}
for(int j = 3; j < 7; j++)
{
if(LCD[num][j])
{
drawDisplay(display, j, '|');
}
}
for(int j = 0; j < 3+s*2; j++)
{
output[j] += display[j];
if(i != n.size()-1)
output[j] += " ";
}
}
for(int i = 0; i < output.size(); i++)
{
cout << output[i] << endl;
}
cout << endl;
}
}
# /* 題目: UVa 11233 - Deli Deli
# * onlinejudge.org/external/112/11233.pdf
# * Language: Python
# * Created on: 2019年12月19日
# * Author: hanting
# */
dic = {}
L, N = map(int, input().split())
for i in range(L):
key, value = input().split()
dic[key] = value
for i in range(N):
key = input()
if key in dic:
print(dic[key])
else:
if key[-1] == 'y' and key[-2] not in ['a','e','i','o','u']:
print(key[:-1] + 'ies')
elif key[-1] == 'o' or key[-1] == 's' or key[-2:] == 'ch' or key[-2:] == 'sh' or key[-1] == 'x':
print(key + 'es')
else:
print(key + 's')
題目連結
題目說明：
給偶數個字串，要輸出一個最短字串 S 可以滿足一半的字串小於等於S，一半大於S。
例如：
D A ABC AD
要輸出AC
==================================================
我的作法：
先將全部字串排序。
接著找到最中間兩個字串出來，分別為key1, key2，
對key1字串的每個字元從[0]開始試著+1，如果 < key2就直接break;
如果key1[i]是字元Z不能+1，所以就continue;看下一個字元。
==================================================
程式碼：
題目連結
題目說明：
給定一個9*9的迷宮，給一起點和終點，起點有給起始方向，求最短路徑。
迷宮的每一個點有給固定的條件只能往哪邊走，
例如：
2 3 SFR EL *
就是指當拜訪到(2, 3)這個點若是往S(南邊)則只能往前走或往右走，
如果是往E(東邊)則只能往左走。
==============================
我的作法：
因為到每個點都需要考慮往哪個方向應該往哪邊走，
我直接將每一個點都設置NESW四個方位，重新定義點與點之間的連線，
例如下圖中藍線就是點與點可以走的路，[1]→[40]就是1可以走到40，依此類推。
起點的位置需要注意，若測資是3 1 N 3 3，從3 1位置往N走，所以起點是2 1哦！
終點的位置因為有4個方向所以有4個，4個都當終點跑一次，找到最短的才是答案。
接下來就可以快樂地用BFS，有起點，有終點，求最短路徑不是夢!
需要注意的幾個點是：
- 最後要記得補上真的起點。
- BFS判斷是否有解可以看兩點
- 起點終點同一個 => 有解
- 路徑在儲存的時候>1個 => 有解
==============================
程式碼：
題目連結 → here
題意：
函數BC(n, k, m)為共有 n 個球，現在要分成 k 份，每份不超過 m 個。
然後要用64 bit整數儲存。
==================================================
我的作法：
遞迴方式實作，
BC(7, 4, 3) = 有 7 個球，分成 4 份，每份不超過 3 個，
而 BC(7, 4, 2) = 有 7 個球，分成 4 份，每份不超過 2 個。
有沒有發現呢！
其實每份不超過 3 個的解就是等於每份不超過 2 個的解 + 4份當中有 i 份有 3 個的解。
所以 BC(7, 4, 3) = BC(7, 4, 2) + 其中1份有3個 + 其中2份有3個 + 其中3份有3個 + 4份都是3個。
- 其中1份有3個的算法 = BC(7-3, 4-1, 2) * C(4, 1)，
- 其中2份有3個的算法 = BC(7-3*2, 4-2, 2) * C(4, 2)，
- 其中3份有3個的算法 = BC(7-3*3, 4-3, 2) * C(4, 3)，
- 4份都是3個的算法 = BC(7-3*4, 4-4, 2) * C(4, 4)。
但需要注意的幾點是，
當 n <= 0 || k <= 0 || m <= 0時，BC(n, k, m) = 0;
當 n > k*m 或 n < k 時，BC(n, k, m) = 0;
當 n == k*m 或 k ==1 或 m == 1時， BC(n, k, m) = 1;
根據上面結論得到遞迴公式如下，
BC(n, k, m) = BC(n-i*m, k-i, m-1) * C(k, i);
小補充：
根據巴斯卡定理，
C(n, m) = C(n-1, m) + C(n-1, m-1)。
==================================================
程式碼：
題目連結
題意：
a和b是朋友，b和c是朋友，則a和c也是朋友。
a和b是敵人，b和c是敵人，則a和c是朋友。
a和b是朋友，b和c是敵人，則a和c也是敵人。
==================================================
我的作法：
disjoint set，
將一群選出一個代表。
將朋友做union，另外用一個陣列存敵人，只需整群的代表存即可，
在做操作都是從代表去做。
==================================================
程式碼：
/* 題目: UVa 10158 - War
* Language: C++
* Created on: 2016年12月19日
* Author: hanting
*/
#include <iostream>
#include <vector>
using namespace std;
class DisjointSet
{
vector<int> rep;
vector<int> enemy;
int id;
public:
void init(int n)
{
id = 0;
rep.assign(n, -1);
enemy.assign(n, -1);
}
int Find(int x)
{
if(x < 0) return x;
if(rep[x] < 0) return x;
else return rep[x] = Find(rep[x]);
}
void Union(int x, int y)
{
if(x < 0 || y < 0) return ;
int fx = Find(x),
fy = Find(y);
if(fx != fy)
{
if(rep[fx] <= rep[fy])
{
rep[fx] += rep[fy];
rep[fy] = fx;
}
else
{
rep[fy] += rep[fx];
rep[fx] = fy;
}
}
}
bool setFriend(int x, int y)
{
int fx = Find(x),
fy = Find(y);
if(enemy[fx] == fy) // x和y是敵人關係
{
return 0;
}
else // 分成x, y各自有不同敵人，或是x和y其中一個有敵人
{
Union(x, y);
if(enemy[fx] != -1 && enemy[fy] != -1)
{
Union(enemy[fx], enemy[fy]);
int fefx = Find(enemy[fx]);
fx = Find(x);
enemy[fx] = fefx;
enemy[fefx] = fx;
}
else if(enemy[fx] != -1)
{
int efx = enemy[fx];
fx = Find(x);
enemy[fx] = efx;
}
else if(enemy[fy] != -1)
{
int efy = enemy[fy];
fx = Find(x);
enemy[fx] = efy;
}
return 1;
}
}
bool setEnemy(int x, int y)
{
int fx = Find(x),
fy = Find(y);
if(fx == fy) // x和y是朋友
{
return 0;
}
else
{
Union(x, enemy[fy]);
Union(y, enemy[fx]);
fx = Find(x),
fy = Find(y);
enemy[fx] = fy;
enemy[fy] = fx;
return 1;
}
}
bool areFriend(int x, int y)
{
int fx = Find(x),
fy = Find(y);
return fx == fy;
}
bool areEnemy(int x, int y)
{
int fx = Find(x),
fy = Find(y);
return Find(enemy[fx]) == fy;
}
};
int main()
{
int nodeN;
cin >> nodeN;
int op, s, t;
DisjointSet dSet;
dSet.init(nodeN);
while(cin >> op >> s >> t && op+s+t)
{
switch(op)
{
case 1:
if(!dSet.setFriend(s, t))
{
cout << -1 << endl;
}
break;
case 2:
if(!dSet.setEnemy(s, t))
{
cout << -1 << endl;
}
break;
case 3:
cout << dSet.areFriend(s, t) << endl;
break;
case 4:
cout << dSet.areEnemy(s, t) << endl;
break;
}
}
return 0;
}
題目連結
我的做法：
Disjoint set 同一群選一個代表！
==================================================
程式碼：
/* 題目: UVa 10608 - Friends
* Language: C++
* Created on: 2016年12月16日
* Author: hanting
*/
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
class DisjointSet
{
vector<int> rep;
public:
void init(int n)
{
rep.assign(n, -1);
}
int Find(int x)
{
if(rep[x] < 0) return x;
else return rep[x] = Find(rep[x]);
}
void Union(int x, int y)
{
int fx = Find(x),
fy = Find(y);
if(fx != fy)
{
if(rep[fx] <= rep[fy])
{
rep[fx] += rep[fy];
rep[fy] = fx;
}
else
{
rep[fy] += rep[fx];
rep[fx] = fy;
}
}
}
int groupN(int x)
{
int fx = Find(x);
return -rep[fx];
}
};
int main()
{
int testCase;
cin >> testCase;
while(testCase--)
{
DisjointSet dSet;
int nodeN, edgeN;
cin >> nodeN >> edgeN;
dSet.init(nodeN+1);
int s, t;
for(int i = 0; i < edgeN; i++)
{
//cin >> s >> t;
scanf("%d%d", &s, &t);
dSet.Union(s, t);
}
int maxi = 0;
for(int i = 1; i <= nodeN; i++)
{
maxi = max(maxi, dSet.groupN(i));
}
cout << maxi << endl;
}
return 0;
}
