CSP-S 2019 树上的数 （贪心）（链表）（并查集）（思维）

考完过后心情不太好，下午躺床上看了出题人写的题解，有了一些想法，记录下来
首先请大家不要喷 $t3$ 的出题人了，题真的是一道好题，只是可能放错了位置

题意

根据考场回忆：
给定一棵树，有点权，为$1-n$，你可以按一个顺序删 $n-1$ 条边，每次删边会调换连接这条边的两个点的权值，最后按点权排序，求结点编号的字典序最小的解，输出结点编号最小字典序，$n\le 2000$

部分分大概是：
$n!,10pts$
$n^3$,链 $10pts$
$n^2$ 链 $15pts$
$n^3$ 菊花图 $10pts$
$n^2$ 菊花图 $15pts$
$n^3,40pts$

我考场的想法以及下来与一些神仙交流的想法如下：

按数字贪心归位，归位时直接枚举规到哪一个，只需要支持有没有与之前的冲突
判断的时候就比较头疼，需要处理路径相交的情况
然后还有交换的顺序，一个点换过去需要等那边的边都换完才能最后定下
然后啥也没打出来

正解：
根据我们的贪心策略以及做题前的大致框架，只要枚举到一个点并且判断合法，就一定会把它挪过去
然后用个啥东西维护我们的判断

考虑到一个数如果要在一个点停下，那么它来的这个边是与这个点的所有出边最后选的
如果一个数要从一个点出去，那么它一定是所有出边中第一个被选的
如果一个数要经过这个点，那么它进去和出来的边在选择顺序上一定是相邻的

考虑到菊花图除根只有一个出边，应该比较好做，从这里入手
贪心枚举数字及结尾结点，一个限制要么是经过根即入边出边相邻，要么是到达根或者从根出去
现在的问题就是判断有解？
可以枚举之前所有的限制判断 $O(n^3)$
发现可以一个大多数限制是将两条边捆绑在一起，捆绑的时候要保证第一条边后面没有边，第二条边前面没有边，维护一个链表记录 $pre,nxt$ 应该就可以做了，$O(n^2)$

链的情况：
考虑到 1 个点的度数最多就是 2，那么以上的限制条件对于任何一个点都是一条边在另一条边之前
？？拓扑排序判断，对这些条件建出一个图拓扑排序 $O(n^3)$

考虑到一个点如果要归位到另一个点，产生的限制是中间的一条链上的边产生的限制
而当到一个点的限制已经不满足的时候，它后面的也不会满足
我们直接 $dfs$ 它所有能到达的结点，利用拓扑序$O(1)$检查合不合法，复杂度 $O(n^2)$

一般的情况：
由于度数不是 2，不同点之间在选边的相对顺序上不会有限制，所以没有办法建出上述的图
等等，不同点之间的顺序没有限制，可不可以对每个点分别考虑
一条边 $u,v$ 的限制可以拆成在 $u$ 的限制和在 $v$ 分别的限制，二者不干扰
然后发现一个点到另一个点的限制是一条链上的限制，这和链的做法是特别像的
于是可以类似链的做法 $dfs$，$dfs$ 到的当前点就是归位的终点，实时更新当前点到根的限制合不合法
判断在每一个点的图中用菊花图的链表进行判断，复杂度 $O(n^2)$

反思：
考场上执迷于想正解或者是退化成 $O(n^3)$ 的一般情况
而事后来看这是最繁琐的情况
其实这道题最佳的突破口就是链和菊花图这两个突破口
链的度数为 2 的性质可以将问题转换为一条边在另一条之前之后
菊花图的性质可以把限制集中到一个点
为什么我的方法繁琐，就是因为看问题太过于整体，考虑的一直是全局的限制
而正解的思想就是将一些整体的限制转换到每一个点局部的小限制

看出题人发的题解，第一句话是验题人建议加一个菊花图的部分分以提示选手
现在想了想，部分分的用途不仅是让你拿分，也是让你一步步趋近正解

考场上没有头绪也没有针对性的思考导致最后只有 $10pts$
如果专心想链或是菊花图也许分数不会这么难看

upt (19/11/21)：
判断的一些细节：
注意不合法的情况一种是两条边被合并过了，于是用并查集维护一下已经合并了的边
然后如果是终边要判一下还有没有没有选的边，如果有那么它不能是终边
如果是始边且与终边合并过，要判一下是不是所有边都合并了
如果这条边串起了终边和始边那么也要保证所有边都合并过
并查集维护一个 $size$ 就可以知道合并的边的个数

