牛客多校 2025 R10

K < F < E

 

E Sensei and Affection (affection)

思路

首先我们发现 $m$ 只有两种取值 $1,2$，因此我们分类讨论

当 $m = 1$ 时，初始数组中的最大值一定是不变的，这样只会使得最终的结果变得更大，又因为 $n \leq 400,a_i\leq 100$ ， 因此我们可以遍历数组，我们设数组初始最大值为 $ma$，让每一个小于 $ma$ 的数都 $+1$ ， 统计最少有多少个区间可以符合这样的条件，直到所有数都达到 $ma$ 。我们可以发现只要 $a[i] = ma$ 时 $a[i-1] != ma$ 就会出现一个符合条件的区间（注意 $a[n +1] = ma,a[0] = ma$ ,）。

当 $m = 2$ 时，也就是数组中最终只会出现两个数 $x,y$ ，那么对这个数组进行差分之后我们就会发现除了第一个数，最终差分数组中只会出现三种数 $0,d,-d$ 。因此我们可以枚举 $x$ 和 $y$ 的绝对值 。让 $[i + 1,n]$ 中的每一个位置都变成 $+d,-d,0$，并且对于绝对值等于 $d$ 的位置其上一个绝对值等于 $d$ 的位置与当前位置的正负性相反。因为我们是对一个区间 $+ 1$ ，因此对于差分就是 选择两个位置分别 $+1,-1$ 。我们可以构造这样一个 $dp$， $dp[i][j][1/0]$，i 表示对前 $i$ 个位置分析的情况，$j$ 表示在前 $i$ 个位置有多少个 $+ 1$ ，这里的 $+ 1$ 实际上指的就是选取区间的左边界。

代码如下

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define endl '\n'
#define double long double
#define PII pair<int,int>
#define F first 
#define S second 
#define int long long
#define i128 __int128_t
#define all(vec) vec.begin(),vec.end()  
#define vi vector<int>   
#define vii vector<vector<int>>   
#define viii vector<vii>   
using namespace std;
const int N = 1e6+10 ;
const int M = 1e3+10 ;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD1 = 1e9 + 7 ;
const int MOD2 = 998244353 ;
const double eps = 1e-9 ;
int gcd(int a, int b){ return b == 0 ? a : gcd(b, a%b); }
int lcm(int a, int b){ return a * b / gcd(a,b); } 
int _ = 1 ;
int ans = 0 ;
int n , m, k, q ;
int MAX = 150 ;
int dp[407][207][2] ;
int a[407] ;
void solve(){
    cin >> n >> m ;
    // 出现 m 种不同的数
    int ma = -INF ;
    for(int i = 1; i <= n ; ++ i){
        cin >> a[i] ;
        ma = max(ma, a[i]) ;
    }
    a[n + 1] = ma ;
    if(m == 1){
        ans = 0 ;
        int cma = -INF ;
        for(int i = 1; i <= n ; ++ i){
            cma = max(cma, ma - a[i]) ;
        }
        for(int i = 1 ; i <= cma ; ++ i){
            for(int j = 2 ; j <= n + 1 ; ++ j){
                if(a[j] == ma) ans += (a[j-1] != ma) ;
            }
            for(int j = 1 ; j <= n ; ++ j){
                a[j] = min(a[j] + 1, ma);
            }
        }
    }else{
        ans = INF ;
        // 最后的差分只会有三种值，并且
        // 只有两个数的时候差分的每一个位置只有三种可能
        // 所以说差分的第一个值大于等于 ma 
        for(int i = n; i >= 1 ; -- i){
            a[i] = a[i] - a[i-1] ;
        }
        a[n + 1] = 0 ;
        for(int d = 1 ; d <= MAX ; ++ d){// 假设两种不同的数之差为 d 
            memset(dp, 0x3f, sizeof dp) ;
            for(int i = 0 ; i <= MAX ; ++ i) dp[1][i][0] = dp[1][i][1] = i ;
            for(int i = 2; i <= n ; ++ i){
                for(int j = 0 ; j <= MAX ; ++ j){
                    // 假如在这一个位置放 0 ;
                    if(a[i] > 0 && j >= a[i]){// 当前位置要变成 0 , 需要让 a[i] 减少 a[i], 也会使得 + 1 减少 a[i]
                        dp[i][j-a[i]][1] = min(dp[i][j-a[i]][1],dp[i-1][j][1]) ;
                        dp[i][j-a[i]][0] = min(dp[i][j-a[i]][0],dp[i-1][j][0]) ;
                    }
                    if(a[i]<=0){// 当前位置要变成 0 , 需要让 a[i] 增加 -a[i], 也会使得 + 1 减少鞥加 - a[i]
                        dp[i][j-a[i]][1] = min(dp[i][j-a[i]][1],dp[i-1][j][1]-a[i]) ;
                        dp[i][j-a[i]][0] = min(dp[i][j-a[i]][0],dp[i-1][j][0]-a[i]) ;
                    }
                    if(a[i] > d && j >= a[i] - d ){ // 要使得 a[i] 变成 + d, 说明会让 + 1 减少 a[i] - d ;
                        dp[i][j - (a[i] - d)][1] = min(dp[i][j-(a[i] - d)][1],dp[i-1][j][0]) ;
                    }
                    if(a[i] <= d){// 要使得 a[i] 变成 d 就需要a[i] 加上 d - a[i], 也就会让 j 增加 d - a[i]
                        dp[i][j + (d - a[i])][1] = min(dp[i][j + (d - a[i])][1] ,dp[i-1][j][0] + (d - a[i])) ;
                    }
                    if(a[i] > -d && j >= a[i] + d ){ // 要使得 a[i] 变成 -d,让 a[i] 减少 a[i] + d  说明会让 + 1 减少 a[i] + d ;
                        dp[i][j - (a[i] + d)][0] = min(dp[i][j-(a[i] + d)][0],dp[i-1][j][1]) ;
                    }
                    if(a[i] <= -d ){ // 要使得 a[i] 变成 -d,让 a[i] 加上 - d - a[i]  说明会让 + 1 增加- d - a[i] 
                        dp[i][j + (-d - a[i])][0] = min(dp[i][j + (-d - a[i])][0],dp[i-1][j][1] + (-d - a[i])) ;
                    }
                }
            }
            for(int j = 0; j <= MAX ; ++ j){
                ans = min(ans,dp[n][j][0]) ;
                ans = min(ans,dp[n][j][1]) ;
            }
            // 每一个为
        }
    }
    // 二分找到第一个大于等于当前位置的数
    cout << ans << endl ;

    // 也就是说保留m个最大的数
}

