GDUT 2020寒假训练 排位赛四 C
原题链接
- C. Defining Labels
题目
Microsoft Excel is a spreadsheet developed by Microsoft. It features calculation, graphing tools, pivot tables, and a macro programming language called Visual Basic for Applications. It has been a very widely applied spreadsheet for many different operating systems, especially since version 5 in 1993, and it has replaced Lotus 1-2-3 as the industry standard for spreadsheets.
In Excel, the labelling for columns uses upper case letters instead of numbers to distinguish it from the labelling for rows. The first column in Excel is labelled A, the second is labelled B and so on. And after column Z, the next columns are labelled AA,AB,⋯,ZZ,AAA,⋯.
In this problem, we’ll define a new labelling scheme. Let’s use numerical digits instead of letters, and only a subset of the digits. Let’s define base k (2≤k≤10) labelling as using only digits from 10−k to 9 in the labels. For example, the labels in base 10 in ascending order are 0,1,⋯,9,00,01,⋯, and in base 7 they are 3,4,⋯,9,33,34,⋯.
Now, given k and X, your task is to find the X-th label in base k.
Input
The input contains multiple cases. The first line of the input contains a single integer T (1≤T≤105), the number of cases.
For each case, the first line of the input contains a single integer k (2≤k≤10), the base of the labelling scheme. The second line contains a single integer X (1≤X≤109), the number of the label you need to find.
Output
For each case, print a single string in a single line, the X-th label.
样例
input
2
10
10
5
10
output
9
59
题目大意
题目呢先是说明Excel里每一栏序号的定义，就是从A ~ Z、AA、AB、AC ~ AZ、BA、BB ~BZ 、CZ ~ ZZ、AAA、AAB ~ ABA……
然后给出了基于数字K的序号定义方法，具体就是讲A ~ Z的排列，改为用从10-k到9的k个数字进行排列。
然后给出K和一个数字x，求在基于数字k的排列中第x出现的序号是
思路1
模拟，找规律
那么先从k等于5开始模拟，
模拟的过程有一点需要注意，59的下一项是65不是555，要一直到99的下一项才是555。这个仔细观察题目就能发现。然后就从这里面找规律了。
不难发现，在模拟的过程中，连续的数字总是五个一组，也就是从5到9，从55到59，从65到69……这些知道都是五个一组，那么我么通过这个规律至少可以得出第x个序号的尾数应该是列表前5个数的第x%5个，其中当余数为0时尾数为9，那么我么再观察x/5的结果，不难看出，这实际上就是往上跃了一个数，换句话说，在讨论x/5的余数时，我们找的是目标序号的尾数，那么x/k就代表目标序号的十位数。如果抽象的想，大概类似是一种“分形”的结构，（以下内容是在瞎想2333）比如拿序号565来说，他的尾部65，以及尾部65的尾部5，都是在这个序号集中。如果我们将视角调整到每一个数字的末尾，那么这个序号集合的末尾分别是：5 6 7 8 9 5 6 7 8 9 5 6 7 8 9 5 6 7 8 9，也就是我们可以按照五个一组，取余数得出想要的第x个序号的尾数，那么我们再将视角放大一位数，那么这个序号集合是：05 06 07 08 09 55 56 57 58 59 65 66 67 68 69 75 76 78 77 79 那么忽略这个集合中每一个数的尾数（上一次的操作），也就是只聚焦于原序号集合的倒数第2位，我们可以得到：（0 0 0 0 0）（5 5 5 5 5）（6 6 6 6 6）（7 7 7 7 7），那么这些数字5个一组，我们将序号除以5（这一步可以抽象的理解为将相同的数字凝聚成一个，或者将视角放大，）就又得出了第一次仅观察尾数的集合：0 5 6 7 8 9 5 6 7 8 9.也就是说，我们只需要每次除以5，得到的余数可以判断出当前的尾数，将除以5 的结果作为新的数继续除以5求余数，就可以得出目标序号的倒数第二位，直到除以5的结果=0。
这个过程想起来其实很容易，只不过我不太清楚如何把我想象的动态的画面描述出来。
不如举个例子，第33个序号是557，
第一次操作 33/5=6…… 3，得出尾数为7
第二次操作6/5=1…… 1，得出尾数是5
第三次操作1/5=0…… 1，得出尾数是5
所以序号是557.
那么还有一种情况，就是当余数为0时候，我们的尾数还是正常可以得到是9，然后再x=x/k之后x要自减1，再继续这样的操作就可以了。
代码
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
int T;
cin>>T;
while(T--)
{
int k,x;
int base[10];
int ans[100];
cin>>k>>x;
for(int i=1;i<k;i++)
{
base[i]=10-k+i-1;
}
base[0]=9;
int len=0;
while(x>0)
{
ans[len]=base[x%k];
len++;
if(x%k==0)
{
x/=k;
x--;
continue;
}
x/=k;
}
for(int i=len-1;i>=0;i--)
{
cout<<ans[i];
}
cout<<endl;
}
return 0;
}