題目連結 → 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;
}
題目連結
我的做法：
0到k最短路徑問題，priority_queue實做Dijkstra演算法。
==================================================
程式碼：
/* 題目: UVa 10801 - Lift Hopping
* Language: C++
* Created on: 2016年12月14日
* Author: hanting
*/
#include <iostream>
#include <sstream>
#include <map>
#include <queue>
using namespace std;
struct Node
{
int num, dis;
Node(int _num = 0, int _dis = 0)
{
num = _num;
dis = _dis;
}
bool operator() (const Node &node1, const Node &node2)const
{
return node1.dis < node2.dis;
}
};
class Graph
{
private:
vector<vector<Node> > adj;
public:
int Dijkstra(int s, int t)
{
vector<int> dis(adj.size());
for(int i = 0; i < adj.size(); i++)
{
dis[i] = 0x3fffffff;
}
dis[s] = 0;
priority_queue<Node, vector<Node>, Node > pque;
pque.push(Node(s, 0));
while(pque.size())
{
int cur = pque.top().num;
pque.pop();
for(int i = 0; i < adj[cur].size(); i++)
{
Node next = adj[cur][i];
int u = cur,
v = next.num,
w = next.dis;
if(dis[v] > dis[u] + w)
{
dis[v] = dis[u] + w;
pque.push(Node(v, dis[v]));
}
}
}
return dis[t];
}
void initNodeN(int nodeN)
{
adj.assign(nodeN, vector<Node>());
}
void link(int s, int t, int w = 0)
{
if(s % 100 == 0) s = 0;
adj[s].push_back(Node(t, w));2
adj[t].push_back(Node(s, w));
}
};
int main()
{
int elevatorN, k;
while(cin >> elevatorN >> k)
{
vector<int> weight(elevatorN);
for(int i = 0; i < elevatorN; i++)
{
cin >> weight[i];
}
Graph graph;
graph.initNodeN(100*elevatorN);
cin.get();
map<int, int> Map;
for(int i = 0; i < elevatorN; i++)
{
string str;
getline(cin ,str);
stringstream sin(str);
int s, t;
sin >> s;
Map[100*i+s] = 1;
for(int j = 100*i+s-100; j >= 0; j -= 100)
{
if(Map[j])
{
graph.link(100*i+s, j, 60);
}
}
while(sin >> t)
{
graph.link(100*i+s, 100*i+t, (t-s)*weight[i]);
Map[100*i+t] = 1;
for(int j = 100*i+t-100; j >= 0; j -= 100)
{
if(Map[j])
{
graph.link(100*i+t, j, 60);
}
}
s = t;
}
}
int mini = graph.Dijkstra(0, k);
for(int i = 1; i < elevatorN; i++)
{
mini = min(mini, graph.Dijkstra(0, k+100*i));
}
if(mini == 0x3fffffff) cout << "IMPOSSIBLE" << endl;
else cout << mini << endl;
}
return 0;
}
