Description
你需要完成下面的任务:
1.韵韵想了m个她想要的名字,请告诉她能玩多少次。
2.由于管理员粗心的操作,导致每辆车的摆放位置都可能出现微小的差错,原来第i辆车现在的位置可能是i-1、i、i+1中的任意一个(第1辆车的位置不可能是0,第n辆车的位置不可能是n+1)。请你计算出共有多少种可能的排列。
注:数据保证当s是name[i]的前缀时,i是唯一确定的。一辆车可以玩多次。
Input
接下来n行,每行1个字符串name[i],表示第i辆车的名字。
接下来m行,每行1个字符串s,表示韵韵想要的名字。
Output
第二行输出共有多少种可能的排列。
Sample Input
4 4 Abcd DeF AAa aBccc Ab AA AbC aBcc
Sample Output
3 5
Data Constraint
Hint
对于题目涉及到的字符串严格区分大小写,且长度小于255。
对于20%的数据 n≤10,m≤10;
对于40%的数据 n≤1000,m≤1000;
对于100%的数据 n≤10000,m≤10000。
分析
关于着前缀,我本想用字典树的
结果MLE。。。无奈,就用了stupid的二分法
然后第二问打波表发现是斐波那契,加高精度即可
#pragma GCC optimize(2) #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; string s[10001]; int cnt; int n,m; bool Bin_Search(string a) { int l=1,r=n; while (l<=r) { int mid=l+r>>1; if (s[mid]>a) r=mid-1; else l=mid+1; } return !s[l].find(a,0); } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) cin>>s[i]; int ans1=0; sort(s+1,s+n+1); for (int i=1;i<=m;i++) { string a; cin>>a; ans1+=Bin_Search(a); } printf("%d\n",ans1); int a[10001],b[10001],c[10001]; memset(a,0,sizeof a); memset(b,0,sizeof b); memset(c,0,sizeof c); a[1]=1;b[1]=2;b[0]=1; if (n<=3) printf("%d",n==1?1:(n==2?1:2)); for (int i=1;i<=n-2;i++) { for (int j=1;j<=b[0];j++) { c[j]=a[j]+b[j]+c[j]; c[j+1]=c[j]/10; c[j]%=10; } if (c[b[0]+1]>0) ++b[0]; for (int j=1;j<=b[0];j++) { a[j]=b[j]; b[j]=c[j];c[j]=0; } } for (int i=b[0];i;i--) printf("%d",b[i]); }
View Code
转载于:https://www.cnblogs.com/mastervan/p/9699165.html
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/101401.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...