如果这篇博客帮助到你，可以请我喝一杯咖啡~
CC BY 4.0 （除特别声明或转载文章外）
首先我按照大臣右手数字的大小排序，结果残忍20分
说明洛谷还是有水数据的！我的心中有信念！
按照左手数字排序肯定不对，又考虑到题目里只出现乘除法，就想到按照左右手乘积排序。
#include<iostream>
#include<algorithm>
using namespace std;
typedef unsigned long long ull;
struct person{
ull l,r;
bool operator<(person&i)const{
return l*r<i.l*i.r;
}
void InPut(){
cin>>l>>r;
}
}p[1024];
int main(){
ull n,l,r,ans=0;cin>>n>>l>>r;
for(ull i=0;i<n;i++)p[i].InPut();
sort(p,p+n);
for(ull i=0;i<n;i++){
ans=max(ans,l/p[i].r);
l*=p[i].l;
}
cout<<ans;
}
结果残忍50分！！！
${\color{white} WTF??}$
下载数据一看，#6的output是 2166489661101032350678866897536628698296804147316726 8781624417379802686213353102333272589274582399676748 79428851028800069063620140885606400000000000000000
即便是能存数范围最大的$ull$也根本存不下！
考虑写高精度
- 啊啊高精度好难写啦~
- 我就不说高精度有多重要啦
- ……
因为写高精度位数很重要，所以……我给每个数组都开了长度变量
高精乘：模拟手算
模拟$14 \times 23$，倒着存
a 4 1 0
b 3 2 0
c 0 0 0
step.1：a[0]的4乘b[0]的3，将c[0]加上12
c 12 0 0
step.2：c[0]超过10，将c[0]减10，c[1]加1
c 2 1 0
step.3：a[0]的4乘b[1]的2，将c[1]加上8
c 2 9 0
step.4：a[1]的1乘b[0]的3，将c[1]加上3
c 2 12 0
step.5：c[1]超过10，将c[1]减10,c[2]加1
c 2 2 1
step.6：a[1]的1乘b[1]的2，将c[2]加上2
c 2 2 3
完成。倒着读，$14 \times 23=322$，没错。
void mul(int a[],int b[],int la,int lb,int c[],int&lc){
for(int i=0;i<la;i++){
int x=0;
for(int j=0;j<lb;j++){
c[i+j]+=a[i]*b[j]+x;
x=c[i+j]/10;
c[i+j]%=10;
}
c[i+lb]=x;
}
for(lc=la+lb;!c[lc];lc--);lc++;
}
高精除
a 4 2 3
b 4 1 0
显然是要做$324/14$。
step.1：将a前端的32与b的14进行比较，得32>14
step.2：将32减去14，得18，c[1]加上1
step.3：18再次与14进行比较，18>14
step.4：18减去14得4，c[1]加上1
step.5：4与14进行比较，4<14，切换到下一个区域（俗称“落位”）
step.6：44与14进行比较，44>14，于是在不停地减，直到剩下的2比14小为止。
得到的商为23
void div(int a[],int b[],int la,int lb,int c[],int&lc){
int ca[4096]={};
for(int i=0;i<la;i++)ca[i]=a[i];
for(int i=la-lb;i>=0;i--){
int d[4096]={};
for(int j=i;j<=i+lb;j++)d[j-i]=ca[j];
while(10*d[lb]+d[lb-1]>b[lb-1])sub(d,b,lb+1),c[i]++;
if(d[lb-1]==b[lb-1]&&bigger(d,b,lb,lb))sub(d,b,lb+1),c[i]++;
for(int j=i;j<i+lb;j++)ca[j]=d[j-i];
}
for(lc=la-lb;c[lc];lc++);
}
高精减
刚才的步骤里有高精减，怎么办
模拟$626-361$
a 6 2 6
b 1 6 3
step.1：6减去1得5
a 5 2 6
step.2：2减去6得-4
a 5 -4 6
step.3：-4<0，将-4加10，高位的6减1
a 5 6 5
step.4：5减去3得2
a 5 6 2
$626-361=265$也是对的
void sub(int a[],int b[],int la){
for(int i=0;i<la;i++){
a[i]-=b[i];
if(a[i]<0){
a[i]+=10;
a[i+1]--;
}
}
}
高精比大小
这个不用说，先看位数，再一位一位比
bool bigger(int a[],int b[],int la,int lb){
if(la>lb)return 1;
if(la<lb)return 0;
for(int i=la;i>=0;i--){
if(a[i]>b[i])return 1;
if(a[i]<b[i])return 0;
}
return 1;
}
所有都讲完啦！贴代码~~
#include<iostream>
#include<algorithm>
using namespace std;
void mul(int a[],int b[],int la,int lb,int c[],int&lc);
bool bigger(int[],int[],int,int);
struct person{
int l[4096],r[4096];
int el,er;
bool operator<(person&i)const{
int px[4096]={},ix[4096]={},lp,li;
mul((int*)l,(int*)r,el,er,px,lp);
mul(i.l,i.r,i.el,i.er,ix,li);
return !bigger(px,ix,lp,li);
}
void InPut(){
el=er=0;
int il,ir;
cin>>il>>ir;
while(il)l[el++]=il%10,il/=10;
while(ir)r[er++]=ir%10,ir/=10;
}
}p[4096],k;
void mul(int a[],int b[],int la,int lb,int c[],int&lc){
//自己写
}
bool bigger(int a[],int b[],int la,int lb){
//自己写
}
void sub(int a[],int b[],int la){
//自己写
}
void div(int a[],int b[],int la,int lb,int c[],int&lc){
//自己写
}
int main(){
int n,ans[4096]={},asl=0;cin>>n;k.InPut();
for(int i=0;i<n;i++)p[i].InPut();
sort(p,p+n);
for(int i=0;i<n;i++){
int mk[4096]={},c[4096]={},mkl,cl;
div(k.l,p[i].r,k.el,p[i].er,mk,mkl);
if(bigger(mk,ans,mkl,asl)){
for(int j=0;j<mkl;j++)ans[j]=mk[j];
asl=mkl;
}
mul(k.l,p[i].l,k.el,p[i].el,c,cl);
for(int i=0;i<cl;i++)k.l[i]=c[i];k.el=cl;
}
asl--;
for(;asl>=0;asl--)cout<<ans[asl];
}
${\color{white} enough?}$
我是不会告诉你空白的地方还有字的