http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1008&cid=843
题解:模板题
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,q;
int ans,cnt,flag,temp,sum;
int a[N];
char str;
struct node{};
int findKthNumber(int n, int k) {
//*************************
//第一部分,得到树群的最大深度。
if (n<10)
return k;
int sum = 9;
int base = 1;
int deep = 0;
while (n>sum) {
base *= 10;
++deep;
sum += 9 * base;
}
//*************************
//第二部分,确定k在左侧树群还是在右侧树群。
int redund = n - (base - 1);
int lisNum = redund;
while (base != 1) {
n /= 10;
base /= 10;
int tmp = n - (base - 1);
//cout << tmp << endl;
lisNum += tmp;
}
if (k > lisNum) {
--deep;
k -= redund;
}
//*************************
//第三部分,在k所归属的树中找到其值。
//cout<<" +"<<endl;
int partSum = 0;
vector<int>work(deep + 1, 0);
for (int i = 0; i <= deep; ++i) {
partSum += pow(10, i);
work[deep - i] = partSum;
}
int seq = (k - 1) / partSum + 1;
int rem = (k - 1) % partSum;
string result;
result.push_back('0' + seq);
for (int i = 1; i <= deep && rem != 0; ++i) {
--rem;
int order = rem / work[i];
rem = rem % work[i];
result.push_back('0' + order);
}
return stoi(result);
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&k);
printf("%d\n",findKthNumber(n,k));
}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}