Yijan's Blog HomeArchives
6.6 模拟赛

A 树

考虑先化一下第一个式子，那么就是

然后我们不考虑 $\binom{|A|}{2}$ 。

可以猜测这个式子有特殊含义，所以把第一部分也加进这里面来统计，具体来说，我们把这个 $\sum_{u \in A} d_u$ 拆成对于每个 $A,B$ 集合的点，算它子树内的 $A$ 集合点的数量。然后考虑现在 $A$ 集合的点的实际贡献，会发现实际上一个 $A$ 集合点 $u$ 的贡献是 $A$ 集合中 $u$ 的子树的点的数量，减去 $A$ 集合中 $w_u \le w_v$ 且 $v$ 在子树内的数量，剪掉之后正好是有多少点 $v$ 满足 $w_u > w_v$ ，$v$ 在 $u$ 子树内。然后对于 $B$ 集合的点 $u$ ，我们需要统计有多少 $A$ 中的点在 $u$ 子树内，以及有多少 $B$ 中的点 $v$ 满足 $w_u < w_v$ ，且 $v$ 在 $u$ 子树内。

所以说，现在对于一对互为祖先关系的点 $(i,j)$ ，其中 $i$ 是 $j$ 祖先，它们有贡献当且仅当

  • $i \in B,j \in A$
  • $i \in B,j\in B,w_i < w_j$
  • $i \in A,j\in A,w_i > w_j$

然后考虑对于一个 $B$ 点，它实际上对答案的贡献是什么，会发现是子树内的 $A$ 点的数量加上子树内 $w$ 大于这个点的数量，一个 $A$ 点的贡献就是子树内 $w$ 小于它的 $A$ 点的贡献。

如果我们按照 $w$ 从小到大的顺序来填 $A,B$ ，那么当你填一个 $B$ 的时候，它的贡献就是子树内 $A$ 点的数量加上子树内权值大于当前点的 $B$ 的数量，当你填一个 $A$ 的时候，它的贡献是子树内 $A$ 的数量。会发现，两边都有子树内 $A$ 的数量，所以事实上，我们可以在填入 $A$ 的时候直接加上这个点到根路径上还未确定的点的数量，但是这样会漏掉下面填 $A$ 的时候上面已经填入 $B$ 的情况，所以填入 $B$ 的时候直接加上子树内还未确定的点的数量，容易发现这样就和原来的贡献等价了。

所以会发现一个优美的形式：对于一个点，如果把它放到 $A$ 里面，它的贡献就是这个点到根路径上的大于这个点权值的个数，放到 $B$ 里面，就是这个点子树内的大于这个点权值的个数。

然后权值相等的情况稍微想一想，会发现先填底下一定更优，因此这也是对的。

于是直接把两种权值分别求出，然后 sort 即可。

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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 500006
//#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;
int n , m;
int A[MAXN];
int w1[MAXN] , w2[MAXN];

vi G[MAXN];
int L[MAXN] , R[MAXN] , clo;
const int SZ = 5e5;

struct BIT {
	int T[MAXN];
	void add( int x , int c ) {
		while( x <= SZ ) T[x] += c , x += ( x & -x );
	}
	int sum( int x ) {
		int ret = 0;
		while( x ) ret += T[x] , x -= ( x & -x );
		return ret;
	}
} T , S ;

void dfs( int u , int f ) {
	w2[u] = - S.sum( SZ - A[u] );
	w1[u] = T.sum( SZ - A[u] );
	T.add( SZ - A[u] + 1 , 1 ) , S.add( SZ - A[u] + 1 , 1 );
	L[u] = ++ clo;
	for( int v : G[u] ) if( v != f ) {
		dfs( v , u );
	}
	R[u] = clo;
	T.add( SZ - A[u] + 1 , -1 );
	w2[u] += S.sum( SZ - A[u] );
}

int idx[MAXN];
ll C2( int x ) {
	return x * 1ll * ( x - 1 ) / 2;
}

