自动搬运

查看原文

来自洛谷，原作者为

	jyz666 原来这就是AFOed

搬运于2025-08-24 21:33:08，当前版本为作者最后更新于2020-08-11 21:34:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解 P2030 【遥控车】

传送门

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

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

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

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

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

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

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

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

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

$f[i][j]$ = $f[i$−$1]$$[j]$+$f[i$−$2][j$−$1]$

$f[i][j]$表示前$i$辆车有$j$辆和右边交换位置。

因为和右边换等同于和左边换所以不作考虑。然后你就会发现$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;
}

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