跳转至

2020HDU暑期多校第七场

排名 当场过题数 至今过题数 总题数
28/757 4 6 11

A

upsolved by

题意

题解

B

upsolved by

题意

题解

C

upsolved by

题意

题解

D

solved by JJLeo

题意

给定\(t,a,c,m\)，等概率地从\([0,t]\)中选择两个数\(v_1,v_2\)，设\(X_0=v_1+v_2\)，\(X_{n+1}=(aX_n+c) \mod m (n \ge 0)\)，求\(X_{|v_1-v_2|}\)是偶数的期望，输出最简分数。\((2 \leq m \leq 10^6, 0 \leq a, c < m, 0 \leq t < \frac{m}{2})\)

题解

可以发现\(X\)数组本质上是多个环，因此我们可以考虑当\(v_1+v_2=b\)时，\(|v_1-v_2|\)的取值情况，分奇偶以及\(v_1+v_2\)与\(t\)的大小关系讨论一下可以发现本质上就是求环上某个点往后两个两个跳，遇到的所有点其中点上数字是偶数的数量，倍增处理一下即可，本题难点在上述讨论过程中细节上的一些处理。

E

upsolved by JJLeo

题意

数轴上一共有\(2n+1\)个点，每个点的坐标为\(x_i\)，下标为奇数的点为洞，下标为偶数的点为球，每次等概率地随机选择一个球，等概率地往左或往右推动它，直到它落入遇到的第一个洞里，每个洞只能放一个球。求球滚过距离之和的期望，对\(998244353\)取模，多组数据。\((n \le 3000, \sum n \le 10^6)\)

题解

每次推球这个过程可以转化为从一个序列中每次选择两个相邻的数，使得总路程增加\(|x_i-x_j|\)，然后将这两个数从序列中删除，不断重复上述操作直到只剩下一个数。考虑拆开上述的绝对值，一个数如果和它右边的数一起被删，贡献为\(-x_i\)；如果和它左边的数一起被删，贡献为\(x_i\)；如果没被删，贡献为\(0\)。因此我们设\(f_{i,j}\)为一个数左边有\(i\)个数，右边有\(j\)个数时和它右边的数一起被删的概率，我们可以通过\(O(n^2)\)dp预处理出该数组，考虑当前状态一共有\((i+j)\)种删除方案，对于每一种删除后都可以转化为一个子问题，因此有如下的递推：

1
2
3
4
5
6
7
8
9
for(int i = 0;i <= n;i++){
    for(int j = 1;i + j <= n;j++){
        if((i + j) & 1) continue;//显然本题中i+j必然为偶数
        if(j) f[i][j] = 1;
        if(j > 1) f[i][j] = (f[i][j] + 1ll * f[i][j - 2] * (j - 1)) % p;
        if(i > 1) f[i][j] = (f[i][j] + 1ll * f[i - 2][j] * (i - 1)) % p;
        f[i][j] = 1ll * f[i][j] * inv[i + j] % p;
    }
}

最后对于每一组数据，答案为\(\sum_{i=1}^{2n+1}(f_{n-i,i-1}x_i-f_{i-1,n-i}x_i)\)，总复杂度\(O(n^2+\sum n)\)。

F

upsolved by

题意

题解

G

upsolved by

题意

题解

H

upsolved by JJLeo

题意

题解

I

solved by 2sozx JJLeo

题意

给出一个长度为 \(n\) 的排列的最长上升子序列与最长下降子序列的长度 \(x,y\)，找出一个符合条件的序列，并且要求字典序最小，没有则输出 \(-1\)。\(n\le10^5\)

题解

字典序最小显然将 \(1,2,3\cdots\) 放在前面，后面考虑将最长下降子序列分块，每块的长度为 \(y\) ，若存在不整除的情况则在 \(1,2,3\cdots\) 后先输出字典序最小。如果 \(x + y > n + 1\) 一定不存在输出 \(-1\) 即可。

J

solved by JJLeo

题意

定义所有横纵坐标不互质的点为“好点”，现在初始在一个好点上，每次可以不动或者前往周围八个格子中的好点，上述操作均等概率随机，设走\(p_t\)为游走\(t\)次后回到初始点的概率，求\(\lim \limits_{t \to +\infty} p_t\)。

题解

如果能走到对角线答案为\(0\)，否则盲猜好点的个数不会很多，因此直接爆搜，再观察样例盲猜出答案为“起点可移动的方向（包括不动）”除以“所有点可移动的方向（包括不动）之和”。
而这样做的正确性，题解如是说：至于证明极限的存在性，需要涉及关于邻接矩阵的特征值等内容，可以自行查阅“图上随机游走”相关书籍文献。

记录

before：提前获得了本场比赛会PE的消息
0min：分题
20+min：ZYF MJX冲I
30min：MJX AC，CSK冲G，ZYF MJX 看J
58min：CSK WA，ZYF 冲 J
72min：ZYF WA
76min：多输出个换行 AC J，CSK AC G，冲D
128min：ZYF AC D
till end：垃圾时间比以往来得更早一些
after end：垃圾hdu测评机

总结

  • MJX：考试前一天早点睡，以免太困
  • ZYF：啥也不会，我学还不行吗。（但为什么某卷翻天的题会无限TLE）
回到页面顶部