1023. Have Fun with Numbers (20)
时间限制
400 ms
内存限制
65536 kB
代码长度限制
16000 B
判题程序
Standard
作者
CHEN, Yue
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 file 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
破解过程：
一开始，想要用next_permutation,其实是想要看投机取巧可不可以通过。
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <cmath>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
long long input,output;
int main(){
cin>>input;
output=2*input;
string str_in=to_string(input);
string str_out = to_string(output);
int flag=0;
// int length=str_in.length();
do{
if(str_out == str_in){
flag=1;
}
}while(next_permutation(str_in.begin(),str_in.end()));
if(flag){
cout<<"Yes"<<endl;
}else{
cout<<"No"<<endl;
}
cout<<output<<endl;
return 0;
}
结果：
有3个测试点运行超时，那么为什么超时，想想都肯定知道一定是循环的时候出的问题。
其实之前还有其他的思路，不只是这一题，每次做题的时候总是会有很多的种思路，多个思路反而会干扰自己，怎么办？尽量多刷题吧；
第二种想法，就是用建一个散列表，题目已经明显说了1~9的数字，那么可以选择用数组【】或者map，这里我觉得数组应该很方便。试着编一下。
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <cmath>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
long long input,output;
int main(){
cin>>input;
output=2*input;
string str_in=to_string(input);
string str_out = to_string(output);
int arr_in[10]={
0},arr_out[10]={
0};
for(auto x:str_in){
arr_in[x-'0']++;
}
for(auto x:str_out){
arr_out[x-'0']++;
}
int flag=1;
for(int i=1;i<10;i++){
if(arr_in[i]!=arr_out[i]){
flag=0;
}
}
if(flag){
cout<<"Yes"<<endl;
}else{
cout<<"No"<<endl;
}
cout<<output<<endl;
return 0;
}
还是有错误，说明第一种想法逻辑正确，第二种想法的逻辑可能就编写错误了。自己再检查检查。
排除不可能有的错误，数据长度，由于第一种时候就是long long，可以正常通过，所以不想把时间浪费在思考这个对不对上。
于是，我重新阅读题意，修改一个小地方，遍历比较两个散列记录数组的时候，我把原来的从1开始改为了从0开始，因为之前一直关注例程，要注意inPUT给出的数据要求是输入一个正数。
改了之后的程序：
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <cmath>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
long long input,output;
int main(){
cin>>input;
output=2*input;
string str_in=to_string(input);
string str_out = to_string(output);
int arr_in[10]={
0},arr_out[10]={
0};
for(auto x:str_in){
arr_in[x-'0']++;
}
for(auto x:str_out){
arr_out[x-'0']++;
}
int flag=1;
for(int i=0;i<10;i++){
if(arr_in[i]!=arr_out[i]){
flag=0;
}
}
if(flag){
cout<<"Yes"<<endl;
}else{
cout<<"No"<<endl;
}
cout<<output<<endl;
return 0;
}
可以看到对了一个点，又可以得到两分。那么下面的三个点，为什么显示答案错误呢？看这种排列，总感觉错误会是在同一个关键的地方。
前面自己说了感觉long long没有问题，那么long long最大可以是多少呢？可以存放10进制的20位数吗？long long 是64位，也就是2的64次方，应该拿他与10的20次方进行比较。
2的63次方-1：
可以看到换算成10进制的时候是19位，不满足题目要求的20位，怎么办呢？看来是处理大数问题。祭出晴神宝典。
重点总结一下，数据长度决定数据类型的采用：
整型int类型：占32位。最大值为2的31次方-1。绝对值在10进制的9次方，就是9位数以内的整数可以定义为int类型；
长整型long long：一个整数占64位，最大值为2的63次方-1。也就是说，如果题目要求的整数取值范围超过2147483647，例如10的10次方或者10的18次方，就是一个10进制数位数为10个以上或者18个以上，就得用long long来存储。但是如果是20位数及其以上的话，那么long long类型也不能存储，需要使用大数据类型。
对于浮点型，只需要记住一点，不要使用float，碰到浮点数的数据都应该使用double来存储。
回归这道题，结合《算法笔记》，以及数据长度，可以得出应该是自己在数据长度上面出了问题，看来需要以string类型接收输入数据，自己定义其乘法运算。
其他地方也大多是采用大数据运算的方式解决这道题，刚才我又想到了一种思路，既然是20位，那么对半分为before高10位数，和last10位，那么就肯定可以在long long进行计算了，只需要注意每个要比较还有就是后10位数的最高位可能产生非0进位，这个进位要加在before数才是真正的高位数据。暂时先写到这里，还没有做完，到数学时间了，以后再说.
以上算法思想编写的程序如下：
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <cmath>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
string str_in,str_out,str_before,str_last;
int main(){
cin>>str_in;
int len_in=str_in.length();
str_before = str_in.substr(0,len_in/2);
int len_before =str_before.length();
str_last = str_in.substr(len_in/2,len_in-len_before);
int num_before=stoll(str_before);
int num_last = stoll(str_last);
int jin=0;
num_before*=2;
num_last*=2;
str_last=to_string(num_last);
if( str_last.length() != len_in-len_before ){
jin=1;
str_last=str_last.substr(1);
}
num_before+=jin;
str_before=to_string(num_before);
int arr_in[10]={
0},arr_out[10]={
0};
for(auto x:str_in){
arr_in[x-'0']++;
}
for(auto x:str_before){
arr_out[x-'0']++;
}
for(auto x:str_last){
arr_out[x-'0']++;
}
int flag=1;
for(int i=0;i<10;i++){
if(arr_in[i]!=arr_out[i]){
flag=0;
}
}
if(flag){
cout<<"Yes"<<endl;
}else{
cout<<"No"<<endl;
}
cout<<str_before<<str_last<<endl;
return 0;
}
但是结果还是有错误。
结果如图，失去耐心，以后遇到这种图，尽量不要浪费时间去想其他的了，直接搞大数据四则运算模板。
这个时候就背模板吧，PAT考场上总共3小时，没有功夫浪费在自己不确定的新奇解题方法上：
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <cmath>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
struct bign{
int d[21];
int len;
bign(){
memset(d,0,sizeof(d));
len = 0;
}
};
bign change(char str[]){
bign a;
a.len = strlen(str);
for(int i=0;i<a.len;i++){
a.d[i] = str[a.len - i - 1] - '0';
}
return a;
}
bign multi(bign a,int b){
//高精度乘法
bign c;
int carry =0; //进位
for(int i=0;i<a.len;i++){
int temp = a.d[i]*b + carry;
c.d[c.len++] = temp%10; //个位作为该位结果
carry = temp/10; //高位部分作为新的进位
}
while(carry!=0){
//和加法不一样，乘法的进位可能不止1位，因此用while
c.d[c.len++] = carry%10;
carry /=10;
}
return c;
}
bool Judge(bign a,bign b){
//判断b的所有位是否是a的某个排列
if(a.len != b.len ){
return false;
}
int count[10] = {
0};
for(int i=0;i<a.len;i++){
count[a.d[i]]++; //数位a.d[i]对应的count值加1
count[b.d[i]]--;
}
for(int i=0;i<10;i++){
if(count[i]!=0){
return false;
}
}
return true;
}
void print(bign a){
for(int i=a.len-1;i>=0;i--){
printf("%d",a.d[i]);
}
}
int main(){
char str[21];
gets(str); //输入数据
bign a = change(str); //转换为bign
bign mul = multi(a,2); //计算a*2
if(Judge(a,mul) == true){
printf("Yes\n");
}else{
printf("No\n");
}
print(mul);
return 0;
}
京公网安备 11010502036488号