ICPC_2022_Xian&&Guiling 赛后补题

Find Maximum

一个很重要的性质就是f（x）表示的是x在三进制下的位数加上各位上的数字之和 这个观察f（x）的题面也很容易看出来

所以只需要尽量让x在三进制下2最多即可 直接枚举贪心就行 

#include<bits/stdc++.h>
using namespace std ;
#define maxn 400100
#define int long long
int read(){
    int ans = 0 , f = 1 ; char ch = getchar() ;
    while ( !isdigit(ch) ){ if( ch == '-' ) f = -1 ; ch = getchar() ; }
    while ( isdigit(ch) ) ans = (ans * 10) + (ch ^ '0') , ch = getchar() ;
    return ans * f ;
}
int l , r , t ; 
int f(int x){
    if(x == 0){
        return 1 ; 
    }
    if(x > 0 && x % 3 == 0)
        return f(x / 3) + 1 ; 
    return f(x - 1) + 1 ; 
}
void solve(){
    vector<int> R ; 
    l = read() , r = read() ; 
    int ans = max(f(l) , f(r)) ; 
    int temp = r ; 
    while(temp){
        R.push_back(temp % 3) ; 
        temp /= 3 ; 
    }
    int si = R.size() ; 
    reverse(R.begin() , R.end()); 
    for(int i = 0 ; i < si ; i++){
        if(R[i] == 0){
            continue ; 
        }
        int sum = 0 ; 
        for(int j = 0 ; j < i ; j++)
            sum = sum * 3 + R[j] ; 
        sum = sum * 3 + R[i] - 1 ;
        for(int j = i + 1 ; j < si ; j++)
            sum = sum * 3 + 2 ; 
        if(sum >= l)
            ans = max(ans , f(sum)) ;
    }
    printf("%lld\n" , ans) ; 
}
signed main(){
//    freopen("test.in" , "r" , stdin) ;
//    freopen("test.out" , "w" , stdout) ;
    t = read() ; 
    while(t--){
        solve() ; 
    }
    return 0 ;
}

L题Tree

首先我们通过对样例的模拟 可以发现一些性质 发现我们现在每次有两种操作 要么是吧最底层的叶子全部砍掉 要么是用链去覆盖 

本题暂未找到严谨的贪心证明 目前我发现先取叶子再取链和先取链再取叶子两种贪心方式都是正确的 （先留个坑吧

#include<bits/stdc++.h>
using namespace std ;
#define maxn 2000100
#define int long long
int read(){
    int ans = 0 , f = 1 ; char ch = getchar() ;
    while ( !isdigit(ch) ){ if( ch == '-' ) f = -1 ; ch = getchar() ; }
    while ( isdigit(ch) ) ans = (ans * 10) + (ch ^ '0') , ch = getchar() ;
    return ans * f ;
}
int to[maxn] , nxt[maxn] , head[maxn] , cnt ; 
void add(int u , int v){
    to[++cnt] = v , nxt[cnt] = head[u] ; head[u] = cnt ; 
}
int num[maxn] , f[maxn]; 
int t , n ; 
void dfs(int u , int fa){
    f[u] = 1 ;  
    for(int i = head[u] ; i ; i = nxt[i]){
        int v = to[i] ; 
        if(v == fa) continue ; 
        dfs(v , u) ; 
        f[u] = max(f[u] , f[v] + 1) ; 
    }
    return ; 
}
void solve(){
    n = read() ;
    memset(f , 0 , sizeof(int) * (n + 10)) ; memset(num , 0 , sizeof(int) * (n + 10)) ; 
    cnt = 0  ; //memset(to , 0 , sizeof(to)) ; 
    memset(head , 0 , sizeof(int) * (n * 2 + 10)) ; //memset(nxt , 0 , sizeof(nxt)) ; 
    int ans = 999999999 ; 
//    n = read() ; 
    for(int i = 2 ; i <= n ; i++){
        int u = read() , v = i ; 
        add(u , v) ; add(v , u) ; 
    }
    for(int i = 1 ; i <= n ; i++)
        if(f[i] == 0) dfs(i , i) ;  
    for(int i = 1 ; i <= n ; i++)
        num[f[i]]++ ;// printf("f[%lld] :%lld \n" , i , f[i]); 
    for(int i = 1 ; i <= n ; i++)
        ans = min(ans , num[i] + i - 1) ;// printf("num[%lld] : %lld \n" , i , num[i] + i - 1); 
    printf("%lld\n" , ans) ; 
}
signed main(){
//    freopen("test.in" , "r" , stdin) ;
//    freopen("test.out" , "w" , stdout) ;
    t = read() ; 
    while(t--){
        solve() ; 
    }
    return 0 ;
}

