高精度 + 微扰证明

高精度除低精度

题目链接：

https://www.luogu.com.cn/problem/P1480

代码：

#include 
using namespace std;
#define LL long long
string aa;
LL b;
vector  div(vector  a, LL b){
	vector  c;
	bool f = true;
	for (LL i = a.size() - 1, t = 0; i >= 0; i -- ){
		t = t * 10 + a[i];
		LL x = t / b;
		if (!f || x){
			f = false;
			c.push_back(x);
		}
		t %= b;
	}
	reverse(c.begin(), c.end());
	return c;
}
int main(){
	cin >> aa >> b;
	vector  a;
	for (int i = 0; i < aa.size(); i ++ )
		a.push_back(aa[i] - '0');
	reverse(a.begin(), a.end());
	vector  ans = div(a, b);
	for (int i = ans.size() - 1; i >= 0; i -- )
		cout << ans[i];
	cout << "\n";
	return 0;
}

微扰证明

题目链接：

https://www.acwing.com/problem/content/127/

代码：

#include 
using namespace std;
#define LL long long
const int N = 5e4 + 10;
LL a, b, n, s, ans = -1e9;
pair  p[N];
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i ++ ){
		cin >> a >> b;
		p[i] = {a + b, b};
	}
	sort(p + 1, p + n + 1);
	for (int i = 1; i <= n; i ++ ){
		ans = max(ans, s - p[i].second);
		s += p[i].first - p[i].second;
	}
	cout << ans << "\n";
	return 0;
}

高精度乘除低精度 + 微扰证明

题目链接：

https://www.acwing.com/problem/content/116/

思路：

先微扰证明，发现所有大臣要按照 \(a * b\) 的大小来排序，然后就是高精度的一个乘除了。

代码：

y总代码：

#include 
using namespace std;
#define fi first
#define se second
#define pb push_back
const int N = 1010;
int n;
pair  p[N];
vector  mul(vector  a, int b){
	vector  c;
	int t = 0;
	for (int i = 0; i < a.size(); i ++ ){
		t += a[i] * b;
		c.pb(t % 10);
		t /= 10;
	}
	while (t){
		c.pb(t % 10);
		t /= 10;
	}
	return c;
}
vector  div(vector  a, int b){
	vector  c;
	bool f = true;	//去掉前导0 
	for (int i = a.size() - 1, t = 0; i >= 0; i -- ){
		t = t * 10 + a[i];
		int x = t / b;
		if (!f || x){
			f = false;
			c.pb(x);
		}
		t %= b;
	}
	reverse(c.begin(), c.end());
	return c;
}
vector  max_vec(vector  a, vector  b){
	if (a.size() > b.size()) return a;
	if (a.size() < b.size()) return b;
	if ( vector  (a.rbegin(), a.rend()) > vector  (b.rbegin(), b.rend()) ) return a;
	return b;
}
int main(){
	cin >> n;
	for (int i = 0; i <= n; i ++ ){
		int a, b;
		cin >> a >> b;
		p[i] = {a * b, a};
	}
	sort(p + 1, p + n + 1);
	vector  s(1, 1), ans(1, 0);
	for (int i = 0 ; i <= n; i ++ ){
		if (i) ans = max_vec( ans, div(s, p[i].fi / p[i].se) );
		s = mul(s, p[i].se);
	}
	for (int i = ans.size() - 1; i >= 0; i -- )
		cout << ans[i];
	cout << "\n";
	return 0;
}