Yijan's Blog HomeArchives
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！
比赛