DDOSvoid's Blog

题目描述

https://acm.hdu.edu.cn/showproblem.php?pid=7171

简要题意：给定一个 $n$ 个点 $m$ 条边的 $DAG$，现在有 $q$ 次询问，每次询问给定 $u,v,l,r$，问从 $u$ 出发，只经过编号在 $[l,r]$ 内的边能否到达 $v$

$n,q\le 50000,m\le 100000$

题目描述

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

简要题意：给定 $n$ 个点 $m$ 条边的 $DAG$，求最多能删掉多少条边的同时不改变原图的连通性

$n\le 3\times 10^4,m\le 10^5$

题目描述

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

简要题意：给定一个长度为 $n$ 的字符串 $S$，现在有 $m$ 次询问，每次询问规定一个整数 $k_i$ 和一个字符串 $T_i$，对于每次询问要求找到一个字符串 $B$ 满足 $B$ 是 $S$ 的子串，且 $T_i$ 在 $B$ 中至少出现了 $k_i$ 次，保证每次询问的 $T_i$ 不同

$|S|,n,\sum |T|\le 10^5$

题目描述

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

简要题意：给定一个长度为 $n$ 的字符串 $S$，现在有 $m$ 次操作，操作有两种，第一种操作是给定一个整数 $x$ 和一个字符 $ch$，将 $S_x$ 改成 $ch$；第二种操作给定 $[l,r]$ 和字符串 $T$，求字符串 $T$ 在 $S[l..r]$ 中出现了多少次

$|S|,m,\sum |T|\le 10^5$

简介

$bitset$ 确实是一个很好用的东西

题目描述

https://acm.hdu.edu.cn/showproblem.php?pid=7232

简要题意：给定 $n,m$，求有多少长度为 $m$ 的序列 $a_i$，满足 $a_i\in[1,n]$，且不存在一个长度为 $n$ 的子区间且这个子区间是一个 $1$ 到 $n$ 的排列

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

题目描述

https://acm.hdu.edu.cn/showproblem.php?pid=7221

简要题意：给定一个长度为 $n$ 的序列 $a_i$，保证 $a_i$ 互不相同，求有多少种合法的划分，一个划分是合法的当且仅当所有子段都满足最大值的下标为奇数，最小值的下标为偶数，需要注意的是每个子段的下标都是从 $1$ 开始重新编号的
$n\le 3\times 10^5$

题目描述

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

简要题意：给定一个 $n$ 个点 $m$ 条边的带权无向图，第 $i$ 条边的边权为 $(a_i,b_i)$，现在有 $q$ 次询问，每次询问给定 $u,v,a,b$，问是否存在一条从 $u$ 到 $v$ 的路径满足路径上所有边的 $a_i\le a,b_i\le b$ 且满足 $max a_i=a,max b_i=b$

$n,q\le 5\times 10^4,m\le 10^5$

题目描述

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

简要题意：给定 $n,p$，求 $\sum_{i=1}^n\sum_{j=1}^n(i,j)^{(i,j)}$

$n\le 1.5\times 10^6$

题目描述

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

简要题意：给定一棵 $n$ 个点的无根树，现在有 $m$ 个操作，操作有三种，第一种操作加入一条树上的路径 $(a,b)$ 这个路径有一个权值 $c$；第二种操作给定 $x$，删除第 $x$ 个操作所加入的路径；第三种操作给定一个点 $x$，求现在存在的路径中不考虑经过 $x$ 的路径中权值最大的路径的权值

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