Gym 102452D Defining Labels 进制转换+找规律

本文主要是介绍Gym 102452D Defining Labels 进制转换+找规律，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://codeforces.com/gym/102452/problem/D

令k=10，
则1->0，2->1，3->2，4->3，5->4，6->5，7->6，8->9，9->8，10->9，11->00，…
令k=5，
则1->5，2->6，3->7，4->8，5->9，6->55，7->56，8->57，9->58，10->59，11->65，…

再看在五进制下的1到11，为1，2，3，4，10，11，12，13，14，20，21。

再看对应关系，1->5，2->6，3->7，4->8，10->9，11->55，12->56，13->57，14->58，20->59，21->65。

可以看出转换进制后，每个位置上的数仍有一一对应关系。

再次转化为熟悉的形式，即每个位置减去5后再进行观察，1->0，2->1，3->2，4->3，10->4，11->00，12->01，13->02，14->03，20->04，21->10。

发现对应的位置的数总是比实际的数小1，看似不像的10->4和20->04，其实在五进制下4+1=10，04+11=20，效果是一样的，所以全部的计算要在相同的进制下进行。

反过来看，其实我们是要在特定的进制下对每一位都-1才能得出答案。
注意10-k相当于原来的0，所以还要每次加上10-k即可。

#include<cstdio>
using namespace std;
typedef long long ll;
const int maxn = 5000 + 5;
int T, k, x;
void dfs(int n) {if (n == 0)return;n--;dfs(n / k);printf("%d", 10 - k + n % k);
}
int main(void) {scanf("%d", &T);while (T--) {scanf("%d %d", &k, &x);dfs(x); printf("\n");}return 0;
}

这篇关于Gym 102452D Defining Labels 进制转换+找规律的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---