题目描述
波浪数是在一对不同数字之间交替转换的数，如 \(1212121\)，双重波浪数则是指在两种进制下都是波浪数的数，如十进制数 \(191919\) 是一个十进制下的波浪数，它对应的十一进制数 \(121212\) 也是一个波浪数，所以十进制数 \(191919\) 是一个双重波浪数。特别地，只有一位的数也算作波浪数，例如 \(1\)。类似的可以定义三重波浪数，三重波浪数在三种不同的进制中都是波浪数，甚至还有四重波浪数，如 \(300_{(10)}=606_{(7)}=363_{(9)}=454_{(8)}=1\mathtt{A}1_{(13)}\)，下标表示采用的进制。你的任务就是在指定范围内找出双重、三重、四重波浪数。
输入格式
单独一行包含五个用空格隔开的十进制整数 \(l, r, L, R, k\)。\([l, r]\) 表示应当考虑的进制的范围，\([L,R]\) 表示应当考虑的数字的范围，\(k\) 表示你应该找的波浪数的重数。
输出格式
从小到大以十进制形式输出指定范围内的指定重数的波浪数。一行输出一个数。
数据范围及约定
对于全部数据，保证 \(2\le l\le r\le 32\)，\(1\le L\le R\le 10^7\)，\(k\in \{2, 3, 4\}\)。
解析
首先，首先理解题意：任意一个波浪数 \(W\) 中第 \(x\) 位的数字 \(W_x\) 满足条件：
\[\text{check}(x) =
\begin{cases}
\text{return if } W_x \neq W_{x-1}\space(W.\text{size}() \geq 3)\\
\text{return if } W_x \neq W_{x+1}\space∧\space W_x = W_{x+2}\space(W.\text{size}() = 2)\\
\text{return true}\space(W.\text{size}() = 1)\\
\end{cases}\]
我们考虑模拟进制转换的过程，产生转换后的数字字符串，再对其进行判断数据。
\(82\text{ pts}\) 做法：转换字符串
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int l, r, L, R, k, cnt;bool check(int t, int b){int T = t;string res = "";while(T){ // 模拟进制转换int r = T % b; // 余数char c;T /= b;if(r >= 10) c = 'A' + r - 10; // 转化为字符else c = r + '0';res += c;}reverse(res.begin(), res.end()); // 由于处理使用最小到最大位处理，所以要反转字符串if(res.size() < 2) return true; else if(res.size() == 2 && res[0] != res[1]) return true;else if(res[0] == res[1]) return false;else{for(int i=2; i<res.size(); ++i) // 枚举每一位查看是否与波浪数的定义不一样if(res[i-2] != res[i])return false;return true;}
}int main(void){cin >> l >> r >> L >> R >> k;for(int num=L; num<=R; ++num){ // 枚举范围 [l, r] 之内的数字cnt=0;for(int base=l; base<=r; ++base) // 枚举范围 [L, R] 之内的基数if(check(num, base)) // 检查cnt++;if(cnt == k){cout << num << endl;}}return 0;
}
\(100\text{ pts}\) 做法
不转换进制，而是在转换时判断字符 \(W_i\) 和之前的 \(W_{i-2}\) 是否相等。
#include <iostream>
...
inline int read();
inline void write(int x);bool check(int t, int b){if(t < b) return true;char w[2] = {};// 取出两个字符w[0] = t % b; t /= b;w[1] = t % b; t /= b;if(w[0] == w[1]) // W.size() = 2 时判断return false;int f = 0;while(t){if(w[f] != t % b) // 如果不和前面的前面的字符相同return false;t /= b;f ^= 1; // 转换索引，即 f=(f==1)?0:1;}return true;
}int main(void){......
}
return 0;！