2025.7.21 divEducational Codeforces Round 180 (Rated for Div. 2)

总结

今日VP,状态不太好ac1,最近还是给vp+补题+图论的组合,准备花两周先入一下图论基础,目标是能轻易做出以树和图为基础的铜牌题,补足短板.

题目部分

A Race

需要注意到,题目的数据范围为 $ t(1≤t≤1000), a，x， y(1≤a,x,y≤100) $ 这昭示的我们可以使用暴力去解,固直接枚举即可.

时间复杂度$O(n)$ ;

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
int a , n , m ; cin >> a >> n >> m ;
bool ok = 0 ; 
int st1 =abs(a-n) , st2 =  abs(a - m ) ;
for(int i = 0 ; i<= 200 ; i++){
  if(i == a )continue ; 
  if(abs(n - i) < st1 && abs(m - i) < st2 ){
    ok = 1 ; 
  }
}  
if(!ok){
  cout << "NO\n" ; 
}else cout << "YES\n" ;

B Shrinking Array

首先考虑到,我们可以将两个相邻的元素$a_1,a_2$,转化为$ x , x \in min(a,b) , max(a,b) $ 并且只需要两个元素满足$\lvert a_1 - a_2 \rvert \le 1 $

我们可以先去寻找本身即是美丽的数组,遍历一次即可;

代码
1
2
3
4
5
6
for(int i = 1  ; i< n ; i++){
  if(abs(a[i] - a[i+1] ) <= 1  ){
    cout << "0\n" ; 
    return ; 
  }  
}

而后考虑怎么样的情况不可能出现美丽数组,因为我们可以把 $ a_1,a_2 $ 转化为 $ x \in min(a,b) , max(a,b) $ 的任意整数,故而只有在$ a_1 < a_2 < a_3 \dots $ 与相反 , 即是单调递增或单调递减的情况是无法构造成功的

既然单调递增是无法构造成功的,那么怎么样可以构造成功呢? 当 $ a_{i-1} < a_i > a_{i+1} $ 与 $ a_{i-1} > a_i < a_{i+1} $ 这样子的峰值时,我们可以将 $ (a_{i-1},a_i) $ 转化为 $ a_{i+1} -1$或$a_{i+1} +1 $ ,即为构造成功

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
for(int i = 2 ; i < n ; i++){
  if( a[i-1] > a[i] && a[i] < a[i+1]){
    cout << 1 <<'\n' ; 
    return ;
  }
  if(a[i-1] < a[i] && a[i] > a[i+1]){
    cout << 1 <<'\n' ; 
    return ; 
  }
}

// cout << mi<< ' ' << mx <<'\n' ; 
cout << -1<<'\n' ;

C Coloring Game

首先考虑Bob的最优解,Bob的操作只有两种情况,一种刷最大值,另外一种刷$a_z$此时相当于Bob选择了$a_z \times 2$

因为数据范围是 $ 5 \sum n \ge 5 \cdot 10^3 $ 我们可以考虑用 $ O(n^2 \log n) $ 的解法

首先,最暴力的是,我们可以枚举 $ a_x,a_y,a_z $ ,但这时间复杂度是$O(n^3)$根据 $ a_1 < a_2 < a_3 \dots < a_n $ 的提示,我们可以考虑以z与y为端点,进行二分查找,便可通过此题

如果我们已知 $ a_y , a_z $ 那么我们必须满足$a_x > 2 \cdot max(a_z), a_n - a_y - a_z $ 我们二分查找此项即可, 然后$j-x$就是每一份的贡献值了

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int n ; cin >> n;
vector<int>a(n+1) ; 
for(int i = 1 ; i<= n ; i++)cin >> a[i] ; 
i64 ans = 0 ;
for(int i =  1 ; i<= n ; i++){ //我们就枚举ax , ay
  for(int j = 1 ; j< i ;j++){ //ax+ ay + az > max(2*az , an)
    int x = max(a[n] , a[i] * 2 ) - a[i] - a[j] ;//如果选择这个x，那么他就必须是a[n] , a[i*2]
    //x最小需要多少
    //枚举ay ,az 然后 去找ax
    int k =upper_bound(a.begin() + 1 , a.begin() + j , x ) -a.begin() ;
    ans+= j - k ;  

    }
}
cout << ans <<'\n' ;

D Reachability and Tree

首先考虑极端情况,每一份 $ (u,v) $ 或 $ (v,u) $ 各自拆开,我们会拥有 $ n-1 $ 个好队,那我们怎么情况下能凑出 $ n $ 对呢,就是把找两条线,使得 $ (a \to b \to c ) $ 其它原样构造即可.

1.寻找是否存在只有两条线的节点,不然无法构造出来(其它情况我们都会凑出多条,画一下就知道了)

2.以此节点进行dfs,并且箭头不停转换.

代码
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
  void solve(){
  int n ; cin >> n ; 
  vector<vector<int>>ad(n+1) ; 
  for(int i = 1  ; i< n ; i++){
    int u , v ; cin >> u >> v ; 
    ad[u].push_back(v) ; 
    ad[v].push_back(u) ; 
  }
  int root = 0 ; 
  for(int i = 1 ; i <= n ; i++){
    if(ad[i].size() == 2){
      root = i ;    
      break ; 
    }
  }
  const auto dfs = [&](auto && self , int u , int p  , int t ) ->void{
    if(t)cout << u << ' ' << p <<'\n' ; 
    else cout << p << ' ' << u <<'\n' ; 
    for(const auto & y : ad[u]){
      if(y == p )continue ; 
      self(self,y,u,!t);
    }
    return ; 
  };
  if(!root){
    cout << "NO\n" ;
    return ; 
  }
  cout << "YES\n" ; 
  dfs(dfs,ad[root][0] , root , 0) ; 
  dfs(dfs, ad[root][1] , root , 1) ;
}

E. Tree Colorings

首先我们可以观察到, 如果子树节点不是绿色,那么必定是统一颜色的.只有一条链的极端情况是最少的, 然后子树越多,节点越多.

首先考虑$1$个节点的情况,最低为$1$,当节点为2的情况,最低则为$3$每一个新节点的加入,最低可以贡献出2个构造情况.故而得到如果 $ m % 2 \equiv 0 $ 无解,与状态转移方程$ ans[i] = min(ans[i] , ans[i-2] + 1 ) ; $

接下来边界则是,除了原点以外,其它节点都拆开. 以及每一次拆开,可以得到$cnt_{sum} = (cnt_1 +2) \cdot (cnt_2 +2) \cdot \dots (cnt_i*i+2)$次.这是最多的.我们预处理完$O(1)查询即可$(有一说一,这题我也没特别搞懂,所以只能辅助理解)

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int n = 5e5+ 10 ; 
vector<int>ans(n+1000 , inf ) ;
ans[1] = 0 ; ans[2] = -1 ; 
for(int i = 3 ; i<= 500000 ; i++){
  if(i%2 == 0 ){
    ans[i] = -1 ; 
  }else{
    ans[i] = min(ans[i] , ans[i-2] + 1 ) ; //只有一颗子树的情况 至少贡献2
    for(int j = i * 2 ; j <=min(1ll * i*i ,500000ll) ; j+=i){
      if(j %2!= 0 ){//分裂， 分裂成全是子树
        ans[j] = min(ans[j] ,ans[i] + ans[j/i]) ; 
      }
    }
  }
} 
int q ; cin >> q ; 
while(q--){
  int x ; cin >> x;
  if(x%2 == 0 )cout << -1 <<'\n' ; //每多一个至少贡献2，所以无解
  else cout << ans[x] + 1 << '\n' ; 
}