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/2021/07/02/72-xun-lian/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog