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倍。
思路:
该题为大整数运算,因为原数会超过long long的范围,其乘以2后更会超过long long的范围,所以需要用字符串模拟大整数的乘法,得到乘以2后的结果,再判断0~9个数是否一样。

错误代码:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<set>
#include<cmath>
#include<cstring>
#include<queue>
#include<string.h>
using namespace std;
typedef long long ll;
const int maxn=10010;
int v1[10];
int v2[10];
bool isProper(ll n)
{
    ll m=n;
    int i=0,j=0;
    n=n*2;//直接乘以2是不对的,需要模拟大整数乘法
    while(m>0){
        v1[m%10]++;
        m/=10;
    }
    while(n>0){
        v2[n%10]++;
        n/=10;
    }
    for(int i=0;i<10;i++){
        if(v1[i]!=v2[i]){
            return false;
        }
    }
    return true;
    
}
int main(){
    ll n;//n会超过long long范围
    fill(v1,v1+10,0);
    fill(v2,v2+10,0);
    scanf("%lld",&n);
    if(isProper(n)){
        printf("Yes\n");
        printf("%lld\n",2*n);
    }
    else{
        printf("No\n");
        printf("%lld\n",2*n);
    }
    return 0;
}

1023 Have Fun with Numbers (20分)

 

 



AC代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<set>
#include<cmath>
#include<cstring>
#include<queue>
#include<string.h>
using namespace std;
typedef long long ll;
const int maxn=10010;
vector<int> m;
int v1[10];
int v2[10];
bool isProper(vector<int> m,string n)
{
    int temp;
    for(int i=0;i<n.length();i++){
        temp=n[i]-'0';
        v1[temp]++;
    }
    for(int i=0;i<m.size();i++){
        v2[m[i]]++;
    }
    for(int i=0;i<10;i++){
        if(v1[i]!=v2[i]){
            return false;
        }
    }
    return true;
}
int main(){
    string n;
    cin>>n;
    int len=n.length();
    int carry=0;//进位
    int temp=0;
    for(int i=len-1;i>=0;i--){
        temp=(n[i]-'0')*2+carry;
        m.push_back(temp%10);
        carry=temp/10;
    }
    while(carry>0){
        m.push_back(carry%10);
        carry/=10;
    }
    if(isProper(m,n)){
        printf("Yes\n");
    }
    else{
        printf("No\n");
    }
    for(int i=m.size()-1;i>=0;i--){
        printf("%d",m[i]);
    }
    return 0;
}

 

 
上一篇:Leetcode67-二进制求和


下一篇:2. 两数相加