打卡信奥刷题（3239）用C++实现信奥题 P8482 「HGOI-1」Number

rogeliu

385人浏览 · 2026-05-10 10:14:26

rogeliu · 2026-05-10 10:14:26 发布

P8482 「HGOI-1」Number

题目背景

$bh1234666\text{bh1234666}$ 正在学习乘法！

题目描述

$bh1234666\text{bh1234666}$ 有一定数量的数字 $\sim 9$ ，现在他想让你寻找一种分配方案，将它们分成两个整数，使得他们的乘积 $p$ 最大。

由于 $bh1234666\text{bh1234666}$ 不喜欢太大的数，所以你只需要输出两个非负整数，使它们的乘积等于最大乘积 $p$ ，但是这两个整数 $\sim 9$ 的数量不能等于给定的数量（任意一个数字数量不相等即可，不考虑前导零）。

$bh1234666\text{bh1234666}$ 是很善良的，如果 $\sim 9$ 的数量等于给定的数量了，你依旧可以得到的一半的分。

输入格式

第一行十个整数 $c0,c1,⋯c9c_0,c_1,\cdots c_9$ ，分别表示 $\sim 9$ 的个数。

输出格式

共两行每行一个非负整数，分别表示你给出的两个非负整数。

输入输出样例 #1

输入 #1

1 2 3 2 1 1 2 1 2 1

输出 #1

13949030
620572547

说明/提示

样例解释

最大可能乘积为 $97643210 \times 88653221=13949030 \times 620572547=8656385075279410$ 。

若输出 $97643210 \times 88653221$ 则只能得到一半的分，因为 $0∼90\sim 9$ 出现的次数与给定的相同。

数据范围及约定

本题采用捆绑测试，共有 $5$ 个 $subtask\text{subtask}$ ，最终分数为所有 $subtask\text{subtask}$ 分数之和。

$\def\arraystretch{1.5} \begin{array}{|c|c|c|}\hline \textbf{Task} & \textbf{Score} & \sum c_i\le \cr\hline 1 & 10 & 20 \cr\hline 2 & 20 & 100 \cr\hline 3 & 20 & 5000 \cr\hline 4 & 20 & 10^6 \cr\hline 5 & 30 & 10^7 \cr\hline \end{array}$

对于 $100%100\%$ 的数据，保证 $\le c_i$ ， $∑ci≤107\sum c_i \le 10^7$ 。

说明

本题有 $spj\text{spj}$ ，两数乘积正确得一半的分，数量与给出的不同且乘积正确得全部分数。故每一 $subtask\text{subtask}$ 的得分为其中所有数据点得分的最小值。

C++实现

#include<bits/stdc++.h>
using namespace std;
int c[10],len1,len2,res1[10000001],res2[10000001];
int main(){
	for(int i=0;i<10;++i)cin>>c[i];
	bool f=0;
	int cnt=0;
	for(int i=9;~i;--i){
		for(int j=0;j<c[i];++j){
			++cnt;
			if(!f){
				if(cnt&1)res1[++len1]=i;
				else res2[++len2]=i;
			}
			else{
				if(cnt&1)res2[++len2]=i;
				else res1[++len1]=i;
			}
			if(!f&&len1==len2&&res1[len1]>res2[len2])
				f=1;
		}
	}
	int l1=1,l2=1;
	if(res1[len1]==0){
		for(int i=1;i<=len1;++i){
			if(res1[i]&1)res1[i+1]+=10;
			res1[i]/=2;
		}
		if(!res1[1])l1=2;
		for(int i=1;i<=len2;++i)res2[i]+=res2[i];
		for(int i=len2;i;--i)res2[i-1]+=res2[i]/10,res2[i]%=10;
		if(res2[0])l2=0;
	}
	else if(res2[len2]==0){
		for(int i=1;i<=len2;++i){
			if(res2[i]&1)res2[i+1]+=10;
			res2[i]/=2;
		}
		if(!res2[1])l2=2;
		for(int i=1;i<=len1;++i)res1[i]+=res1[i];
		for(int i=1;i<=len1;++i)res1[i+1]+=res1[i]/10,res1[i]%=10;
		if(res1[len1+1])l1=0;
	}
	for(int i=l1;i<=len1;++i)putchar(res1[i]+48);
	putchar('\n');
	for(int i=l2;i<=len2;++i)putchar(res2[i]+48);
	return 0;
}