2018.10.17多校联测测试总结

2018.10.19 多校联测测试总结 T1梦境 解题思路：

题目意思是将点和区间作最大匹配，
先将区间按左端点和点一起从小到大排序
一路扫过去，类似于二维偏序，用堆维护插入点的右端点的最小值，然后查询

#pragma GCC optimize(2) #include<queue> #include<cstdio> #include<algorithm> using namespace std; int read(){ int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9') ch=='-'&&(f=-1),ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x*f; } const int N=2e5+10; int n,m,ans,tot; priority_queue<int,vector<int>,greater<int> > que; struct AC{int x,y;}a[N<<1]; bool cmp(AC x,AC y){return x.x==y.x?x.y>y.y:x.x<y.x;} int main(){ n=read(),m=read(); for (int i=0;i<n;++i)a[++tot]=(AC){read(),read()}; for (int i=0;i<m;++i)a[++tot]=(AC){read(),0}; sort(a+1,a+n+m+1,cmp); for (int i=1,q=n+m;i<=q;++i){ if (a[i].y) que.push(a[i].y); else { while ((!que.empty())&&a[i].x>que.top())que.pop(); if (!que.empty()) que.pop(),++ans; } } printf("%d\n",ans); return 0; } T2 玩具 解题思路：

预处理\(dp[i][j]\)示i个点的森林，有j个点在第⼀棵树的概率，转移考虑第i个点是否在第⼀棵子树中，我们有状态转移方程
\[dp[i][j] = dp[i − 1][j − 1] ∗ (j − 1) ∗ inv[i] + dp[i − 1][j] ∗ (i − j) ∗ inv[i]\]
考虑修改算法三中状态的含义，令\(f[i][j]\)表示有i个点的树，深度不超过j的概率，\(g[i][j]\)表示有i个点的森林，深度不超过j的概率，\(f[i][j]\)直接从\(g[i-1][j-1]\)转移来;\(g[i][j]\)考虑枚举第⼀棵树的大小k，从⼀棵树和⼀个森林转移来，同时还要乘上第⼀棵子树大小为k的概率，我们有状态转移方程：
\[g[i][j] = ∑ f[k][j] ∗ g[i − k][j] ∗ dp[i][k]\]
k=1具体的细节可以见标程。最后只要用\(f[n][j]-f[n][j-1]\)就可以得到深度为j的树的概率
时间复杂度： \(O(n^3)\)

#pragma GCC optimize(2) #include<cmath> #include<cstdio> #include<cstring> #include<iostream> using namespace std; typedef long long ll; const int N=210; int n,P,ans; int inv[N],dp[N][N],f[N][N],g[N][N],get[N]; int ksm(int x,int k){ int su; for (su=1;k;x=1ll*x*x%P,k>>=1) if (k&1) su=1ll*su*x%P; return su; } int solve1(int i,int j); int solve2(int i,int j){ if (j<0) return 0; if (!i) return 1; if (~g[i][j]) return g[i][j]; g[i][j]=0; for (int k=1;k<=i;++k) (g[i][j]+=1ll*solve1(k,j)*solve2(i-k,j)%P*dp[i][k]%P)%=P; return g[i][j]; } int solve1(int i,int j){ if (~f[i][j]) return f[i][j]; return f[i][j]=solve2(i-1,j-1); } int main(){ cin>>n>>P; for (int i=1;i<=n;++i) inv[i]=ksm(i,P-2); dp[1][1]=1; for (int i=2;i<=n;++i) for (int j=1;j<=i;++j) dp[i][j]=(1ll*dp[i-1][j-1]*(j-1)%P*inv[i]+1ll*dp[i-1][j]*(i-j)%P*inv[i])%P; memset(f,-1,sizeof f); memset(g,-1,sizeof g); for (int i=2;i<=n;++i)get[i]=solve1(n,i),ans=(ans+1ll*(get[i]-get[i-1]+P)*i)%P; cout<<(ans-1+P)%P<<endl; return 0; } T3(飘雪圣域) 解题思路:

对于每次询问的\(x_i,y_i\),所有左右端点位于这个区间的边都会将两个联通块连在一起（因为这是一棵树，加一条边少一个联通块），所以此题就是对于每个询问作二维偏序，此题没有强制在线，所以 ** 树和树状数组都可写。

** 树： #pragma GCC optimize(2) #include<cmath> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; int read(){ int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9') ch=='-'&&(f=-1),ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x*f; } const int N=2e5+10,M=4e6; int n,m,tot; int rt[N],ls[M],rs[M],t[M]; struct AC{int x,y;}a[N]; bool cmp(AC x,AC y){return x.x<y.x;} void updata(int p){t[p]=t[ls[p]]+t[rs[p]];} void change(int&p,int l,int r,int x,int las){ if (p==las) p=++tot,t[p]=t[las],ls[p]=ls[las],rs[p]=rs[las]; if (l==r) return ++t[p],void(); int mid=(l+r)>>1; if (x<=mid) change(ls[p],l,mid,x,ls[las]); else change(rs[p],mid+1,r,x,rs[las]); updata(p); } int query(int p1,int p2,int l,int r,int x,int y){ if (x<=l&&r<=y)return t[p2]-t[p1]; int mid=(l+r)>>1; return (x<=mid?query(ls[p1],ls[p2],l,mid,x,y):0)+(y>mid?query(rs[p1],rs[p2],mid+1,r,x,y):0); } int main(){ n=read(),m=read(); for (int i=1;i<n;++i) a[i]=(AC){read(),read()}; sort(a+1,a+n,cmp); for (int i=1,j=1;i<=n;++i){ rt[i]=rt[i-1]; while (a[j].x==i&&j<n) change(rt[i],1,n,a[j].y,rt[i-1]),++j;//printf("...%d %d\n",a[j].x,a[j].y),++j; } for (int i=0,x,y;i<m;++i){ x=read(),y=read(); printf("%d\n",y-x+1-query(rt[x-1],rt[y],1,n,x,y)); } return 0; } 树状数组 #pragma GCC optimize(2) #include<cmath> #include<cstdio> #include<cstring> #include<algorithm> #define low(x) (x&(-x)) using namespace std; typedef long long ll; int read(){ int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9') ch=='-'&&(f=-1),ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x*f; } const int N=2e5+10; int n,m,tot; int c[N],ans[N]; struct AC{int x,y,z,id;}a[N<<1]; bool cmp(AC x,AC y){return x.x==y.x?x.z<y.z:x.x>y.x;} void add(int x,int y){while (x<=n) c[x]+=y,x+=low(x);} int query(int x){ int su=0; while (x) su+=c[x],x-=low(x); return su; } int main(){ n=read(),m=read(); for (int i=1,x,y;i<n;++i)x=read(),y=read(),x>y?swap(x,y):void(),a[++tot]=(AC){x,y,0,i}; for (int i=0,x,y;i<m;++i)x=read(),y=read(),x>y?swap(x,y):void(),a[++tot]=(AC){x,y,1,i}; sort(a+1,a+n+m,cmp); for (int i=1,q=n+m;i<q;++i){ if (a[i].z) ans[a[i].id]=a[i].y-a[i].x+1-query(a[i].y); else add(a[i].y,1); } for (int i=0;i<m;++i)printf("%d\n",ans[i]); return 0; }