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;
}