ZR2020 普及五连测 day1
A设 $f_i$ 表示长度为 $i$ 的答案。考虑开头的元素：首先它只能选择 $\{1,2\}$。如果选择了 $1$，那么变成了 $n-1$ 的子问题；如果选择了 $2$，那么第二个数必须选择 $1$，变成了 $n-2$ 的子问题。所以 $f_i = f_{i-1}+f_{i-2}$，注意到斐波那契数列的通项公式是 $f_n = \frac{1}{\sqrt 5}[(\frac{1+\sqr...
A设 $f_i$ 表示长度为 $i$ 的答案。考虑开头的元素：首先它只能选择 $\{1,2\}$。如果选择了 $1$，那么变成了 $n-1$ 的子问题；如果选择了 $2$，那么第二个数必须选择 $1$，变成了 $n-2$ 的子问题。所以 $f_i = f_{i-1}+f_{i-2}$，注意到斐波那契数列的通项公式是 $f_n = \frac{1}{\sqrt 5}[(\frac{1+\sqr...
A根据期望的线性性，现在转变成了求每个点有多少概率是被自己覆盖的：显然是要在子树内第一个被选中的，所以答案就是 $\sum_{i=1}^n \frac{1}{sz_i}$。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define...
A输出 YES。考虑 Probability Method，我们以 $50\%$ 的概率独立均匀随机每个点是农业城市还是工业城市，一条边成为好边的概率就是 $\frac{1}{2}$，那么期望边数就是 $\frac{m}{2}$，所以一定存在一种方案边数 $>\frac{m}{2}$。出题人比较毒瘤，说 $m$ 是正整数结果数据有 $m=0$。#include <bits/std...
A显然深度相同的点会一起到达一号点，只需要求出深度然后取模加起来即可。B我们先暴力把所有可能的串都求出来，然后我们按照第一个字符进行分类。对于每一类，我们暴力枚举询问哪一位，计算出来询问这一位能区分出这一类中的几个，取个最大值作为这一类的答案。最终的答案是每一类的答案的和。C设 $a_i$ 表示覆盖点 $i$ 个区间个数，我们画图发现所有满足存在一个点被所有区间覆盖等价于 $a$ 是单峰的（...