给定l,r,求[l,r]内每位各不相同的数字个数,所有数字均不含前导零。 例如12345,54320都是满足题目条件的,但415411,189191都不是。c++代码
时间: 2024-03-24 15:40:01 浏览: 47
以下是这道题目的 C++ 代码实现:
```cpp
#include <iostream>
#include <cstring>
using namespace std;
const int N = 15, M = 1 << 10;
int l, r;
int dp[N][M][2];
int num[N];
int dfs(int pos, int state, int limit)
{
if (!pos) return 1;
if (!limit && dp[pos][state][0] != -1) return dp[pos][state][0];
if (limit && dp[pos][state][1] != -1) return dp[pos][state][1];
int up = limit ? num[pos] : 9;
int res = 0;
for (int i = 0; i <= up; i ++ )
if (!(state >> i & 1))
res += dfs(pos - 1, state | (1 << i), limit && i == up);
if (!limit) dp[pos][state][0] = res;
else dp[pos][state][1] = res;
return res;
}
int solve(int x)
{
int len = 0;
while (x)
{
num[ ++ len] = x % 10;
x /= 10;
}
return dfs(len, 0, 1);
}
int main()
{
memset(dp, -1, sizeof dp);
cin >> l >> r;
cout << solve(r) - solve(l - 1) << endl;
return 0;
}
```
其中,dfs 函数表示当前处理到第 pos 位,集合 S 中已经使用了 state 中的数字,且当前位是否已经用过 state 中的数字(用 0 或 1 表示)时,满足条件的数字个数。solve 函数则表示求出 [1, x] 中每位各不相同的数字个数。
具体实现中,我们使用记忆化搜索来优化时间复杂度。同时,我们在 dfs 函数中使用 limit 变量表示当前位是否达到了数字 x 的最高位。这是因为,如果当前位达到了最高位,那么我们不能在其后面填入任何数字,否则就会超过 x 的范围。