「bsoj5160」小T的钢琴 - LCS转LIS+树状数组 | Bill Yang's Blog

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

题目大意




题目分析

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

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

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


代码

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#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;
}

姥爷们赏瓶冰阔落吧~
0%