signed main(){
    IOS ;
    cin >> _ ;
    while(_ --){
        solve() ;
    }
    return 0;
}

 

---

F Sensei and Yuuka Going Shopping (yuuka)

题目大意

把数组 $b$ 划分为三块，求如何划分能够让这三个集合的交集的元素的数目最大，边界分别为 $b_0 = 1 < b_1 < b_2 < b_3 = n + 1$。
三个集合分别为 ${b_0,\dots b_1-1}$，${b_1,\dots b_2-1}$，${b_2,\dots b_3-1}$，输出交集的元素的数目和 $b_1$ 和 $b_2$ 的值。

思路

我们首先求出每一个位置 $i$ 的下一个 $a[i]$ 的位置和最后一个 $a[i]$ 的位置，分别用 $nex$ 和 $lax$ 表示。

我们枚举第一个区间的右边界的位置，实际上就是枚举 $b_1 - 1$ ，如果这个元素是第一次出现，我们就看一下这个数能否作为这三个区间的共有元素，只要 $nex[i] < lax[i]$ 就说明该元素是合法的，也就是说当$b_2$ 取 $[nex[i] + 1, lax[i]]$ 时，就能让共有元素 $+1$ ，我们设计一个数组，数组每一位表示当 $b_2 = i$ 时共有元素的大小，那么我们让这个区间 $[nex[i] + 1, lax[i]]$ 全部 $+1$ 即可。但是如果不是第一次出现该数是需要进行处理，因为此时 $[i + 2,lax[i]]$ 这一段会多算一次，让这个区间 $-1$ 即可。每一次查询 $[i+2，n]$ 的最大值即可。实现采用线段树。

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define endl '\n'
#define double long double
#define PII pair<int,int>
#define F first 
#define S second 
#define i128 __int128_t
#define all(vec) vec.begin(),vec.end()  
#define vi vector<int>   
#define vii vector<vector<int>>
#define lc p << 1
#define rc p << 1 | 1   
using namespace std;
const int N = 1e6+10 ;
const int M = 1e5+50010 ;
const int MOD1 = 1e9 + 7 ;
const int MOD2 = 998244353 ;
const double eps = 1e-9 ;
int gcd(int a, int b){ return b == 0 ? a : gcd(b, a%b); }
int lcm(int a, int b){ return a * b / gcd(a,b); } 
int _ = 1 ;
int ans = 0 ;
int n , m, k, q ;
int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}