#include<bits/stdc++.h>
#define cs const
using namespace std;
int read(){
int cnt = 0, f = 1; char ch = 0;
while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1; }
while(isdigit(ch)) cnt = cnt*10 + (ch-'0'), ch = getchar();
return cnt * f;
}
cs int N = 2e3 + 5;
int T, n, ps[N];
int L[N][N], R[N][N], fa[N][N];
int st[N], ed[N];
int siz[N][N], pre[N];
vector<int> v[N];
bool vis[N];
int ans[N];
int find(int rt, int x){ return fa[rt][x] == x ? x : fa[rt][x] = find(rt, fa[rt][x]); }
void dfs(int u, int f){
for(int i = 0; i < v[u].size(); i++) if(v[u][i]^f) pre[v[u][i]] = u;
if(f == 0){
for(int i = 0; i < v[u].size(); i++){
int t = v[u][i];
if(ed[t]) continue; // finish position
if(L[u][t] != t) continue;
if(find(t, st[t]) == find(t, u)){
if(siz[t][find(t, st[t])] != v[t].size()) continue;
}
if(find(u, ed[u]) == find(u, t)){
if(siz[u][find(u, ed[u])] != v[u].size()) continue;
}
if(R[t][u] != u) continue;
vis[t] = 1;
}
}
else{
for(int i = 0; i < v[u].size(); i++){
int t = v[u][i];
if(t == f) continue;
if(ed[t]) continue;
if((R[u][f] == t && L[u][t] == f) || (R[u][f] == f && L[u][t] == t && find(u, f) != find(u, t))){
if(find(t, st[t]) == find(t, u)){
if(siz[t][find(t, st[t])] != v[t].size()) continue;
}
if(find(u, t) == find(u, ed[u])){
if(find(u, f) == find(u, st[u])){
if(siz[u][find(u, f)] + siz[u][find(u, t)] != v[u].size()) continue;
}
}
if(find(u, t) == find(u, st[u])){
if(find(u, f) == find(u, ed[u])){
if(siz[u][find(u, f)] + siz[u][find(u, t)] != v[u].size()) continue;
}
} if(R[t][u] == u) vis[t] = 1;
}
}
}
if(f == 0){
for(int i = 0; i < v[u].size(); i++){
int t = v[u][i];
if(find(u, t) == find(u, ed[u])){
if(siz[u][find(u, ed[u])] != v[u].size()) continue;
} dfs(t, u);
}
}
else{
if(ed[u] != f){
for(int i = 0; i < v[u].size(); i++){
int t = v[u][i];
if(t == f) continue;
if( ((R[u][f] == f && find(u, f) != find(u, t)) || R[u][f] == t) &&
((L[u][t] == t && find(u, t) != find(u, f)) || L[u][t] == f) ){
if(find(u, t) == find(u, ed[u])){
if(find(u, f) == find(u, st[u])){
if(siz[u][find(u, f)] + siz[u][find(u, t)] != v[u].size()) continue;
}
}
if(find(u, t) == find(u, st[u])){
if(find(u, f) == find(u, ed[u])){
if(siz[u][find(u, f)] + siz[u][find(u, t)] != v[u].size()) continue;
}
} dfs(t, u);
}
}
}
}
}
void modify(int u, int v){ // u -> v
ed[v] = pre[v];
R[v][pre[v]] = -1;
int nxt = v; v = pre[v];
while(v ^ u){
R[v][pre[v]] = nxt;
L[v][nxt] = pre[v];
int fx = find(v, pre[v]);
int fy = find(v, nxt);
if(fx ^ fy){ fa[v][fy] = fx; siz[v][fx] += siz[v][fy]; }
nxt = v; v = pre[v];
} st[v] = nxt; L[v][nxt] = -1;
}
void Solve(){
n = read();
for(int i = 1; i <= n; i++) ps[i] = read();
for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) fa[i][j] = L[i][j] = R[i][j] = j, siz[i][j] = 1;
for(int i = 1; i <= n; i++) v[i].clear(), st[i] = ed[i] = 0;
for(int i = 1; i < n; i++){
int x = read(), y = read();
v[x].push_back(y);
v[y].push_back(x);
}
for(int t = 1; t <= n; t++){
int nx = ps[t];
for(int i = 1; i <= n; i++) vis[i] = pre[i] = 0;
dfs(nx, 0);
for(int i = 1; i <= n; i++){
if(vis[i]){ ans[t] = i; modify(nx, i); break; }
}
} for(int i = 1; i <= n; i++) cout << ans[i] << " ";
puts("");
}
int main(){
T = read();
while(T--) Solve();
return 0;
}

最后

以上就是合适金鱼为你收集整理的CSP-S 2019 树上的数 （贪心）（链表）（并查集）（思维）的全部内容，希望文章能够帮你解决CSP-S 2019 树上的数 （贪心）（链表）（并查集）（思维）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。