题干:
如果一个数大于等于 10且任意连续两位都是质数,那么就称之为 Wish 数。当然,第一个 Wish 数是 11。
比如 97,111,131,119 都是 Wish 数,而 12,136 则不是。
问第 N 个 Wish 数是多少。
输入格式
一个整数 NN。
输出格式
一个 Wish 数。
数据范围
对于 30\%30% 的数据:1 \le N \le 211≤N≤21。
对于 60\%60% 的数据:1 \le N \le 10001≤N≤1000。
对于 100\%100% 的数据:1 \le N \le 97979797979797971≤N≤9797979797979797。
输出时每行末尾的多余空格,不影响答案正确性
样例输入复制
1
样例输出复制
11
解题报告:
思路:预处理一下 1 - 9 每个数后面可以跟的能够与它组成两位数字并且为素数的数字。
dp[ i ] [ j ] i 的含义是 i 长度为i 的数字,开头为 j 的 wish 数,那么他就可以由 dp [ i - 1] [ 预处理的 g[ j ] ]转移而来,注意处理边界,也就是i==2的情况。
需要f [ i ]存储的是 长度为 i 的Wish总数 ,最后根据res去具体定位那个数是个几位数(也就是看还剩下多少数可以放)。然后从 高位开始确定每一位数字是什么,枚举每一位数字时候从小到大。。这也是为什么预处理的时候需要两层循环,而非10~99这样,就是因为这个顺序问题。
AC代码:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX = 2e6 + 5;
ll dp[45][10],f[45];//dp[i][j] : i位整数以j这个数字开头
vector<int> vv[11];
ll n,sum;
string ans;
bool is(int x) {
if(x<2) return 0 ;
for(int i = 2; i*i<=x; i++) {
if(x%i == 0) return 0 ;
}
return 1;
}
int main()
{
for(int i = 0; i<10; i++) {
for(int j = 0; j<10; j++) {
if(is(i*10 + j)) vv[i].pb(j);
}
}
for(int j = 1; j<10; j++) vv[10].pb(j);
//for(int j = 1; j<10; j++) dp[2][j]=1;
//f[2] =
for(int i = 2; i<=40; i++) {
for(int j = 1; j<10; j++) {
int up = vv[j].size();
for(int k = 0; k<up; k++) {
int x = vv[j][k];
if(i == 2) dp[i][j]++;
else dp[i][j] +=dp[i-1][x] ;
}
f[i] += dp[i][j];
}
}
cin>>n;
int i=2;
while(sum + f[i] < n) sum += f[i],i++;
ll res = n;
res -= sum;
int x = 10;//枚举首位
for(;i>=2; i--) {
int up = vv[x].size();
for(int k = 0; k<up; k++) {
int j = vv[x][k];
if(res - dp[i][j] > 0 ) res -= dp[i][j];
else {
ans.pb('0'+j);x=j;break;
}
}
}
ans.pb('0'+vv[x][res-1]);
cout << ans << endl;
return 0 ;
}