void write(int x)
{
    if(x < 0) putchar('-'), x = -x ;
    if(x > 9) write(x / 10) ;
    putchar(x % 10 + '0') ;
    return ;
}

struct node{
    int l, r, ma,pos,add ;
}tr[M*4] ;
void pushup(int p){
    if(tr[lc].ma > tr[rc].ma){
        tr[p].pos = tr[lc].pos ;
    }else{
        tr[p].pos = tr[rc].pos ;
    }
    tr[p].ma = max(tr[lc].ma, tr[rc].ma) ;
}
void build(int p, int l, int r){
    tr[p] = {l,r,0,l,0} ;//如果不是叶子节点那么在之后的计算会覆盖
    if(l == r) return ;
    int m = l + r >> 1 ;
    build(lc,l,m);
    build(rc,m+1,r);
    pushup(p) ;
}

void pushdown(int p){
    if(tr[p].add){
        tr[lc].ma += tr[p].add ;
        tr[rc].ma += tr[p].add ;
        tr[lc].add += tr[p].add ;
        tr[rc].add += tr[p].add ;
        tr[p].add = 0 ;
    }
}

PII querry(int p, int l, int r){
    if(l <= tr[p].l && r >= tr[p].r){
        return {tr[p].ma,tr[p].pos} ;
    }
    int m = (tr[p].l + tr[p].r) >> 1 ;
    pushdown(p) ;
    int ma = 0 ;
    int pos ;
    if(l <= m) {
        PII t1 = querry(lc, l, r) ;
        if(t1.first > ma){
            ma = t1.first ;
            pos = t1.second ;
        }
    }
    if(r > m){
        PII t1 = querry(rc, l, r) ;
        if(t1.first > ma){
            ma = t1.first ;
            pos = t1.second ;
        }
    }
    return {ma,pos} ;
}

void update(int p, int l, int r, int k){
    if(l <= tr[p].l && r >= tr[p].r){
        tr[p].ma +=  k ;
        tr[p].add += k ;
        return ;
    }
    int m = (tr[p].l + tr[p].r) >> 1 ;
    pushdown(p) ;
    if(l <= m) update(lc, l, r, k) ;
    if(r > m) update(rc, l, r, k) ;
    pushup(p) ;
}
int la[N] ;
int ne[N] ;
int a[M] ;
int nex[M] ;
int lax[M] ;
void solve(){
    n = read() ;
    for(int i = 1; i <= n ; ++ i){
        a[i] = read() ;
    }
    for(int i = n ; i >= 1 ;  -- i){
        nex[i] = ne[a[i]] ;
        if(la[a[i]] == 0) la[a[i]] = i ;
        ne[a[i]] = i ;
        lax[i] = la[a[i]] ;
    }
    ans = 0 ;
    int pos1 = 0,pos2 =0 ;
    build(1,1,n) ; // b2 可能的范围
    for(int i = 1 ;  i + 2 <= n  ; ++ i){// 枚举第一个断点
        if(ne[a[i]] == i){// 说明是第一个 a[i]
            if(nex[i] + 1 <= la[a[i]])update(1,nex[i] + 1,la[a[i]],1) ;
        }else{
            if(i + 2 <= nex[i] )update(1,i + 2 ,nex[i],-1) ;
        }
        PII t = querry(1,i + 2,n) ;
        if(t.first > ans){
            ans = t.first ;
            pos1 = i+1 ;
            pos2 = t.second  ;
        }
    }
    if(ans == 0){
        pos1 = 2 , pos2 = 3 ;
    }
    write(ans) ;
    putchar('\n') ;
    write(pos1) ;
    putchar(' ') ;
    write(pos2) ;
    putchar('\n') ;
    for(int i = 1; i <= n ; ++ i){
        ne[a[i]] = 0 ;
        la[a[i]] = 0 ;
        nex[i] = 0 ;
    }
}

signed main(){
    // IOS ;
    cin >> _ ;
    while(_ --){
        solve() ;
    }
    return 0;
}

---

K Amazing Sets (amazing)

思路

