csp-s模拟10
\(T1\) T3673. 欧几里得的噩梦 \(0pts\)
- 部分分
- \(0 \%\) ：状压加枚举子集。
- \(20 \%\) ：线性基暴力做。
- 正解
\(T2\) T3672. 清扫 \(6pts\)
-
钦定根节点 \(rt\) 的度数 \(\ge 2\) ，所以需要特判 \(n=2\) 的情况。
-
部分分
- 未知 \(pts\) ：
- 等价于查询是否存在一种进行若干次点差分方式，对于差分数组 \(d\) 满足 \(\forall x \in [1,n],a_{x}=\sum\limits_{y \in Subtree(x)}d_{y}\) 。
- 直接进行高斯消元时间复杂度不可接受，手动解出 \(d_{x}=a_{x}-\sum\limits_{y \in Son(x)}a_{y}\) 。
- 又因为对于非叶子节点的 \(x\) 其 \(d_{x}\) 由 \(x\) 作为 \(fa_{\operatorname{LCA}(u,v)}\) 和 \(x\) 作为 \(\operatorname{LCA}(u,v)\) 两部分的贡献组成，设它们分别为 \(f_{x},g_{x}\) ，有 \(f_{x}+g_{x}=d_{x}\) 。
- 不难得到 \(f_{x}=\sum\limits_{y \in Son(x)}g_{y}\) ，即 \(d_{x}=g_{x}+\sum\limits_{y \in Son(x)}g_{y}\) ，类似 \(\{ d \}\) 的求法再次手动求出 \(\{ f \},\{ g \}\) 。
- 问题就转化为是否存在一种构造方式使得点差分时叶子节点 \(x\) 恰好访问了 \(d_{x}\) 次，而非叶子节点 \(y\) 作为任意两个叶子节点的 \(\operatorname{LCA}\) 被访问了 \(-g_{y}\) 遍。
- 赛时因为不知道怎么判断，所以只写了最基本的 \(-\sum\limits_{i=1}^{n}[du_{i} \ne 1] \times g_{i}=\sum\limits_{i=1}^{n}[du_{i}=1] \times d_{i}\) ，没过大样例。
- 未知 \(pts\) ：
-
正解
- \(\{ f \}\) 数组好像没啥用，直接扔掉。并令 \(\{ g \}\) 都乘以 \(-1\) 表示作为 \(\operatorname{LCA}(u,v)\) 的次数，此时 \(g_{x}=-d_{x}-\sum\limits_{y \in Son(x)}g_{y}\) ，令叶子节点的 \(g=0\) 。
- 令 \(f_{x}\) 表示 \(x\) 子树内叶子节点向上拓展的总路径条数（差分剩下的），有 \(f_{x}=\begin{cases} a_{x} & du_{x}=1 \\ -2g_{x}+\sum\limits_{y \in Son(x)}f_{y} & du_{x} \ne 1 \end{cases}\) 。
- 考虑此时如何判断有解。
- \(g_{x} \ge 0\)
- \(f_{rt}=0\)
- \(0 \le f_{x} \le a_{x} \land \sum\limits_{y \in Son(x)}f_{y}- \max\limits_{y \in Son(x)}\{ f_{y} \} \ge g_{x}\)
- 前者隐含了 \(\frac{\sum\limits_{y \in Son(x)}f_{y}}{2} \ge g_{x}\) 的条件。
- 后者的感性理解是若 \(\max\limits_{y \in Son(x)}\{ f_{y} \} > \frac{\sum\limits_{y \in Son(x)}f_{y}}{2}\) ，则合并次数在满足 \(f_{y}\) 最大的 \(y\) 子树和其他子树进行合并时取到最多 \(\sum\limits_{y \in Son(x)}f_{y}- \max\limits_{y \in Son(x)}\{ f_{y} \}\) ；否则两两进行匹配，合并次数为 \(\frac{\sum\limits_{y \in Son(x)}f_{y}}{2}\) 。
- 证明有点抽象，感性理解吧。
点击查看代码
struct node { ll nxt,to; }e[200010]; ll head[200010],du[200010],a[200010],d[200010],f[200010],g[200010],cnt=0; void add(ll u,ll v) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt; } void dfs(ll x,ll fa) { ll sum=0,maxx=0; d[x]=a[x]; if(du[x]==1) { f[x]=a[x]; return; } for(ll i=head[x];i!=0;i=e[i].nxt) { if(e[i].to!=fa) { dfs(e[i].to,x); d[x]-=a[e[i].to]; g[x]-=g[e[i].to]; sum+=f[e[i].to]; maxx=max(maxx,f[e[i].to]); } } g[x]-=d[x]; f[x]=-2*g[x]+sum; if(g[x]<0||f[x]<0||f[x]>a[x]||sum-maxx<g[x]) { cout<<"NO"<<endl; exit(0); } } int main() { freopen("tree.in","r",stdin); freopen("tree.out","w",stdout); ll n,u,v,rt,i; cin>>n; for(i=1;i<=n;i++) { cin>>a[i]; } for(i=1;i<=n-1;i++) { cin>>u>>v; du[u]++; du[v]++; add(u,v); add(v,u); } if(n==2) { if(a[1]==a[2]) { cout<<"YES"<<endl; } else { cout<<"NO"<<endl; } } else { for(i=1;i<=n;i++) { if(du[i]>=2) { rt=i; break; } } dfs(rt,0); if(f[rt]==0) { cout<<"YES"<<endl; } else { cout<<"NO"<<endl; } } fclose(stdin); fclose(stdout); return 0; }
\(T3\) T1072. 购物 \(20pts\)
- 部分分
-
子任务 \(1,3\) ：背包处理出能拼出来的商品价格，然后写一个静态推平全局查询的数据结构即可。
点击查看代码
struct ODT { struct node { ll l,r; mutable ll col; bool operator < (const node &another) const { return l<another.l; } }; set<node>s; void init() { s.insert((node){0,1000000000010,0}); } set<node>::iterator split(ll pos) { set<node>::iterator it=s.lower_bound((node){pos,0,0}); if(it!=s.end()&&it->l==pos) { return it; } it--; if(it->r<pos) { return s.end(); } ll l=it->l,r=it->r,col=it->col; s.erase(it); s.insert((node){l,pos-1,col}); return s.insert((node){pos,r,col}).first; } void assign(ll l,ll r,ll col) { set<node>::iterator itr=split(r+1),itl=split(l); s.erase(itl,itr); s.insert((node){l,r,col}); } ll query(ll l,ll r) { set<node>::iterator itr=split(r+1),itl=split(l); ll ans=0; for(set<node>::iterator it=itl;it!=itr;it++) { ans+=(it->col==1)*(it->r-it->l+1); } return ans; } }O; ll a[100010]; bool f[1000010]; void dfs(ll pos,ll n,ll sum) { if(pos==n+1) { if(sum!=0) { O.assign(ceil(sum/2.0),sum,1); } } else { dfs(pos+1,n,sum+a[pos]); dfs(pos+1,n,sum); } } int main() { freopen("buy.in","r",stdin); freopen("buy.out","w",stdout); ll n,m=0,i,j; cin>>n; for(i=1;i<=n;i++) { cin>>a[i]; m+=a[i]; } O.init(); if(m<=1000000) { f[0]=1; for(i=1;i<=n;i++) { for(j=m;j>=a[i];j--) { f[j]|=f[j-a[i]]; } } for(i=1;i<=m;i++) { if(f[i]==1) { O.assign(ceil(i/2.0),i,1); } } } else { dfs(1,n,0); } cout<<O.query(0,1000000000000)<<endl; fclose(stdin); fclose(stdout); return 0; }
-
- 正解
\(T4\) T1042. ants \(20pts\)
- 弱化版： BZOJ4358 permu
- 部分分
-
\(20pts\) ：枚举值域起点，时间复杂度为 \(O(nm)\) 。
点击查看代码
int a[100010],pos[100010],vis[100010]; int main() { freopen("ants.in","r",stdin); freopen("ants.out","w",stdout); int n,m,l,r,ans; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); pos[a[i]]=i; } for(int j=1;j<=m;j++) { scanf("%d%d",&l,&r); ans=0; for(int i=1;i<=n;i++) { if(vis[i]==0) { int k; for(k=i;l<=pos[k]&&pos[k]<=r;k++) { vis[k]=1; } ans=max(ans,k-i); } vis[i]=0; } printf("%d\n",ans); } fclose(stdin); fclose(stdout); return 0; } -
\(50pts\) ：同 BZOJ4358 permu 的做法，时间复杂度为 \(O(n \sqrt{m} \log n)\) 。因普通版线段树常数过大所以无法通过。
点击查看代码
int a[400000],ans[400000],L[400000],R[400000],pos[400000],klen,ksum; struct ask { int l,r,id; }q[400000]; bool q_cmp(ask a,ask b) { return (pos[a.l]==pos[b.l])?((pos[a.l]%2==1)?(a.r<b.r):(a.r>b.r)):(a.l<b.l); } struct SegmentTree { int l,r,maxl,maxr,ans; }tree[400000]; int lson(int x) { return x*2; } int rson(int x) { return x*2+1; } void pushup(int rt) { tree[rt].maxl=tree[lson(rt)].maxl+(tree[lson(rt)].maxl==tree[lson(rt)].r-tree[lson(rt)].l+1)*tree[rson(rt)].maxl; tree[rt].maxr=tree[rson(rt)].maxr+(tree[rson(rt)].maxr==tree[rson(rt)].r-tree[rson(rt)].l+1)*tree[lson(rt)].maxr; tree[rt].ans=max(max(tree[lson(rt)].ans,tree[rson(rt)].ans),tree[lson(rt)].maxr+tree[rson(rt)].maxl); } void build(int rt,int l,int r) { tree[rt].l=l; tree[rt].r=r; if(l==r) { return; } int mid=(l+r)/2; build(lson(rt),l,mid); build(rson(rt),mid+1,r); pushup(rt); } void update(int rt,int pos,int ans) { if(tree[rt].l==tree[rt].r) { tree[rt].ans=tree[rt].maxl=tree[rt].maxr=ans; return; } else { int mid=(tree[rt].l+tree[rt].r)/2; if(mid>=pos) { update(lson(rt),pos,ans); } else { update(rson(rt),pos,ans); } pushup(rt); } } SegmentTree query(int rt,int l,int r) { if(l<=tree[rt].l&&tree[rt].r<=r) { return tree[rt]; } else { int mid=(tree[rt].l+tree[rt].r)/2; if(r<=mid) { return query(lson(rt),l,r); } else { if(l>mid) { return query(rson(rt),l,r); } else { SegmentTree p=query(lson(rt),l,r),q=query(rson(rt),l,r),num; num.maxl=p.maxl+(p.maxl==p.r-p.l+1)*q.maxl; num.maxr=q.maxr+(q.maxr==q.r-q.l+1)*p.maxr; num.ans=max(max(p.ans,q.ans),p.maxr+q.maxl); return num; } } } } void init(int n,int m) { klen=n/sqrt(m)+1; ksum=500; for(int i=1;i<=ksum;i++) { L[i]=R[i-1]+1; R[i]=R[i-1]+klen; } if(R[ksum]<n) { ksum++; L[ksum]=R[ksum-1]+1; R[ksum]=n; } for(int i=1;i<=ksum;i++) { for(int j=L[i];j<=R[i];j++) { pos[j]=i; } } } void add(int x) { update(1,a[x],1); } void del(int x) { update(1,a[x],0); } int main() { freopen("ants.in","r",stdin); freopen("ants.out","w",stdout); int n,m,l=1,r=0,i; cin>>n>>m; for(i=1;i<=n;i++) { cin>>a[i]; } build(1,1,n); init(n,m); for(i=1;i<=m;i++) { cin>>q[i].l>>q[i].r; q[i].id=i; } sort(q+1,q+1+m,q_cmp); for(i=1;i<=m;i++) { while(l>q[i].l) { l--; add(l); } while(r<q[i].r) { r++; add(r); } while(l<q[i].l) { del(l); l++; } while(r>q[i].r) { del(r); r--; } ans[q[i].id]=query(1,1,n).ans; } for(i=1;i<=m;i++) { cout<<ans[i]<<endl; } return 0; }
-
- 正解
-
考虑只加不减莫队。加入一个数 \(x\) 时判断 \(x-1,x+1\) 是否已经加入并连一条边，接着链表或可撤销并查集维护即可。
点击查看代码
struct ask { int l,r,id; }q[100010]; int a[100010],b[100010],ans[100010],L[100010],R[100010],pos[100010],vis[100010],klen,ksum; bool q_cmp(ask a,ask b) { return (pos[a.l]==pos[b.l])?(a.r<b.r):(a.l<b.l); } void init(int n,int m) { klen=n/sqrt(m)+1; ksum=n/klen; for(int i=1;i<=ksum;i++) { L[i]=R[i-1]+1; R[i]=R[i-1]+klen; } if(R[ksum]<n) { ksum++; L[ksum]=R[ksum-1]+1; R[ksum]=n; } for(int i=1;i<=ksum;i++) { for(int j=L[i];j<=R[i];j++) { pos[j]=i; } } } struct DSU { struct quality { int id,fa,siz; }; stack<quality>s; int fa[100010],siz[100010]; void init(int n) { for(int i=1;i<=n;i++) { fa[i]=i; siz[i]=1; } } int find(int x) { return (fa[x]==x)?x:find(fa[x]); } void merge(int x,int y,int &sum) { x=find(x); y=find(y); if(x!=y) { if(siz[x]<siz[y]) { swap(x,y); } s.push((quality){x,fa[x],siz[x]}); s.push((quality){y,fa[y],siz[y]}); fa[y]=x; siz[x]+=siz[y]; sum=max(sum,siz[x]); } } void split(int tmp) { while(s.empty()==0&&s.size()>tmp) { fa[s.top().id]=s.top().fa; siz[s.top().id]=s.top().siz; s.pop(); } } }D; void add(int x,int &sum) { vis[x]=1; if(vis[x-1]==1) { D.merge(x,x-1,sum); } if(vis[x+1]==1) { D.merge(x,x+1,sum); } } int main() { freopen("ants.in","r",stdin); freopen("ants.out","w",stdout); int n,m,l=1,r=0,sum,tmp=1,num,lastblock=0,i,j; cin>>n>>m; for(i=1;i<=n;i++) { cin>>a[i]; } for(i=1;i<=m;i++) { cin>>q[i].l>>q[i].r; q[i].id=i; } init(n,m); sort(q+1,q+1+m,q_cmp); D.init(n); for(i=1;i<=m;i++) { if(pos[q[i].l]==pos[q[i].r]) { sum=num=1; for(j=q[i].l;j<=q[i].r;j++) { b[j]=a[j]; } sort(b+q[i].l,b+q[i].r+1); for(j=q[i].l+1;j<=q[i].r;j++) { num=(b[j-1]==b[j]-1)*num+1; sum=max(sum,num); } } else { if(lastblock!=pos[q[i].l]) { while(r>R[pos[q[i].l]]) { vis[a[r]]=0; r--; } while(l<R[pos[q[i].l]]+1) { vis[a[l]]=0; l++; } tmp=1; r=R[pos[q[i].l]]; l=R[pos[q[i].l]]+1; lastblock=pos[q[i].l]; D.split(0); } while(r<q[i].r) { r++; add(a[r],tmp); } sum=tmp; num=D.s.size(); while(l>q[i].l) { l--; add(a[l],sum); } D.split(num); while(l<R[pos[q[i].l]]+1) { vis[a[l]]=0; l++; } } ans[q[i].id]=sum; } for(i=1;i<=m;i++) { cout<<ans[i]<<endl; } fclose(stdin); fclose(stdout); return 0; }
-
总结
- 感觉思维越来越不行了，需要稍微跳跃点的就反应不过来了。
- \(T2\) 只判了叶子节点的 \(d\) 忘判非叶子节点的 \(g\) 了，挂了 \(20pts\) 。
- \(T3\) 只记得写子任务 \(3\) 的超大背包部分分了，忘了写子任务 \(1\) 的正常背包部分分了，挂了 \(30pts\) 。
- \(T4\) 赛时没记得做过原题，我是不是该拉出去毙了。