「NOI2020」超现实树
2022/8/2 23:22:46
本文主要是介绍「NOI2020」超现实树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目
点这里看题目。
分析
困难的题目。
思路一
从命题逻辑的角度考察一棵树的限制。
某棵树的 \(\operatorname{grow}\) 可以被写作树上结点存在性(在或不在)的合取。考察 \(\operatorname{grow}\) 的并的时候,出于方便运算的考虑可以取补集,于是就变成了析取范式的合取运算。
然而树形结构并没有给析取式带来什么很好的性质,并且两个析取式合并后貌似没法转化成树形,只能作罢。不知道这个思路能不能用在其它题目里面。
思路二
即便我们可以给出最后所有树的 \(\operatorname{grow}\) 对应的一个逻辑条件,我们还是得检查“是否有无穷多组解”,倒不如一开始就从这个切口入手。
考虑 \(m\) 棵树的结点的并集,记为 \(T^\cup\)。可以发现,\(\operatorname{grow}(\mathscr{T})\) 是不完备的,当且仅当存在一棵满足如下条件的树 \(T^*\):
-
\(T^*\) 包含了 \(T^{\cup}\) 中至少一个叶子。
-
\(T^*\not\in \operatorname{grow}(\mathscr T)\)。
这个条件的充分性是显然的——我们可以随便替换那一个叶子,从而产生无穷棵 \(\not\in \operatorname{grow}(\mathscr T)\) 的树。而必要性应该可以直接通过分析 \(\not\in \operatorname{grow}(\mathscr T)\) 的树的数量是有限的来达成,就不赘述了。反正我也不会
那么,如果我们选定了一个叶子 \(l\),怎么检查是否有一棵 \(T^*\) 包含了它且不在 \(\operatorname{grow}(\mathscr T)\) 内?最傻瓜的策略是,我们从树根拉一条路径到 \(l\),但是这当然很容易被一些简单的单链堵住。再做一些调整,我们在其它位置上支出去一些支链——此时就可以发现,支出去的支链必然是叶子,不会更长。如果有另一棵树在支链位置上伸出来了一棵非叶子的子树,那么它不可能防得住我这一个叶子,所以现在我们只需要考虑叶子的限制。
Note.
这里的想法仍然是从“傻瓜策略”出发,一路调整。
思考过程其实更加接近于博弈题目,考虑一些基本的操作,然后看好不好,不好就修修补补,总可以走到一个较优的策略。
最好要熟悉这样的思考方式,不要下一次又想不起来。
那么,我们从 \(\mathscr T\) 中的树的角度来分析。如果有 \(T\in \mathscr T\),满足 \(T\) 中有一个叶子 \(\overline l\) 是 \(l\) 或者 \(l\) 的祖先,我们考察 \(T\) 上从根到 \(\overline l\) 的路径:如果路径上有一些不是叶子的支链,这样的 \(T\) 不可能产生任何效果,因为我们只会在支链的位置上放或不放叶子;否则,这条路径就可以被描述成 \(01\) 串 \(S_T\),每个位置描述路径上的结点有没有支出去一个叶子。如果最终我们构造的树上,描述分支情况的 \(01\) 串包含 \(S_T\) 作为一个前缀,那么这样的树就会存在于 \(\operatorname{grow}(T)\) 中,寄了。
对于某个 \(T^\cup\) 上的叶子 \(l\),找出所有可能的 \(S_T\),构成集合 \(P_l\)。我们现在需要检查是否存在一个 \(01\) 串,使得任意的 \(P_l\) 中的串都不是它的前缀。显然现在我们应该建立 \(P_l\) 的 Trie 树,且为了方便处理,我们将所有儿子个数不充分的非叶子结点的儿子补全。类似于上面的分析,存在一个上述 \(01\) 串的条件就是,存在一个 Trie 上的叶子,满足它的祖先都不在 \(P_l\) 中。这样的检查可以用标记做到线性。
Note.
两个都是在处理特定“存在性”的检查问题。并且还有一定的共性,那就是考虑一些极小的、特殊的不合法解(当然,也可以是极大的、特殊的合法解)。关键在于,我们要主动施加特殊性质,从而避免繁杂的讨论和太多可能性。
从技术的角度来看,我们可以看作是先有“完整的”\(T^\cup\) 和“完整的”Trie(也就是叶子深度相同,完全补全了),然后再收缩大量无用的结点,精简到了只需要考虑有限的结点的情况。
也可以记忆一下这里的处理方式,
毕竟自己还是走了弯路想错过一次的,不要再犯这样的错误了。
现在我们完成了一个叶子的检查。依据树形结构,我们很容易想到按照 DFS 顺序枚举叶子,这样可以充分利用公共信息。所以,我们首先建立出 \(T^\cup\),以及 \(\bigcup_l P_l\) 对应的 Trie 树,并把 Trie“补全”。此时我们将每一个 \(T\) 在叶子上的限制挂到 \(T^{\cup}\) 对应的结点上,在 DFS 的时候我们就在这些结点上将限制插入 Trie。处理 Trie 一边的限制也就容易了,我们将 \(P_l\) 处理成树上标记,这样相当于需要处理区间加减、维护全局最小值,线段树即可胜任。最终复杂度即为 \(O(n\log n)\)。
代码
#include <cstdio> #include <vector> #define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ ) #define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- ) const int MAXN = 4e6 + 5; template<typename _T> inline void Read( _T &x ) { x = 0; char s = getchar(); bool f = false; while( ! ( '0' <= s && s <= '9' ) ) { f = s == '-', s = getchar(); } while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s ^ '0' ), s = getchar(); } if( f ) x = -x; } template<typename _T> inline void Write( _T x ) { if( x < 0 ) putchar( '-' ), x = -x; if( 9 < x ) Write( x / 10 ); putchar( x % 10 + '0' ); } template<typename _T> inline _T Max( const _T &a, const _T &b ) { return a > b ? a : b; } template<typename _T> inline _T Min( const _T &a, const _T &b ) { return a < b ? a : b; } struct Node { int ch[2]; Node(): ch{} {} Node( int L, int R ): ch{ L, R } {} inline bool IsLeaf() const { return ! ch[0] && ! ch[1]; } }; typedef std :: vector<Node> Tree; int mn[MAXN << 2], tag[MAXN << 2]; int lef[MAXN], rig[MAXN], ID; std :: vector<int> chg[MAXN]; Tree tre, pref, uni; int M; void DFS1( const int &u, int uUni, int uPref ) { if( tre[u].IsLeaf() ) { if( uPref ) chg[uUni].push_back( uPref ); return ; } rep( k, 0, 1 ) if( int v = tre[u].ch[k] ) { if( ! uni[uUni].ch[k] ) { uni.push_back( { 0, 0 } ); uni[uUni].ch[k] = ( int ) uni.size() - 1; chg[( int ) uni.size() - 1].clear(); } int nxt = uPref, d; if( ! tre[u].ch[k ^ 1] ) d = 0; else { if( ! tre[tre[u].ch[k ^ 1]].IsLeaf() ) nxt = 0; else d = 1; } if( ! nxt ) DFS1( v, uni[uUni].ch[k], 0 ); else { if( ! pref[uPref].ch[d] ) { pref.push_back( { 0, 0 } ); pref[uPref].ch[d] = ( int ) pref.size() - 1; } DFS1( v, uni[uUni].ch[k], pref[uPref].ch[d] ); } } } void DFS2( const int &u ) { if( pref[u].IsLeaf() ) lef[u] = rig[u] = ++ ID; else { lef[u] = 1e9, rig[u] = - 1e9; rep( k, 0, 1 ) if( int v = pref[u].ch[k] ) { DFS2( v ); lef[u] = Min( lef[u], lef[v] ); rig[u] = Max( rig[u], rig[v] ); } } } inline void Upt( const int &x ) { mn[x] = Min( mn[x << 1], mn[x << 1 | 1] ); } inline void Add( const int &x, const int &delt ) { mn[x] += delt, tag[x] += delt; } inline void Normalize( const int &x ) { if( ! tag[x] ) return ; Add( x << 1, tag[x] ); Add( x << 1 | 1, tag[x] ); tag[x] = 0; } void Build( const int &x, const int &l, const int &r ) { if( l > r ) return ; tag[x] = mn[x] = 0; if( l == r ) return ; int mid = ( l + r ) >> 1; Build( x << 1, l, mid ); Build( x << 1 | 1, mid + 1, r ); } void Update( const int &x, const int &l, const int &r, const int &segL, const int &segR, const int &delt ) { if( segL <= l && r <= segR ) { Add( x, delt ); return ; } int mid = ( l + r ) >> 1; Normalize( x ); if( segL <= mid ) Update( x << 1, l, mid, segL, segR, delt ); if( mid < segR ) Update( x << 1 | 1, mid + 1, r, segL, segR, delt ); Upt( x ); } inline void Init() { rep( i, 1, ( int ) pref.size() - 1 ) { if( pref[i].IsLeaf() ) continue; if( ! pref[i].ch[0] ) { pref.push_back( Node() ); pref[i].ch[0] = ( int ) pref.size() - 1; } if( ! pref[i].ch[1] ) { pref.push_back( Node() ); pref[i].ch[1] = ( int ) pref.size() - 1; } } ID = 0, DFS2( 1 ); Build( 1, 1, ID ); } bool DFS4( const int &u ) { int n = chg[u].size(); rep( i, 0, n - 1 ) Update( 1, 1, ID, lef[chg[u][i]], rig[chg[u][i]], +1 ); if( uni[u].IsLeaf() ) { if( mn[1] == 0 ) return true; } else rep( k, 0, 1 ) if( int v = uni[u].ch[k] ) if( DFS4( v ) ) return true; rep( i, 0, n - 1 ) Update( 1, 1, ID, lef[chg[u][i]], rig[chg[u][i]], -1 ); return false; } int main() { int T; Read( T ); while( T -- ) { Read( M ); pref.clear(); pref.push_back( { 0, 0 } ); pref.push_back( { 0, 0 } ); uni.clear(); uni.push_back( { 0, 0 } ); uni.push_back( { 0, 0 } ); chg[0].clear(); chg[1].clear(); bool anyOne = false; rep( i, 1, M ) { int n; Read( n ); tre.clear(); tre.push_back( { 0, 0 } ); rep( j, 1, n ) { int x, y; Read( x ), Read( y ); tre.push_back( { x, y } ); } anyOne |= n == 1; DFS1( 1, 1, 1 ); } if( anyOne ) { puts( "Almost Complete" ); continue; } Init(); puts( ! DFS4( 1 ) ? "Almost Complete" : "No" ); } return 0; }
这篇关于「NOI2020」超现实树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-23Springboot应用的多环境打包入门
- 2024-11-23Springboot应用的生产发布入门教程
- 2024-11-23Python编程入门指南
- 2024-11-23Java创业入门:从零开始的编程之旅
- 2024-11-23Java创业入门:新手必读的Java编程与创业指南
- 2024-11-23Java对接阿里云智能语音服务入门详解
- 2024-11-23Java对接阿里云智能语音服务入门教程
- 2024-11-23JAVA对接阿里云智能语音服务入门教程
- 2024-11-23Java副业入门:初学者的简单教程
- 2024-11-23JAVA副业入门:初学者的实战指南