暑假集训CSP提高模拟21
组题人： @Muel_imj
\(T1\) P241. 黎明与萤火 \(10pts\)
-
部分分
- \(10pts\) ：生成 \(1 \sim n\) 的全排列然后依次判断。
- \(20pts\) ：输出
NO。
-
正解
- 叶子节点的度数为 \(1\) ，不能直接删除，只能先删除父亲节点后再单点删除。若父亲节点度数是偶数可以直接删，否则接着向上找到一个度数为偶数的祖先节点删掉后一连串地删下来。
- 接着再从上到下扫一遍，看有没有被漏下的度数为奇数的点，若有说明无解，否则删掉这个点。
- 本质上是一个钦定最优解然后进行 \(check\) 的过程。
点击查看代码
int du[200010],vis[200010]; vector<int>e[200010],ans; void del(int x) { vis[x]=1; ans.push_back(x); for(int i=0;i<e[x].size();i++) { du[e[x][i]]--; } } void dfs1(int x,int fa) { for(int i=0;i<e[x].size();i++) { if(e[x][i]!=fa) { dfs1(e[x][i],x); } } if(du[x]%2==0) { del(x); } } void dfs2(int x,int fa) { if(vis[x]==0) { if(du[x]%2==0) { del(x); } else { cout<<"NO"<<endl; exit(0); } } for(int i=0;i<e[x].size();i++) { if(e[x][i]!=fa) { dfs2(e[x][i],x); } } } int main() { int n,u,v,rt=0,i; cin>>n; for(i=1;i<=n;i++) { cin>>u; v=i; if(u==0) { rt=i; } else { du[u]++; du[v]++; e[u].push_back(v); e[v].push_back(u); } } dfs1(rt,0); dfs2(rt,0); cout<<"YES"<<endl; for(i=0;i<ans.size();i++) { cout<<ans[i]<<endl; } return 0; }
\(T2\) P242. Darling Dance \(100pts\)
-
建出最短路 \(DAG\) 后在 \(DAG\) 上的边就是候选集合的边。接着进行大力分讨。
- 若边的数量 \(\le k\) ，直接输出 \(DAG\) 上的边即可。
- 若边的数量 \(>k\) ，不断找度数最大的点删边，直至成为一棵树，若还 \(>k\) 遍历一遍整棵树取 \(k\) 条边即可。
点击查看代码
struct node { ll nxt,to,w,id; }e[600010]; ll head[600010],dis[600010],vis[600010],din[600010],cut[600010],e_cnt=0,E_cnt=0,cnt=0; vector<pair<ll,ll> >E[600010],fE[600010]; void add(ll u,ll v,ll w,ll id) { e_cnt++; e[e_cnt].nxt=head[u]; e[e_cnt].to=v; e[e_cnt].w=w; e[e_cnt].id=id; head[u]=e_cnt; } void dijstra(ll s) { memset(dis,0x3f,sizeof(dis)); memset(vis,0,sizeof(vis)); priority_queue<pair<ll,ll> >q; dis[s]=0; q.push(make_pair(-dis[s],-s));; while(q.empty()==0) { ll x=-q.top().second; q.pop(); if(vis[x]==0) { vis[x]=1; for(ll i=head[x];i!=0;i=e[i].nxt) { if(dis[e[i].to]>dis[x]+e[i].w) { dis[e[i].to]=dis[x]+e[i].w; q.push(make_pair(-dis[e[i].to],-e[i].to)); } } } } } void build(ll n) { for(ll x=1;x<=n;x++) { for(ll i=head[x];i!=0;i=e[i].nxt) { if(dis[e[i].to]==dis[x]+e[i].w) { E_cnt++; E[x].push_back(make_pair(e[i].to,e[i].id)); fE[e[i].to].push_back(make_pair(x,e[i].id)); din[e[i].to]++; } } } } void top_sort(ll n) { queue<ll>q; for(ll i=1;i<=n;i++) { if(din[i]==0) { q.push(i); } } while(q.empty()==0) { ll x=q.front(); q.pop(); for(ll i=0;i<E[x].size();i++) { if(cut[E[x][i].second]==0) { cout<<E[x][i].second<<" "; din[E[x][i].first]--; if(din[E[x][i].first]==0) { q.push(E[x][i].first); } } } } } void dfs(ll x,ll k) { for(ll i=0;i<E[x].size();i++) { if(cut[E[x][i].second]==0&&cnt<k) { cnt++; cout<<E[x][i].second<<" "; dfs(E[x][i].first,k); } } } struct quality { ll pos,val; }a[600010]; bool cmp(quality a,quality b) { return a.val>b.val; } int main() { ll n,m,k,u,v,w,flag=0,i,j; cin>>n>>m>>k; for(i=1;i<=m;i++) { cin>>u>>v>>w; add(u,v,w,i); add(v,u,w,i); } dijstra(1); build(n); for(i=1;i<=n;i++) { a[i].pos=i; a[i].val=din[i]; } sort(a+1,a+1+n,cmp); for(i=1;i<=n;i++) { for(j=1;j<fE[a[i].pos].size();j++) { if(E_cnt<=k||E_cnt==n-1) { flag=1; break; } else { E_cnt--; din[a[i].pos]--; cut[fE[a[i].pos][j].second]=1; } } if(flag==1) { break; } } if(E_cnt>k) { cout<<k<<endl; dfs(1,k); } else { cout<<E_cnt<<endl; top_sort(n); } return 0; } -
或者只建最短路树，然后遍历一遍整棵树取 \(\min(k,n-1)\) 条边即可。
\(T3\) P243. Non-breath oblige \(0pts\)
- 原题： luogu P5524 [Ynoi2012] NOIP2015 充满了希望
- 部分分
- \(10pts\) ：暴力枚举操作，时间复杂度为 \(O(mq \log n)\) 。
- \(20pts\) ：没有操作 \(2\) ，则序列始终都是 \(0\) ，输出 \(0\) 即可。
- 正解
\(T4\) P244. 妄想感伤代偿联盟 \(0pts\)
- 部分分
- \(subtask 1\) ：输出 \(|a_{1}|\) 。
- \(subtask 2,subtask 3\) ：哈希优化字符串匹配或 \(KMP\) 维护，同 luogu P4824 [USACO15FEB] Censoring S 。
- 正解
- 等价于将 \(a_{x},a_{y}\) 拼起来问最长重叠长度，基础字符串拿个什么玩意维护，之前应该做过类似的。
总结
- \(T3\) 因 Ctrl+A 全选时因一些奇怪错误把
粘成了if(tree[rt].lazy!=-1) { tree[lson(rt)].sum=tree[rson(rt)].sum=tree[rt].lazy; tree[lson(rt)].lazy=tree[rson(rt)].lazy=tree[rt].lazy; tree[rt].lazy=-1; }
但是没有爆 \(CE\) ，挂了 \(10pts\) 。if(tree[rt].lazy!=-1) tree[lson(rt)].sum=tree[rson(rt)].sum=tree[rt].lazy; { tree[lson(rt)].lazy=tree[rson(rt)].lazy=tree[rt].lazy; tree[rt].lazy=-1; } - \(T4\) 以为 \(subtask 2,subtask 3\) 代码能过 \(subtask 1\) 就没写 \(subtask 1\) 的部分分，挂了 \(10pts\) 。