hk_cnyali's Blog

又是一场疯狂罚时的ACM

恶补大家小学就会的知识点

其实是一些乱七八糟的基础知识

称一个长度为 $n$，元素取值$\in[1,D]$的整数序列是合法的，当且仅当其中能够选出至少 $m$ 对相同元素（不能重复选出元素）

问合法序列个数，答案对$998244353$取模

$n, m\le 10^9, D\le 10^5$

来自csy课件的一些字符串题

$n$个点，$m$次操作：

• 1, _x, _y

  令$x = (\_x + last - 1) \mathrm{mod}~n + 1, y=(\_y + last - 1) \mathrm{mod}~n + 1$

  若$(x, y)$已经连接，则删掉$(x, y)$，否则连接$(x, y)$

• 2, _x, _y

  令$x = (\_x + last - 1) \mathrm{mod}~n + 1, y=(\_y + last - 1) \mathrm{mod}~n + 1$

  询问$x$和$y$是否联通，输出$0/1$

其中$last$表示上一次询问的答案

$n, m\le 2\times 10^5$

一棵$n$个点的树，进行轮操作，每轮操作随机选择一条边$(u,v)$，将$u,v$两点合成一个点。即删去这两个点后新建一个点$x$，将原来与$u$或$v$连边的点连向$x$，接着$x$的编号随机为$u,v$中的一个。

求每个点最终留下的概率。

$n\le 50$

给一个 $n$ 个点,$m$ 条边的图,边权为 $[0, 1]$ 的均匀分布的随机实数,求最小生成树的最大边权的期望

提示：对于 $n$ 个 $[0, 1]$ 之间的随机变量 ，第 $k$ 小的那个的期望值是$\frac{k}{n + 1}$

$n\le 10, m\le \frac{n(n-1)}{2}$

你有一个 $n$ 行、$m$ 列的、每个格子都填写着 $0$ 的表格。你进行了下面的操作:

• 对于每一行 $i$ ,选定自然数 $r_i (0 \le r_i \le m)$,将这一行最左边的 $r_i$ 个格子中的数 $+1$
• 对于每一列 $i$ ,选定自然数 $c_i (0 \le c_i \le n)$, 将这一列最上面的 $c_i$ 个格子中的数 $+1$

问最终表格有多少种本质不同的方案

搞颓记录

有一棵$n$个点的树, 边有边权.

树上有k个点移动速度为正无穷,人初始在s位置,移动速度为1,求至少多少时间才能将抓住所有点(人和点都进行最优决策，点尽可能拖延时间).

$n,k<=50.$