暑假集训CSP提高模拟8
\(T1\) P155.基础的生成函数练习题（gf） \(100pts\)
-
设通过操作 \(a,b,c\) 所能达到的最小整数为 \(x\) 。
-
观察到对同两个数进行操作 \(2\) 等价于分别对这两个数各进行操作 \(1\) ，在 \(a,b,c\) 达到 \(x\) 的过程中优先使用操作 \(1\) ，不够的再用操作 \(1\) 来凑。
-
最终，有 \(\dfrac{3x-a-b-c}{2}\) 即为所求，其中 \(x\) 是满足 \(\ge \max(a,b,c)\) 且 \((3x-a-b-c) \bmod 2=0\) 的最小整数。
-
直接枚举判断就行，可以证明枚举次数不会太多。
点击查看代码
#define endl '\n' int main() { ll a,b,c,i; cin>>a>>b>>c; for(i=max(a,max(b,c));;i++) { if((3*i-a-b-c)%2==0) { cout<<(3*i-a-b-c)/2<<endl; break; } } return 0; }
\(T2\) P156. 简单的拉格朗日反演练习题（lagrange） \(35pts\)
-
部分分
-
\(35pts\) ：显然答案具有单调性，考虑二分答案 \(k\) 。可持久化并查集维护历史祖先节点并依次枚举 \([l,r]\) 判断，时间复杂度为 \(O(m \log^{2} n+nq \log n \log m)\) 。
点击查看代码
int a[200010]; struct PDS_SMT { int root[200010],rt_sum=0; struct SegmentTree { int ls,rs,fa,dep; }tree[200010<<5]; #define lson(rt) tree[rt].ls #define rson(rt) tree[rt].rs int build_rt() { rt_sum++; return rt_sum; } void build_tree(int &rt,int l,int r) { rt=build_rt(); if(l==r) { tree[rt].fa=l; tree[rt].dep=0; return; } int mid=(l+r)/2; build_tree(lson(rt),l,mid); build_tree(rson(rt),mid+1,r); } void update(int pre,int &rt,int l,int r,int pos,int val,int pd) { rt=build_rt(); tree[rt]=tree[pre]; if(l==r) { tree[rt].fa=(pd==0)?val:tree[rt].fa; tree[rt].dep+=(pd==1)*val; return; } int mid=(l+r)/2; if(pos<=mid) { update(lson(pre),lson(rt),l,mid,pos,val,pd); } else { update(rson(pre),rson(rt),mid+1,r,pos,val,pd); } } int query(int rt,int l,int r,int pos) { if(l==r) { return rt; } int mid=(l+r)/2; if(pos<=mid) { return query(lson(rt),l,mid,pos); } else { return query(rson(rt),mid+1,r,pos); } } }T; struct PDS_DSU { int find(int rt,int x,int n) { int fa=T.query(rt,1,n,x); return (T.tree[fa].fa==x)?fa:find(rt,T.tree[fa].fa,n); } void merge(int pre,int &rt,int x,int y,int n) { x=find(rt,x,n); y=find(rt,y,n); if(T.tree[x].fa!=T.tree[y].fa) { if(T.tree[x].dep>T.tree[y].dep) { swap(x,y); } T.update(pre,rt,1,n,T.tree[x].fa,T.tree[y].fa,0); if(T.tree[x].dep==T.tree[y].dep) { T.update(rt,rt,1,n,T.tree[y].fa,1,1); } } } }D; bool check(int mid,int u,int v,int n) { int fa=D.find(T.root[mid],u,n); for(int i=u+1;i<=v;i++) { if(fa!=D.find(T.root[mid],i,n)) { return false; } } return true; } int main() { int n,m,q,u,v,l,r,mid,ans,i; scanf("%d%d%d",&n,&m,&q); T.build_tree(T.root[0],1,n); for(i=1;i<=m;i++) { scanf("%d%d",&u,&v); T.root[i]=T.root[i-1]; D.merge(T.root[i-1],T.root[i],u,v,n); } for(i=1;i<=q;i++) { scanf("%d%d",&u,&v); l=0; r=m; ans=0; while(l<=r) { mid=(l+r)/2; if(check(mid,u,v,n)==true) { ans=mid; r=mid-1; } else { l=mid+1; } } printf("%d\n",ans); } return 0; } -
\(80pts\) ：维护历史节点并不是最优做法，考虑记录当前属于第几个连通块，主席树维护历史版本，线段树上子节点信息在上传至父亲节点时判断是否均属于一个连通块，方便查询。由于合并时需要启发式合并，主席树需要多点修改，时间复杂度为 \(O(m \log^{2} n+q \log n \log m)\) 。
- 因为学校 \(OJ\) 跑得慢所以过不了。
-
-
正解
- 将时间作为这条边的权值。
- \([l,r]\) 两两连通等价于 \(\forall i \in [l,r),i\) 和 \(i+1\) 连通。
- 设 \(f_{u,v}\) 表示 \(u \to v\) 的最大边权的最小值，跑 \(Kruskal\) 重构树维护即可，做法同 luogu P2245 星际导航 。那么 \(\max\limits_{i=l}^{r-1}\{ f_{i,i+1} \}\) 即为所求，挂个 \(ST\) 表维护即可。
点击查看代码
struct DSU { int fa[400010]; int find(int x) { return (fa[x]==x)?x:fa[x]=find(fa[x]); } }D; struct ST { int fmaxx[400010][25]; void init(int n,int a[]) { for(int i=1;i<=n;i++) { fmaxx[i][0]=a[i]; } for(int j=1;j<=log2(n);j++) { for(int i=1;i<=n-(1<<j)+1;i++) { fmaxx[i][j]=max(fmaxx[i][j-1],fmaxx[i+(1<<(j-1))][j-1]); } } } int query(int l,int r) { int t=log2(r-l+1); return max(fmaxx[l][t],fmaxx[r-(1<<t)+1][t]); } }T; struct node { int nxt,from,to,w; }e[400010],E[400010]; int head[400010],dep[400010],fmaxx[400010][25],fa[400010][25],f[400010],N,cnt=0; bool cmp(node a,node b) { return a.w<b.w; } void add(int u,int v,int w) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; e[cnt].w=w; head[u]=cnt; } void kruskal(int m) { int x,y,i; sort(E+1,E+1+m,cmp); for(i=1;i<=m;i++) { x=D.find(E[i].from); y=D.find(E[i].to); if(x!=y) { D.fa[x]=y; add(E[i].from,E[i].to,E[i].w); add(E[i].to,E[i].from,E[i].w); } } } void dfs(int x,int father,int w) { fa[x][0]=father; dep[x]=dep[father]+1; fmaxx[x][0]=w; for(int i=1;(1<<i)<=dep[x];i++)//原题为避免清空带来的时间影响，这里需要遍历到 N { fa[x][i]=fa[fa[x][i-1]][i-1]; fmaxx[x][i]=max(fmaxx[x][i-1],fmaxx[fa[x][i-1]][i-1]); } for(int i=head[x];i!=0;i=e[i].nxt) { if(e[i].to!=father) { dfs(e[i].to,x,e[i].w); } } } int lca(int x,int y) { if(D.find(x)!=D.find(y)) { return -1; } else { int maxx=0; if(dep[x]>dep[y]) { swap(x,y); } for(int i=N;i>=0;i--) { if(dep[x]+(1<<i)<=dep[y]) { maxx=max(maxx,fmaxx[y][i]); y=fa[y][i]; } } if(x==y) { return maxx; } else { for(int i=N;i>=0;i--) { if(fa[x][i]!=fa[y][i]) { maxx=max(maxx,max(fmaxx[x][i],fmaxx[y][i])); x=fa[x][i]; y=fa[y][i]; } } maxx=max(maxx,max(fmaxx[x][0],fmaxx[y][0])); return maxx; } } } int main() { int n,m,q,u,v,i; cin>>n>>m>>q; N=log2(n)+1; for(i=1;i<=m;i++) { cin>>E[i].from>>E[i].to; E[i].w=i; } for(i=1;i<=n;i++) { D.fa[i]=i; } kruskal(m); for(i=1;i<=n;i++) { if(dep[i]==0) { dfs(i,0,0); } } for(i=1;i<=n-1;i++) { f[i]=lca(i,i+1); } T.init(n,f); for(i=1;i<=q;i++) { cin>>u>>v; cout<<((u==v)?0:T.query(u,v-1))<<endl; } return 0; }
\(T3\) P157. 容易的多元拉格朗日反演练习题（multi） \(10pts\)
\(T4\) P158. 朴素的抽象代数题（algebra） \(0pts\)
总结
后记
-
可能没有 指 \(T1,T2,T3\) 没有， \(T4\) 有。
