fshp971

本场比赛四道中等题，其中三道题数据范围故意放水降低难度。 然后。。没放水那题。。好像。。没人过啊。。？ B - 修仙时在做什么？有没有空？可以来炼丹吗？ 题目链接 M姓出题人：这么老的idea怎么还没人做XD 考虑到本题的idea非常古老，所以在预估难度时设为中等题，然而现场没人过。题意本质上就是给出一个含$2^{18}$个结点的无向连通图，再指定其中$n$个点，求这$n$个指定点的两两之间的最短路的最小值。 接下来的讨论假定$n$个指定点的编号两两不同（如果出现相同编号的话答案就是$0$）。我们不妨考虑二进制分组。

D - 神经网络 题目链接 这是一道经典题目改编，原题是dreamoon出的NTU-WF选拔赛D题（题目链接）。 不难发现，修复时所产生的花费，可以分解为一系列有向简单路径上结点权值之和。因此由期望的线性性可知，要求总花费的期望值，我们只需分别计算$n^2$条有向简单路径对总花费产生贡献的期望值。 对于树上一条有向简单路径$u \rightarrow v$，设该路径长度为$d \ (0 \leq d \leq n-1)$（也就是说有$d$条边，$d+1$个结点）

本场比赛5道简单题，除了A题榜歪了以外，其他4题通过率均符合预期。 A - NB群友 题目链接 问题可以转化成求“积$\leq R$的数的个数” $-$ “积$\leq (L-1)$的数的个数”，于是我们可以dfs枚举$2 \sim 9$每个数字出现的次数，然后再组合数统计一下答案，剪剪枝就能过。 #include<bits/stdc++.h> using namespace std;

咕咕咕姑姑～ 比赛链接 题目难度设置 table th:nth-of-type(1) { width: 500px; } table th:nth-of-type(2) { width: 500px; } 难度 题号 签到 L 简单 A, C, E, I 中等 F, H, K 中等偏难 B 难 D，J