社区讨论
请问这题该怎么构造?
P8482 「HGOI-1」Number参与者 4已保存回复 5
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 5 条
- 当前快照
- 1 份
- 快照标识符
- @lo7zcky8
- 此快照首次捕获于
- 2023/10/27 10:14 2 年前
- 此快照最后确认于
- 2023/10/27 10:14 2 年前
Subtask #1、Subtask #2、Subtask #3用了贪心+高精乘,得了50分;Subtask #4、Subtask #5只用了贪心,25分。总分75分。请问 位的数 位的数有什么小于 的算法吗?
代码如下:
CPP#include<bits/stdc++.h>
using namespace std;
int num[10],la,lb,lc,a[5010],b[5010],c[10010];
string sa,sb;
bool numcmp(string a,string b){
if(a.length()!=b.length()) return a.length()<b.length();
return a<b;
}
int main(){
for(int i=0;i<10;i++) scanf("%d",&num[i]);
for(int i=9;i>=0;i--){
if(!numcmp(sa,sb)) swap(sa,sb);
if(sa.length()<sb.length()){
if(num[i]%2){
for(int j=0;j<num[i]/2+1;j++) sa+=char(i+'0');
for(int j=0;j<num[i]/2;j++) sb+=char(i+'0');
}else{
sa+=char(i+'0');
if(numcmp(sa,sb)){
for(int j=0;j<num[i]/2;j++) sa+=char(i+'0');
for(int j=0;j<num[i]/2-1;j++) sb+=char(i+'0');
}else{
for(int j=0;j<num[i]/2-1;j++) sa+=char(i+'0');
for(int j=0;j<num[i]/2;j++) sb+=char(i+'0');
}
}
}else{
if(num[i]%2){
for(int j=0;j<num[i]/2+1;j++) sa+=char(i+'0');
for(int j=0;j<num[i]/2;j++) sb+=char(i+'0');
}else{
for(int j=0;j<num[i]/2;j++) sa+=char(i+'0');
for(int j=0;j<num[i]/2;j++) sb+=char(i+'0');
}
}
}
la=sa.length();
lb=sb.length();
if(la+lb>5000){
cout<<sa<<endl<<sb;
return 0;
}
lc=la+lb-1;
for(int i=0;i<la;i++) a[i]=sa[la-i-1]-'0';
for(int i=0;i<lb;i++) b[i]=sb[lb-i-1]-'0';
for(int i=0;i<la;i++){
for(int j=0;j<lb;j++) c[i+j]+=a[i]*b[j];
}
for(int i=0;i<lc;i++){
if(c[i]>9){
c[i+1]+=c[i]/10;
c[i]%=10;
}
}
while(c[lc]){
if(c[lc]>9){
c[lc+1]+=c[lc]/10;
c[lc]%=10;
}
lc++;
}
putchar('1');
putchar('\n');
for(int i=lc-1;i>=0;i--) putchar(c[i]+'0');
return 0;
}
回复
共 5 条回复,欢迎继续交流。
正在加载回复...