SDUT 2021 Winter Individual Contest - F

博主： spirit
发布时间：2021 年 01 月 25 日
1461 次浏览
暂无评论
3064字数
分类： VJ训练赛

[gym102433](https://codeforces.com/gym/102433)

# [A - Radio Prize](https://vjudge.net/problem/Gym-102433A)

- 题意：给出一个无根树，每条边有边权 $w_i$ ，每个点有点权 $t_i$ ，记点 $u$ 到点 $v$ 的距离为 $d_{u, v}$ ，则从 $u$ 点到 $v$ 点的花费为 $(t_u + t_v)d_{u, v}$ 。求每个点到其他所有点花费的和。
- 思路：
  
  - 最多有点 $n = 1e5$ 个，暴力 $O(n^2)$ 会超时。
  - 首先我们抛开题目中所说的”花费“，只考虑统计每个点到其他点的距离和。
    - 我们令点 $1$ 为树根，把无根树“拎起来”。对于任意节点，我们把它子节点的方向称之为向下的方向，这个方向的点称之为“下方的点”，而除了这些点和当前节点之外的所有节点一律称之为“上方的点”。
    - 我们首先考虑对一条边来说，由它下方的所有点到达其他点中的任意一个，这条边被使用的次数等于它下方所有节点的数量。那么对于任意一个点 $u$ 来说，只通过一遍 $dfs$ 统计子树中所有边的贡献，就可以算出点 $u$ 到它下方所有点的距离和。
    - 接下来我们来考虑所有“上方的点”。这些点中除了点 $u$ 的祖先节点，还有它祖先节点的其他子节点。对于祖先节点显然我们直接通过 $dfs$ 把距离传递下来即可。对于那些”其他节点“，他们到点 $u$ 的路径可以分为两部分：从”其他节点“到祖先节点，再由祖先节点到 $u$ 。注意到第一遍 $dfs$ 中，我们已经把第一部分路径的值求出来了，在第二遍 $dfs$ 中把这些已经求出来的值也通过 $dfs$ 传递下来即可（这里画一下把 $u$ 视为根节点，将树分为两部分的图可能更好理解一些）。
  - 接下来我们把题目的要求代入到上述过程中去，假如我们用 $downTSum$ 记录一条边下方所有点权和，$downNum_u$ 记录下方所有点的数量，那么这条边对于点 $u$ 的贡献为：$downTSum_u \cdot w_i + t_u \cdot downNum_u \cdot w_i$。我们发现上述表达式第一部分是一个常数，和点 $u$ 的信息完全没有关系，可以用一个变量 $downSum_u$ 来记录点 $u$ 子树中所有边贡献的第一部分；第二部分除了 $t_u$ 外也是一个常数，用变量 $downWSum_u$ 来记录第二部分中常数的和，当需要统计的时候和当前点的点权乘起来就可以了。
  - 对于“上方的点”，计算方法与上述思想一致，~~懒得写~~ 不再赘述。
  - 其实这个方法基本上是一个树形 $DP$ ，状态转移就看代码吧。
- 代码：
  
  ```cpp
  #include <bits/stdc++.h>
  
  using namespace std;
  const int N = 1e5 + 10;
  typedef long long LL;
  struct TNode {
      int id;
      LL upTSum, upSum, upWSum, upNum;
      LL downTSum, downSum, downWSum, downNum;
  } a[N];
  LL ans[N];
  int t[N], head[N], ne[N * 2], w[N * 2], ver[N * 2], cnt, n;
  
  inline void addEdge(int a, int b, int c) {
      ver[++cnt] = b, w[cnt] = c, ne[cnt] = head[a], head[a] = cnt;
  }
  
  void dfs1(int u, int fa) {
      for (int i = head[u]; i; i = ne[i]) {
          if (ver[i] == fa) continue;
          dfs1(ver[i], u);
          a[u].downNum += a[ver[i]].downNum + 1;
          a[u].downWSum += a[ver[i]].downWSum + (a[ver[i]].downNum + 1) * w[i];
          a[u].downTSum += a[ver[i]].downTSum + t[ver[i]];
          a[u].downSum +=
              a[ver[i]].downSum + (a[ver[i]].downTSum + t[ver[i]]) * w[i];
      }
      ans[u] += a[u].downSum + a[u].downWSum * t[u];
  }
  
  void dfs2(int u, int fa, int val) {
      if (fa != -1) {
          //注意父节点fa统计的down相关信息中，是包含以u为根节点的这棵子树的，在由父节点信息推导u的信息时，要先把这一部分减去
          a[u].upNum = n - a[u].downNum - 1;
          a[u].upTSum +=
              a[fa].downTSum - (a[u].downTSum + t[u]) + a[fa].upTSum + t[fa];
          a[u].upWSum += a[fa].downWSum - a[u].downWSum +
                         (n - 2 * (a[u].downNum + 1)) * val + a[fa].upWSum;
          a[u].upSum += a[fa].downSum -
                        (a[u].downSum + (a[u].downTSum + t[u]) * val) +
                        a[fa].upSum + a[u].upTSum * val;
          ans[u] += a[u].upSum + a[u].upWSum * t[u];
      }
      for (int i = head[u]; i; i = ne[i]) {
          if (ver[i] == fa) continue;
          dfs2(ver[i], u, w[i]);
      }
  }
  
  int main() {
      int u, v, w;
      cin >> n;
      for (int i = 1; i <= n; i++) scanf("%d", &t[i]);
      for (int i = 1; i < n; i++) {
          scanf("%d %d %d", &u, &v, &w);
          addEdge(u, v, w);
          addEdge(v, u, w);
      }
      dfs1(1, -1);
      dfs2(1, -1, 0);
      for (int i = 1; i <= n; i++) printf("%lld\n", ans[i]);
      return 0;
  }
  ```

# [B - Perfect Flush](https://vjudge.net/problem/Gym-102433B)

- 题意：给出一个长度为 $n$ 的序列，序列中的数字都满足 $1 \leq a_i \leq k$ ，保证 $1$ 到 $k$ 中每个数字都至少出现了一次，要求选择一个子序列，是字典序最小的 $1$ 到 $k$ 的排列。
- 思路：
  
  1. 如果一个元素 $a_i$ 是数组中最后一次出现该元素的值，那么这个元素必须选择。
  2. 一个元素到它前面距离最近的一个小于它或者必须被选择的数字之间，比它大的元素都不能选择（要求字典序最小）。
- 代码：
  
  ```cpp
  #include <bits/stdc++.h>
  
  using namespace std;
  const int N = 2e5 + 10;
  int book[N], a[N], ans[N];
  bool vis[N];
  
  int main() {
      int n, k;
      cin >> n >> k;
      for (int i = 1; i <= n; i++) {
          scanf("%d", &a[i]);
          book[a[i]]++;
      }
      stack<int> s;
      for (int i = 1; i <= n; i++) {
          book[a[i]]--;
          if (vis[a[i]]) continue;
          while (!s.empty() && book[s.top()] && a[i] < s.top()) {
              vis[s.top()] = false;
              s.pop();
          }
          s.push(a[i]);
          vis[a[i]] = true;
      }
      for (int i = k; i; i--) {
          ans[i] = s.top();
          s.pop();
      }
      for (int i = 1; i <= k; i++) printf("%d%c", ans[i], i == k ? '\n' : ' ');
      return 0;
  }
  ```

# [C - Coloring Contention](https://vjudge.net/problem/Gym-102433C)

- 题意：给一张无向图，$Alice$ 可以把图中的边任意染成红色或者蓝色，$Bob$ 要选择一条从 $1$ 到 $n$ 的路径，路径上如果第 $i$ 条边和第 $i+1$ 条边的颜色不同，记为一次颜色变化，$Alice$ 想让该路径颜色变化尽可能多，$Bob$ 想让颜色变化尽可能少，求最终选择的路径会有多少次颜色变化。
- 思路：按照到点 $1$ 的距离为每个点赋值，可以证明图中任意一条边的两端权值差不会超过 $1$ 。令所有形如 $[i, i+1]$ 的边按照 $i$ 的奇偶不同染色，边的端点权值相同的边可以随意染色。

最后修改：2021 年 02 月 09 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

SDUT 2021 Winter Individual Contest - F

spirit • 2021 年 01 月 25 日

[gym102433](https://codeforces.com/gym/102433)

# [A - Radio Prize](https://vjudge.net/problem/Gym-102433A)

# [B - Perfect Flush](https://vjudge.net/problem/Gym-102433B)

# [C - Coloring Contention](https://vjudge.net/problem/Gym-102433C)

SDUT 2021 Winter Individual Contest - F

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

Kattis Message （状态机模型 + 矩阵快速幂）

数论进阶——莫比乌斯反演

Codeforces Round #703 (Div. 2)

SDUT 2021 Winter Individual Contest - E

Kattis Fruit Slicer （计算几何 + 扫描线）

Gym 101147 A-The game of Osho

Windows Terminal & PowerShell 美化记录

SDUT 2021 Winter Individual Contest - F

SDUT 2021 Winter Individual Contest - G

SDUT 2020 Autumn Team Contest---43(for 19)

SDUT 2021 Winter Individual Contest - F

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

SDUT 2021 Winter Individual Contest - F

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款