首页 > 代码库 > P2030 遥控车
P2030 遥控车
P2030 遥控车
- 2通过
- 11提交
- 题目提供者LittleZ
- 标签二分字符串递推高精洛谷原创
- 难度尚无评定
提交该题 讨论 题解 记录
最新讨论
- 暂时没有讨论
题目描述
平平带着韵韵来到了游乐园，看到了n辆漂亮的遥控车，每辆车上都有一个唯一的名字name[i]。韵韵早就迫不及待地想玩名字是s的遥控车。可是韵韵毕竟还小，她想象的名字可能是一辆车名字的前缀（也就是说能确定一个i，使s是name[i]的前缀），这时她就能玩第i辆车；或者是一个无中生有的名字，即s不是任何一辆车名字的前缀，这时候她什么也不能玩。
你需要完成下面的任务：
1.韵韵想了m个她想要的名字，请告诉她能玩多少次。
2.由于管理员粗心的操作，导致每辆车的摆放位置都可能出现微小的差错，原来第i辆车现在的位置可能是i-1、i、i+1中的任意一个（第1辆车的位置不可能是0，第n辆车的位置不可能是n+1）。请你计算出共有多少种可能的排列。
注：数据保证当s是name[i]的前缀时，i是唯一确定的。一辆车可以玩多次。
输入输出格式
输入格式：
第一行是2个正整数n、m。
接下来n行，每行1个字符串name[i]，表示第i辆车的名字。接下来m行，每行1个字符串s，表示韵韵想要的名字。
输出格式：
第一行输出韵韵能玩的次数。第二行输出共有多少种可能的排列。
输入输出样例
4 4AbcdDeFAAaaBcccAbAAAbCaBcc
35
说明
【注意】
对于题目涉及到的字符串严格区分大小写，且长度小于255。
【数据范围】
对于20％的数据 n≤10,m≤10；
对于40％的数据 n≤1000，m≤1000；
对于100％的数据 n≤10000，m≤10000。
题解：
第一问是字符串的简单运用，第二问是n-1的高精度斐波那契数列
排序+二分答案
我们先把所有的车的名字排序（sort大法好）
因为 题目中有说 “ 数据保证当s是name[i]的前缀时，i是唯一确定的"
这句话很重要，这说明s不可能是一个以上的名字的前缀
给我们的信息是，这题使用二分答案，而不是二分出上下界（所以要很注意题目的用词）
AC代码：
#include<cstdio>#include<cstring>#include<string>#include<algorithm>#include<iostream>using namespace std;#define N 10010string s[N],c[N];int n,m,len,ans,a[N],b[N],d[N];void jia(){ memset(d,0,sizeof d); for(int i=1;i<=len;i++){ d[i]+=a[i]+b[i]; if(d[i]>9){ d[i+1]+=d[i]/10; d[i]%=10; } } while(d[len+1]) len++; for(int i=1;i<=len;i++) a[i]=b[i]; for(int i=1;i<=len;i++) b[i]=d[i]; }int main(){ ios::sync_with_stdio(false); cin>>n>>m; a[1]=1;b[1]=2;len=1; for(int i=1;i<=n;i++) cin>>s[i]; for(int i=3;i<=n;i++) jia(); sort(s+1,s+n+1); for(int i=1;i<=m;i++){ cin>>c[i]; int pos=lower_bound(s+1,s+n+1,c[i])-s; if(!s[pos].find(c[i],0)) ans++; } cout<<ans<<endl; for(int i=len;i;i--) cout<<d[i]; return 0;}
P2030 遥控车