正文
PAT 甲级 1023 Have Fun with Numbers (20 分)(permutation是全排列题目没读懂)
小程序:扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序
【扫一扫了解最新限行尾号】
复制小程序
1023 Have Fun with Numbers (20 分)
Notice that the number 123456789 is a 9-digit number consisting exactly the numbers from 1 to 9, with no duplication. Double it we will obtain 246913578, which happens to be another 9-digit number consisting exactly the numbers from 1 to 9, only in a different permutation. Check to see the result if we double it again!
Now you are suppose to check if there are more numbers with this property. That is, double a given number with k digits, you are to tell if the resulting number consists of only a permutation of the digits in the original number.
Input Specification:
Each input contains one test case. Each case contains one positive integer with no more than 20 digits.
Output Specification:
For each test case, first print in a line "Yes" if doubling the input number gives a number that consists of only a permutation of the digits in the original number, or "No" if not. Then in the next line, print the doubled number.
Sample Input:
1234567899
Sample Output:
Yes
2469135798
解题思路:
给定一个数,乘以2之后,各个数位的出现次数,是否与乘之前是否相同,相同输出Yes,否认输出No,然后下一行打印出乘2之后的各个数位。
这个题目是属于超大数运算的类型,题目给出的最高数位是20位,那么即便是用最高的unsigned long long 也会面临溢出的情况,所以输入和输出,只能用string,诸位乘2,然后再记录每一位出现的次数,相比较就行。
大数乘法!全排列的意思是:各个数字出现的次数分别相同!
AC代码:
#include<bits/stdc++.h>
using namespace std;
char a[];
char b[];
int ori[];
int ne[];
int main(){
memset(ori,,sizeof(ori));
memset(ne,,sizeof(ne));
cin>>a;
//先反着放
int l=strlen(a);
for(int i=l-;i>=;i--){
b[l-i]=a[i];
ori[a[i]-'']++;
}
//大数乘法
int x=;
for(int i=;i<=l;i++){
int y=b[i]-'';
y*=;y+=x;
b[i]=y%+'';
x=y/;
ne[b[i]-'']++;
}
int l2=l;
if(x!=){
l2++;
b[l2]=x+'';
ne[b[l2]-'']++;
}
//判断
int f=;
for(int i=;i<=;i++){
if(ne[i]!=ori[i]){
f=;
break;
}
}
if(f){
cout<<"Yes"<<endl;
}else{
cout<<"No"<<endl;
}
for(int i=l2;i>=;i--){
cout<<b[i];
}
return ;
}