DDOSvoid's Blog

题目描述

https://codeforces.com/problemset/problem/38/G

题目描述

https://www.luogu.com.cn/problem/P3960

题目描述

https://www.luogu.com.cn/problem/CF804D

简要题意：给定一个森林和 $q$ 个询问，每次询问给定一个无序二元组 $(x,y)$，问将 $x$ 和 $y$ 所在的树随机连接起来后的直径的期望

$n,q\le 10^5$

题目描述

https://www.luogu.com.cn/problem/P2053

简要题意：有 $n$ 辆车，$m$ 个修车人，现在 $n$ 辆车都需要被修，第 $i$ 辆车被第 $j$ 个人修的时间为 $c_{i,j}$，一个人同时只能修一辆车，求顾客平均等待时间最小为多少

$n\le 60,m\le 9$

题目描述

https://www.luogu.com.cn/problem/P6517

简要题意：给定一张 $n\times m$ 的四连通网格图，图上的点分为 $5$ 种：空地、精灵、人类、矮人、霍比特人，这四种生物的要求如下：精灵：只需要与一个邻居结盟；人类：需要与两个邻居结盟，且这两个邻居不能在上下或者左右方向；矮人：需要与三个邻居结盟；霍比特人：需要与四个邻居结盟，结盟关系是双向的，且只有相邻两个点才可结盟，请求出任何一种合法方案

$n,m\le 70$

题目描述

https://www.luogu.com.cn/problem/P7368

题目描述

https://www.luogu.com.cn/problem/P1251

简要题意：现在有一个餐厅，在接下来的 $n$ 天中，第 $i$ 天需要 $r_i$ 块餐巾，购买新的餐巾的费用为 $p$，将旧餐巾送到快洗部需要 $m$ 天，费用为 $f$，送到慢洗部需要 $n(n>m)$ 天，费用为 $s$，求最小花费

$n\le 2000$

题目描述

https://www.luogu.com.cn/problem/P3159

题目描述

简要题意：给定一个 $n\times n\times n$ 的六连通立方体，每个位置可以填 $0$ 或 $1$，现在有些位置已经填了数，如果两个相邻的格子所填数不同则会产生 $1$ 的收益，问最大收益

$n\le 40$

题目描述

https://www.luogu.com.cn/problem/P1935

简要题意：现在有一个 $n\times m$ 的四连通网格，每个位置填 $0$ 有 $a_{i,j}$ 的收益，填 $1$ 有 $b_{i,j}$ 的收益，对于每个格子 $(i,j)$ 如果它周围的格子中有 $k$ 个格子和它填的数不同，那么会有 $k\times c_{i,j}$ 收益，求最大收益

$n,m\le 100$