w
h
y
?
y
o
u
a
r
e
h
e
r
e
?
题意给你n个串 每个串都有一个价值$c_i$ 然后让你构造一个串$S$ $S$的价值定义为:
$F(S)=\sum_{i=1}^{n}c_ip_{S,i}|S|$
$p_{S,i}$ 表示在第$T_i$中$S$出现的次数
$|S|$表示串的长度
问 如何选择$S$能得到最大价值 输出最大价值
题
...
题意给定长度为$n$的整数序列
$q$次查询 区间$[l,r]$能’’匹配’’多少长度与其一致且不相交的区间 匹配的定义是for all $i$ $(0 ≤ i≤ r1 - l1)$ the following condition holds: $h1 + i + hl2 + i = hl1
...
题意给定一个括号序列,现在能进行两类操作:
循环移位,将末尾的字符移动到开头
在任意位置加入任意类型字符
问在满足加入字符最小的情况下,输出合法的括号序列,如果有多种情况满足长度最下,则输出字典序最小的
题解首先
对于加入字符最少 必然是加入$|左括号num-右括号num|$个
若左括号多 必
...
题意给定$m$个字符串 问构造长度为$n$的串的方案数
构造串需满足 对于任意位置 $i$ 都存在一个子区间[l,r] 包含$i$且子区间对应m个串中的任意一个
题解AC自动机+DP
我们可以设$dp[i][j][k]$ 表示已经构造了长度为$i$的串 且在自动机中第$j$状态 且存在$k$字符属
...
题目描述在图论中，“简单环” 被定义为一个点数和边数相等的回路，并且这条回路上没有出现重复的点或边。
对于一个无向图，小象定义 “项链” 是由一些简单环组成的子图，不妨设项链包括 k 个简单环 $C_1, C_2, \ldots…, C_k (k \in \mathbb{N}^+)$，那么项链需要满
...
题目描述现在，我想知道自己是否还有选择。
给定n个点m条边的无向图以及顺序发生的q个事件。
每个事件都属于下面两种之一：
1、删除某一条图上仍存在的边
2、询问是否存在两条边不相交的路径可以从点u出发到点v
题解神奇的并查集 %%%%
我们考虑离线下来 从后到前做 把删边处理成加边(注意重边)
把剩
...
题解经典$0/1$分数规划 二分答案$ans$
对于所有的边权减去$ans$
问题转化成 树上是否存在一条路径 $L<=len<=R$ 并且路径和大于等于0
比较直观的做法 用点分+线段树查询 复杂度$O(nlog^2nlogw)$ 然而会T飞
我们考虑 每个深度对应的是一段区间 总体
...
题解很牛逼的点分啊 !!!!!
我们考虑二分答案 然后直接点分统计大于等于k的点对个数 复杂度$(O(nlog^2nlogw))$ 据说卡卡常数肯定是能过的 但是我们主要用下面这种方法
我们对于当前重心的子树节点按照点到重心的距离排序 因为点只有$nlogn$个 (点分的性质) 所以预处理复杂度$O
...
题解点对问题考虑点分
我们考虑子树合并 有两种情况 分别是当前子树链作为开头或者结尾 对于长度大于$m$和小于等于$m$再分情况讨论下 然后分别维护已经合并完的子树在长度为$x$时 分别作为开头和结尾的情况下的方案数 统计贡献的话 就直接用hash判当前的子串是否合法即可
hash我们考虑自然溢出
...
题解分为两部分
对于树形结构 直接点分 然后排序/树状数组统计贡献
对于基环树结构 我们先把环取出来 以环上的点为根做点分治 统计每个子树内的贡献 然后考虑环上点的相互影响 对于每个子树维护每种深度的个数 然后我们可以考虑到每个点作用的是一段连续区间 可以采用树状数组来维护答案 时间复杂度是$
...