BCells Coloring（待补）

Group Homework

换跟dp 

换跟的步骤其实就是先删掉v节点对u节点的贡献 然后再把u节点的贡献插入v节点即可 

对于每个点 我们可以开一个multiset 这样再计算转移的时候的最大值会方便很多

需要注意的是撤销贡献和计算贡献的顺序 搞清楚先后

#include<bits/stdc++.h>
using namespace std ;
#define maxn 400100
#define int long long
int read(){
    int ans = 0 , f = 1 ; char ch = getchar() ;
    while ( !isdigit(ch) ){ if( ch == '-' ) f = -1 ; ch = getchar() ; }
    while ( isdigit(ch) ) ans = (ans * 10) + (ch ^ '0') , ch = getchar() ;
    return ans * f ;
}
int ans = 0 ;  
vector<int> G[maxn] ;
int a[maxn] ; 
int n ; 
struct node{
    multiset<int> st ; 
    void add(int x){
        st.insert(x) ; 
    }
    void del(int x){
        st.erase(st.find(x));
    }
    int operator [] (int id)const {
        auto it = st.end() ; 
        for(int i = 0 ; i <= id ; i++) it-- ; 
        return *it ; 
    }
}mx_line[maxn] , mx_sub[maxn];
void dfs(int u , int fa){
    for(int i = 1 ; i <= 3 ; i++){
        mx_line[u].add(0) ; 
        mx_line[u].add(0) ; 
        mx_sub[u].add(0) ;  
    }
    for(int i = 0 ; i < G[u].size() ; i++){
        int v = G[u][i] ; 
        if(v == fa) continue ; 
        dfs(v,u) ; 
        mx_line[u].add(mx_line[v][0] + a[v]) ; 
        mx_sub[u].add(mx_sub[v][0]) ; 
    }
    mx_sub[u].add(mx_line[u][0] + a[u] + mx_line[u][1]) ; 
} 
void dfs1(int u , int fa){
//    ans = max(ans , mx_line[u][0] + mx_line[u][1] + mx_line[u][2] + mx_line[u][3]) ; 
    for(int i = 0 ; i < G[u].size() ; i++){
        int v = G[u][i] ; 
        if(v == fa) continue ; 
        int del_sub1 = mx_line[u][0] + a[u] + mx_line[u][1] ; 
        int del_sub2 = mx_sub[v][0] ; 
        int del_line = mx_line[v][0] + a[v] ; 
        mx_sub[u].del(del_sub1) ; 
        mx_sub[u].del(del_sub2) ; 
        mx_line[u].del(del_line) ; 
        mx_sub[u].add(mx_line[u][0] + a[u] + mx_line[u][1]) ; 
        ans = max(ans , mx_sub[u][0] + mx_sub[v][0]) ; 
        mx_sub[v].del(mx_line[v][0] + mx_line[v][1] + a[v]) ; 
        mx_line[v].add(mx_line[u][0] + a[u]) ;
        mx_sub[v].add(mx_line[v][0] + mx_line[v][1] + a[v]) ;
        mx_sub[v].add(mx_sub[u][0]) ; 
        dfs1(v , u) ; 
        mx_sub[u].del(mx_line[u][0] + a[u] + mx_line[u][1]) ;
        mx_line[u].add(del_line) ; 
        mx_sub[u].add(del_sub2) ; 
        mx_sub[u].add(del_sub1) ;  
    }
}
signed main(){
//    freopen("test.in" , "r" , stdin) ;
//    freopen("test.out" , "w" , stdout) ;
    n = read() ; 
    for(int i = 1 ; i <= n ; i++){
        a[i] = read() ; 
    }
    for(int i = 1 ; i < n ; i++){
        int u = read() , v = read() ; 
        G[u].push_back(v) ; 
        G[v].push_back(u) ; 
    }
    if(n == 1){
        printf("0") ; 
        return 0 ; 
    }    
    dfs(1,0) ; 
//    ans = mx_sub[1][0] ; 
    dfs1(1,0) ; 
    printf("%lld" , ans) ; 
    return 0 ;
}