题解 P2030 【遥控车】

· · 题解

题解 P2030 【遥控车】

传送门

蒟蒻又来写题解了，只能交交蓝题题解这样生活了（泪）。

一看这题，一开始有些懵阿巴阿巴。 分成两问来看：

第一问，字符串的简单运用；

我们先把所有的车的名字排序（sort大法好）。

因为 题目中有说 "数据保证当s是name[i]的前缀时，i是唯一确定的"。

这句话很重要，这说明s不可能是一个以上的名字的前缀。

给我们的信息是，这题使用二分答案，而不是二分出上下界（所以要很注意题目的用词）。

第二问，n-1的高精度斐波那契数列。

先是一本正经列了一个2维dp如下：

f[i][j]$ = $f[i$−$1]$$[j]$+$f[i$−$2][j$−$1] 因为和右边换等同于和左边换所以不作考虑。然后你就会发现$j$是个酱油,设$g[i]$表示前i辆车的总方案数，则 $g[i]$=$g[i$−$1]$+$g[i$−$2]

这是什么?是斐波那契数列!!

而且，由于数据大，要打高精度哦。

上代码》》

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
#define maxn 50010
#define inf 0x3f3f3f3f
const int mod=100003;

void read(int &x){
    int f=1;x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
string s[maxn],na[maxn];
int n,m,len,ans,a[maxn],b[maxn],c[maxn];
void big_jia(){//高精加 
    memset(c,0,sizeof(c));
    for(int i=1;i<=len;i++){
        c[i]+=a[i]+b[i];
        if(c[i]>=10){
            c[i+1]+=c[i]/10;
            c[i]%=10;
        }
    }
    while(c[len+1])len++;
    for(int i=1;i<=len;i++)a[i]=b[i];
    for(int i=1;i<=len;i++)b[i]=c[i];
}
int main(){
    read(n),read(m);
    for(int i=1;i<=n;i++)cin>>s[i];
    a[1]=1;b[1]=2,len=1;
    for(int i=3;i<=n;i++){
        big_jia();
    }
    sort(s+1,s+n+1);
    for(int i=1;i<=m;i++){
        cin>>na[i];
        int pos=lower_bound(s+1,s+n+1,na[i])-s;
        if(!s[pos].find(na[i],0))ans++;
    }
    cout<<ans<<endl;
    for(int i=len;i;i--)cout<<c[i];
    return 0;
}

強さに欠けているのではなく　意志が足りていないので