NOIP 2012 T2 国王游戏 (贪心+高精)
2024-09-08 08:35:01
思路:
呃呃网上那么多题解写得都不错…..
就是高精 巨坑。。。
这里展出的是任氏高精(纯自己yy滴)
//By SiriusRen
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,temp[5555],len,A[5555],ans[5555],ans_max;
char s[11],jya[11];
struct Node{
char a[11];
int alen,b;
}node[1005];
bool cmp(Node x,Node y){
int xa=0,ya=0;
for(int i=x.alen-1;~i;i--)xa=xa*10+x.a[i];
for(int i=y.alen-1;~i;i--)ya=ya*10+y.a[i];
return xa*x.b<ya*y.b;
}
int main(){
scanf("%d",&n);
scanf("%s%d",s,&node[0].b);
len=strlen(s)-1;
for(int i=0;i<=len;i++)A[i]=s[len-i]-'0';
for(int i=1;i<=n;i++){
scanf("%s%d",jya,&node[i].b);
node[i].alen=strlen(jya);
for(int j=0;j<node[i].alen;j++)
node[i].a[j]=jya[node[i].alen-j-1]-'0';
}
sort(node+1,node+1+n,cmp);
for(int i=1;i<=n;i++){
memset(temp,0,sizeof(temp));
int res=0,maxx=0;
for(int j=len;~j;j--){
res=res*10+A[j];
temp[j]=res/node[i].b;
if(temp[j])maxx=max(maxx,j);
res=res%node[i].b;
}
for(int j=5000;~j;j--)
if(ans[j]<temp[j]){
for(int j=maxx;~j;j--)
ans[j]=temp[j];
ans_max=maxx;
break;
}
else if(ans[j]>temp[j])break;
memset(temp,0,sizeof(temp));
for(int j=0;j<=len;j++)
for(int k=0;k<node[i].alen;k++)
temp[j+k]+=A[j]*node[i].a[k];
for(int j=0;j<=len+10;j++){
temp[j+1]+=temp[j]/10;
temp[j]=temp[j]%10;
if(temp[j])len=j;
}
for(int j=len;~j;j--)A[j]=temp[j];
}
for(int j=ans_max;~j;j--)printf("%d",ans[j]);
}
最新文章
- MySQL,MariaDB:Undo | Redo [转]
- javascript json转为 go struct 小工具代码
- Apache Virtual Include
- Avoid The Lakes--poj3620
- C#去掉字符串中的汉字
- (76) Clojure: Why would someone learn Clojure? - Quora
- IIS6 伪静态
- FreeRTOS初步认识
- [leetcode-623-Add One Row to Tree]
- zookeeper使用和原理探究
- MyBatis源码解析(一)——执行流程
- 环境变量(1):PATH的修改
- RabbitMQ服务端配置详解
- Git tag 标签操作
- IDEA批量修改变量名操作
- MySQL数据库启停
- SqlServer日常积累(二)
- TFS自动签出解决方案sln或者项目文件csproj的解决办法
- 阿里云CentOS7部署ASP.NET Core
- Robust Online Visual Tracking with a Single Convolutional Neural Network