首页 > 代码库 > 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,表示韵韵想要的名字。

 

输出格式:

 

第一行输出韵韵能玩的次数。第二行输出共有多少种可能的排列。

 

输入输出样例

输入样例#1:
4 4AbcdDeFAAaaBcccAbAAAbCaBcc
输出样例#1:
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 遥控车