10.25 模拟赛

A 闯关

对于一个数组，前缀最小值肯定是一段一段得

我们可以考虑一个显然得贪心，每一段最开头从后往前放1，2，3，…，除开最开头的位置直接从前往后放没有放过的。

每一段其实就是一个极长的递增子段。

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int a[N], b[N];

int main() {
	int n; scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	int ct = 0;
	for (int i = 1; i <= n; i++) {
		int r = i;
		while (r < n && a[i] <= a[r + 1]) r++;
		b[a[i]] = ++ct, i = r;
	}
	for (int i = 1; i <= n; i++) {
		if (!b[i]) b[i] = ++ct;
		printf("%d ", b[i]);
	}
}

B 动物园

考虑对于一个1操作，看作 u 作为左儿子， v 作为右儿子建立一个类似kruskal重构树的东西。

由于考虑种类狠毒瘤，而考虑概率很方便就可以考虑概率。

然后对于一次 1 操作， u 的动物保留的概率是$\frac{2}{3}$v 的动物保留的概率是$\frac{1}{3}$。

所以查询一个点最后的概率就是它向上走的过程中作为左子树出现了多少次，作为右子树出现了多少次，一个点每作为左子树出现一次保留的概率就乘以 2/3 。

维护可以随便拿个数据结构，目测最短的是带权并查集，比较容易理解的是splay直接合并。我写的set按秩合并打tag维护。（真的想吐槽一下这数据真的就随机数据吧。。本机拍的时候运气坏都可以跑1.2s。。

#include <bits/stdc++.h>
using namespace std;
#define tup tuple<int,int,int>
typedef long long ll;
#define MAXN 200006
#define P 998244353
int n , m;
set<tup> vec[MAXN];
int dirl[MAXN] , dirr[MAXN];
int fa[MAXN];
int find( int x ) {
	return x == fa[x] ? x : fa[x] = find( fa[x] );
}
ll power( ll x , ll a ) {
	ll res = 1 , cur = x % P;
	while( a ) {
		if( a & 1 ) res *= cur , res %= P;
		cur *= cur , cur %= P , a >>= 1;
	}
	return res;
}
int main() {
	cin >> n >> m;
	ll dl = power( 3 , P - 2 );
	int opt = 0 , u , v , U , V;
	for( int i = 1 ; i <= n ; ++ i ) fa[i] = i , vec[i].insert( make_tuple( i , 0 , 0 ) );
	while( m --> 0 ) {
		scanf("%d",&opt);
		if( opt == 1 ) {
			scanf("%d%d",&u,&v);
			U = find( u ) , V = find( v );
			if( vec[U].size() < vec[V].size() ) {
				fa[U] = V , ++ dirr[V];
				for( auto pr : vec[U] ) vec[V].insert( make_tuple( get<0>(pr) , get<1>(pr) + dirl[U] - dirl[V] + 1 , get<2>(pr) - dirr[V] + dirr[U] ) );
			} else {
				fa[V] = U , ++ dirl[U];
				for( auto pr : vec[V] ) vec[U].insert( make_tuple( get<0>(pr) , get<1>(pr) - dirl[U] + dirl[V] , get<2>(pr) - dirr[U] + dirr[V] + 1 ) );
			}
		} else {
			scanf("%d",&u);
			U = find( u );
			tup pr = *vec[U].lower_bound( make_tuple( u , -0x3f3f3f3f , -0x3f3f3f3f ) );
//			cout << get<0>(pr) << ' ' << get<1>(pr) + dirl[U] << ' ' << get<2>(pr) + dirr[U] << endl;
			ll res = power( 2 , get<1>(pr) + dirl[U] ) * power( dl , get<1>(pr) + dirl[U] + get<2>(pr) + dirr[U] ) % P * power( 3 , n ) % P;
			printf( "%lld\n", res );
		}
	}
	
}

C 树

首先做一个最简单的树形dp，设$f[i][0/1]$表示 i 为根的子树的最大独立集，其中 i 不选/可选可不选。

考虑进行题目中给定的这个操作，加入我们在尝试构建$T_i$，用$G_0$表示$T_{i-1}$的根节点不选的最大独立集，$G_1$表示$T_{i-1}$根节点可以选择可以不选时的最大独立集。

然后分类讨论：

-$G_0 = G_1$果断选择所有被挂上去的$T_{i-1}$都不选根，我们还可以给当前的$base$来选个最大独立集。
-$G_1 = G_0 + 1$ 我们给所有挂上去的都选择根，显然优秀于第一个情况的选法，因为树的最大独立集不可能超过$n$

这样设计状态有一个好处，就是碰撞的概率很小。如果直接拿小于符号和大于符号来比模了错误概率是很大的。

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
#define MAXN 100006
#define P 998244353
int n , m;
vector<int> G[MAXN];
int dp[MAXN][2];
void dfs( int u , int fa ) {
	dp[u][0] = 0 , dp[u][1] = 1;
	for( int v : G[u] ) if( v != fa )
		dfs( v , u ),
		dp[u][0] += max( dp[v][0] , dp[v][1] ) , dp[u][1] += dp[v][0];
}
void dfs2( int u , int fa ) {
	int t0;
	for( int v : G[u] ) if( v != fa ) 
		t0 = dp[u][0] - max( dp[v][0] , dp[v][1] ) ,
		dp[v][0] += max( t0 , dp[u][1] - dp[v][0] ) ,
		dp[v][1] += t0 ,
		dfs2( v , u );
}
int main() {
	cin >> n >> m;
	for( int i = 1 , u , v ; i < n ; ++ i )
		scanf("%d%d",&u,&v) , G[u].push_back( v ) , G[v].push_back( u );
	dfs( 1 , 1 );
	dfs2( 1 , 1 );
	for( int i = 1 ; i <= n ; ++ i ) dp[i][1] = max( dp[i][0] , dp[i][1] );
	int kel = 0 , lst0 = dp[1][0] , lst1 = dp[1][1];
	printf("%d\n",lst1);
	while( m --> 0 ) {
		scanf("%d",&kel);
		if( lst0 == lst1 ) 
			lst1 = ( 1ll * n * lst0 % P + dp[kel][1] ) % P , lst0 = ( 1ll * n * lst0 + dp[kel][0] ) % P;
		else 
			lst1 = lst0 = 1ll * n * lst1 % P;
		printf("%d\n",lst1);
	}
}