写了两个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 肖羽思 阅读(402) |
评论 (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 肖羽思 阅读(341) |
评论 (0) |
编辑 收藏
摘要: ZOJ有很多与大数相关的题目,干脆写了一个比较完整的大数类一次性解决,基本思想很简单,不多解释,代码如下:
CodeCode highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> 1#ifndef BIG_INTEGER ...
阅读全文
posted @
2009-03-26 21:41 肖羽思 阅读(738) |
评论 (0) |
编辑 收藏
摘要: "马走日"问题,BFS解决,比较简单,状态即为当前所在的位置,代码如下:
CodeCode highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> 1#include <iostream> 2#inc...
阅读全文
posted @
2009-03-26 21:17 肖羽思 阅读(1314) |
评论 (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 肖羽思 阅读(299) |
评论 (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 肖羽思 阅读(454) |
评论 (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 肖羽思 阅读(607) |
评论 (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 肖羽思 阅读(685) |
评论 (0) |
编辑 收藏
摘要: DFS+剪枝.剪枝主要是判断现有输出是否与最终期望字符串前缀匹配.
CodeCode highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> 1#include <iostream> 2#includ...
阅读全文
posted @
2009-03-24 20:45 肖羽思 阅读(1895) |
评论 (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 肖羽思 阅读(598) |
评论 (0) |
编辑 收藏