void solve() {
	cin >> n;
	rep( i , 1 , n ) scanf("%d",A + i) , idx[i] = i;
	rep( i , 2 , n ) {
		int u , v;
		scanf("%d%d",&u,&v);
		G[u].pb( v ) , G[v].pb( u );
	}
	dfs( 1 , 1 );
	sort( idx + 1 , idx + 1 + n , [&]( int a , int b ) { return w2[a] - w1[a] < w2[b] - w1[b]; } );
	ll as = 0;
	rep( i , 1 , n ) as = as + w1[i];
	printf("%lld\n",as + C2( n ));
	rep( i , 1 , n ) {
		as += w2[idx[i]] - w1[idx[i]];
		printf("%lld\n",as + C2( n - i ));
	}
}

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

B 旅行

阴间题！！1

思路很简单，我们只需要按照拓扑序给整张图排好序，然后从前到后 $dp[u][v]$ 表示第一个路径走到了 $u$ ，第二个路径走到了 $v$ 的方案数。

我们考虑怎么转移，对于 $dp[a][b]$ 如果有 $a > b$ ，必然有一条路径上一次结尾走到了 $a-1$ ，然后跳过来。我们考虑把转移分为两步，第一步是从两个点都在之前的环里面转移到存在点在当前环里面。这时候需要分类讨论，要么是一个点跳进来，要么是两个点都跳进来。

然后我们现在求出的 $dp[u][v]$ 是只考虑跳进来，不考虑环内行走的情况。然后我们需要讨论环内的阴间转移。

首先我们需要特判掉环大小为 $1$ ，其中有 $k = 1$ 的情况。然后是只有一个点在环内的情况，这种情况比较容易我们去枚举从哪个点到达要转移到的点，然后乘上 $k-1$ 表示可以到达后再转这么多圈，然后如果到达的点正好是这个点上一个点可以不转圈，这个再特判加上即可。

然后是两个点在环内跑的情况，我们需要讨论几种情况，具体情况就不写了，建议手玩一下，但是有一种 djq 写的非常精妙的实现，可以先把基本情况，也就是两个人必须转至少一圈，最后加起来不超过 $k-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
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 5006
//#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;
const int P = 998244353;
int n , m , k;
vi G[MAXN] , rG[MAXN];

int dfn[MAXN] , low[MAXN] , clo , ins[MAXN] , stk[MAXN] , tp , bel[MAXN] , scc;
vi poi[MAXN];
void tarjan( int u ) {
	dfn[u] = low[u] = ++ clo;
	ins[u] = 1 , stk[++ tp] = u;
	for( int v : G[u] ) {
		if( !dfn[v] ) tarjan( v ) , low[u] = min( low[u] , low[v] );
		else if( ins[v] ) low[u] = min( low[u] , dfn[v] );
	}
	if( dfn[u] == low[u] ) {
		int x;
		++ scc;
		do {
			x = stk[tp --];
			poi[scc].pb( x );
			bel[x] = scc , ins[x] = 0;
		} while( x != u );
		reverse( all( poi[scc] ) );
	}
}

int dp[MAXN][MAXN] , pr[MAXN][MAXN] , pd[MAXN][MAXN] , tm[MAXN];
void Inc( int& a , int b ) {
	a = a + b < P ? a + b : a + b - P;
}
int le;
int calc( int i , int j ) {
	if( i > j ) swap( i , j );
	return ( ( 1ll * pr[i][j] - pr[i][i] + pr[le][j] - pr[le][i] - pr[j][j] + pr[j][i] ) % P + P ) % P;
}

