寫了兩個parse加
大數類就解決了,基本不難.
Code
1
#include "BigInteger.h"
2#include <iostream>
3#include <string>
4using namespace std;
5
6int ConvertToInt(char c)
7
{
8
if(isdigit((int)c))
9 return c - '0';
10 else
11 return c - 'a' + 10;
12
}
13
14char ConvertToChar(int value)
15{
16 if(value < 10)
17 return value + '0';
18 else
19 return value - 10 + 'a';
20}
21
22int _tmain(int argc, _TCHAR* argv[])
23{
24 string a, b;
25 while(cin >> a >> b)
26
{
27 int a_length = a.length();
28 int b_length = b.length();
29
30 BigInteger big_a(0), big_b(0);
31 BigInteger p(20), zero(0);
32 for(int i = a_length - 1; i >= 0; --i)
33 {
34 big_a = big_a + BigInteger(ConvertToInt(a.at(i))) * p.Pow(a_length - 1 - i);
35
}
36 for(int i = b_length - 1; i >= 0; --i)
37 {
38 big_b = big_b + BigInteger(ConvertToInt(b.at(i))) * p.Pow(b_length - 1 - i);
39 }
40 BigInteger result = big_a + big_b;
41 vector<char> r;
42 if(result == zero)
43 {
44 cout << "0" << endl;
45 continue;
46 }
47 while(result != zero)
48 {
49 BigInteger big_integer = result % p;
50 r.push_back(ConvertToChar(big_integer.GetIntValue()));
51 result = result / p;
52 }
53
54 vector<char>::reverse_iterator end = r.rend();
55 for(vector<char>::reverse_iterator ite = r.rbegin(); ite != end; ++ite)
56 {
57 cout << (*ite);
58 }
59 cout << endl;
60 }
61 return 0;
62}
63posted @
2009-03-26 21:51 肖羽思 閱讀(412) |
評論 (0) |
編輯 收藏
利用
大數類非常容易解決,代碼如下:
Code
1#include "BigInteger.h"
2#include <iostream>
3#include <cmath>
4using namespace std;
5
6int _tmain(int argc, _TCHAR* argv[])
7{
8 int cases;
9 cin >> cases;
10 while(cases--)
11 {
12 int base;
13 string num;
14 while(cin >> base && base != 0)
15 {
16 cin >> num;
17 BigInteger b(base);
18 BigInteger n(num);
19
20 BigInteger result(0);
21 BigInteger divide(0);
22
23 int length = num.length();
24
25 for(int i = length - 1; i >= 0; --i)
26 {
27 result = result + b.Pow(length - 1 - i) * ((int)(num.at(i) - '0'));
28 divide = divide + ((int)(num.at(i) - '0'));
29 }
30
31 const BigInteger zero(0);
32 if(result % divide == zero)
33 cout << "yes" << endl;
34 else
35 cout << "no" << endl;
36 }
37 if(cases > 0)
38 cout << endl;
39 }
40
41 return 0;
42}
43
posted @
2009-03-26 21:46 肖羽思 閱讀(355) |
評論 (0) |
編輯 收藏
摘要: ZOJ有很多與大數相關的題目,干脆寫了一個比較完整的大數類一次性解決,基本思想很簡單,不多解釋,代碼如下:
CodeCode highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> 1#ifndef BIG_INTEGER ...
閱讀全文
posted @
2009-03-26 21:41 肖羽思 閱讀(751) |
評論 (0) |
編輯 收藏
摘要: "馬走日"問題,BFS解決,比較簡單,狀態即為當前所在的位置,代碼如下:
CodeCode highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> 1#include <iostream> 2#inc...
閱讀全文
posted @
2009-03-26 21:17 肖羽思 閱讀(1343) |
評論 (1) |
編輯 收藏
簡單模擬題,稍微注意即可,不羅嗦,直接貼代碼.
Code
1#include <iostream>
2using namespace std;
3
4void PrintSheet(int sheet_num, int i, int j, int n, bool isFront)
5{
6 if(i > n && j > n)
7 return;
8 cout << "Sheet " << sheet_num << ", " << (isFront ? "front: " : "back : ");
9 if(isFront)
10 {
11 if(j > n)
12 cout << "Blank";
13 else
14 cout << j;
15 cout << ", " << i << endl;
16 }
17 else
18 {
19 cout << i << ", ";
20 if(j > n)
21 cout << "Blank";
22 else
23 cout << j;
24 cout << endl;
25 }
26}
27
28int _tmain(int argc, _TCHAR* argv[])
29{
30 int n;
31 while(cin >> n && n != 0)
32 {
33 int sheet = n / 4;
34 int fullfill_n = n;
35 if(n % 4 != 0)
36 {
37 fullfill_n = (sheet + 1) * 4;
38 }
39
40 cout << "Printing order for " << n << " pages:" << endl;
41
42 int current_sheet = 1;
43
44 for(int i = 1, j = fullfill_n; i < j;)
45 {
46 PrintSheet(current_sheet, i, j, n, true);
47 ++i;
48 --j;
49 PrintSheet(current_sheet, i, j, n, false);
50 ++i;
51 --j;
52 ++current_sheet;
53 }
54 }
55 return 0;
56}
57
58
posted @
2009-03-26 21:11 肖羽思 閱讀(307) |
評論 (0) |
編輯 收藏
簡單題,不羅嗦,直接上代碼.
Code
1#include <iostream>
2using namespace std;
3
4int _tmain(int argc, _TCHAR* argv[])
5{
6 int index = 0;
7 int n, m, c, current_power, max_power;
8
9 while(cin >> n >> m >> c && (n != 0 || m != 0 || c != 0))
10 {
11 cout << "Sequence " << ++index << endl;
12
13 current_power = 0;
14 max_power = 0;
15 int * power = new int[n];
16 bool * state = new bool[n];
17 for(int i = 0; i < n; ++i)
18 {
19 cin >> power[i];
20 state[i] = false;
21 }
22
23 int operation;
24
25 for(int i = 0; i < m; ++i)
26 {
27 cin >> operation;
28 // array count from 0
29 --operation;
30 // if it's open
31 if(state[operation])
32 {
33 current_power -= power[operation];
34 state[operation] = false;
35 }
36 else
37 {
38 current_power += power[operation];
39 state[operation] = true;
40 }
41
42 max_power = max(current_power, max_power);
43 }
44
45 if(max_power > c)
46 {
47 cout << "Fuse was blown." << endl;
48 }
49 else
50 {
51 cout << "Fuse was not blown." << endl;
52 cout << "Maximal power consumption was " << max_power << " amperes." << endl;
53 }
54 cout << endl;
55 }
56
57 return 0;
58}
59
60
posted @
2009-03-26 21:09 肖羽思 閱讀(466) |
評論 (0) |
編輯 收藏解決此題需掌握兩個基本原理:
1.任何奇數都可以被2n-1整除,而偶數則不能.
2.將n1...nx全部相乘后對M取模恒等于n1...nx分別單獨對M取模后相乘.
基于以上兩個原理,代碼如下:
1#include <iostream>
2using namespace std;
3
4int _tmain(int argc, _TCHAR* argv[])
5{
6 int n;
7 while(cin >> n)
8 {
9 if((n & 0x1) == 0)
10 cout << "2^? mod " << n << " = 1" << endl;
11 else
12 {
13 int temp = 1;
14 int result = 1;
15 while(true)
16 {
17 temp *= 2;
18 temp %= n;
19 if(temp == 1)
20 break;
21 ++result;
22 }
23 cout << "2^" << result << " mod " << n << " = 1" << endl;
24 }
25 }
26 return 0;
27}
28
29
posted @
2009-03-26 21:01 肖羽思 閱讀(625) |
評論 (0) |
編輯 收藏
摘要: BFS+剪枝.所謂的剪枝就是如果A為空的時候不能進行"empty A"的操作等.PS:也可利用A和B的互質性解決,在此用搜索主要是想多練習一下搜索的代碼.
CodeCode highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> 1#inclu...
閱讀全文
posted @
2009-03-24 20:49 肖羽思 閱讀(698) |
評論 (0) |
編輯 收藏
摘要: DFS+剪枝.剪枝主要是判斷現有輸出是否與最終期望字符串前綴匹配.
CodeCode highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> 1#include <iostream> 2#includ...
閱讀全文
posted @
2009-03-24 20:45 肖羽思 閱讀(1917) |
評論 (2) |
編輯 收藏
非常簡單的題,沒什么好說的.唯一值得一提的就是在判斷是否是回文的時候只需遍歷一半的元素即可,稍微提高一點性能.
Code
1#include <vector>
2#include <iostream>
3using namespace std;
4
5const int BASE = 16;
6
7bool isPalindrom(int num, int base)
8{
9 vector<int> v;
10 while(num)
11 {
12 v.push_back(num % base);
13 num /= base;
14 }
15
16 int start, end;
17 for(start = 0, end = v.size() - 1; start < (end + 1) / 2; ++start, --end)
18 {
19 if(v[start] != v[end])
20 return false;
21 }
22 return true;
23}
24
25int _tmain(int argc, _TCHAR* argv[])
26{
27 int n;
28 vector<int> result;
29 while(cin >> n && n != 0)
30 {
31 result.clear();
32 for(int i = 2; i <= BASE; ++i)
33 {
34 if(isPalindrom(n, i))
35 result.push_back(i);
36 }
37
38 int length = result.size();
39 if(length == 0)
40 {
41 cout << "Number " << n << " is not a palindrom" << endl;
42 }
43
44 else
45 {
46 cout << "Number " << n << " is palindrom in basis ";
47 for(int i = 0; i < length - 1; ++i)
48 {
49 cout << result[i] << " ";
50 }
51 cout << result[length - 1] << endl;
52 }
53 }
54 return 0;
55}
56
57
posted @
2009-03-24 20:38 肖羽思 閱讀(607) |
評論 (0) |
編輯 收藏