摘要: 大浮点数运算.
CodeCode highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> 1#include "BigInteger.h" 2#include <iostream> ...
阅读全文
posted @
2009-03-31 21:28 肖羽思 阅读(468) |
评论 (2) |
编辑 收藏.
Code
1
#include <iostream>
2using namespace std;
3
4int _tmain(int argc, _TCHAR* argv[])
5
{
6
int p,e,i,d,x;
7 int test;
8 while (cin >> test)
9
{
10 int index = 1;
11 while (cin >> p >> e >> i >> d)
12 {
13 if (p == -1)
14 return 0;
15
16 x = (p * 6 * 28 * 33 + e * 19 * 23 * 33 + i * 2 * 23 * 28) % 21252;
17 x -= d;
18
19 if (x <= 0 )
20 x += 21252;
21
22 cout << "Case " << index++ << ": the next triple peak occurs in " << x << " days." << endl;
23
}
24 }
25 return 0;
26
}
27
28posted @
2009-03-31 21:24 肖羽思 阅读(371) |
评论 (0) |
编辑 收藏
摘要: 本来想写一个大浮点数类,后来因为时间关系,只将浮点除法写了.其实除了除法有点难度外,加减乘均可借鉴大整数类.代码写得比较乱,因为时间比较急.
CodeCode highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> 1#include ...
阅读全文
posted @
2009-03-31 21:21 肖羽思 阅读(471) |
评论 (0) |
编辑 收藏
根据二分图的性质,最小结点覆盖=结点数-最大匹配数.
Code
1#include <iostream>
2using namespace std;
3
4const int M = 121;
5int rlink[M];
6bool g[M][M];
7bool visited[M];
8
9int intersections, streets;
10
11bool Search(int pos)
12{
13 for(int i = 1; i <= intersections; ++i)
14 {
15 if(!visited[i] && g[pos][i])
16 {
17 visited[i] = true;
18 if(rlink[i] == -1 || Search(rlink[i]))
19 {
20 rlink[i] = pos;
21 return true;
22 }
23 }
24 }
25
26 return false;
27}
28
29int _tmain(int argc, _TCHAR* argv[])
30{
31 int cases;
32 cin >> cases;
33 while(cases--)
34 {
35 cin >> intersections >> streets;
36
37 memset(g, false, sizeof(g));
38 memset(rlink, -1, sizeof(rlink));
39
40 int start, end;
41 for(int i = 0; i < streets; ++i)
42 {
43 cin >> start >> end;
44 g[start][end] = true;
45 }
46
47 int result = 0;
48
49 for(int i = 1; i <= intersections; ++i)
50 {
51 memset(visited, false, sizeof(visited));
52
53 if(Search(i))
54 ++result;
55 }
56
57 cout << intersections - result << endl;
58 }
59 return 0;
60}
61
62
posted @
2009-03-31 21:07 肖羽思 阅读(584) |
评论 (1) |
编辑 收藏
直观的二分图最大匹配.
Code
1#include <iostream>
2using namespace std;
3
4int n, m;
5int **p;
6bool * visited;
7int *llink, *rlink;
8
9bool match(int pos)
10{
11 for(int i = 0; i < m; ++i)
12 {
13 if(!visited[i] && p[pos][i] == 1)
14 {
15 visited[i] = true;
16 if(rlink[i] == -1 || match(rlink[i]))
17 {
18 rlink[i] = pos;
19 return true;
20 }
21 }
22 }
23 return false;
24}
25
26int _tmain(int argc, _TCHAR* argv[])
27{
28 int jobs;
29 while(cin >> n && n != 0)
30 {
31 cin >> m >> jobs;
32
33 p = new int*[n];
34 for(int i = 0; i < n; ++i)
35 {
36 p[i] = new int[m];
37 }
38
39 int jobId, mode_A, mode_B;
40
41 for(int i = 0; i < jobs; ++i)
42 {
43 cin >> jobId >> mode_A >> mode_B;
44 if(mode_A * mode_B != 0)
45 p[mode_A][mode_B] = 1;
46 }
47
48
49 int result = 0;
50 rlink = new int[m];
51 visited = new bool[m];
52 for(int i = 0; i < m; ++i)
53 rlink[i] = -1;
54
55 for(int i = 0; i < n; ++i)
56 {
57 for(int j = 0; j < m; ++j)
58 visited[j] = false;
59
60 if(match(i))
61 ++result;
62 }
63
64 cout << result << endl;
65 delete llink, rlink, visited;
66 delete [] p;
67 }
68
69 return 0;
70}
71
72
posted @
2009-03-31 21:03 肖羽思 阅读(468) |
评论 (0) |
编辑 收藏
简单题,非常简单直观的BFS.
Code
1#include <iostream>
2#include <vector>
3#include <queue>
4using namespace std;
5
6const int NODE = 20;
7vector<vector<int> > g(20);
8
9int search(int s, int e)
10{
11 queue<int> q;
12 q.push(s);
13 bool visited[NODE];
14 int high[NODE];
15 memset(visited, false, NODE);
16 memset(high, -1, NODE);
17
18 visited[s] = true;
19 high[s] = 0;
20 while(!q.empty())
21 {
22 int node = q.front();
23 q.pop();
24
25 vector<int>::iterator end = g[node].end();
26 for(vector<int>::iterator ite = g[node].begin(); ite != end; ++ite)
27 {
28 if(visited[*ite] == false)
29 {
30 q.push(*ite);
31 visited[*ite] = true;
32 high[*ite] = high[node] + 1;
33 if(*ite == e)
34 return high[*ite];
35 }
36 }
37 }
38}
39
40int _tmain(int argc, _TCHAR* argv[])
41{
42 int cases(0);
43 while(true)
44 {
45 for(int i = 0; i < NODE; ++i)
46 {
47 g[i].clear();
48 }
49
50 for(int i = 0; i < NODE - 1; ++i)
51 {
52 int n, t;
53 if(!(cin >> n))
54 return 0;
55 while(n--)
56 {
57 cin >> t;
58 g[i].push_back(t - 1);
59 g[t - 1].push_back(i);
60 }
61 }
62
63 int s, start, end;
64 cin >> s;
65 cout << "Test Set #" << ++cases << endl;
66 for(int i = 0; i < s; ++i)
67 {
68 cin >> start >> end;
69 cout << start << " to " << end << ": " << search(start - 1, end - 1) << endl;
70 }
71 cout << endl;
72 }
73 return 0;
74}
75
76
posted @
2009-03-31 20:58 肖羽思 阅读(950) |
评论 (1) |
编辑 收藏的强化版,求序列中多个数之和是否存在于序列之中,并排序输出.
由于题目要求按算式"字符串"顺序输出,在DFS过程中以数字个数为DFS的深度限制.
Code
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6vector<int> datas;
7vector<int> result;
8bool isFind;
9
10// int sort function
11int IntCompare(const void * i1, const void * i2)
12{
13 return (*(const int*)i1) > (*(const int*)i2);
14}
15
16// start is the search start index
17// dest_deep is the search destination depth
18// current_deep is the search of current depth
19// current_sum is the sum of current searchable numbers
20void DFS(int start, int dest_deep, int current_deep, int current_sum)
21{
22 // if reach the dstination depth
23 if(current_deep == dest_deep)
24 {
25 // if we have the sum in the list
26 if(binary_search(datas.begin(), datas.end(), current_sum))
27 {
28 // output it
29 for(int i = 0; i < dest_deep - 1; ++i)
30 {
31 cout << result[i] << "+";
32 }
33 cout << result[dest_deep - 1] << "=" << current_sum << endl;
34 isFind = true;
35 }
36 }
37 // otherwise if we haven't reach the destination depth, go on searching
38 else
39 {
40 int size = datas.size();
41 // search from start to avoid duplicate result such as 1+2=3 and 2+1=3
42 for(int i = start; i < size; ++i)
43 {
44 // store my search result
45 if(current_deep < result.size())
46 {
47 result[current_deep] = datas[i];
48 }
49 else
50 {
51 result.push_back(datas[i]);
52 }
53
54 // if the sum is bigger than the biggest one in the list, break the loop
55 if(current_sum + datas[i] > datas[datas.size() - 1])
56 break;
57 // search next, increase start avoid duplicate, increase depth, re-calculate sum
58 DFS(i + 1, dest_deep, current_deep + 1, current_sum + datas[i]);
59 }
60 }
61}
62
63int _tmain(int argc, _TCHAR* argv[])
64{
65 int n;
66 cin >> n;
67 for(int i = 0; i < n; ++i)
68 {
69 int count;
70 cin >> count;
71 int number;
72 for(int j = 0; j < count; ++j)
73 {
74 cin >> number;
75 datas.push_back(number);
76 }
77
78 qsort(&datas[0], count, sizeof(int), IntCompare);
79
80 isFind = false;
81 for(int i = 2; i < count; ++i)
82 {
83 // i indicate the depth of the search, 2 is the lowest and count-1 is the largest
84 DFS(0, i, 0, 0);
85 }
86 if(!isFind)
87 cout << "Can't find any equations." << endl;
88 cout << endl;
89 datas.clear();
90 }
91 return 0;
92}
93
posted @
2009-03-31 20:54 肖羽思 阅读(2058) |
评论 (0) |
编辑 收藏
简单题,求解序列中三个数相加最大且存在于序列中的数.利用三层循环遍历加二分搜索可在n
3*logn时间内解决(排序用nlogn时间).
Code
1#include <iostream>
2#include <algorithm>
3using namespace std;
4
5int IntCompare(const void * i1, const void * i2)
6{
7 return (*(const int*)i1) > (*(const int*)i2);
8}
9
10int _tmain(int argc, _TCHAR* argv[])
11{
12 int * gamblers, n;
13 while(cin >> n && n != 0)
14 {
15 int firstResult, secondResult;
16 bool isFind = false;
17 gamblers = new int[n];
18 for(int i = 0; i < n; ++i)
19 {
20 cin >> gamblers[i];
21 }
22
23 qsort(gamblers, n, sizeof(int), IntCompare);
24
25 for(int i = n - 1; i >= 0; --i)
26 {
27 for(int j = 0; j < n; ++j)
28 {
29 if(j == i)
30 continue;
31 firstResult = gamblers[i] - gamblers[j];
32 for(int k = 0; k < n; ++k)
33 {
34 if(k == i || k == j)
35 continue;
36 secondResult = firstResult - gamblers[k];
37
38 if(secondResult == gamblers[i]
39 || secondResult == gamblers[j]
40 || secondResult == gamblers[k])
41 continue;
42
43 if(binary_search(gamblers, gamblers + n, secondResult))
44 {
45 cout << gamblers[i] << endl;
46 isFind = true;
47 break;
48 }
49 }
50 if(isFind)
51 break;
52 }
53 if(isFind)
54 break;
55 }
56
57 if(!isFind)
58 cout << "no solution" << endl;
59
60 delete gamblers;
61 }
62
63 return 0;
64}
65
66
posted @
2009-03-31 20:43 肖羽思 阅读(871) |
评论 (0) |
编辑 收藏
将
大数类稍做修改(主要是输出的修改,每三个数字加上逗号),26进制的数字转换,比较简单.
Code
1#include "BigInteger.h"
2#include <iostream>
3using namespace std;
4
5bool IsDigit(string s)
6{
7 if(s.length() == 0)
8 return false;
9 return isdigit((int)s.at(0));
10}
11
12char ConvertToChar(int value)
13{
14 return (char)(value + 'a' - 1);
15}
16
17int _tmain(int argc, _TCHAR* argv[])
18{
19 string input;
20 bool isDigit;
21 while(cin >> input && input != "*")
22 {
23 isDigit = IsDigit(input);
24
25 if(isDigit)
26 {
27 BigInteger integer(input);
28 BigInteger zero(0);
29
30 vector<char> result;
31 while(integer != zero)
32 {
33 BigInteger r = integer % 26;
34 result.push_back(ConvertToChar(r.GetIntValue()));
35 integer = integer / 26;
36 }
37 vector<char>::reverse_iterator end = result.rend();
38 int length = 0;
39 for(vector<char>::reverse_iterator ite = result.rbegin(); ite != end; ++ite)
40 {
41 cout << (*ite);
42 ++length;
43 }
44 while(++length < 23)
45 cout << " ";
46 cout << BigInteger(input) << endl;
47 }
48 else
49 {
50 int length = input.length();
51 BigInteger result(0);
52 BigInteger p(26);
53 for(int i = length - 1; i >= 0; --i)
54 {
55 result = result + BigInteger((int)(input.at(i) - 'a' + 1)) * p.Pow(length - 1 - i);
56 }
57 cout << input;
58 int index = length;
59 while(++index < 23)
60 cout << " ";
61 cout << result << endl;
62 }
63 }
64 return 0;
65}
66
67
posted @
2009-03-26 21:59 肖羽思 阅读(426) |
评论 (0) |
编辑 收藏
利用
大数类非常简单地解决.
Code
1#include "BigInteger.h"
2#include <iostream>
3using namespace std;
4
5int _tmain(int argc, _TCHAR* argv[])
6{
7 int cases;
8 cin >> cases;
9 while(cases)
10 {
11 string input;
12 BigInteger result(0);
13 while(cin >> input && input != "0")
14 {
15 result = result + BigInteger(input);
16 }
17 cout << result << endl;
18 if(cases != 1)
19 cout << endl;
20 --cases;
21 }
22 return 0;
23}
24
posted @
2009-03-26 21:55 肖羽思 阅读(377) |
评论 (0) |
编辑 收藏