2020牛客暑期多校训练营（第九场）

A. Groundhog and 2-Power Representation $\looparrowright$

题目描述

Groundhog took a math class. In this class, his math teacher said, any positive integer can be represented by the power of $2$ . For example, $137=2^7+2^3+2^0$ .
And powers are expressed in parentheses. That is, $a(b)$ stands for $a^b$ . Therefore, $137$ can be expressed as $137=2(7)+2(3)+2(0)$ .
Further more,for $7=2^2+2+2^0$ is expressed with $2$ , $3=2+2^0$ ,137 can be finally expressed as $137=2(2(2)+2+2(0))+2(2+2(0))+2(0)$ .
Another example, $1315=2^{10}+2^8+2^5+2+1 =$ $ 2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)$.
Groundhog feels amazing and wants you to write a program to simulate the above content. You need to read in an expression that is a power of $2$ and calculate its value.

输入描述

Given a string, indicating the power representation.

输出描述

Output the original number.

示例1

输入

1	2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

输出

备注

The range of answers is $[10,10^{180}]$ ，and the length of the input data shall not exceed $20000$ .

分析

题面的本质是定义了一个表达式，然后计算表达式的值；而众所周知， $\text{Python}$ 的 $\text{eval}$ 函数可以直接输出表达式的值。
题中定义 $a(b)$ 为 $a^b$ ，而 $\text{Python}$ 中认为 $a\ast\ast (b)$ 为 $a^b$ 。因此，只需要将表达式中的 $($ 替换为 $\ast\ast($ ，就能用 $\text{eval}$ 函数计算表达式的值。

代码

"""***************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第九场） Problem A
Date: 9/3/2020
Description: The Basis Of Python
***************************************************"""
print(eval(input().replace('(','**(')))

I. Groundhog Looking Dowdy $\looparrowright$

题目描述

Today, ZLZX has a mysterious case, Orange lost his down jacket hanging in his dorm room. Under the expectations of everyone, detective Groundhog took his small spoon of the artifact and started the journey to solve the case.
After an in-depth investigation of the northernmost mysterious room on each floor, Groundhog discovered $n$ mysterious numbers. As long as the clues conveyed by these numbers are deciphered, he can reveal the truth of the matter. The deciphering method is, using these numbers to generate two positive integers without leading zeros, and minimizing the product of these two positive integers is the final clue.
Then Groundhog wants to know what the smallest product is?
As he continued to investigate in the room west of the new building, he gave you the question.
Concise meaning, given $n$ numbers between $0$ and $9$ , use them to make two positive integers without leading zeros to minimize the product.

输入描述

The first line of input is a single integer $T$ , the number of test cases.
For each set of data, each test case begins with a single integer $n$ , the count of numbers.
The next line are $n$ numbers.

输出描述

For each set of case, an integer is output, representing the smallest product.

示例1

输入

1
2
3

1
4
1 2 2 1

输出

示例2

输入

输出

1
2

1223
10

备注

${ 1 \leqslant T \leqslant 1000}$ , $2 \leqslant n \leqslant 100000$ , ${ 1 \leqslant \sum n \leqslant 1000000}$ .
There are at least two Numbers that are guaranteed not to be zero.
The Numbers range between $[0,9]$ .

分析

若不考虑前导零的限制，取 $x$ 为 $n$ 个数中的最小值， $y$ 为其余 $n-1$ 个数组合起来的最小整数， $x\times y$ 即为最小乘积。
考虑前导零后， $x$ 为 $n$ 个数中的最小正整数， $y$ 为其余 $n-1$ 个数组合起来的最小正整数。具体方法为：将 $n$ 个数从小到大排序，取最小的正整数为 $x$ ；在剩余 $n-1$ 个数中，取最小正整数为 $y$ 的最高位，然后向 $y$ 的低位补零，最后向 $y$ 的低位从小到大不正整数。最后模拟个位数乘多位数的乘法输出 $x\times y$ 。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第九场） Problem I
Date: 9/3/2020
Description: Simulation
*******************************************************************/
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
const int N=100146;
vector<short>ans;
short a[N];
short y[N],x;
int n;
int _;
int main(){
	for(cin>>_;_;_--){
		scanf("%d",&n);
		int i;
		for(i=1;i<=n;i++){
			scanf("%hd",a+i);
		}
		sort(a+1,a+1+n);
		int pos;//不为0的最小值
		for(pos=1;pos<=n;pos++){
			if(a[pos]){
				break;
			}
		}
		x=a[pos];
		int len=0;
		for(i=pos+1;i<=n;i++){
			y[++len]=a[i];
			if(i==pos+1){
				int num=pos-1;
				while(num--){
					//补零
					y[++len]=0;
				}
			}
		}
		// debug
		// cout<<x<<endl;
		// for(i=1;i<=len;i++){
		// 	cout<<y[i];
		// }
		// cout<<endl;
		reverse(y+1,y+1+len);
		//debug
		// for(i=1;i<=len;i++){
		// 	cout<<y[i];
		// }
		// cout<<endl;
		short carry=0;
		ans.clear();
		//模拟乘法
		for(i=1;i<=len;i++){
			short num=x*y[i]+carry;
			carry=num/10;
			ans.push_back(num%10);
		}
		if(carry){
			ans.push_back(carry);
		}
		reverse(ans.begin(),ans.end());
		for(i=0;i<ans.size();i++){
			printf("%hd",ans[i]);
		}
		putchar('\n');
	}
	return 0;
}