Yijan's Blog HomeArchives
7.2 训练

A [CTSC2010]星际旅行

我们考虑每次旅行收益一样，提示我们这题很可能可以贪心。然后考虑每个点有 $H_i \ge deg_i$ ，可以发现这正好是从 $1$ 出发遍历所有点然后回到 $1$ 的代价，于是我们先考虑终点在 $1$ ，直接把这个代价减掉，得到新的 $H_i$ 。此时能够增加答案的方法就是选择相邻的两个点把他们的 $H$ 同时减少 $1$ ，然后路径上就是进行一次左右横跳，会让答案增加 $2$ 。

这个过程显然是可以贪心做的（因为一个点）把 $H$ 留着匹配上面的收益和往下匹配收益相同。

然后考虑终点不在 $1$ ，可以发现去掉的就是从这个点回到根路径上的 $H$ ，也就是把这个点到根路径上除了根的部分 $+1$ ，所以就有了一个 $O(n^2)$ 的做法。

然后考虑怎么优化。这个东西看起来可以考虑换根 $dp$ 一下。具体来说，当我们处理到 $u$ 的时候，设 $pd[f]$ 表示它的父亲在不考虑 $u$ 儿子的时候做完贪心剩下的 $H$ ，同时维护答案，然后就可以转移了。对于一个点 $u$ ，它向某个儿子转移的时候，我们可以维护所有儿子的前后缀所剩 $H$ 和，然后就可以算出 $pd$ 了。

复杂度 $O(n)$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 50006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
typedef double db;
const int P = 998244353;
int n , m , q;
int A[MAXN];

vi G[MAXN];

int dp[MAXN] , as[MAXN] , re[MAXN];
void dfs( int u , int f ) {
	dp[u] = A[u];
	for( int v : G[u] ) if( v != f ) {
		dfs( v , u );
		if( dp[v] > dp[u] ) as[u] += max( dp[u] , 0 ) , dp[u] = -1;
		else as[u] += max( dp[v] , 0 ) , dp[u] -= max( dp[v] , 0 );
		as[u] += as[v];
	}
}

int pd[MAXN] , er[MAXN] , dep[MAXN] , sd;
void dfs$( int u , int f ) {
	if( u != 1 ) {
		re[u] = as[u];
		int lef = dp[u] + 1;
		if( dp[u] < 0 ) ++ re[u];
		re[u] += min( lef , pd[f] );
		re[u] += er[f];
		re[u] = re[u] * 2 + sd - dep[u];
	}
	pd[u] = dp[u] + 1;
	vi ps( G[u].size() + 1 ) , pse( G[u].size() + 1 );
	per( i , G[u].size() - 1 , 0 ) if( G[u][i] != f ) {
		ps[i] = ps[i + 1] + max( dp[G[u][i]] , 0 ) , pse[i] = pse[i + 1] + as[G[u][i]];
	} else ps[i] = ps[i + 1] , pse[i] = pse[i + 1];
	int pr = 0 , pe = 0;
	for( int i = 0 ; i < G[u].size() ; ++ i ) if( G[u][i] != f ) {
		int v = G[u][i];
		int lef = pr + ps[i + 1] + pd[f];
		pd[u] = max( A[u] + ( u != 1 ) - lef , 0 );
		er[u] = pe + pse[i + 1] + er[f] + min( lef , A[u] + ( u != 1 ) );
		dep[v] = dep[u] + 1;
		dfs$( v , u );
		pr += max( dp[v] , 0 ) , pe += as[v];
	}
}

void solve() {
	cin >> n;
	rep( i , 1 , n ) scanf("%d",A + i);
	rep( i , 2 , n ) {
		int u , v;
		scanf("%d%d",&u,&v);
		++ u , ++ v;
		G[u].pb( v ) , G[v].pb( u );
	}
	rep( i , 1 , n ) A[i] -= G[i].size() , sd += G[i].size();
	dfs( 1 , 1 );
	re[1] = as[1] * 2 + sd;
	dfs$( 1 , 0 );
	rep( i , 1 , n ) printf("%d\n",re[i]);
}

signed main() {
//	freopen("input","r",stdin);
//	freopen("logo.out","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
	solve();
}


B TreasureOfWinedag

可以发现最后答案在 $[k,k + 26]$ ，因为我们可以直接把前 $k-1$ 个字符每个分成一段，最后单独成一段。

