社区讨论

请问这题该怎么构造?

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分。请问 10710^7 位的数 ×107×10^7 位的数有什么小于 O(nlogn)O(nlogn) 的算法吗?
代码如下:
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 条回复,欢迎继续交流。

正在加载回复...