CF Round 591

CF1240 A ~ D

CF Round 591

A Save the Nature

为啥 A 放个这么长的题啊读着好累。。

二分一下在哪天之前结束,只需要判断当前最大捐款是否到达 $k$ 。这个贪心很显然, $(x+y)\%$ 的位置放最大的 $\frac{d}{\text{lcm}(a,b)}$ ,然后按照 $x,y$ 大小关系放剩下的最大的那部分就好了。

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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 200006
#define int long long
#define rep(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
typedef long long ll;
int n , m , A[MAXN];
int x , a , y , b; long long k;
int gcd( int a , int b ) {
return b ? gcd( b , a % b ) : a;
}
int lcm( int a , int b ) {
return a / gcd( a , b ) * b;
}
bool cmp( int a , int b ) { return a > b; }
bool chk( int r ) {
int t = lcm( a , b );
int gd = r / t , X = r / a - gd , Y = r / b - gd;
int res = A[gd] / 100 * ( x + y ) + ( A[gd + X] - A[gd] ) / 100 * x + ( A[gd + X + Y] - A[gd + X] ) / 100 * y;
return res >= k;
}
void solve( ) {
cin >> n;
rep( i , 1 , n ) scanf("%lld" , A + i);
sort( A + 1 , A + 1 + n , cmp );
for( int i = 1 ; i <= n ; ++ i ) A[i] += A[i - 1];
cin >> x >> a >> y >> b >> k;
if( x < y ) swap( x , y ) , swap( a , b );
int l = 0 , r = n , mid;
while( l <= r ) {
mid = l + r >> 1;
if( chk( mid ) ) r = mid - 1;
else l = mid + 1;
}
cout << ( l > n ? -1 : l ) << endl;
}
signed main() {
int T;cin >> T;while( T-- ) solve();
}

B Sequence Sorting

不难发现,最后的最有决策一定是拿 $1 \sim s$ 的数一个一个放到左边,$t \sim n$ 的数一个一个放到右边,并且中间的数原本想对顺序就是排好的。

考虑对于 $s$ 扫出最远的 $t$ ,这个扫的过程就是比较当前数的最右侧和下一个数的最左侧,显然当 $s$ 在当前的 $s\sim t$ 内 $t$ 不会发生变化,只需要把 $s$ 变成 $t+1$ ,所以复杂度 $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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 300016
//#define int long long
#define rep(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
typedef long long ll;
int n , m , A[MAXN] , L[MAXN] , R[MAXN] , a[MAXN];
void solve( ) {
cin >> n;
rep( i , 1 , n ) scanf("%d",&A[i]) , a[i] = A[i] , L[i] = R[i] = 0;
sort( a + 1 , a + 1 + n );
int sz = unique( a + 1 , a + 1 + n ) - a - 1;
for( int i = 1 ; i <= n ; ++ i ) A[i] = lower_bound( a + 1 , a + 1 + sz , A[i] ) - a;
for( int i = 1 ; i <= n ; ++ i ) if( !L[A[i]] ) L[A[i]] = i;
for( int i = n ; i >= 1 ; -- i ) if( !R[A[i]] ) R[A[i]] = i;
int ok = 1 , ok1 = 1;
for( int i = 1 ; i <= sz ; ) {
int ps = 0;
for( int j = i + 1 ; j <= sz ; ++ j ) {
if( R[j - 1] > L[j] ) { ps = j - 1; break; }
}
if( !ps ) ps = sz;
ok = max( ok , ps - i + 1 );
i = ps + 1;
}
cout << sz - ok << endl;
}
signed main() {
int T;cin >> T;while( T-- ) solve();
}

C Paint the Tree

没想到 1C 会有这么显然的树形 dp !

我们称一条边被染色,当且仅当这个边的两个端点被染了同一种颜色。那么题目的 k-coloring 的限制其实就是每个点染色的边的度数不超过 $k$ 。

先钦定 1 为根,考虑 $dp[u][0/1]$ 表示 $u$ 的子树内都被染完了,其中 $u$ 到父亲的边 未染色 / 染色 的方案数量。

怎么转移,我们相当于是在 $u$ 的儿子 $v$ 中选择 $k$ 或 $k-1$ (取决于这个点到父亲是否染色) 个作为染色的,剩下的作为不染色的。考虑按照 $dp[v][1] - dp[v][0]$ 排序取前 $k$ 或 $k-1$ 大就好了。