void solve() {
	cin >> n >> m >> k;
	rep( i , 1 , m ) {
		int u , v;
		scanf("%d%d",&u,&v);
		G[u].pb( v ) , rG[v].pb( u );
	}
	if( !k ) return void( puts("0") );
	rep( i , 1 , n ) G[n + 1].pb( i ) , rG[i].pb( n + 1 );
	++ n;
	rep( i , 1 , n ) if( !dfn[i] ) tarjan( i );
//	tarjan( n );
	dp[n][n] = 1;
//	cout << scc << endl;
	per( i , scc - 1 , 1 ) {
		for( int u : poi[i] ) rep( t , 1 , n ) if( bel[t] > i ) { // 钦定一个点在当前联通块作为以前跳过来的点
					for( int v : rG[u] ) if( min( bel[v] , bel[t] ) == i + 1 )
							Inc( dp[u][t] , dp[v][t] ) , Inc( dp[t][u] , dp[v][t] );
				}
		for( int u : poi[i] ) for( int v : poi[i] ) { // 由上一种情况转移到两个都是跳进来的情况
				for( int x : rG[u] ) if( bel[x] > i )
						Inc( dp[u][v] , dp[x][v] );
			}
		if( poi[i].size() == 1 ) {
			if( k == 1 ) dp[poi[i][0]][poi[i][0]] = 0;
			continue;
		}
		le = poi[i].size();
		// 考虑环内转移，先是只有一个点在环内的状态的转移
		rep( x , 1 , n ) if( bel[x] > i ) {
				int sum = 0;
				for( int u : poi[i] )
					tm[u] = dp[x][u] , Inc( sum , dp[x][u] );
				sum = sum * 1ll * ( k - 1 ) % P;
				rep( j , 0 , le - 1 )
					dp[x][poi[i][j]] = dp[poi[i][j]][x] = ( sum + tm[poi[i][( j + 1 ) % le]] ) % P;
			}
		// 然后是两个点都在环内的转移
//		continue;
		rep( j , 0 , le - 1 ) rep( t , 0 , le - 1 )
				pr[j + 1][t + 1] = dp[poi[i][j]][poi[i][t]];
		if( k == 1 ) {
			rep( j , 0 , le - 1 ) rep( t , 0 , le - 1 )
					dp[poi[i][j]][poi[i][t]] = ( j == t ? 0 : pr[( t + 1 ) % le + 1][( j + 1 ) % le + 1] );
			continue;
		}
		rep( j , 1 , le ) rep( t , 1 , le ) Inc( pr[j][t] , pr[j][t - 1] );
		// #1 一个点由它的上一个位置转一圈得到
		rep( j , 1 , le ) rep( t , 1 , le ) {
				int nxj = j % le + 1 , nxt = t % le + 1;
				pd[j][t] = ( pr[nxj][le] + pr[nxt][le] + 1ll * P - dp[poi[i][nxj - 1]][poi[i][nxt - 1]] ) % P;
			}
		rep( j , 1 , le ) rep( t , 1 , le ) Inc( pr[j][t] , pr[j - 1][t ] );
		int sum = pr[le][le] * 1ll * ( ( k - 2 ) * 1ll * ( k + 1 ) / 2 % P ) % P;
//		cout << sum << endl;
		// add for all x_1 + x_2 <= k - 2 , x_1 + x_2 > 0
		rep( j , 1 , le ) rep( t , 1 , le ) if( j != t )
					pd[j][t] = ( pd[j][t] + k * 1ll * calc( t , j ) + calc( t % le + 1 , j % le + 1 ) ) % P;
		rep( j , 1 , le ) rep( t , 1 , le ) dp[poi[i][j - 1]][poi[i][t - 1]] = ( pd[j][t] + sum ) % P;
	}
	int res = 0;
	rep( i , 1 , n ) rep( j , 1 , n ) if( min( bel[i] , bel[j] ) == 1 ) Inc( res , dp[i][j] );
	cout << res << endl;
}

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


C 数学

这题几乎等价于前几天的那个 T1 。

首先我们可以发现 $\frac{a}{b} > p$ 等价于 $A - Bp > 0$ ，相当于每遇到一个好数就获得 $-p$ ，否则获得 $1-p$ ，求最少需要多久才能使得前缀和大于 $0$ 。

