【洛谷】P1015 [NOIP1999 普及组] 回文数

比眉伴天荒 2022-09-06 01:28 217阅读 0赞

# 1. 分析 #

判断是否可以在指定步数内以某中进制加法构造出一个回文数 ：  
需要注意的是：

*  指定步数得到的数可能会很大
 *  100位之内的数肯定只能用字符串处理了。
 *  本题需要注意特殊的取值N =16。可能乍一想，会认为使用单纯的`int arr[]` 不行，因为需要存储诸如`A,B`这样的字符，但其实可以将`A,B`存储成10,11就可以了。所以还是建议使用`int arr`处理。【因为使用int型处理会方便进行加减计算。】

# 2. 代码 #

下面这版代码存在问题，有一个样例无法通过，下次再继续修改~

#include<string> 
    #include<iostream>
    using namespace std;
    const int maxN = 10005;
    
    int N;
    string M; //M 的值很大，必须使用string 存储 
    //判断是否回文 
    bool is_recu(int arr[],int cnt){ 
    	//回文判断
    	for (int i = 0;i <= cnt/2;i++){ 
    		if(arr[i] != arr[cnt-1-i]){  // 因为cnt最后多加了一次，所以这里要 -1 
    			return false;
    		}
    	}
    	return true;
    }
    
    
    int main(){ 		
    	cin >> N >> M; // 输入进制，输入初始值 
    	int step = 0;
    	int len;
    	len = M.length();
    	int arr_1[maxN] ;//顺序
    	int arr_2[maxN]; //逆序 
    	for (int i = 0; i< M.length(); i++){ 
    		arr_1[i] = M[i] - '0';
    		arr_2[i] = M[len-1-i] - '0';		
    	}
    	//cout <<"\n";
    	
    	while(step <= 30){ 
    		if ( is_recu(arr_1,len)){ 
    			cout << "STEP="<< step<<"\n"; // 支持对STEP=0的输出 
    			return 0;
    		}
    		int sum[maxN] ;			
    		int temp = 0;
    		for (int i = 0;i< len;i++){ 		
    			sum[i] = (arr_1[i] + arr_2[i] + temp) % N; 			
    			temp = (arr_1[i] + arr_2[i] + temp) / N; 
    		}
    		if(temp ){ 
    			sum[len] = temp;
    			len++;
    		}
    		
    		//重新赋值 
    		for (int i = 0;i < len;i++){ 
    			cout << sum[i] ;
    			arr_1[i] = sum[i]; //顺值 
    			arr_2[i] = sum[len-1-i]; //反值 
    		}
    		cout <<"\n";
    		//cout <<"STEP="<<step<<" "<< M <<"\n";
    		step ++;
    	}
    	cout <<"Impossible!";
    }

这里给出一个没有bug的代码，如下：

#include <cstdio>
    #include <cstring>
    const int maxN=303;//一次加法顶多多一位，所以顶多多30位，也就是130位左右。我开大一点，开到300.
    int n,a[maxN],l;
    char c[maxN],d[maxN];//使用字符串存储 => 其实是可以使用数组存储的 
    
    inline void add()
    { 	 
    	for (int i=0;i<l;++i)//下面这个就是为了逆序 
    		d[l-i-1]=c[i];
    		
    	l+=2;//可能有进位，所以我们干脆在前面先多空个两位
    	for (int i=0;i<l;++i)
    	{ 
    		c[i]+=d[i];
    		//下面这种写法较优 
    		if (c[i]>=n) c[i+1]++,c[i]-=n;
    	}
    	while (!c[l-1]) --l;//大不了多余的前导0再减回来嘛~~简化思维~~
    }
    
    inline bool pd()
    { 
    	for (int i=0;i<l;++i)
    		if (c[i]!=c[l-1-i]) return false;
    	return true;
    }
    
    
    int main()
    { 
    	scanf("%d%s",&n,c);
    	l=strlen(c);
    	for (int i=0;i<l;++i)
    	{ 
    		if (c[i]>='0' && c[i]<='9') c[i]-='0'; //这得到的不是int类型吗？但是c被定义成字符类型？ 
    		else c[i]=c[i]-'A'+10;
    	}
    	for (int i = 0;i<l;i++){ 
    		printf("%d",c[i]);
    	}
    	int step=0;
    	while (!pd())
    	{ 
    		++step;
    		if (step>30) break;
    		add();
    	}
    	if (step<=30) printf("STEP=%d\n",step);
    	else puts("Impossible!");
    	return 0;
    }

可能会下列代码：

if (c[i]>='0' && c[i]<='9') c[i]-='0'; //这得到的不是int类型吗？但是c被定义成字符类型？ 
    		else c[i]=c[i]-'A'+10;

存在疑惑，但实际上我们照下面这么理解就好了：  
![在这里插入图片描述][5292a8ec54bb4e6d95fb18939e422deb.png]

[5292a8ec54bb4e6d95fb18939e422deb.png]: /images/20220829/fa1b888a5c68454dbb4b1ff727489f28.png