CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!) A－Ｅ

从Ｃ题开始写好了　

Make It Permutation

首先我们分析假如我们确定了要选择一个长度为ｎ的序列，该怎么计算代价　

很明显　一个是算保留多少个　一个是算要加多少个，然后如果我们算完了选择长度ｎ－１的序列　那么更新答案的时候只需要看ｎ这个数字是否存在就可以了，然后更新一下删掉多少个数字　

所以我们把原序列排序　然后枚举选长度为ｂ［ｉ］的排列　就可以每次ｏ（１）计算了　时间复杂度Ｏ（ｎ）　

#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 t , n , c , d ; 
int ans; 
int a[maxn] , b[maxn] ; 
signed main(){
    t = read() ; 
    while(t--){
        n = read() , c = read() ,d = read() ; 
        for(int i = 1 ; i <= n ; i++)
            a[i] = read() , b[i] = a[i] ; 
        sort(b + 1 , b + 1 + n) ; 
        int size = unique(b + 1 , b + 1 + n) - b - 1; 
        ans = 99999999999999 ; int temp = 0 ;  
        if(b[1] != 1)
            ans = n * c + d ; 
        for(int i = 1 ; i <= size ; i++){
            int sum = 0 ; 
            temp += (b[i] - b[i - 1] - 1) * d ; 
            sum = (n - i) * c + temp ;
//            printf("sunm : i : %lld %lld temp : %lld \n" , i , sum , temp) ; 
            ans = min(ans , sum) ; 
        }
        printf("%lld\n" , ans) ; 
    }
    return 0 ;
 }

D - Climbing the Tree

 感觉题解其实写的非常明白　实际上这个题也很简单　考试的时候很快公式就推出来了　结果最后错在用了　ｃｅｉｌ（（Ｌ－ａ）／　（ａ　－　ｂ））　可能精度会有点问题　最后爆在这里了　查了好久没查出来　警钟长鸣！！！

E.Monsters

其实这个难就难在你可以证明暴力是对的　

考虑从一个点出发可以到哪些点　我们可以用类似于ｂｆｓ的方式来完成　每次取一个最小的ａ值的可以便利的点，判断一下可不可以遍历即可　

此时的复杂度是ｎｌｏｇｎ的　因为我们可以用一个堆来维护可能遍历的点的状态　

所以最后，我们从每一个从ａ值为０，且没有被遍历过的点开始ｂｆｓ即可　

所以我们现在需要考虑　一个点最多会被遍历多少次　

假如现在有三个点　ａ　，　ｂ　，　ｃ　ａ还连着很多边　ｃ也是

ａ点是之前已经遍历过的点　我们现在在ｃ点上　ｃ是我们第一次遍历的点　

也就是说　之前从ａ那边开始遍历的时候　它遍历不过来　也就是没法到ｃ的位置　为什么　因为ｂ把它卡住了！

那么现在　假设我们从ｃ这边有这个能力遍历过去，也就是说　我们有能力打败这个ｃ　这意味着什么呢

意味从ｃ这边的已经打过的怪物数量已经大于ａ［ｂ］，也就是ｃ这边的点集的大小大于ａ【ｂ】

而且ａ这边的点集大小是小于ａ【ｂ】的　，　因为ａ没打过去　

所以最终ｃ这边的大小一定是ａ这边的大小的两倍　，因为ｃ最后会把ａ这边也遍历一遍　点集的大小自然就扩大了

所以说，ａ每次被遍历的时候，新的点集的大小至少是翻倍的，所以ａ这个点最终会被遍历ｌｏｇｎ次　

因此　总复杂度就是ｎ（ｌｏｇｎ）＾２的

#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 t , n , m ; 
int a[maxn] ; 
#define pii pair<int,int> 
vector<int> G[maxn] ; 
int vis[maxn] ; 
set<pii> q ; 
bool check(int u){
    q.clear() ; 
    q.insert({a[u] , u}) ; 
    int sum = 0 ; 
    while(!q.empty()){
        pii now = *q.begin() ; 
        q.erase(q.begin()) ; 
        if(now.first > sum){
            return 0 ; 
        }
        vis[now.second] = u ; 
        sum++ ; 
        for(int i = 0 ; i < G[now.second].size() ; i++){
            int v = G[now.second][i] ; 
            if(vis[v] < u)
                q.insert({a[v] , v}) ; 
        }
    }
    return sum == n ; 
}
signed main(){
    t = read() ; 
    while(t--){
        n = read() , m = read() ; 
        for(int i = 1 ; i <= n ; i++)
            G[i].clear() , a[i] = read() , vis[i] = 0; 
        for(int i = 1 ; i <= m ; i++){
            int u = read() , v = read(); 
            G[u].push_back(v) ; 
            G[v].push_back(u) ; 
        }
        bool flag = 0 ; 
        for(int i = 1 ; i <= n ; i++){
            if(a[i] == 0 && vis[i] == 0){
                if(check(i)){
                    flag = 1; 
                    break ; 
                }
            }
        }
        if(flag == 1){
            printf("yes\n") ; 
        }
        else printf("no\n") ; 
    }
    return 0 ;
 }