注意,有些时候会出现 $dp[v][0] - dp[v][1] < 0$ 的情况,这种情况我们选 $dp[v][0]$ 就好了,所以前 $k$ 个实际上选的是 $\max\{dp[v][1],dp[v][0]\}$ 。

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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 500016
#define int long long
#define rep(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
typedef long long ll;
int n , k;
vector<pii> G[MAXN];
int dp[MAXN][2];
void work( int u , int fa , int wfa ) {
dp[u][1] = wfa , dp[u][0] = 0;
for( auto& t : G[u] ) if( t.se != fa ) {
work( t.se , u , t.fi );
t.fi = dp[t.se][1] - dp[t.se][0];
}
sort( G[u].rbegin( ) , G[u].rend() );
int kel = 0;
for( pii x : G[u] ) {
if( x.se == fa ) continue;
++ kel;
if( kel < k ) dp[u][1] += max( dp[x.se][1] , dp[x.se][0] ); else dp[u][1] += dp[x.se][0];
if( kel <= k ) dp[u][0] += max( dp[x.se][1] , dp[x.se][0] ); else dp[u][0] += dp[x.se][0];
}
}
void solve( ) {
scanf("%lld%lld",&n,&k);
rep( i , 1 , n ) G[i].clear();
for( int i = 1 , u , v , w ; i < n ; ++ i ) {
scanf("%lld%lld%lld",&u,&v,&w);
G[u].emplace_back( mp( w , v ) );
G[v].emplace_back( mp( w , u ) );
}
work( 1 , 1 , 0 );
printf("%lld\n",dp[1][0]);
}
signed main() {
int T;cin >> T;while( T-- ) solve();
}

D Stack Exterminable Arrays

这题才比较有 1C 的难度啊。

我们考虑对于一个 $l$ ,求出最小的 $r$ 使得 $l,r$ 是优秀的子串(反正就是题目那个定义吧我也不知道叫啥)。不难发现这个东西很类似合法括号序列(虽然没啥关系)。

假设我们这的求出了这个东西,那么我们可以用一个很 naive 的 dp 求出答案,$dp[x]$ 表示 $x$ 到 $n$ 的合法括号序列个数,于是 $dp[l] = dp[r] + 1$。

然后考虑怎么求上面说的那个东西?我们如果要求出 $nxt[l]$ (暂且叫那个东西 $nxt$ 吧),就需要找到 $nxt[l] + 1$ 开始的一个极短的优秀的子串,并且满足这个优秀的子串的右端点的后一个位置和 $l$ 相同。于是我们用一个类似子序列自动机的 dp 来做这个,$dp[x][c]$ 表示 $x$ 开头的一个极短的优秀的子串的长度,满足这个优秀的子串的右端点的后一位置是 $c$ 。后面这个 $dp$ 可以用主席树来维护,每次就是一个从 $dp[x+1][c]$ copy 到这个位置,并且类似子序列自动机进行一些修改。但是直觉告诉我们, $dp[x+1][c]$ 在被 copy 过来之后就再也不会被用了。画个图就能理解了(懒得画图了放这里了),于是可以直接用 map 维护,每次 copy 就直接 swap

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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 500016
//#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
typedef long long ll;
int n , k;
int A[MAXN];
int dp[MAXN] , S[MAXN];
map<int,int> nxt[MAXN];
void solve( ) {
cin >> n;
rep( i , 1 , n ) scanf("%d",&A[i]);
rep( i , 1 , n + 1 ) dp[i] = -1 , S[i] = 0 , nxt[i].clear();
per( i , n , 1 ) {
if( nxt[i + 1].count( A[i] ) ) {
int ps = nxt[i + 1][A[i]];
dp[i] = ps;
swap( nxt[ps + 1] , nxt[i] );
if( ps + 1 <= n ) nxt[i][A[ps + 1]] = ps + 1;
}
nxt[i][A[i]] = i;
}
long long ans = 0;
per( i , n , 1 ) if( ~dp[i] )
S[i] = 1 + S[dp[i] + 1] , ans += S[i];
cout << ans << endl;
}
signed main() {
int T;cin >> T;while( T-- ) solve();
}
文章作者: yijan
文章链接: https://yijan.co/cf-round-591/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog