牛客----电话号码

牛客----电话号码

​​题目描述​​

给你一个整数n表示手机号码的位数 再给你m个字符串表示保留的号码,比如911 110 120等 问你一共有多少的手机号码不以保留号码开头

输入描述:

第一行输入两个整数n, m (1 ≤ n ≤ 17, 0 ≤ m ≤ 50) 接下来m行每行输入一个数字串,长度为1到n

输出描述:

输出一个整数

示例1输入

7 30 1911

示例1输出

7990000

示例2输入

10 301911

示例2输出

7990000000

示例3输入

8 3112123

示例3输出

90000000

示例4输入

9 3121314

示例4输出

970000000

示例5输入

3 1411

示例5输出

999

题目分析:由于保留手机号码较少,所以可以逆向思考,用总的情况减去以这些号码开头的数量; 但要注意,有可能这里面存在一个号码A是另一个号码B的前缀,这样的话在计算时,只需要计算A的情况即可.

AC代码

#include#includeusing namespace std;typedef long long LL;LL cal(int x){ return pow(10,x);}int judge(string &s1,string &s2)//判断s2是否是s1的前缀.{ int len1 = s1.size(); int len2 = s2.size(); if(len1<=len2){//s2长度比s1小,不可能是s1前缀, return 0; }//len1>len2 for(int i = 0;i>n>>m; for(int i = 0;i < m;i++){ cin>>arr[i]; } //判断串的前缀 for(int i = 0; i < m;i++){ for(int j = 0;j < m;j++){ if(i!=j&&judge(arr[i],arr[j])){ vis[i] = 1; } } } ans = cal(n); for(int i = 0;i < m;i++){ if(!vis[i]){ int len = n-arr[i].size(); ans -= cal(len); } } cout<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。