1.2.5 USACO Dual Palindromes 双重回文数（进制转换回文数）

雨点打透心脏的1/2处 2023-07-13 03:33 9阅读 0赞

**Dual Palindromes**  
**Mario Cruz (Colombia) & Hugo Rickeboer (Argentina)**

A number that reads the same from right to left as when read from left to right is called a palindrome. The number 12321 is a palindrome; the number 77778 is not. Of course, palindromes have neither leading nor trailing zeroes, so 0220 is not a palindrome.

The number 21 (base 10) is not palindrome in base 10, but the number 21 (base 10) is, in fact, a palindrome in base 2 (10101).

Write a program that reads two numbers (expressed in base 10):

*  N (1 <= N <= 15)
 *  S (0 < S < 10000)

and then finds and prints (in base 10) the first N numbers strictly greater than S that are palindromic when written in two or more number bases (2 <= base <= 10).

Solutions to this problem do not require manipulating integers larger than the standard 32 bits.

### PROGRAM NAME: dualpal ###

### INPUT FORMAT ###

A single line with space separated integers N and S.

### SAMPLE INPUT (file dualpal.in) ###

3 25

### OUTPUT FORMAT ###

N lines, each with a base 10 number that is palindromic when expressed in at least two of the bases 2..10. The numbers should be listed in order from smallest to largest.

### SAMPLE OUTPUT (file dualpal.out) ###

26
    27
    28

翻译：[https://www.luogu.com.cn/problem/P1207][https_www.luogu.com.cn_problem_P1207]

## 题目背景 ##

如果一个数从左往右读和从右往左读都是一样，那么这个数就叫做“回文数”。例如，1232112321 就是一个回文数，而 7777877778 就不是。当然，回文数的首和尾都应是非零的，因此 02200220 就不是回文数。

事实上，有一些数（如 2121 ），在十进制时不是回文数，但在其它进制（如二进制时为 1010110101 ）时就是回文数。

## 题目描述 ##

给定两个十进制数 n,sn,s，然后找出前 nn 个满足大于 ss 且在不少于两种进制（二进制至十进制）上是回文数的十进制数，输出到文件上。

本问题的解决方案不需要使用大于 3232 位的整型数

## 输入格式 ##

只有一行，用空格隔开的两个正整数 n,sn,s。

## 输出格式 ##

nn 行, 每行一个满足上述要求的数，并按从小到大的顺序输出。

## 输入输出样例 ##

**输入 \#1**复制

3 25

**输出 \#1**复制

26
    27
    28

## 说明/提示 ##

【数据范围】  
对于 100\\%100% 的数据，1\\le n \\le 151≤n≤15，1\\le s \\le 99991≤s≤9999

题目翻译来自NOCOW。

USACO Training Section 1.2

> 解析：对大于s的每一个数进行枚举，判断：
> 
> 转换为2进制后是否是回文数
> 
> 转换为3进制后是否是回文数
> 
> ……
> 
> 转换为10进制后是否是回文数
> 
> 如果上述条件有至少2个条件满足，则输出，直到输出n个数为止。

/*
    ID: L
    PROG: dualpal
    LANG: C++ 
    */ 
    #include<bits/stdc++.h> 
    using namespace std;
    bool huiwen(string s)//12321 判断是否为回文数 
    {
    	int n = s.length();
    	for(int i = 0; i <= n/2; ++i)
    	{
    		if(s[i] != s[n-i-1]) return false;
    	}
    	return true;
    }
    
    
    string ten_to_r(int n, int r)//将十进制的n转为r进制 
    {
    	char str[10005]={0};//记得要初始化，否则结果是错的 
    	stack<int> st;
    	while(n!=0)
    	{
    		st.push(n%r); 
    		n = n/r;
    	}
    	int i = 0;
    	while(!st.empty())//将数字转成字符 
    	{
    		int s = st.top();
    		if(s >= 10)	str[i++] = s - 10 + 'A';// 大于10的数字转成字符，比如11->B 12->C 
    		else str[i++] = s+'0';//小于10的数字转成字符 
    		st.pop();
    	}
    
    	return str;
    }
    
    int main()
    {
    	freopen("dualpal.in","r",stdin);
    	freopen("dualpal.out","w",stdout);
    	int n, s;
    	cin >> n >> s;
    	int sum2 = 0;//统计满足大于等于2个进制是回文数总个数 
    	while(++s)
    	{
    		if(sum2 >= n) break;
    		int sum1 = 0;//枚举每一个数的时候需要重新对这个数满足进制是回文数的进行计数 
    		for(int r = 2; r <= 10; ++r)
    		{
    			string ss = ten_to_r(s,r);
    			if(huiwen(ss))
    			{
    				sum1++;
    				if(sum1 >= 2)
    				{
    					sum2++;
    					cout << s << endl; 
    					break;
    				}
    			}
    		}
    	}
    	return 0;
    }

[https_www.luogu.com.cn_problem_P1207]: https://www.luogu.com.cn/problem/P1207