显然我们需要缩点，直接套一遍塔扬算出每一个点的 $SCC$，缩完点后属于新的图中的哪个点。然后我们发现只要人选几个子树，他们的根不会出现一个根为另一个根的祖先节点的情况就可以。因此我们就可以构造一个这样的 $dp$，$dp[i][j]$，$i$ 表示新图（缩完点后的）中 $i$ 为根的子树中权值为 $j$ 的情况是否存在。转移时直接背包即可。

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define endl '\n'
#define double long double
#define PII pair<int,int>
#define F first 
#define S second 
#define int long long
#define i128 __int128_t
#define all(vec) vec.begin(),vec.end()  
#define vi vector<int>   
#define vii vector<vector<int>>   
using namespace std;
const int N = 1e6+10 ;
const int M = 1e4+10 ;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD1 = 1e9 + 7 ;
const int MOD2 = 998244353 ;
const double eps = 1e-9 ;
int gcd(int a, int b){ return b == 0 ? a : gcd(b, a%b); }
int lcm(int a, int b){ return a * b / gcd(a,b); } 
int _ = 1 ;
int ans = 0 ;
int n , m, k, q ;
int a[M] ;
vector<int> e[M] ;//存图
int sm[M] ;
int dfn[N], low[N] , tot;//时间戳
int scc[N], sz[N], cnt ;//分组
int stk[N], top ;//入栈
bool instk[N] ;//收收存在栈中
int din[N], dout[N] ;//缩点后入度和出读
int dp[M][M] ;
void add(int u, int v){
    e[u].push_back(v) ;
}
void tarjan(int x){
    dfn[x] =  low[x] = ++tot ;//已经走过的
    stk[++top] = x , instk[x] = true ;//入栈
    for(auto y : e[x]){
        if(!dfn[y]){//还未走过的
            tarjan(y) ;
            low[x] = min(low[x],low[y]) ;
        }else if(instk[y]){//还在在栈中的
            low[x] = min(low[x],low[y]) ;
        }
    }
    if(dfn[x] == low[x]){
        int y;
        cnt ++ ;
        do{
            y = stk[top--] ;
            instk[y] = false ;
            sz[cnt] += a[y] ;
            scc[y] = cnt ;
        }while(x != y ) ;
    }

}
int s ;
void solve(){
    ans = 1 ; // 空集为一种情况
    cin >> n  ;
    int u, v ;
    int cal = 0 ;
    for(int i = 1 ; i <= n ; ++ i){
        cin >> a[i] ;
        cal += a[i] ;
    }
    for(int i = 1;  i < n ; ++ i){
        cin >> u >> v ;
        e[u].push_back(v) ;
    }
    cin >> q ;
    while(q -- ){
        cin >> u >> v ;
        e[u].push_back(v) ;
    }
    for(int i = 1 ; i <= n ; ++ i){
        if(!dfn[i]) tarjan(i) ;
    }
    map<int,vi> mp ;
    for(int i = 1 ; i <= n ; ++ i){
        mp[scc[i]].push_back(i) ;
    }
    vector<set<int>> g(n + 1) ;
    vi din(cnt + 1,0) ;
    for(int i = 1; i <= n ; ++ i){
        for(auto e1 : e[i]){
            if(scc[i] != scc[e1] && g[scc[i]].find(scc[e1]) == g[scc[i]].end()){
                g[scc[i]].insert(scc[e1]) ;
                din[scc[e1]] ++ ;
            }
        }
    }
    int root = -1 ;
    set<int> res ;
    for(int i = 1; i <= cnt ; ++ i){
        if(din[i] == 0){
            root = i ;
            break ;
        }
    }
    auto dfs = [&](auto && self, int x) -> void {
        dp[x][0] = 1 ;
        for(auto e1 : g[x]){
            self(self,e1) ;
            for(int i = sm[x] ; i >= 0 ; -- i){
                if(!dp[x][i]) continue ;
                for(int j = sm[e1] ; j >= 0 ; -- j){
                    if(!dp[e1][j]) continue ;
                    dp[x][i + j] = 1 ;
                }

            }
            sm[x] += sm[e1] ;
        }
        sm[x] += sz[x] ;
        dp[x][sm[x]] = 1 ;
    };
    dfs(dfs,root) ;
    for(int i = 1 ; i <= cal ; ++ i){
        if(dp[root][i]) ans ++ ;
    }
    cout << ans << endl ;

}  

signed main(){
    IOS ;
    // cin >> _ ;
    while(_ --){
        solve() ;
    }
    return 0;
}