i*****e
发帖数: 63 | 1 设有个N位数，其中有“0” N0个, "1" N1个,..."i" Ni个,..., "9" N9个
0<=Ni <= N 且 sum(Ni : i from 0 to 9) = N
请中，有多少个由这些数字组成的数在范围[a, b]中, B的位数可能大于N（此时可随意
添加0的个数）
比如
1022, 其中有1 1个, 0 1个，2 2个
如果a= 1000, b = 20000则 1202, 2012, 10220, 12020等都是备选
不知道说清楚没 | p*****2
发帖数: 21240 | 2 最简单的解法就是brute force，如果b不大的话。
要不就把所有的排列得出来，后边再加0。 | i*****e
发帖数: 63 | 3 要是b很大呢，似乎两种方法都太耗时了
【在 p*****2 的大作中提到】
: 最简单的解法就是brute force，如果b不大的话。
: 要不就把所有的排列得出来，后边再加0。
| p*****2
发帖数: 21240 | 4
你这题是从哪里来的？a,b的范围多大？
【在 i*****e 的大作中提到】
: 要是b很大呢，似乎两种方法都太耗时了
| i*****e
发帖数: 63 | 5 一朋友问的，觉得是到数学题，呵呵
应该可以用排列组合的理论来解，但是想不到好方法
1<= a <= b <= 2^64 or 2^128 | p*****2
发帖数: 21240 | 6
数学题我不擅长，等着数学博士过来看看吧。
【在 i*****e 的大作中提到】
: 一朋友问的，觉得是到数学题，呵呵
: 应该可以用排列组合的理论来解，但是想不到好方法
: 1<= a <= b <= 2^64 or 2^128
| a***o
发帖数: 1182 | 7 二爷求加俱乐部！
【在 p*****2 的大作中提到】
:
: 数学题我不擅长，等着数学博士过来看看吧。
| C***U
发帖数: 2406 | 8 可以这样。找到和a最接近但是比a大的组合。 找到和b最接近但是比b小的组合
用nextpremutation来找出之间的数
找那两个数应该都用o(n)时间
加上nextpermutation们的时间
设有个N位数，其中有“0” N0个, "1" N1个,..."i" Ni个,..., "9" N9个0
★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite
【在 i*****e 的大作中提到】
: 设有个N位数，其中有“0” N0个, "1" N1个,..."i" Ni个,..., "9" N9个
: 0<=Ni <= N 且 sum(Ni : i from 0 to 9) = N
: 请中，有多少个由这些数字组成的数在范围[a, b]中, B的位数可能大于N（此时可随意
: 添加0的个数）
: 比如
: 1022, 其中有1 1个, 0 1个，2 2个
: 如果a= 1000, b = 20000则 1202, 2012, 10220, 12020等都是备选
: 不知道说清楚没
| i*****e
发帖数: 63 | 9 恩，应该可以试一试
之前用python试了一把，python的permutation函数不区分重复数字，candidates太多.
..
貌似stl的next_permutation可以
【在 C***U 的大作中提到】
: 可以这样。找到和a最接近但是比a大的组合。 找到和b最接近但是比b小的组合
: 用nextpremutation来找出之间的数
: 找那两个数应该都用o(n)时间
: 加上nextpermutation们的时间
:
: 设有个N位数，其中有“0” N0个, "1" N1个,..."i" Ni个,..., "9" N9个0
: ★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite
| g***s
发帖数: 3811 | 10 以前好像做过类似的，不过没有可以随便加０这个条件。
基本思路就是固定头几位，后面数字不影响的时候直接用排列公式来算。
例如 ０１２３５５，［１２４００１，３１５５０６］
１０＊全排除
１２［０３］＊全排除
１２５＊ 全ok 直接计算０３５的全排列树目。
２＊ 全ok 直接计算０１３５５的全排列树目。
３０＊ 全ok 直接计算１２５５的全排列树目。
３１０ 全ok
３１２ 全ok
３１５０
。。。
复杂度是数字的长度.
这题０可以随便加，指的是加到最后吧。一样的思路可以解。
【在 i*****e 的大作中提到】
: 设有个N位数，其中有“0” N0个, "1" N1个,..."i" Ni个,..., "9" N9个
: 0<=Ni <= N 且 sum(Ni : i from 0 to 9) = N
: 请中，有多少个由这些数字组成的数在范围[a, b]中, B的位数可能大于N（此时可随意
: 添加0的个数）
: 比如
: 1022, 其中有1 1个, 0 1个，2 2个
: 如果a= 1000, b = 20000则 1202, 2012, 10220, 12020等都是备选
: 不知道说清楚没
|
|
