CF Round 591

CF1240 A ~ D

CF Round 591

A Save the Nature

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

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

#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

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

考虑对于 ss 扫出最远的 tt ,这个扫的过程就是比较当前数的最右侧和下一个数的最左侧,显然当 ss 在当前的 sts\sim ttt 不会发生变化,只需要把 ss 变成 t+1t+1 ,所以复杂度 O(n)O(n)

为了方便处理离散化了一下。

#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 的限制其实就是每个点染色的边的度数不超过 kk

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

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

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

#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 的难度啊。

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

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

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

#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();
}
\