当前位置:网站首页>NOIP 2012 提高组 复赛 第一天 第二题 国王游戏 game 数学推导 AC代码(高精度 低精度 乘 除 比较)+60代码(long long)+20分代码(全排列+深搜dfs)
NOIP 2012 提高组 复赛 第一天 第二题 国王游戏 game 数学推导 AC代码(高精度 低精度 乘 除 比较)+60代码(long long)+20分代码(全排列+深搜dfs)
2020-11-08 07:14:08 【osc_56801rv0】
NOIP 2012 提高组 复赛 第一天 第二题 国王游戏 game 数学推导 AC代码(高精度 低精度 乘 除 比较)+60代码(long long)+20分代码(全排列+深搜dfs)
总目录详见:NOIP 提高组 复赛 试题 目录 信奥 历年
在线测评地址:https://www.luogu.com.cn/problem/P1080
数学推导如下:
我们对于国王身后的两个点来分析
队列可能是这样的:
* | Left | Right |
---|---|---|
king: | a0 | b0 |
p1 | a1 | b1 |
p2 | a2 | b2 |
那么我们计算可得ans1=max(a0/b1,a0*a1/b2)
队列也有可能是这样的
* | Left | Right |
---|---|---|
king: | a0 | b0 |
p2 | a2 | b2 |
p1 | a1 | b1 |
那么我们计算可得ans2=max(a0/b2,a0*a2/b1)
考虑ans1最优,那么ans1<ans2,
请注意:
(ans1中的)a0/b1<(ans2中的)a0*a2/b1
(ans1中的)a0*a1/b2>(ans2中的)a0/b2
要保证ans1<ans2一定成立,必须(ans1中的)a0*a1/b2<(ans2中的)a0*a2/b1
即a1/b2<a2/b1
即a1*b1<a2*b2
即,按a*b自小到大排序,可以保证是符合题意的最优解。
从成功率来说,还是比较推崇60分代码。
提供一组测试数据
输入:
5
9999 1
9999 1
9999 2
9999 3
9999 4
9999 5
输出:
19990001999800009999
1.AC代码(高精度 低精度 乘 除 比较)
#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){//高精度*低精度
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++;写此句也能过,但总觉不妥
while(aa[an+1])an++,aa[an+1]+=aa[an]/BASE,aa[an]%=BASE;
}
void div(int x){//高精度/低精度
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--;//去除前导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代码(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分代码(全排列+深搜dfs)
20分代码(全排列+深搜dfs)如下:
#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]所创,转载请带上原文链接,感谢
https://my.oschina.net/u/4381796/blog/4707817
边栏推荐
- C++ 数字、string和char*的转换
- C++学习——centos7上部署C++开发环境
- C++学习——一步步学会写Makefile
- C++学习——临时对象的产生与优化
- C++学习——对象的引用的用法
- C++编程经验(6):使用C++风格的类型转换
- Won the CKA + CKS certificate with the highest gold content in kubernetes in 31 days!
- C + + number, string and char * conversion
- C + + Learning -- capacity() and resize() in C + +
- C + + Learning -- about code performance optimization
猜你喜欢
-
C + + programming experience (6): using C + + style type conversion
-
Latest party and government work report ppt - Park ppt
-
在线身份证号码提取生日工具
-
Online ID number extraction birthday tool
-
️野指针?悬空指针?️ 一文带你搞懂!
-
Field pointer? Dangling pointer? This article will help you understand!
-
HCNA Routing&Switching之GVRP
-
GVRP of hcna Routing & Switching
-
Seq2Seq实现闲聊机器人
-
【闲聊机器人】seq2seq模型的原理
随机推荐
- LeetCode 91. 解码方法
- Seq2seq implements chat robot
- [chat robot] principle of seq2seq model
- Leetcode 91. Decoding method
- HCNA Routing&Switching之GVRP
- GVRP of hcna Routing & Switching
- HDU7016 Random Walk 2
- [Code+#1]Yazid 的新生舞会
- CF1548C The Three Little Pigs
- HDU7033 Typing Contest
- HDU7016 Random Walk 2
- [code + 1] Yazid's freshman ball
- CF1548C The Three Little Pigs
- HDU7033 Typing Contest
- Qt Creator 自动补齐变慢的解决
- HALCON 20.11:如何处理标定助手品质问题
- HALCON 20.11:标定助手使用注意事项
- Solution of QT creator's automatic replenishment slowing down
- Halcon 20.11: how to deal with the quality problem of calibration assistant
- Halcon 20.11: precautions for use of calibration assistant
- “十大科学技术问题”揭晓!|青年科学家50²论坛
- "Top ten scientific and technological issues" announced| Young scientists 50 ² forum
- 求反转链表
- Reverse linked list
- js的数据类型
- JS data type
- 记一次文件读写遇到的bug
- Remember the bug encountered in reading and writing a file
- 单例模式
- Singleton mode
- 在这个 N 多编程语言争霸的世界,C++ 究竟还有没有未来?
- In this world of N programming languages, is there a future for C + +?
- es6模板字符
- js Promise
- js 数组方法 回顾
- ES6 template characters
- js Promise
- JS array method review
- 【Golang】️走进 Go 语言️ 第一课 Hello World
- [golang] go into go language lesson 1 Hello World