10.23 模拟赛

10.23 模拟赛

dls 毒瘤!

T1 爬杆

首先,50分很好做,单调栈找找就行了。。后面做法考场胡了个错误的贪心(Orz zzh 会正解)

每个点到全局最小点都得有路。我们可以考虑拿最小点出来递归左右(其实就是笛卡尔树)。

然后还有一个贪心,对于两个点我们想在其中修路,假设小的在左边,大的在右边,那么一定是小的走一段,剩下的都走大的,显然最优。其实第一段之间是不会有其他点的,所以可以看成是全部走的大的。

一个生动形象的例子,如果我们向从第一个梯子到最后一个得到一条路,那么可以这么修:

L90CB`D7EBR_0_F96R__TIP.png

如果到达一个点,发现假设左边原本就搭建了高度$h_l$的梯子,那么递归时考虑如果$h_l = a_i$那么显然递归时不需要再修建新的梯子,否则都需要。 右边同理。

相当于存了笛卡尔树的板子了

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<stack>
using namespace std;
#define pii pair<int,int>
#define mp make_pair
#define int long long
#define MAXN 200006
#define MAXV 1000006
int n , mx;
int h[MAXN] , stk[MAXN] , top = 0;
int L[MAXN] , R[MAXN];

int T[MAXV << 2];
int que( int rt , int l , int r , int L , int R ) {
if( L <= l && R >= r ) return T[rt];
int m = l + r >> 1 , ret = -0x3f3f3f3f;
if( L <= m ) ret = max( ret , que( rt << 1 , l , m , L , R ) );
if( R > m ) ret = max( ret , que( rt << 1 | 1 , m + 1 , r , L , R ) );
return ret;
}
void mdfy( int rt , int l , int r , int p , int c ) {
T[rt] = max( T[rt] , c );
if( l == r ) return;
int m = l + r >> 1;
if( p <= m ) mdfy( rt << 1 , l , m , p , c );
else mdfy( rt << 1 | 1 , m + 1 , r , p , c );
}
int S[MAXN] , len[MAXN];
namespace solve2 {
int l[MAXN] , r[MAXN] , d[MAXN] , rt , stk[MAXN] , tp = 0;
bool cmp( int x , int y ) {
return h[x] < h[y];
}
void build(){
for( int i = 1 ; i <= n ; ++ i ) {
int k=tp;
while (k > 0 && h[stk[k-1]] > h[i]) --k;
if (k) r[stk[k-1]]=i;
if (k<tp) l[i]=stk[k];
stk[k++]=i;
tp=k;
}
}
int res(0);
void dfs( int u , int ll , int rr ) {
if( l[u] )
if( h[u] == ll ) dfs( l[u] , ll , ll );
else res += u - l[u] , dfs( l[u] , ll , h[l[u]] );
if( r[u] )
if( h[u] == rr ) dfs( r[u] , rr , rr );
else res += r[u] - u , dfs( r[u] , h[r[u]] , rr );
}
int main() {
build();
dfs( stk[0] , -1 , -1 );
return res;
}
}
int tt;
signed main() {
cin >> n;
for( int i = 1 ; i <= n ; ++ i ) scanf("%lld",&h[i]) , mx = max( mx , h[i] ) , S[i] = S[i - 1] + h[i];
cin >> tt;
for( int i = 0 ; i <= mx * 4 + 3 ; ++ i ) T[i] = -0x3f3f3f3f;
for( int i = 1 ; i <= n ; ++ i ) {
int t = que( 1 , 1 , mx , 1 , h[i] );
L[i] = t;
mdfy( 1 , 1 , mx , h[i] , i );
}
int ans = 0;
for( int i = 1 ; i <= n ; ++ i )
if( L[i] != -0x3f3f3f3f )
len[i] = len[L[i]] + ( h[i] - h[L[i]] ) * L[i] + S[i - 1] - S[L[i]] - ( i - 1 - L[i] ) * h[i] , ans += len[i] , ans += i * ( n - i );
else
len[i] = S[i] - h[i] * i , ans += len[i] , ans += i * ( n - i );
cout << ans << ' ';
if( tt == 1 ) return 0;
cout << solve2::main() << endl;
}

T2 变换

可以发现答案就是 不是 k 的数量 + 大于k小于k的连续段的长度/2的和

然后写代码是不可能写代码的这辈子不可能写代码的。

1
duliu!

T3 游戏

满足条件的情况一定是原树存在完美匹配。如果有点到子孙或者子孙到祖先的完美匹配,先手选择了一个位置,后手一定可以选择一个和它匹配的位置。否则在几次选择后先手必胜,因为无法完美匹配。

然后考虑设$dp[i][j]$表示 i 为根子树中有 j 个点还没有被匹配的情况数,就可以直接转移了。考虑根节点是否被选择,被选择其实就是$dp[i][j] = dp[i][j] + dp[i][j + 1]$

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
#define int long long
#define MAXN 2006
#define P 998244353
int n;
int dp[MAXN][MAXN];
vector<int> G[MAXN];
int siz[MAXN];
void dfs( int u , int fa ) {
dp[u][0] = 1 , siz[u] = 1;
for( int v : G[u] ) {
if( v == fa ) continue;
dfs( v , u );
siz[u] += siz[v];
for( int j = siz[u] ; j >= 0 ; -- j ) {
dp[u][j] *= dp[v][0] , dp[u][j] %= P;
for( int k = 1 ; k <= siz[v] && j - k >= 0 ; ++ k )
dp[u][j] += dp[v][k] * dp[u][j - k] % P , dp[u][j] %= P;
}
}
int tt = dp[u][0];
for( int i = 0 ; i < siz[u] ; ++ i ) dp[u][i] += dp[u][i + 1] , dp[u][i] %= P;
dp[u][1] += tt;
}
signed main() {
cin >> n;
for( int i = 1 , u , v ; i < n ; ++ i )
scanf("%lld%lld",&u,&v) , G[u].push_back( v ) , G[v].push_back( u );
dfs( 1 , 1 );
int res = 0;
for( int i = 1 ; i <= n ; ++ i ) res += dp[1][i] , res %= P;
cout << res << endl;
}
文章作者: yijan
文章链接: https://yijan.co/old12/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog