/* 題目: UVa 297 - Quadtrees
* Language: C++
* Created on: 2016年3月26日
* Author: hanting
*/
#include <iostream>
using namespace std;
int stri = 1;
void build(bool *table, string str, int index)
{
if(stri < str.size())
{
for(int i = 1; i <= 4; i++)
{
if(str[stri] == 'p')
{
stri++;
table[index+i] = 0;
build(table, str, 4*(index+i));
}
else if(str[stri] == 'e')
{
stri++;
table[index+i] = 0;
}
else // if(str[stri] == 'f')
{
stri++;
table[index+i] = 1;
}
}
}
}
int value(bool *table, int index)
{
if(index < 2048)
{
if(table[index])
{
if(index == 0) return 1024;
else if(index <= 4) return 256;
else if(index <= 20) return 64;
else if(index <= 84) return 16;
else if(index <= 340) return 4;
else return 1;
}
else
{
int subIndex = index*4;
int sum = 0;
for(int i = 1; i <= 4; i++)
{
sum += value(table, subIndex+i);
}
return sum;
}
}
return 0;
}
int main()
{
int testCase = 0;
cin >> testCase;
while(testCase--)
{
stri = 1;
bool table1[2048] = {0};
bool table2[2048] = {0};
string str1, str2;
cin >> str1 >> str2;
if(str1[0] == 'p')
build(table1, str1, 0);
else
table1[0] = str1[0] == 'f';
stri = 1;
if(str2[0] == 'p')
build(table2, str2, 0);
else
table2[0] = str2[0] == 'f';
for(int i = 0; i < 2048; i++)
{
table1[i] = table1[i] or table2[i];
}
cout << "There are " << value(table1, 0) << " black pixels." << endl;
}
return 0;
}
2016年3月26日 星期六
[UVA] 297 - Quadtrees
2015年12月21日 星期一
[UVA] 318 - Domino Effect
題目連結
題意：
給你n個點和m條邊，點和點之間有骨牌，
會給你兩個點之間的骨牌個數，
問從點1開始推，一直到最後一個骨牌倒下會經過多少個骨牌，
最後一個骨牌是在哪個點，或在哪兩個點之間。
--------------------------------------------------
我的作法：
2015年12月15日 星期二
[UVA] 378 - Intersecting Lines
題目連結
平行(NONE)
重疊(LINE)
還是交於一點(POINT)
若是焦於一點則輸出該點並輸出到小數第二位。
--------------------------------------------------
題意：
由兩點組成一個線段，
現在給你兩條線段，要你求出這兩條線段是平行(NONE)
重疊(LINE)
還是交於一點(POINT)
若是焦於一點則輸出該點並輸出到小數第二位。
--------------------------------------------------
我的作法：
2015年12月10日 星期四
[UVA] 10506 - Ouroboros
題目連結
M是表示一組幾個數字，
N是代表N進位，最大到10進位
現在要利用N進位的數字去做排列組合，可以排出N的M次方種組合，
例如M = 2，N = 3，可以排出3的2次方 = 9種，
也就是
(00)
(01)
(02)
(10)
(11)
(12)
(20)
(21)
(22)
今天有一字串可以在這字串中找到所有這些組合的數字，
最後一組要連接第一組。
以上面M = 2，N = 3為例，=> 字串可以為 001021122
001021122
001021122
001021122
001021122
001021122
001021122
001021122
001021122
001021122
9組數字都可以在字串中找到，
題目要你輸出這個字串(可能很多答案，隨便一個都可以)
--------------------------------------------------
題意：
給你M, N兩個數字，M是表示一組幾個數字，
N是代表N進位，最大到10進位
現在要利用N進位的數字去做排列組合，可以排出N的M次方種組合，
例如M = 2，N = 3，可以排出3的2次方 = 9種，
也就是
(00)
(01)
(02)
(10)
(11)
(12)
(20)
(21)
(22)
今天有一字串可以在這字串中找到所有這些組合的數字，
最後一組要連接第一組。
以上面M = 2，N = 3為例，=> 字串可以為 001021122
001021122
001021122
001021122
001021122
001021122
001021122
001021122
001021122
001021122
9組數字都可以在字串中找到，
題目要你輸出這個字串(可能很多答案，隨便一個都可以)
--------------------------------------------------
我的作法：
2015年12月4日 星期五
[UVA] 599 - The Forrest for the Trees
題目連結
題意：
給你一堆邊，問你有幾棵tree, 幾個acorn
tree就是有點有邊的連通圖，
acorn就是單單一個點，沒有任何邊。
tree就是有點有邊的連通圖，
acorn就是單單一個點，沒有任何邊。
--------------------------------------------------
我的作法：
[UVA] 10608 - Friends
/* 題目: UVa 10608 - Friends
*
Language: C++
*
Created on: 2015年12月4日
*
Author: hanting
*/
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int> >
node;
vector<bool> visit;
void ConnectNode(int a, int b)
{
node[a].push_back(b);
node[b].push_back(a);
}
int DFS(int cur)
{
visit[cur] = 1;
int cnt = 1;
for(int i = 0; i < node[cur].size(); i++)
{
int tmp =
node[cur][i];
if(!visit[tmp])
{
cnt += DFS(tmp);
}
}
return cnt;
}
int main()
{
int testCase = 0;
cin >> testCase;
while(testCase--)
{
int manN, pairN;
cin >> manN >> pairN;
visit.assign(manN+1, 0);
node.assign(manN+1, vector<int>());
for(int i = 0; i < pairN; i++)
{
int a, b;
cin >> a >> b;
ConnectNode(a, b);
}
int maxi = 0;
for(int i = 1; i <= manN; i++)
{
if(!visit[i])
{
int groupNum = DFS(i);
maxi = max(maxi, groupNum);
}
}
cout << maxi << endl;
}
return 0;
}
2015年12月2日 星期三
[UVA] 10315 - Poker Hands
/* 題目: UVa 10315 - Poker Hands
*
Language: C++
*
Created on: 2015年12月2日
*
Author: hanting
*/
// 2 3 4 5 6 > 1 2 3 4 5
#include <iostream>
#include <vector>
#include <algorithm> // sort
using namespace std;
int trans(char c)
{
if(isdigit(c)) return c - 48;
else
{
if(c == 'T') return 10;
else if(c == 'J') return 11;
else if(c == 'Q') return 12;
else if(c == 'K') return 13;
else if(c == 'A') return 14; // * A 不是1
}
}
bool input(vector<pair<int, int> > &black, vector<pair<int, int> > &white)
{
black.clear();
white.clear();
string str;
bool read = false;
for (int i = 0; i < 5; i++)
{
read = (cin >> str);
int num = trans(str[0]);
black.push_back(pair<int, int>(num, str[1]));
}
for (int i = 0; i < 5; i++)
{
cin
>> str;
int num = trans(str[0]);
white.push_back(pair<int, int>(num, str[1]));
}
return read;
}
int StraightFlush(vector<pair<int, int> > &vec)
{
int cnt = 0;
int maxi = 0;
for(int i = 1; i < vec.size(); i++)
{
if(vec[i].first == vec[i-1].first + 1 and vec[i].second == vec[i-1].second) cnt++, maxi = vec[i].first;
}
if (cnt == 4) return maxi;
return 0;
}
int FourOfAKind(vector<pair<int, int> > &vec)
{
int cnt = 0;
for(int i = 1; i < vec.size() and cnt != 3; i++)
{
if(vec[i].first == vec[i-1].first) cnt++;
else cnt = 0;
}
if (cnt == 3) return vec[3].first;
return 0;
}
int FullHouse(vector<pair<int, int> > &vec)
{
int cnt[15] = {0};
for(int i = 0; i < vec.size(); i++)
{
int tmp = vec[i].first;
cnt[tmp]++;
}
int three = -1, two = -1;
for(int i = 2; i < 15; i++)
{
if(cnt[i] == 3)
{
three = i;
}
else if(cnt[i] == 2)
{
two = i;
}
}
if(three != -1 and two != -1)
{
return three;
}
return 0;
}
int Flush(vector<pair<int, int> > &vec)
{
int cnt = 0;
int maxi = 0;
int flag[15] = {0};
for(int i = 0; i < vec.size(); i++)
{
int tmp = vec[i].first;
flag[tmp]++;
}
for(int i = 1; i < vec.size(); i++)
{
if(vec[i].second == vec[i-1].second) cnt++;
}
if(cnt == 4)
{
int sum = 0;
int j = 1;
for(int i = 2; i < 15; i++)
{
if(flag[i])
{
sum += i * j;
j *= 14;
}
}
return sum;
}
return 0;
}
int Straight(vector<pair<int, int> > &vec)
{
int cnt = 0;
int maxi = 0;
for(int i = 1; i < vec.size() and cnt != 4; i++)
{
if(vec[i].first == vec[i-1].first + 1)
{
cnt++;
maxi = vec[i].first;
}
else cnt = 0;
}
if(cnt == 4)
{
return maxi;
}
return 0;
}
int ThreeOfAKind(vector<pair<int, int> > &vec)
{
int cnt[15] = {0};
for(int i = 0; i < vec.size(); i++)
{
int tmp = vec[i].first;
cnt[tmp]++;
}
int j = 1;
int sum = 0;
int Three = 0;
for(int i = 2; i <= 14; i++)
{
if(cnt[i] == 3)
{
Three = 1;
sum += i*14*14*14;
}
else if(cnt[i])
{
sum += j * i;
j *= 14;
}
}
if(Three)
return sum;
return 0;
}
int TwoPairs(vector<pair<int, int> > &vec)
{
int cnt[15] = {0};
for(int i = 0; i < vec.size(); i++)
{
int tmp = vec[i].first;
cnt[tmp]++;
}
vector<int> two;
vector<int> one;
for(int i = 2; i < 15; i++)
{
if(cnt[i] == 2) two.push_back(i);
else if(cnt[i]) one.push_back(i);
}
if(two.size() == 2)
{
int big = max(two[0], two[1]);
int small = min(two[0], two[1]);
return (big * 10000 + small * 100 + one[0]);
}
return 0;
}
int Pair(vector<pair<int, int> > &vec)
{
int cnt[15] = {0};
for(int i = 0; i < vec.size(); i++)
{
int tmp = vec[i].first;
cnt[tmp]++;
}
vector<int> two;
vector<int> one;
for(int i = 2; i < 15; i++)
{
if(cnt[i] == 2) two.push_back(i);
else if(cnt[i]) one.push_back(i);
}
if(two.size() == 1)
{
return (two[0] * 10000 + one[2]*14*14 + one[1]*14 + one[0]);
}
return 0;
}
int HighCard(vector<pair<int, int> > &vec)
{
int cnt[15] = {0};
for(int i = 0; i < vec.size(); i++)
{
int tmp = vec[i].first;
cnt[tmp]++;
}
int j = 1;
int sum = 0;
for(int i = 2; i <= 14; i++)
{
if(cnt[i])
{
sum += i * j;
j *= 14;
}
}
return sum;
}
int compare(vector<pair<int, int> > &black, vector<pair<int, int> > &white)
{
int b, w;
b = StraightFlush(black);
w = StraightFlush(white);
if(b > w) return 0;
else if(b < w) return 1;
else if(b and b == w)
{
return 2;
}
b = FourOfAKind(black);
w = FourOfAKind(white);
if(b > w) return 0;
else if(b < w) return 1;
else if(b and b == w)
{
return 2;
}
b = FullHouse(black);
w = FullHouse(white);
if(b > w) return 0;
else if(b < w) return 1;
else if(b and b == w)
{
return 2;
}
b = Flush(black);
w = Flush(white);
if(b > w) return 0;
else if(b < w) return 1;
else if(b and b == w)
{
return 2;
}
b = Straight(black);
w = Straight(white);
if(b > w) return 0;
else if(b < w) return 1;
else if(b and b == w)
{
return 2;
}
b = ThreeOfAKind(black);
w = ThreeOfAKind(white);
if(b > w) return 0;
else if(b < w) return 1;
else if(b and b == w)
{
return 2;
}
b = TwoPairs(black);
w = TwoPairs(white);
if(b > w) return 0;
else if(b < w) return 1;
else if(b and b == w)
{
return 2;
}
b = Pair(black);
w = Pair(white);
if(b > w) return 0;
else if(b < w) return 1;
else if(b and b == w)
{
return 2;
}
b = HighCard(black);
w = HighCard(white);
if(b > w) return 0;
else if(b < w) return 1;
else if(b and b == w)
{
return 2;
}
}
int main()
{
vector<pair<int, int> > black, white;
while (input(black, white))
{
sort(black.begin(), black.end());
sort(white.begin(), white.end());
int ans = compare(black, white);
if(ans == 0)
{
cout << "Black wins." << endl;
}
else if(ans == 1)
{
cout << "White wins." << endl;
}
else
{
cout << "Tie." << endl;
}
}
return 0;
}
訂閱：
文章 (Atom)