这里会显示出您选择的修订版和当前版本之间的差别。
两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
2020-2021:teams:farmer_john:2020hdu暑期多校第六场 [2020/08/21 16:09] jjleo [E.] |
2020-2021:teams:farmer_john:2020hdu暑期多校第六场 [2020/12/22 09:10] (当前版本) 2sozx |
||
---|---|---|---|
行 1: | 行 1: | ||
- | ======2020 Multi-University Training Contest 6====== | + | ======2020HDU暑期多校第六场====== |
[[https://vjudge.net/contest/389024|比赛链接]] | [[https://vjudge.net/contest/389024|比赛链接]] | ||
=====A.===== | =====A.===== | ||
行 6: | 行 6: | ||
给出一个序列,等概率地选择左右端点$l \le r$,求$[l,r]$区间平均数的期望值。 | 给出一个序列,等概率地选择左右端点$l \le r$,求$[l,r]$区间平均数的期望值。 | ||
====题解==== | ====题解==== | ||
- | 题目本质是问长度为$1,2, \cdots , n$的连续子区间中,每个数各出现了多少次。可以发现如下规律:$$1 1 1 1 1 1 1$$ $$1 2 2 2 2 2 1$$ $$1 2 3 3 3 2 1$$ $$1 2 3 4 3 2 1$$ $$1 2 3 3 3 2 1$$ $$1 2 2 2 2 2 1$$ $$1 1 1 1 1 1 1$$ 因此整个前缀和,对于每个除以一下区间长度,最后再除以总方案数即可。 | + | 题目本质是问长度为$1,2, \cdots , n$的连续子区间中,每个数各出现了多少次。可以发现如下规律:$$1 1 1 1 1 1 1$$ $$1 2 2 2 2 2 1$$ $$1 2 3 3 3 2 1$$ $$1 2 3 4 3 2 1$$ $$1 2 3 3 3 2 1$$ $$1 2 2 2 2 2 1$$ $$1 1 1 1 1 1 1$$ 因此求出前缀和,对于每个除以一下区间长度,最后再除以总方案数即可。 |
=====B.===== | =====B.===== | ||
**solved by 2sozx** | **solved by 2sozx** | ||
行 29: | 行 29: | ||
**solved by JJLeo** | **solved by JJLeo** | ||
====题意==== | ====题意==== | ||
+ | 将$1145141919$循环无限次得到一个字符串,现在需要选取一个前缀,将这个前缀添加任意数量的$()\times+$使得表达式的值等于$x$,问对于$x=1,2, \cdots , 5000$,选取的最短前缀长度是多少,或判断无解。 | ||
====题解==== | ====题解==== | ||
+ | 选取前$11$个数打个表发现除了$3,7$都有解,然后就完事了。 | ||
=====F.===== | =====F.===== | ||
**solved by Bazoka13 JJLeo** | **solved by Bazoka13 JJLeo** | ||
行 92: | 行 92: | ||
=====H.===== | =====H.===== | ||
- | **upsolved by ** | + | **upsolved by JJLeo** |
====题意==== | ====题意==== | ||
行 98: | 行 98: | ||
=====I.===== | =====I.===== | ||
- | **solved by ** | + | **solved by JJLeo** |
====题意==== | ====题意==== | ||
+ | 给定$b$和$x$,问是否满足**__一个数是$x$的倍数__**等价于**__该数在$b$进制下的各数位上数字之和是$x$的倍数__**。 | ||
====题解==== | ====题解==== | ||
+ | 最常见的满足条件的有十进制下的$3$和$9$,盲猜满足条件等价于$x \equiv 1 \pmod{b}$就过了。 | ||
=====J.===== | =====J.===== | ||
- | **solved by ** | + | **solved by 2sozx JJLeo** |
====题意==== | ====题意==== | ||
+ | 给定一个$n$个点的无向图,每条边有边权,定义生成树的权值为所有树边边权的$\operatorname{AND}$,求生成树权值的期望,对$998244353$取模。$(n \le 100)$ | ||
====题解==== | ====题解==== | ||
+ | 按位考虑进行计算,枚举最终答案有每一位有多少种方案,通过只选择该位位$1$的边然后套用矩阵树定理即可。最后把所有边都算上再使用一个矩阵树定理计算出生成树总数,除以该数量即可。 | ||
=====K.===== | =====K.===== | ||
**upsolved by ** | **upsolved by ** |