2022杭电多校（六）

2022杭电多校（六）

一、比赛小结

比赛链接：Problems (hdu.edu.cn)

二、题目分析及解法（基础题） 1006、Maex

题目链接：Problem - 7202 (hdu.edu.cn)

题意：

给出一棵有根树，每个节点的值为子节点的 m e x mex mex ，求根的最大值

题解：

转移为： d p [ u ] = s z [ u ] + max ⁡ ( d p [ v ] ) ,   v ∈ s u b t r e e ( u ) dp[u]=sz[u]+\max(dp[v]), \ v\in subtree(u) dp[u]=sz[u]+max(dp[v]), v∈subtree(u) ，简单树形 dp

代码：

#include 
#define int long long
using namespace std;
const int maxn = 5e5 + 5;
int n;
// 父节点、深度、子树节点数
int pre[maxn], deep[maxn], num[maxn];
// 子树最长值、最长子节点
int len[maxn], son[maxn];
struct e {
  int to, next;
} edge[maxn  n;
    for (int i = 1; i > u >> v;
      addedge(u, v), addedge(v, u);
    }
    predfs(1, 0, 1);
    int ans = 1ll;
    for (int i = 1; i q;
        assert(n  0);
        assert(q  0);
        
        sol1();
    }
    return 0;
}

1008、Shinobu Loves Segment Tree

题目链接：Problem - 7204 (hdu.edu.cn)

题意：

有一棵线段树，每个节点记录子节点的值的加和，每次 shinobu 会 u p d a t e ( 1 , 1 , i , 1 ) update(1, 1, i, 1) update(1,1,i,1) ，他会 u p d a t e update update 上 n n n 天，然后问 x x x 节点的值为何

题解：

考虑第 a a a 天，会对 v a l u e [ x ] value[x] value[x] 产生的影响：

依次看 x x x 次高位到最低位:

如果这一位是1，则说明 x 在右子树，当前区间长度 a = ⌊ a 2 ⌋ a=\lfloor \frac{a}2 \rfloor a=⌊2a​⌋

如果这一位是0，则说明 x 在左子树，当前区间长度 a = ⌊ a 2 ⌋ a=\lfloor \frac{a}2 \rfloor a=⌊2a​⌋

由此可以在 O ( log ⁡ a ) O(\log a) O(loga) 时间快速模拟得到某一天 v a l u e [ x ] value[x] value[x] 的变化。

现在考虑 c a l c ( l , r , p ) calc(l, r, p) calc(l,r,p) 表示，从第 l l l 天到第 r r r 天，上述模拟过程从 x x x 的第 p p p 位进行到第 0 0 0 位，对 v a l u e [ x ] value[x] value[x] 产生的贡献。

那么可以发现， c a l c ( l , r , p ) calc(l, r, p) calc(l,r,p) 可以由 c a l c ( l / 2 , r / 2 , p − 1 ) calc(l/2, r/2, p-1) calc(l/2,r/2,p−1) 或者 c a l c ( ( l + 1 ) / 2 , ( r + 1 ) / 2 , p − 1 ) calc((l+1)/2, (r+1)/2, p-1) calc((l+1)/2,(r+1)/2,p−1) 推得 。

具体的，对任意 k > 0 k>0 k>0 , 第 2 k 2k 2k 天和第 2 k + 1 2k+1 2k+1 天，下取整之后，他们对应的区间长度相同，后续的操作也相同，因此对答案产生的贡献也相同。上取整同理可得类似关系。总复杂度 T log ⁡ 2 n T\log^2n Tlog2n

代码：

#include 
using namespace std;
int t, n;
long long x;
vector d;
long long get(int x, int n) {
  if (x == d.size()) return n;
  if (n  r) return 0;
  if (d[x]) {
    long long ans = dg(x + 1, l / 2, r / 2) * 2;
    if (l % 2 == 1) ans -= get(x + 1, l / 2);
    if (r % 2 == 0) ans -= get(x + 1, r / 2);
    return ans;
  } else {
    long long ans = dg(x + 1, (l + 1) / 2, (r + 1) / 2) * 2;
    if (l % 2 == 0) ans -= get(x + 1, (l + 1) / 2);
    if (r % 2 == 1) ans -= get(x + 1, (r + 1) / 2);
    return ans;
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  cin >> t;
  while (t--) {
    cin >> n >> x;
    d.clear();
    while (x) d.emplace_back(x & 1), x >>= 1;
    d.pop_back();
    reverse(d.begin(), d.end());
    cout  n >> m;
    for (int i = 1; i  u[i] >> v[i];
    }
    int tot = m;
    for (int i = m; i >= 1; i--) {
      int x = dsu(u[i]), y = dsu(v[i]);
      if (x != y) {
        tot--;
        vis[i] = 1;
        p[x] = y;
      }
    }
    cout