「bsoj5160」小T的钢琴 - LCS转LIS+树状数组

题目大意

---

题目分析

很显然，这道题要我们求LCS，数据量太大，普通的$O(n^2)$算法超时。

我们可以将LCS转化为LIS，然后采用$O(n\log n)$的算法解决：

每次找到$B$串在$A$串中的出现位置，在该出现位置前拼接LIS，注意$B$串中可能存在$A$串不存在的元素，可以直接去掉。

---

代码

其实这道题的主要难点在读入

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
using namespace std;

namespace FastIO {
	char buffer[1<<20],*S,*T=S;
	char getchar() {return (S==T)?(T=(S=buffer)+fread(buffer,1,1<<20,stdin),*S++):*S++;}
	inline string Get_Str(){
		char x=getchar();
		string s="";
		while(x>'Z'||'A'>x)x=getchar();
		while(('A'<=x&&x<='Z')||isdigit(x)||x=='.')s+=x,x=getchar();
		return s;
	}
	inline int Get_Int() {
		int num=0,bj=1;
		char x=getchar();
		while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
		while(isdigit(x))num=num*10+x-'0',x=getchar();
		return num*bj;
	}
}
using namespace FastIO;

const int maxn=200005;
int len,n,v[maxn];
map<string,int>M;

struct BIT {
	int c[maxn];
#define lowbit(x) x&(-x)
	void clear() {
		memset(c,0,sizeof(c));
	}
	void add(int x,int v) {
		for(int i=x; i<=len; i+=lowbit(i))c[i]=max(c[i],v);
	}
	int sum(int x) {
		int ans=0;
		for(int i=x; i>=1; i-=lowbit(i))ans=max(ans,c[i]);
		return ans;
	}
} bit;

int main() {
	len=Get_Int();
	n=Get_Int();
	for(int i=1; i<=len; i++) {
		string s=Get_Str();
		M[s]=i;
	}
	for(int i=1; i<=n; i++) {
		int Len=Get_Int(),tmp=Len;
		bit.clear();
		for(int j=1;j<=Len;j++){
			string k=Get_Str();
			auto it=M.find(k);
			if(it==M.end())j--,Len--; //不存在
			else v[j]=it->second;
		}
		for(int j=1; j<=Len; j++)bit.add(v[j],bit.sum(v[j]-1)+1);
		printf("%0.6lf\n",(double)bit.sum(len)/tmp);
	}
	return 0;
}