当前位置:网站首页>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)
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)
2020-11-08 07:14:00 【osc_56801rv0】
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;
}
版权声明
本文为[osc_56801rv0]所创,转载请带上原文链接,感谢
边栏推荐
- 鼠标变小手
- Wechat applet request reported 400 error @ requestbody failed to receive
- Face recognition: attack types and anti spoofing techniques
- 你的主机中的软件中止了一个已建立的连接。解决方法
- QT hybrid Python development technology: Python introduction, hybrid process and demo
- ubuntu实时显示cpu、内存占用率
- Application of bidirectional LSTM in outlier detection of time series
- Goland 编写含有template的程序
- Sum up some useful functions
- Animation techniques and details you may not know
猜你喜欢
Basic knowledge of C + +
Problems of Android 9.0/p WebView multi process usage
Hand tearing algorithm - handwritten singleton mode
2020-11-07:已知一个正整数数组,两个数相加等于N并且一定存在,如何找到两个数相乘最小的两个数?
Animation techniques and details you may not know
Swiper window width changes, page width height changes lead to automatic sliding solution
SQL Server 2008R2 18456 error resolution
高并发,你真的理解透彻了吗?
Lay UI left tree Dtree right list table
On the stock trading of leetcode
随机推荐
Goland 编写含有template的程序
About the promotion of the whole stack of engineers, from the introduction to give up the secret arts, do not click in to have a look?
GET,POST,PUT,DELETE,OPTIONS用法与说明
[solution] distributed timing task solution
2020天翼智能生态博览会中国电信宣布5G SA正式规模商用
Application of bidirectional LSTM in outlier detection of time series
Do you really understand the high concurrency?
Supervisor process management installation and use
Brief history of computer
Android Basics - RadioButton (radio button)
Bili Bili common API
CPP (3) what is cmake
c# 表达式树(一)
Experience the latest version of erofs on Ubuntu
laravel8更新之速率限制改进
C/C++编程笔记:C语言相比其他编程语言,有什么不一样的优势?
WPF personal summary on drawing
C语言I博客作业03
Python image recognition OCR
Fortify漏洞之 Privacy Violation(隐私泄露)和 Null Dereference(空指针异常)