于是我们直接跟之前那个 Stickers 一样的办法去 $dp$ 即可。具体来说我们先用 $dp$ 确定位数，然后从低到高依次确定即可。

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 500006
//#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;
int n , m;
struct num {
#define N 500
	int A[N + 1];
	void flip( ) {
		rep( i , 0 , N ) A[i] = 9 - A[i];
	}
	num( ll x = 0 ) {
		ll t = abs( x );
		mem( A );
		if( !x ) return;
		int lt = 0;
		while( t ) A[lt ++] = t % 10 , t /= 10;
		if( x < 0 ) {
			flip( );
			rep( i , 0 , N ) {
				if( A[i] != 9 ) { ++ A[i]; break; }
				A[i] = 0;
			}
		}
	}
	num operator + ( num x ) {
		num ret;
		int ad = 0;
		rep( i , 0 , N ) {
			ret.A[i] = x.A[i] + A[i] + ad;
			ad = 0;
			if( ret.A[i] > 9 ) ad = 1 , ret.A[i] -= 10;
		}
		return ret;
	}
	bool operator < ( num x ) const {
		if( x.A[N] != A[N] ) return A[N] == 9;
		per( i , N , 0 ) if( A[i] != x.A[i] ) return A[i] < x.A[i];
		return false;
	}
	void mul10( int x ) {
		int flg = 0;
		if( A[N] == 9 ) {
			flip( );
			rep( i , 0 , N ) {
				if( A[i] != 9 ) { ++ A[i]; break; }
				A[i] = 0;
			}
			flg = 1;
		}
		per( i , N - 1 , x ) A[i] = A[i - x];
		per( i , x - 1 , 0 ) A[i] = 0;
		if( flg ) {
			flip( );
			rep( i , 0 , N ) {
				if( A[i] != 9 ) { ++ A[i]; break; }
				A[i] = 0;
			}
		}
	}
};

num p;

bool chk( int x ) {
	while( x >= 100 ) {
		int tl = x % 10 , tll = x / 10 % 10 , tlll = x / 100 % 10;
		if( tlll < tll && tll < tl ) return true;
		x /= 10;
	}
	return false;
}
ll pw[MAXN];

struct pr {
	num mx , s;
	pr(  ) : mx( -1e18 ) , s(0) {}
	pr( ll a , ll b ) : mx( a ) , s( b ) {}
	pr( num a , num b ) : mx( a ) , s( b ) {}
	pr operator + ( pr x ) {
		return pr( max( mx , s + x.mx ) , s + x.s );
	}
} dp[114][2][10][2] ;

pr cal( int l , int w , int x , int t ) {
	if( !l ) return pr( p , p );
	if( num( -1e18 ) < dp[l][w][x][t].mx ) return dp[l][w][x][t];
	pr& ret = dp[l][w][x][t];
	rep( i , w , 9 ) {
		if( i > x && t ) {
			num rr = ( p + num( 100000 ) );
			rr.mul10( l - 1 );
			ret = ret + pr( rr , rr );
		}
		else {
			ret = ret + cal( l - 1 , 0 , i , i > x );
		}
	}
	return ret;
}

int res[MAXN];

void solve() {
	double tt;
	cin >> tt;
	p = num( - tt * 100000 );
	pw[0] = 1;
	rep( i , 1 , 18 ) pw[i] = pw[i - 1] * 10;
	int lt = 0;
	pr tc;
	rep( i , 1 , 100 ) {
		pr tmp = ( tc + cal( i , 1 , 9 , 0 ) );
		if(  tmp.mx.A[N] == 0 ) {
			lt = i; break;
		} else tc = tmp;
	}
	int las = 9 , llas = 9 , flg = 0;
	pr tr = tc;
	per( i , lt , 1 ) {
		rep( j , ( i == lt ) , 9 ) {
			if( llas < las && las < j ) flg = 1;
			pr tmp;
			if( flg ) {
				num rr = ( p + num( 100000 ) );
				rr.mul10( i - 1 );
				tmp = tr + pr( rr , rr );
			} else tmp = tr + cal( i - 1 , 0 , j , las < j );
			if( tmp.mx.A[N] == 0 ) {
				llas = las , las = j , res[i] = j;
				break;
			} else tr = tmp;
		}
	}
	per( i , lt , 1 ) printf("%1d",res[i]); puts("");
}

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



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