题目描述
给你一个整数n表示手机号码的位数
再给你m个字符串表示保留的号码,比如911 110 120等
问你一共有多少的手机号码不以保留号码开头
输入描述:
第一行输入两个整数n, m (1 ≤ n ≤ 17, 0 ≤ m ≤ 50)
接下来m行每行输入一个数字串,长度为1到n
输出描述:
输出一个整数
示例1输入
7 3 0 1 911
示例1输出
7990000
示例2输入
10 3 0 1 911
示例2输出
7990000000
示例3输入
8 3 1 12 123
示例3输出
90000000
示例4输入
9 3 12 13 14
示例4输出
970000000
示例5输入
3 1 411
示例5输出
999
题目分析:由于保留手机号码较少,所以可以逆向思考,用总的情况减去以这些号码开头的数量;
但要注意,有可能这里面存在一个号码A是另一个号码B的前缀,这样的话在计算时,只需要计算A的情况即可.
AC代码
#include<bits/stdc++.h> #include<cmath> using 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<len2;i++){ if(s1[i]!=s2[i]){//如果不想等. return 0; } } return 1; } LL ans; string arr[55];//字符串数组,用于存储保留手机号 int n,vis[50],m; //vis标记是否是前缀.如果是1说明另一个是该字符串的前缀,当前 字符串无需考虑. int main() { cin>>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<<ans<<endl; return 0; }
