DDOSvoid's Blog

简介

大概就是用来求 $\sum_{T \in Tree}\prod_{e\in T}w_e$ 的值

题目描述

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

简要题意：给定一棵 $n$ 个节点的树，现在有 $m$ 次询问，每次询问给出 $k_i$ 个关键点，然后将树上的每个点划分到离他最近的关键点，如果距离两个关键点相同，则划分给编号较小的关键点，输出每个关键点被分配到多少点

$n,m,\sum k_i\le 3\times 10^5$

简介

大概就是将给定的树上的 $k$ 个点和它们之间的 $lca$ 拿出来重新建一棵树，时间复杂度为 $O(k\log k)$

题目描述

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

简要题意：给定一棵以 $1$ 为根的有根树，边权不为 $1$，现在有 $m$ 次询问，每次询问给定一个点集 $|S|$，保证该点集不包含 $1$，现在要求断掉一些边，使得点集中任意一个点都不与 $1$ 相连，求最小代价

$n\le 2.5\times 10^5,m,\sum |S|\le 5\times 10^5$

题目描述

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

简要题意：给定一棵 $n$ 个节点的树，每个点有一个颜色 $c_i$，令 $d(i,j)$ 表示 $i$ 到 $j$ 的简单路径上的颜色种数， 令 $f_i=\sum_{j=1}^nd(i,j)$，求所有的 $f_i$

$n,c_i\le 10^5$

题目描述

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

简要题意：给定 $m$ 个字符串 $S_i$，字符集为 $[1,n]$，现在要求对于每个字符串 $S_i$ 进行如下操作：从空串 $T$ 开始，每次随机生成一个 $[1,n]$ 内的整数，添加到 $T$ 的末尾，直到 $S$ 作为 $T$ 的子串出现过，求 $T$ 的期望长度

$|S_i|,n\le 10^5,m\le 50$

题目描述

http://oj.daimayuan.top/course/10/problem/668

简要题意：给定一个长度为 $n$ 的序列 $a_i$，令 $d_i=max(a_1, a_2, \cdots, a_i)-min(a_1, a_2, \cdots, a_i)$，现在要求重新排列 $a$，使得 $\sum_{i=1}^nd_i$ 最小

$n\le 2000$

题目描述

https://ac.nowcoder.com/acm/contest/30896/J

简要题意：给定一个长度为 $n$ 的序列 $a_i$，现在需要计算对于所有满足条件的序列 $b_i$ $\prod_{i=1}^n\binom{b_i}{a_i}$ 的累加和，序列 $b_i$ 满足的条件为序列 $b$ 只包含自然数且长度为 $n$，序列 $b_i$ 中所有数的和小于等于 $m$

$n\le 5000,a_i\le 2000,m\le 10^9$

题目描述

https://codeforces.com/gym/103102/problem/F

简要题意：给定一个长度为 $n$ 的排列 $p_i$，现在你可以若干次操作，每次操作选定一个区间 $[l,r]$，将区间 $[l,r]$ 内的数都变成 $[l,r]$ 的最小值，求可能会有多少种序列

$n\le 3000$

题目描述

https://codeforces.com/gym/103102/problem/L

简要题意：给定 $n$ 个数对 $(m_i,p_i)$，现在要求选择尽量多的数对，不妨设选择了 $2\times k$ 个，则需保证恰好有 $k$ 个数对取第一位 $m_i$，同时恰好有 $k$ 个数对取第二维 $p_i$，且需保证 $\sum m\ge \sum p$，求最多取多少个数对

$n\le 10^5$