Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

终于过了,贴个代码(c++)纪念下

Posted by cantwait at 2016-10-04 13:40:47 on Problem 1001
#include <string>
#include <vector>
#include <iostream>
using namespace std;

void TrimZero(string &s)
{
	// head
	int i = 0;
	while (i < s.length())
	{
		if (s[i] == '0')
		{
			i++;
			continue;
		}
		else
		{
			break;
		}
	}
	if (i != 0)
	{
		s.erase(0, i);
	}
	int j = s.find_first_of('.');
	if (j != string::npos)
	{
		i = s.length() - 1;
		//tail
		while (i >= 0)
		{
			if (s[i] == '0')
			{
				i--;
			}
			else if (s[i] == '.')
			{
				i--;
				break;
			}
			else
			{
				break;
			}
		}
		if (i < (int)s.length()-1)
		{
			s.erase(s.begin() + (i + 1), s.end());
		}
	}
	if (s.length() == 0)
	{
		s.append(1, '0');
	}
}
// d1=d1+d2
void AddDoubleStr(string &d1, string &d2)
{
	if (d1.length() == 0)
	{
		d1 = d2;
		return;
	}
	int carry = 0;
	int a, b, r; // 加数
	int pos1 = d1.find_first_of('.');
	if (pos1 == string::npos)
	{
		pos1 = d1.length();
	}
	int pos2 = d2.find_first_of('.');
	if (pos2 == string::npos)
	{
		pos2 = d2.length();
	}
	int l1 = d1.length() - pos1;
	int l2 = d2.length() - pos2;
	int i1, i2; // index
	if (l1 < l2)
	{
		i1 = d1.length() - 1;
		i2 = pos2 + l1 - 1;
	}
	else
	{
		i2 = d2.length() - 1;
		i1 = pos1 + l2 - 1;
	}
	while ((i1 >= 0 && i2 >= 0) || carry > 0)
	{
		if (i1 >= 0)
		{
			if (d1[i1] == '.')
			{
				i1--;
				i2--;
				continue;
			}
			a = d1[i1] - '0';
		}
		else
		{
			a = 0;
		}
		if (i2 >= 0)
		{
			b = d2[i2] - '0';
		}
		else
		{
			b = 0;
		}
		r = (a + b + carry) % 10;
		carry = (a + b + carry) / 10;
		
		if (i1 >= 0)
		{
			d1[i1] = '0' + r;
		}
		else
		{
			d1.insert(0, 1, (char)('0' + r));
		}
		if (i1 >= 0)
		{
			i1--;
		}
		if (i2 >= 0)
		{
			i2--;
		}
	}
	// d2 head
	if (i2 >= 0)
	{
		d1.insert(0, d2, 0, i2 + 1);
	}
	// d2 tail
	if (l2 > l1)
	{
		d1.insert(d1.end(), d2.begin() + pos2 + l1, d2.end());
	}
}

// d2=d1*m*10^n
void Multiply1(string &d1, string &d2, int m, int n)
{
	int a,r;
	int i = d1.length() - 1;
	int j = 0;
	int carry = 0;
	while (i >= 0)
	{
		if (d1[i] == '.')
		{
			d2.insert(0, 1, '.');
			j = d2.length();
			i--;
			continue;
		}
		a = d1[i] - '0';
		r = (a * m + carry) % 10;
		carry = (a * m + carry) / 10;
		d2.insert(0,1,(char)('0' + r));
		i--;
	}
	if (carry > 0)
	{
		d2.insert(0, 1, (char)('0' + carry));
	}
	int point_pos = d2.length() - j;
	if (n == 0)
	{
		TrimZero(d2);
		return;
	}
	// delete old point
	if (n != 0 && point_pos != d2.length())
	{
		d2.erase(d2.begin() + point_pos);
	}
	
	int len = d2.length();
	// add new point and zero
	point_pos += n;
	if (point_pos > len)
	{
		d2.insert(d2.end(), point_pos - len, '0');
	}
	else if (point_pos >= 0 && point_pos < len)
	{
		d2.insert(point_pos, 1, '.');
	}
	else if(point_pos < 0)
	{
		d2.insert(0, -point_pos, '0');
		d2.insert(0, 1, '.');
	}
	TrimZero(d2);
}

// r=d1*d2
void Multiply2(string &d1, string &d2, string &r)
{
	string t;
	int point_pos = d2.find_first_of('.');
	if (point_pos == string::npos)
	{
		point_pos = d2.length();
	}
	for (int i = d2.length() - 1; i >= 0; i--)
	{
		if (d2[i] == '.' || d2[i] == '0')
		{
			continue;
		}
		if (i > point_pos)
		{
			Multiply1(d1, t, d2[i] - '0', point_pos - i);
		}
		else
		{
			Multiply1(d1, t, d2[i] - '0', point_pos - i-1);
		}
		//cout << r << " " << t << endl;
		AddDoubleStr(r, t);
		t.clear();
	}
}
string& Pow(string &d1, int m, string &r)
{
	r.clear();
	if (m == 0)
	{
		r.append(1, '1');
		return r;
	}
	r = d1;
	for (int i = 1; i < m; i++)
	{
		string t;
		Multiply2(r, d1, t);
		r = t;
	}
	TrimZero(r);
	return r;
}


int main()
{	
	string d1;
	int m;
	vector<string> sv;
	vector<int> iv;	
	while (cin >> d1 >> m)
	{
		sv.push_back(d1);
		iv.push_back(m);
	}
	for (int i = 0; i < sv.size(); i++)
	{
		cout << Pow(sv[i], iv[i], d3) << endl;
	}
	system("pause");
        return 0;
}


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator