w h y ? y o u a r e h e r e ?

题意给你n个串 每个串都有一个价值ci 然后让你构造一个串S S的价值定义为: F(S)=i=1ncipS,i|S| pS,i 表示在第TiS出现的次数 |S|表示串的长度 问 如何选择S能得到最大价值 输出最大价值 题 ...
Read more »

题意给定长度为n的整数序列 q次查询 区间[l,r]能’’匹配’’多少长度与其一致且不相交的区间 匹配的定义是for all i (0ir1l1) the following condition holds: $h1 + i + hl2 + i = hl1 ...
Read more »

题意给定一个括号序列,现在能进行两类操作: 循环移位,将末尾的字符移动到开头 在任意位置加入任意类型字符 问在满足加入字符最小的情况下,输出合法的括号序列,如果有多种情况满足长度最下,则输出字典序最小的 题解首先 对于加入字符最少 必然是加入|numnum|个 若左括号多 必 ...
Read more »

题意给定m个字符串 问构造长度为n的串的方案数 构造串需满足 对于任意位置 i 都存在一个子区间[l,r] 包含i且子区间对应m个串中的任意一个 题解AC自动机+DP 我们可以设dp[i][j][k] 表示已经构造了长度为i的串 且在自动机中第j状态 且存在k字符属 ...
Read more »

题目描述在图论中,“简单环” 被定义为一个点数和边数相等的回路,并且这条回路上没有出现重复的点或边。 对于一个无向图,小象定义 “项链” 是由一些简单环组成的子图,不妨设项链包括 k 个简单环 C1,C2,,Ck(kN+),那么项链需要满 ...
Read more »

题目描述现在,我想知道自己是否还有选择。 给定n个点m条边的无向图以及顺序发生的q个事件。 每个事件都属于下面两种之一: 1、删除某一条图上仍存在的边 2、询问是否存在两条边不相交的路径可以从点u出发到点v 题解神奇的并查集 %%%% 我们考虑离线下来 从后到前做 把删边处理成加边(注意重边) 把剩 ...
Read more »

题解经典0/1分数规划 二分答案ans 对于所有的边权减去ans 问题转化成 树上是否存在一条路径 L<=len<=R 并且路径和大于等于0 比较直观的做法 用点分+线段树查询 复杂度O(nlog2nlogw) 然而会T飞 我们考虑 每个深度对应的是一段区间 总体 ...
Read more »

题解很牛逼的点分啊 !!!!! 我们考虑二分答案 然后直接点分统计大于等于k的点对个数 复杂度(O(nlog2nlogw)) 据说卡卡常数肯定是能过的 但是我们主要用下面这种方法 我们对于当前重心的子树节点按照点到重心的距离排序 因为点只有nlogn个 (点分的性质) 所以预处理复杂度$O ...
Read more »

题解点对问题考虑点分 我们考虑子树合并 有两种情况 分别是当前子树链作为开头或者结尾 对于长度大于m和小于等于m再分情况讨论下 然后分别维护已经合并完的子树在长度为x时 分别作为开头和结尾的情况下的方案数 统计贡献的话 就直接用hash判当前的子串是否合法即可 hash我们考虑自然溢出 ...
Read more »

题解分为两部分 对于树形结构 直接点分 然后排序/树状数组统计贡献 对于基环树结构 我们先把环取出来 以环上的点为根做点分治 统计每个子树内的贡献 然后考虑环上点的相互影响 对于每个子树维护每种深度的个数 然后我们可以考虑到每个点作用的是一段连续区间 可以采用树状数组来维护答案 时间复杂度是$ ...
Read more »