DDOSvoid's Blog

题目描述

https://open.kattis.com/problems/dotsboxes

简要题意：给定一个 $n \times n$ 的网格图，有一些格点之间存在边，但保证不存在变长为 $1$ 的正方形，求最多加多少条边使得仍然不存在边长为 $1$ 的正方形

$n\le 80$

题目描述

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

简要题意：给定一个 $n$ 个点 $m$ 条边的无向图，边权均为 $a$，现在将原图中所有最短路为 $2a$ 的点对 $(i,j)$ 之间加一条长度为 $b$ 的无向边，求新图的以 $S$ 为起点的单源最短路径

$n,m\le 10^5$

题目描述

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

简要题意：给定一个长度为 $n$ 的序列 $a_i$ 和一个整数 $s$，满足 $a_i$ 互不相同，$s\in[1,n]$，现在有 $m$ 次操作，操作有两种，第一种操作给定 $i,e$，将 $a_i$ 变成第 $e$ 大，保证之前 $i$ 的排名大于 $e$；第二种操作给定 $x$，问从 $s$ 开始向两边拓展到 $x$ 最少需要拓展多少次，拓展规则如下，假设现在已经拓展了 $[l,r]$，那么下一次会从 $l-1$ 和 $r+1$ 中选择一个较小的进行拓展

$n\le 2.5\times 10^5,q\le 5\times 10^5,e\le 10$

例题

题目描述

简要题意：给定一个 $n$ 个点 $m$ 条边的有向图，求以每个点为根的外向树的个数

$n\le 500$

题目描述

https://codeforces.com/gym/102798/problem/E

简要题意：给定一个长度为 $n$ 的序列 $a_i$，每秒会随机选择一个大于 $0$ 的 $a_i$ 将其减 $1$，求 $m$ 秒后期望有多少个 $a_i=0$

$n\le 15,m,a_i\le 100$

题目描述

https://ac.nowcoder.com/acm/contest/38727/L

简要题意：给定一个多重集 $S$，满足 $S$ 中的元素都在 $[0,n]$，且 $|S|=n$，求由 $S$ 组成的长度为 $n$ 的序列的价值和，一个序列的价值定义为它的所有区间的 $mex$ 的和

$n\le 10^5$

题目描述

https://codeforces.com/problemset/problem/1603/D

简要题意：现在有 $q$ 次询问，每次询问给定 $n$ 和 $k$，求将 $[1,n]$ 这个序列分成 $k$ 段的最小代价和，$[l,r]$ 的代价为 $c(l,r)=\sum_{i=l}^r\sum_{j=i}^r[(i,j)\ge l]$

$k\le n\le 10^5,q\le 3\times 10^5$

题目描述

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

简要题意：给定 $n$ 和 $k$，定义一个合法序列为 $a_i\in[1,k],i\in[1,n]$，一个序列的值为 $\prod_{i=1}^na_i$，求对于 $m\in[1,n]$，所有长度为 $m$ 的序列的价值和

$n\le 5\times 10^5 $

题目描述

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

简要题意：给定一个 $n$ 个点的带权完全无向图，给定 $k$，求所有生成树的权值的 $k$ 次方之和

$n,k\le 30$