链接

https://ac.nowcoder.com/acm/contest/9700/E

题意

给定一张 $n$ 个点 $m$ 条边的无向带边权连通图，点有颜色，为黑或白，保证无自环和重边。

定义一次操作为：随机选择两个不同的点，将它们之间的最短路上的点全部染黑（若有多条最短路就都染黑）。

现在你想知道，经过 $k$ 次操作后，黑色点的期望个数是多少。

链接

https://ac.nowcoder.com/acm/contest/9700/D

题意

无向连通图，规定只能走权值在 $[L , R]$ 内的边。

求在 $L，R$ 分别等于多少时，可以顺利从 $s$ 到达 $t$，要求 $L$ 尽可能大，在 $L$ 最大的情况下 $R$ 尽可能小。

链接

https://ac.nowcoder.com/acm/contest/9700/C

题意

一个 $n*n$ 的矩形内布满了老鼠。

万幸的是，你有一个 $k*k$ 的锤子，一锤子砸下去可以把它覆盖到的所有老鼠清除。

这个锤子只能斜着锤，对于一个 $3*3$ 的锤子，它能覆盖到的区域如下：

- - * - -

- * * * -

* * * * *

- * * * -

- - * - -

一锤子砸下去，最多能清除多少只老鼠？

链接

https://codeforces.com/contest/723/problem/E

题意

将无向图转为有向图，使图中入度等于出度的点尽量多。

链接

https://ac.nowcoder.com/acm/contest/8688/D

题意

$A$ 有 $hp1$ 血量，$B$ 有 $hp2$ 血量。

每个回合 $A$ 会发起一次攻击，每次攻击造成 $w$ 伤害，有 $p$ 概率击中 $B$，$1-p$ 概率击中自己。

当有一个人血量少于等于 $0$ 时，游戏结束。

求回合数的期望。

链接

https://codeforces.com/contest/55/problem/D

题意

$T(1\le t \le 10)$ 次询问，求$[l,r](1 \le l \le r \le 9e18)$ 内多少数能被其自身每位非零数字整除。

链接

https://ac.nowcoder.com/acm/contest/9983/E

题意

带修改询问区间内是否有相同的数。

链接

https://loj.ac/p/10173

题意

矩阵中有山和平地，只能在平地上放置炮兵，炮兵的射程为上下左右两格内。

必须保证所有炮兵不在别的炮兵射程内。

求最大放置炮兵数。

链接

https://ac.nowcoder.com/acm/contest/4370/H

题意

将一个 $n$ 个节点的点权树切为 $k$ 个树，使每棵树的点权和的最大值最小。

链接

https://ac.nowcoder.com/acm/contest/9983/A

题意

已知 $a,b$，$x \equiv a \pmod p$，$y \equiv b \pmod p$，求 $gcd(x,y) \bmod p$ 的最大值以及 $x,y$ 的取值。