当前位置：网站首页>【6.15】Codeforces Round ＃798 (Div. 2)

【6.15】Codeforces Round ＃798 (Div. 2)

2022-07-19 13:40:00 【ZhgDgE】

ALL：7
I AC+ Teammate AC：7
With your teammates AK div3

F. Equate Multisets

The question ： Given two sizes n ( 1 ≤ n ≤ 2 × 1 0 5 ) n(1\leq n\leq 2\times 10^5) n(1≤n≤2×105) Multiple sets of a , b a,b a,b . You can do the following several times ：

  1. b i = 2 × b i b_i=2\times b_i bi​=2×bi​
  2. b i = ⌊ b i 2 ⌋ b_i=\left\lfloor\frac{b_i}{2}\right\rfloor bi​=⌊2bi​​⌋

ask , Can multiple operations be carried out , bring a = b a=b a=b

Answer key ：Codeforces Round #805 (Div. 3) E( dyeing ) F( greedy ) G(lca)

Ideas ： Yes b i b_i bi​ multiply 2 It is equivalent to a i a_i ai​ Divide 2 , Then it turns into a i = ⌊ a i 2 ⌋ ( When a i % 2 = 0 ) a_i=\left\lfloor\frac{a_i}{2}\right\rfloor( When a_i\%2=0) ai​=⌊2ai​​⌋( When ai​%2=0) and b i = ⌊ b i 2 ⌋ b_i=\left\lfloor\frac{b_i}{2}\right\rfloor bi​=⌊2bi​​⌋ Two kinds of operations , Use the priority queue to maintain the maximum value and get the match .

AC Code ：https://codeforces.com/contest/1702/submission/163767144

G2. Passable Paths (hard version)

The question ： Given a tree n ( 1 ≤ n ≤ 2 × 1 0 5 ) n(1\leq n\leq 2\times 10^5) n(1≤n≤2×105) Rootless tree with nodes .

Now there is q q q Time to ask , Give out... Every time you ask k k k A little bit , Ask whether these points can be connected by a simple path . ( ∑ k ≤ 2 × 1 0 5 ) (\sum k \leq 2\times 10^5) (∑k≤2×105)

Ideas ： Virtual tree for game + Change one DP. Virtual tree will not say , Shortening the path does not affect the answer . How many subtrees contain special points when changing the root to maintain each point as the root , If there is a point g g g A value greater than or equal to 3 , Then it must not be a chain .

AC Code ：https://codeforces.com/contest/1702/submission/163566226

原网站

版权声明
本文为[ZhgDgE]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/200/202207171827573973.html

边栏推荐

猜你喜欢

随机推荐