写在前面
$STL$固然好,但记不住的人(比如我这种cb),就用了其他解法
进制数
$Idea$
我们如何思考呢?
对于第$i$根手指,有$n-i+1$种选择,于是这一位数是$n-i+1$进制的
我们的过程分为三步
- 将火星数变为进制数
- 进制数$+m$
- 把进制数在转回火星数
我们举个栗子:样例
将1,2,3,4,5变为进制数
- 首位1是5种选择$\{1,2,3,4,5\}$的第1种,故变为0(从0开始)
- 次位2是4种选择$\{2,3,4,5\}$的第1种,故变为0
- 中间位3是3种选择$\{3,4,5\}$的第1种,故变为0
- 次低位4是2种选择$\{4,5\}$的第1种,故变为0
- 末位5是1种选择的$\{5\}$第1种,故变为0
- 最后,1,2,3,4,5变成了$(00000)_{unknown}$
其中对于每一位,都是$n-i+1$进制的数。
于是
(写的很丑,请不要在意)
再转化回来
- 首位0表示这位应选择$\{1,2,3,4,5\}$4第1种,即1
- 次位0表示这位应选择$\{2,3,4,5\}$第1种(1被选过了),即2
- 中间位1表示这位应选择$\{3,4,5\}$第2种,即4
- 次低位1表示这位应选择$\{3,5\}$第2种,即5
- 末位0表示这位应选择$\{3\}$第1种,即3
- 所以本题答案为“12345”+3=“12453”
所以,代码献上
$Code$
int a[maxn];
bool vis[maxn];
int n,m;
int main(){
n=read(); m=read();
for(int i=1;i<=n;i++){
a[i]=read();
int x=a[i];
for(int j=1;j<=a[i];j++) x-=vis[j];
vis[a[i]]=1;
a[i]=x-1;
}
a[n]+=m;
for(int i=n;i;i--){
a[i-1]+=a[i]/(n-i+1);
a[i]%=n-i+1;
}
mem(vis,0);
for(int i=1;i<=n;i++){
for(int j=0;j<=a[i];j++)
if(vis[j]) a[i]++;
printf("%d ",a[i]+1);
vis[a[i]]=1;
}
return 0;
}
$$ The \quad End $$
$$ \text{若男孩笑了哭了累了,说要去流浪;留下大人的模样,看岁月剑拔弩张.总会有个人成为你的远方。-《牧马城市》毛不易} $$