首页 > 考试 > 其他 >

Bus Number习题解析 (二进制枚举 + 组合数学 or DFS)

2019-04-18

Bus Number习题解析 (二进制枚举 + 组合数学 or DFS)。Vasya模糊的记得公交车车牌号码为n≤1018 " role= "presentation ">n≤1018n≤1018,但是他不会漏掉某个数字,号码不允许以0开头,问可能的号码种数。

Bus Number习题解析 (二进制枚举 + 组合数学 or DFS)

Vasya模糊的记得公交车车牌号码为n≤1018" role="presentation">n≤1018,但是他不会漏掉某个数字,号码不允许以0开头,问可能的号码种数。
比如2028,可能的号码有208,280,802,820,2028,2082,2208,2280,2802,2820,8022,8202,8220。
但028和128都是不合法的。

思路

这里写图片描述
知道这个以后就可以暴力了,二进制枚举n的所有子集,然后统计所有子集的情况就是答案。
子集可能会漏掉某个数字导致不合法,所以我们应该判断该子集是否合法。
两个子集选的数字可能相同,会重复导致多算,所以我门应该用set判重,如果之前算过就不算这种情况了。
还有就是前导0的情况,所以我们计算的时候先把所有的情况算出来,如果含有前导0的情况,我们就把前导0的情况减去就好了。

#include
using namespace std;
typedef long long ll;
int a[15], vis[15];
ll fac[20];
set s;
void split(string x, int *a)
{
 for (int i = 0; i < 10; i++) a[i] = 0;
 for (char i: x) a[i-&#39;0&#39;]++;
}
ll getcount()//去重全排列
{
 ll ans = fac[accumulate(a, a+10, 0)];
 for (int i = 0; i < 10; i++) ans /= fac[a[i]];
 return ans;
}
ll getans(string x)
{
 split(x, a);
 for (int i = 0; i < 10; i++) if (vis[i] && !a[i]) return 0;//比原来少了i数字
 sort(x.begin(), x.end());
 if (s.count(x)) return 0;//x这种子集算过了
 else s.insert(x);

 ll ans = getcount();
 if (a[0]) { a[0]--; ans -= getcount(); }//减去前导0情况
 return ans;
}
int main()
{
 fac[0] = 1; for(int i = 1; i < 20; i++) fac[i] = fac[i-1]*i;//计算阶乘
 string n; cin >> n;
 split(n, vis);
 int k = n.size();
 ll ans = 0;
 for (int i = 1; i < (1<
相关文章
最新文章
热点推荐