DDOSvoid's Blog

题目描述

简要题意：给定一个二维平面，平面上有 $n$ 个白点，第 $i$ 个白点的坐标为 $(x_i,y_i)$，其能传输的范围为 $r_i$，收益为 $s_i$，第 $i$ 个点能传输到第 $j$ 个点，当且仅当两点之间的欧几里得距离小于等于 $r_i$，现在要将某些点涂黑，如果染黑每个点则必须将其能到达的点都染黑，染黑一个点能得到它的收益，求最大收益

$n\le 100$

简介

这一类做法常用于最优化问题中，我们通过减弱题目的条件来多求得一些更差的状态但是我们仍然能求得最优的状态

最常见的就是拆绝对值的过程，例如我们要最大化 $\sum_{i=1}^n|a_i-b_i|$，那么我们考虑 $O(2^n)$ 枚举 $a_i$ 和 $b_i$ 的符号即可，这样我们就将绝对值去掉了，如果符号不对的话答案一定是更差的，所以不会造成影响

题目描述

https://www.codeforces.com/problemset/problem/559/E

简要题意：给定 $n$ 个数轴上的点，以及每个点可以延伸的长度，现在每个点只能向左或者右一个方向延伸，求这 $n$ 个延伸出的线段的并的最大值

$n\le 100$

题目描述

https://www.codeforces.com/problemset/problem/1473/E

简要题意：给定一张 $n$ 个点 $m$ 条边的带权无向图，对于一条路径 $E$，这条路径的权值是 $\sum_{i\in E} w_i-max_{i\in E}w_i+min_{i\in E}w_i$，求 $1$ 到其它所有点的最短路

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

题目描述

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

简要题意：给定一个长度为 $n$ 的字符串和 $m$ 次询问，每次询问给定四个参数 $a,b,c,d$，求 $S[a\cdots b]$ 的所有子串和 $S[c\cdots d]$ 的 $lcp$

$n,m\le 10^5$

题目描述

http://codeforces.com/problemset/problem/452/E

简要题意：给定三个字符串 $A,B,C$，求对于所有 $l$，有多少个数对 $(a,b,c)$，满足 $A[a\cdots a+l-1]=B[b\cdots b+l-1]=C[c\cdots c+l-1]$

$|A|+|B|+|C|\le 3\times 10^5$

题目描述

http://codeforces.com/problemset/problem/1073/G

简要题意：给定一个字符串和 $m$ 次询问，每次询问给定两个集合 $A$ 和 $B$，求 $\sum_{i\in A,j\in B}lcp(suf(S,i),suf(S,j))$

$n,m,\sum |A|,\sum |B|\le 2\times 10^5$

题目描述

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

简要题意：给定一个长度为 $n$ 的字符串 $S$，求 $\sum_{1\le i<j\le n}len(suf(S,i))+len(suf(S,j))-2lcp(suf(S,i),suf(S,j))$

$n\le 5\times 10^5$

题目描述

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

简要题意：给定一个长度为 $n$ 的字符串和 $k$，求长度最长的一个子串，满足这个子串至少出现了 $k$ 次

$n\le 2\times 10^4$

题目描述

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

简要题意：给定 $n$ 个物品和 $m$ 个属性以及常数 $w$，第 $i$ 个物品有一个价值 $c_i$ 以及其所拥有的属性 $S_i$，现在要依次选择若干个物品，满足相邻两个物品 $i$ 和 $j$ 满足 $i<j\wedge w+c_i\ge c_j\wedge S_i\subseteq S_j$，求最多选择多少个物品

$n\le 10^5,m\le 18$