ARC173A Neq Number

题目大意

正整数 \(X\) 如果满足以下条件，则称为 "Neq 数 "：

• 当 \(X\) 用十进制符号书写时，没有两个相邻的字符是相同的。

例如，\(1\)、\(173\) 和 \(9090\)是 Neq 数，而 \(22\) 和 \(6335\) 不是。

给你一个正整数 \(K(1\leq K\leq10^{12})\)。请找出第 \(K\) 小的 Neq 数。

Solve

大体思路就是 对于每次询问的 \(K\)，判断出 \(K\) 的位数 \(n\)，然后按位枚举，使我们枚举出的这个数的位次不断逼近 \(K\)。具体见下。

首先想办法处理处 \([1,10^n-1]\)（即 \(n\) 位数）之间的Neq数的数量，记为 \(sum_n\)，那么若 \(sum_{n-1}<K\leq sum_n\)，则第 \(K\) 个Neq数是一个 \(n\) 位数。

然后考虑处理出 \([a\times10^i,(a+1)\times10^i-1]\) 之间Neq数的数量，记为 \(sum1_i\)。接着按位枚举。若 \((a-1)\times sum1_{i-1}<K\leq a\times sum1_{i-1}\)，则 \(K\) 的第 \(i\) 位是 \(a\)。

接下来考虑 \(sum\) 和 \(sum1\) 怎么求。

先看 \(sum1\)，拿 \(sum1_3[1000,1999]\) 举例。\([1000,1999]\) 可拆分为 \([1000,1099],[1100,1199],\cdots,[1899,1999]\) 这 \(10\) 个区间，其中 \([1100,1199]\) 中由于前两位都是 \(1\)，所以无Neq数，不计。所以 \(sum1_3=sum1_2\times9\)。

以此类推，我们有 \(\large sum1_i=sum1_{i-1}\times9,sum1_0=1\)。

至于 \(sum\)，以 \(sum_4[1,9999]\) 举例。\([1,9999]\) 可拆分为 \([1,999],[1000,1999],[2000,2999],\cdots,[8999,9999]\)。所以 \(sum_4=sum_3+sum1_3\times9\)。

以此类推，\(\large sum_i=sum_{i-1}+sum1_{i-1}\times9=sum_{i-1}+sum1_i,sum_0=0\)。

注意，单独看 \([0\times10^i,1\times10^i-1]\)之间的Neq数，应该是 \(sum_i\)，但我们在计算时应记为 \(sum1_i\)，\(i=n\) 时除外。以 \(n=5,i=4\) 即 \([10000,10999]\) 为例。显然 \(sum_2[10000,10099]\) 之间的Neq数都由于相邻的两个 \(0\) 而不计数了，即 \([10000,10999]\) 之间的Neq数应为 \(sum_3-sum_2\)。

以此类推，\([0\times10^i,1\times10^i-1](i\neq n)\) 之间的Neq数为 \(\large sum_{i-1}-sum_{i-2}=sum_{i-2}+sum1_i-sum_{i-2}=sum1_i\)。

Code

#include<bits/stdc++.h>
#pragma GCC optimize(1,2,3,"Ofast","inline")
using namespace std;
#define int long long
inline int read()
{
	short f=1;
	int x=0;
	char c=getchar();
	while(c<'0'||c>'9')	{if(c=='-')	f=-1;c=getchar();}
	while(c>='0'&&c<='9')	x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
int T,k,sum[20]/*1~10^n-1*/,n,sum1[20]={1}/*a*10^n~(a+1)*10^n-1*/;
signed main()
{
	for(int i=1;i<=13;i=-~i)//预处理
		sum1[i]=sum1[i-1]*9,
		sum[i]=sum1[i]+sum[i-1];
	T=read();
	for(int t=1;t<=T;t=-~t)
	{
		k=read();
		for(n=1;n<=13;n=-~n)	if(sum[n]>=k)	break;//枚举位数
		int res=0,x=-1,now;
		for(int i=n;i;i--)
			for(int j=0;j<=9;j=-~j)
			{
				now=res;
				if(j!=x)	res+=i==n&&j==0?sum[i-1]:sum1[i-1];
				//只有当枚举第n位为0时才加sum，其余都加sum1，证明见上
				if(res>=k)
				{
					printf("%lld",x=j);
					res=now;//回溯
					break;
				}
			}
		puts("");
	}
	return 0;
}