DDOSvoid's Blog

题目描述

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

简要题意：给定一个 $n$ 个点无向树，求对于 $k\in[1,n - 1]$，有多少棵这 $n$ 个点的完全无向图的生成树与这棵树有恰好 $k$ 条边重复

$n\le 100$

题目描述

https://codeforces.com/problemset/problem/660/E

简要题意：给定 $n,m$，现在要求所有长度为 $n$ 的序列，序列中每个位置只能填 $[1,m]$，的本质不同的子序列的个数的和

$n,m\le 10^6$

题目描述

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

简要题意：给定一个 $n$ 个点 $m$ 条边的简单无向图，点 $i$ 个初始点权为 $w_i$，$w_i$ 构成了一个 $[1,n]$ 的排列，现在有 $q$ 次操作，操作有两种，第一种操作给定 $v$，查询与 $v$ 相连的点中点权最大的点的点权，然后点权最大的这个点的点权置为 $0$；第二种操作给定一个整数 $i$，将第 $i$ 条边删掉

题目描述

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

简要题意：给定一个 $n$ 个点 $m$ 条边的简单无向图，如果原图有 $k$ 个连通块，求添加 $k-1$ 条边是整个图连通的方案数

$n,m\le 10^5$

题目描述

https://codeforces.com/problemset/problem/961/F

简要题意：定义 $S$ 的 $k$ 子串为 $S_k=S[k..n-k+1],k\le \lceil\frac{n}{2}\rceil$，求 $S_k$ 的最长 $border$ 长度，$k\in [1,\lceil\frac{n}{2}\rceil]$

$|S|\le 10^6$

题目描述

简要题意：给定一个长度为 $n$ 的排列 $p_i$ 和一个长度为 $m$ 的序列 $a_i$，对于一个长度为 $n$ 的序列 $a_i$ 和一个长度为 $n$ 的排列 $p_i$，称 $a_i$ 符合 $p_i$ 当且仅当 $a_i$ 互不相同，且将 $a_i$ 从小到大排序会得到 $a_{p_1},\cdots, a_{p_n}$，现在需要对给定的序列 $a_i$ 求其有多少个符合给定排列 $p_i$ 的长度为 $m$ 的子串

$n\le m\le 10^6$

题目描述

https://codeforces.com/problemset/problem/1439/C

简要题意：给定一个长度为 $n$ 的非升序列 $a_i$，现在有 $m$ 次操作，操作有两种，第一种操作给定 $x,y$，对于所有 $i\in[1,x]$，修改 $a_i=\max(a_i,y)$；第二种操作给定 $x,y$，从左往右访问序列 $a_i$，如果 $a_i\le y$，则 $ans++,y = y-a_i$，求 $ans$

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

题目描述

https://codeforces.com/problemset/problem/920/E

简要题意：给定一个 $n$ 个点 $m$ 条边简单无向图，求该图的补图的连通块个数

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

题目描述

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

简要题意：给定字符串 $S$ 和 $T$，其长度分别为 $n$ 和 $m$，$S[l..r]$ 的价值为 $T$ 在 $S[l..r]$ 中的出现次数，求 $S$ 的所有长度为奇数的回文子串的价值和

$n,m\le 3\times 10^6$

题目描述

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

简要题解：给定一个字符串 $S$，求 $S$ 有多少前缀 $T$，满足 $T$ 进行若干次操作后得到的串 $T’$ 存在一个前缀为 $S$，字符串 $S$ 进行一次操作定义为固定 $S$ 的最后一个字符，将剩下的字符翻转并且拼接到 $S$ 的后面，例如 $abcd$ 操作一次后得到 $abcdcba$

$|S|\le 10^6$