这又是一个 $dp$ 复杂度很高，但是 $dp$ 值的范围很小的题，这种题往往会把 $dp$ 值做状态来做。尝试一下，可以设 $dp[i][x]$ 表示当前在 $i$ ，答案超过了分的段数 $x$ ，最少需要分的段数，然后转移就是枚举最后的一段会有多少不同数，转移即可。

可以发现，最后如果有 $dp[n][x] \le k$ ，那么一定可以做到 $k + x$ ，只需要选择一些段合并起来即可，答案不会变大。

复杂度 $O(n26^2)$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 100006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
typedef double db;
const int P = 998244353;
int n , k , m;
char ch[MAXN];
int dp[MAXN][40];

int las[26];

struct TreasureOfWinedag {
	int solvePuzzle( int N , int K , int M , int c0 , vi c1 , vi c2 , vi c3 , vi c4 , string s ) {
		n = N , k = K , m = M;
		rep( i , 0 , s.length() - 1 ) ch[i + 1] = s[i];
		rep( i , s.length() + 1 , n ) {
			int t = ( ( i - 1 ) * 1ll * c0 ) % m;
			ch[i] = 'z';
			rep( j , 0 , 24 ) if( t >= c3[j] && t <= c4[j] && ( t % c1[j] == c2[j] ) ) {
				ch[i] = j + 'a';
				break;
			}
		}
		memset( dp , 0x3f , sizeof dp );
		dp[0][0] = 0;
		rep( i , 1 , n ) {
			las[ch[i] - 'a'] = i;
			vi ps;
			rep( j , 0 , 25 ) ps.pb( las[j] );
			ps.pb( 0 );
			sort( ps.rbegin() , ps.rend() );
			int tr = 0;
			for( int x : ps ) if( x != i ) {
				++ tr;
				rep( k , 0 , 28 ) if( k - ( tr - 1 ) >= 0 )
					dp[i][k] = min( dp[i][k] , dp[x][k - ( tr - 1 )] + 1 );
			}
		}
		rep( t , 0 , 30 ) if( dp[n][t] <= k ) return t + k;
		return 114514;
	}
} S ;

void solve() {
//	cout << S.solvePuzzle(
//	) << endl;
}

//signed main() {
//	freopen("input","r",stdin);
//	freopen("logo.out","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
//	solve();
//}

C SetAndSet

可以考虑容斥，钦定一些位必须是一边是 $0$ 一边是 $1$ 。

然后考虑怎么计算这个东西，可以从小到大枚举位，对每一位，我们把所有为 $0$ 的数缩起来，表示它们不可被分到两堆。对每队缩完后，最后答案显然就是 $2^{tot} - 2$ ，其中 $tot$ 就是联通块个数。

这个东西复杂度 $O(2^{20}\times 20\times n)$ ，实际上常数比较小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 100006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
typedef double db;
const int P = 998244353;
int n , k , m;
char ch[MAXN];
int dp[MAXN][40];

int las[26];

struct TreasureOfWinedag {
	int solvePuzzle( int N , int K , int M , int c0 , vi c1 , vi c2 , vi c3 , vi c4 , string s ) {
		n = N , k = K , m = M;
		rep( i , 0 , s.length() - 1 ) ch[i + 1] = s[i];
		rep( i , s.length() + 1 , n ) {
			int t = ( ( i - 1 ) * 1ll * c0 ) % m;
			ch[i] = 'z';
			rep( j , 0 , 24 ) if( t >= c3[j] && t <= c4[j] && ( t % c1[j] == c2[j] ) ) {
				ch[i] = j + 'a';
				break;
			}
		}
		memset( dp , 0x3f , sizeof dp );
		dp[0][0] = 0;
		rep( i , 1 , n ) {
			las[ch[i] - 'a'] = i;
			vi ps;
			rep( j , 0 , 25 ) ps.pb( las[j] );
			ps.pb( 0 );
			sort( ps.rbegin() , ps.rend() );
			int tr = 0;
			for( int x : ps ) if( x != i ) {
				++ tr;
				rep( k , 0 , 28 ) if( k - ( tr - 1 ) >= 0 )
					dp[i][k] = min( dp[i][k] , dp[x][k - ( tr - 1 )] + 1 );
			}
		}
		rep( t , 0 , 30 ) if( dp[n][t] <= k ) return t + k;
		return 114514;
	}
} S ;

void solve() {
//	cout << S.solvePuzzle(
//	) << endl;
}

//signed main() {
//	freopen("input","r",stdin);
//	freopen("logo.out","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
//	solve();
//}


文章作者: yijan
文章链接: https://yijan.co/72-xun-lian/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog！