P6387 [COCI2007-2008#4] VECI 题解
hensier
·
·
题解
本题可用两种方法：
【方案1：暴力算法】
题目中要求数字中每一个数码的个数都相同，所以如果有答案的话，那么就必定与原数字位数相同。
于是我们可以在如下区间内循环：
[x,{\lceil log_{10}x \rceil}^{10})
由于$lg(n)$的定义就是能够满足以$10$为底数的幂，而$lg(n)$就是指数，即$10^{lg(n)}=n$。
那么当$lg(n)$为整数的时候，$n$为$10$的整数幂，而$n$又是正数，所以$n$就是一个首位是$1$，其他位数全是$0$的数。此时位数为$lg(n)+1$。
当$lg(n)$不为整数的时候，有$10^{lg(n)}=n$。假设小于$lg(n)$的最大整数为$m$，则$n$的位数等同于$m$的位数。所以$n$的位数就等于$m+1$。所以$n$的位数为$\lfloor lg(n) \rfloor+1$。
综合两种情况，我们发现位数为$\lceil lg(n) \rceil$。所以循环的上限（不含）就是${lg(x)}^{10}$。
而$cmath$库中正好有$log10$函数。
得到上限之后，我们依次进行循环，每次加$1$，逐个枚举并判断，不提。
代码：
```cpp
#include<cstdio>
#include<cmath>
int x,a[10],b[10];//a,b数组分别表示x的
void f(int n,int check)//计数用
{
while(n)
{
if(check==1)b[n%10]++;
else if(!check)a[n%10]++;
n/=10;
}
}
bool check()//检查两个数组是否完全相同
{
for(int i=0;i<10;i++)if(a[i]!=b[i])return 0;
return 1;
}
void memset()//清零
{
for(int i=0;i<10;i++)b[i]=0;
}
int main()
{
scanf("%d",&x);//输入
f(x,0);//后面的0表示将数据存入a中
for(int i=x+1;i<pow(ceil(log10(x)),10);i++)//区间上面已详细说明
{
memset();//清零
f(i,1);//把i的数位存入b中
if(check())//检查是否相同
{
printf("%d",i);//输出
return 0;
}
}
putchar('0');//没有答案，输出0
}
```
然而，我们很愉快地超时了——第$1$个点用了$1.2s$。于是我们开始优化——可以手写$pow$，因为$cmath$中的是浮点运算，时间耗费肯定长，因此：
```cpp
int pow10(int x)
{
int s=1;
while(x--)s=(s<<3)+(s<<1);//位运算快
return s;
}
```
改为调用手写函数之后，愉快地$AC$了（原来的$1.2s$降到了$5ms$！）
【方案$2$：`dfs`】
因为题目的本质就是排列，我们可以使用`dfs`。详细的在注释里说明。
```cpp
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
string s;
int a[10],b[10],len,n,minn=1e7;//a保存数位，b保存排列的数，len为数的数位个数，n为数字，minn为最小值
bool flag[10];//由于本题排列不能有重复数位，所以用flag数组标记
void dfs(int k)//k为层数
{
if(k>len)//超过len就进行操作
{
int num=0;
for(int i=1;i<=len;i++)num=(num<<3)+(num<<1)+a[b[i]];//转化为数
if(num>n&&num<minn)minn=num;//赋值
return;//跳出该层dfs
}
for(int i=1;i<=len;i++)//循环
{
if(!flag[i])//没有被使用的话就继续
{
flag[i]=1;//标记使用
b[k]=i;//赋值
dfs(k+1);//下层循环
flag[i]=0;//回溯
}
}
}
int main()
{
ios::sync_with_stdio(0);//关闭同步
cin>>s;//输入（字符串形式）
len=s.size();//len赋值
for(int i=0;i<len;i++)//循环
{
a[i+1]=s[i]^'0';//数组保存数位
n=(n<<3)+(n<<1)+a[i+1];//计算字符串的数字形式
}
dfs(1);//开始搜索
printf("%d",minn==1e7?0:minn);//输出
}
```