努力两个月终于过了(AC代码没用到结构体, 求优化)
查看原帖
努力两个月终于过了(AC代码没用到结构体, 求优化)
745288
Joker_Error_404楼主2023/12/31 06:47
#include<bits/stdc++.h>
using namespace std;
string A, B;
int a[100000], b[100000], c[100000], q, w, e, d[100000], len, f[1000000];
void into() {
	q = 0;w = 0;
	for (int i = A.size() - 1; i >= 0; --i) {
		a[q++] = A[i] - 48;
	}
	for (int i = B.size() - 1; i >= 0; --i) {
		b[w++] = B[i] - 48;
	}
}
void add() {
	memset(c, 0, sizeof(c));
	e = max(q, w);
	for (int i = 0; i < e; ++i) {
		c[i] = a[i] + b[i];
	}
	for (int i = 0; i < e; ++i) {
		c[i + 1] += c[i] / 10;
		c[i] %= 10;
	}
	while (c[e]) {
		++e;
		c[e] = c[e - 1] / 10;
		c[e - 1] %= 10;
	}
	for (int i = e - 1; i >= 0; --i) {
		printf("%d", c[i]);
	}
	putchar('\n');
}
int cmp() {
	if (A.size() == B.size()) {
		for (int i = q - 1; i >= 0; --i) {
			if (a[i] < b[i]) {
				return -1;
			} else if (a[i] > b[i]) {
				return 1;
			}
		}
	} else {
		int x = A.size(), y = B.size();
		if (x > y) {
			return 1;
		} else if (x == y) {
			return 0;
		} else {
			return -1;
		}
	}
	return 0;
}
void sub() {
	memset(c, 0, sizeof(c));
	e = max(q, w);
	int x = cmp();
	if (x == 0) {
		putchar('0');
		putchar(10);
		return;
	} else if (x > 0) {
		for (int i = 0; i < e; ++i) {
			c[i] = a[i] - b[i];
		}
		while (c[e] == 0 && e > 1) {
			--e;
		}
		for (int i = 0; i < e; ++i) {
			if (c[i] < 0) {
				--c[i + 1];
				c[i] += 10;
			}
		}
		if (c[e]) {
			++e;
			if (c[e - 1] < -9) {
				c[e - 1] += 10;
				--c[e];
			}
		}
	} else {
		for (int i = 0; i < e; ++i) {
			c[i] = b[i] - a[i];
		}
		while (c[e] == 0 && e > 1) {
			--e;
		}
		for (int i = 0; i < e; ++i) {
			if (c[i] < 0) {
				--c[i + 1];
				c[i] += 10;
			}
		}
		if (c[e]) {
			++e;
			if (c[e - 1] < -9) {
				c[e - 1] += 10;
				--c[e];
			}
		}
		putchar('-');
	}
	for (int i = e - 1; i >= 0; --i) {
		printf("%d", c[i]);
	}
	putchar('\n');
}
void mul() {
	for (int i = 0; i < q; ++i) {
		for (int j = 0; j < w; ++j) {
			d[i + j] += a[i] * b[j];
		}
	}
	e = q + w - 1;
	for (int i = 0; i < e; ++i) {
		d[i + 1] += d[i] / 10;
		d[i] %= 10;
	}
	while (d[e]) {
		d[e + 1] = d[e] / 10;
		d[e] %= 10;
		++e;
	}
	for (int i = e - 1; i >= 0; --i) {
		printf("%d", d[i]);
	}
	putchar('\n');
}
bool check(const int x, const int w1) {
	for (int i = 0; i < w1; ++i) {
		if (a[x + i] > b[i]) {
			return true;
		} else if (b[i] > a[x + i]) {
			return false;
		}
	}
	return true;
}
void div() {
	int x = cmp();
	if (x < 0) {
		putchar('0');
		putchar(10);
		for (int i = q - 1; i >= 0; --i) {
			printf("%d",a[i]);
		}
	} else if (x == 0) {
		putchar('1');
		putchar(10);
		putchar('0');
	} else {
		memset(c, 0, sizeof(c));
		for (int i = 0; i < (int)B.size(); ++i) {
			b[i] = B[i] - 48;
		}		
		for (int i = 0; i < (int)A.size(); ++i) {
			a[i] = A[i] - 48;
		}
		int x = 0;
		while (q - x >= w) {
			while (check(x, w)) {
				for (int i = w - 1; i >= 0; --i) {
					a[x + i] -= b[i];
					if (a[x + i] < 0) {
						--a[x + i - 1];
						a[x + i] += 10;
					}
				}
				++f[x];
			}
			a[x + 1] += a[x] * 10;
			a[x] = 0;
			++x;
		}
		bool b1 = 1;
		int la;
		for (int i = 0; i < x; ++i) {
			if (b1 && !f[i]) continue;
			if (b1) {
				la = i;
			}
			b1 = 0;
			printf("%d",f[i]);
		}
		putchar('\n');
		int l = 0;
		while (a[l] == 0 && l + 1 < q) {
			++l;
		}
		for (int i = l; i < q; ++i) {
			printf("%d",a[i]);
		}
	}
}
int main() {
	cin >> A >> B;
	into();
	len = A.size() - B.size();
	add();
	sub();
	mul();
	div();
	return 0;
}
2023/12/31 06:47
加载中...