bzoj3244: [Noi2013]树的计数

神题……

不到1k的noiT2

重在理解dfs，bfs性质

#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm> using namespace std; int n; double ans=2; int dx[200005],pos[200005],lc[200005],rc[200005]; int cnt=0; int main() { int i,j,k,l,x; scanf("%d",&n); for(i=1;i<=n;i++){scanf("%d",&x);dx[x]=i;} for(i=1;i<=n;i++){scanf("%d",&x);pos[i]=dx[x];} lc[n+1]=n+1; for(i=n;i;i--){ lc[i]=min(lc[i+1],pos[i]); rc[i]=max(rc[i+1],pos[i]); } for(i=2;i<n;i++){ if(pos[i]>pos[i+1])ans+=1; else if(pos[i]+1==pos[i+1]&&rc[i+1]-lc[i+1]+1==n-i)ans+=0.5; } printf("%.3lf\n%.3lf\n%.3lf\n",ans-0.001,ans,ans+0.001); return 0; }