Game mathematical derivation AC code (high precision and low precision multiplication and division comparison) + 60 code (long long) + 20 point code (Full Permutation + deep search DFS)

NOIP 2012 Improvement group The rematch The first day The second question is King's game game   Mathematical derivation AC Code ( High precision   Low precision ride except Compare )+60 Code (long long)+20 Code division ( Full Permutation + Deep search dfs)

For the general catalogue, please refer to ：NOIP Improvement group The rematch test questions Catalog Xinao Calendar year

Online evaluation address ：https://www.luogu.com.cn/problem/P1080

The mathematical derivation is as follows ：

We analyze the two points behind the king

The queue might look like this ：

*	Left	Right
king:	a0​	b0​
p1	a1​	b1​
p2	a2​	b2​

So we can calculate that ans1​=max(a0/b1,a0*a1/b2​​)

The queue could be like this

*	Left	Right
king:	a0​	b0​
p2	a2​	b2​
p1	a1​	b1​

So we can calculate that ans2​=max(a0/b2,a0*a2/b1​​)

consider ans1 The optimal , that ans1<ans2,

Please note that :

(ans1 Medium )a0/b1<(ans2 Medium )a0*a2/b1

(ans1 Medium )a0*a1/b2>(ans2 Medium )a0/b2

Make sure that ans1<ans2 It must be true , must (ans1 Medium )a0*a1/b2<(ans2 Medium )a0*a2/b1

namely a1/b2<a2/b1

namely a1*b1<a2*b2

namely , Press a*b Sort from small to large , It can be guaranteed that it is the optimal solution to the problem .

In terms of success rate , It's still highly recommended 60 Code division .

Provide a set of test data

 Input ：
5
9999 1
9999   1
9999 2
9999 3
9999 4
9999 5
 Output ：
19990001999800009999

1.AC Code ( High precision   Low precision ride except Compare )

#include <bits/stdc++.h>
#define maxn 1010
#define BASE 10000
using namespace std;
int n,aa[maxn],an,bb[maxn],bn,cc[maxn],cn;
struct node{
	int a,b,c;
}q[maxn];
int cmp(node a,node b){
	return a.c<b.c;
}
void mul(int x){// High precision * Low precision  
	int i;
	for(i=1;i<=an;i++)
		aa[i]=aa[i]*x;
	for(i=1;i<=an;i++){
		aa[i+1]+=aa[i]/BASE;
		aa[i]%=BASE;
	}
	//if(aa[an+1])an++; You can also write this sentence , But I don't think it's right  
	while(aa[an+1])an++,aa[an+1]+=aa[an]/BASE,aa[an]%=BASE;	
}
void div(int x){// High precision / Low precision  
	int i,yu;
	yu=0;
	for(i=an;i>=1;i--){
		bb[i]=(aa[i]+yu*BASE)/x;
		yu=(aa[i]+yu*BASE)%x;
	}
	bn=an;
	while(!bb[bn])bn--;// Remove the lead 0 
}
int compare(){
	if(bn>cn)return 1;//bb>cc
	if(bn<cn)return -1;//bb<cc
	for(int i=bn;i>=1;i--)//bb==cc
		if(bb[i]>cc[i])return 1;//bb>cc
		else if(bb[i]<cc[i])return -1;//bb<cc
	return 0;//bb==cc
}
int main(){
	int i,j;
	scanf("%d",&n);
	for(i=0;i<=n;i++)scanf("%d%d",&q[i].a,&q[i].b),q[i].c=q[i].a*q[i].b;
	sort(q+1,q+1+n,cmp);
	aa[1]=1,an=1;
	cc[1]=q[0].a/q[1].b,cn=1;
	for(i=1;i<=n;i++){
		mul(q[i-1].a);
		div(q[i].b);
		if(compare()==1){
			cn=bn;
			for(j=bn;j>=1;j--)cc[j]=bb[j];
		}
	}
	printf("%d",cc[cn]); 
	for(i=cn-1;i>=1;i--)printf("%04d",cc[i]);
	return 0;
}

2.60 Code (long long)

#include <bits/stdc++.h>
#define LL long long
#define maxn 1100
using namespace std;
struct node{
	LL a,b,c;
}q[maxn];
int cmp(node a,node b){
	return a.c<b.c;
}
LL mx,a=1;
int main(){
	int n,i;
	scanf("%d",&n);
	for(i=0;i<=n;i++){
		scanf("%d%d",&q[i].a,&q[i].b);
		q[i].c=q[i].a*q[i].b; 
	}
	sort(q+1,q+1+n,cmp);
	for(i=1;i<=n;i++)
		a*=q[i-1].a,mx=max(mx,a/q[i].b);
	printf("%lld\n",mx);
	return 0;
}

 3.20 Code division ( Full Permutation + Deep search dfs)

 20 Code division ( Full Permutation + Deep search dfs) as follows ：

#include <bits/stdc++.h>
using namespace std;
int a[15],b[15],c[15],vis[15],n,mn=2000000000;
void dfs(int step){
	int i;
	if(step==n+1){
		int j,aa=1,mx=0;
		for(j=1;j<=n;j++){
			aa=aa*a[c[j-1]];
			mx=max(mx,aa/b[c[j]]);
		}
		mn=min(mx,mn);
		return;
	}
	for(i=1;i<=n;i++)
		if(!vis[i]){
			vis[i]=1;
			c[step]=i;
			dfs(step+1);
			vis[i]=0;
		}
}
int main(){
	int i;
	scanf("%d",&n);
	for(i=0;i<=n;i++)scanf("%d%d",&a[i],&b[i]); 
	dfs(1);
	printf("%d\n",mn);
	return 0;
}