Luogu分析每个人的话相当于 $[a_i+1,n-b_i]$ 中的人排名相同。那么如果两个人的话不同且对应的区间无交,他们就可能都说了真话。把相同的区间缩在一起,问题变成每个区间有一个权值,选出若干个无交的区间使得权值和最大。这个可以直接 DP,把所有区间按右端点排序后,二分找到最后的左端点小于当前右端点的位置,然后转移即可。注意把 $a_i+1>n-b_i$ 的人掉,这些人一定说了...
LuoguGym分析先考虑 $c=0$ 的情况。我们计算每个 $l_i$ 和 $t_i$ 对 $(n,n)$ 的贡献。只考虑 $l_i$,那么相当于从 $(i,1)$ 走到 $(n,n)$,第一步必须往右,往右走一步乘 $a$,往下走一步乘 $b$,求所有路径的权值和。这个东西显然等于可以发现,当 $i+j\leq n-2$ 时,贡献就是 $c(a+b)^{i+j}$;当 $i+j>n...
LuoguGym分析竟然一遍 A 了,写篇题解纪念一下。如果一个灯管一直都是 X 或者一直都是 .,那它就有可能恒亮或恒灭。枚举起始时间,那么如果一个不可能恒亮或恒灭的灯管没有正常发光,那么这个起始时间就不合法。如果对于某个起始时间,某个灯管都正常发光,那它就有可能是正常工作的。如果一个灯管的可能性超过 $2$ 种,那么就输出 ?,否则输出对应的东西即可。难点主要在于码,但是想清楚了也不是很...
LuoguGym分析析合树模板题。如果两个点在析合树上的 LCA 是析点,那么答案就是这个析点对应的段;否则还要找到两个点所在的两棵子树,LCA 的儿子序列中这两个子树间的子序列才是答案。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // =...
Luogu分析根据题目里提供的证明,不难得到答案的下界是 $n-1$。下面我们来考虑如何构造出这个下界。考虑拿出 $n-1$ 组匹配,满足两两无交,这样子每组匹配中的边只会有一条被经过,组内直接赋连续权值即可。这 $n-1$ 组匹配可以把下面这个图旋转 $n-1$ 次得到代码// ==================================== // author: M_sea ...
本来不想更了的,但是被催更了,所以还是来更一下。
Luogu分析没想到差分 /ll根据要求的东西,不难想到线性基。现在既然有一个区间询问,而且线性基还很好合并,那么可以想到在外面套一层线段树。问题是区间修改时一个线性基如何整体异或一个值。考虑差分,变成单点修改,直接把叶节点线性基清空然后 pushup 上去即可。可以证明 $a_{l..r}$ 的线性基和 $a_l\cup(a_i-a_{i-1})_{l+1..r}$ 的线性基是相同的,所以...
我做题速度什么时候能有卡老师一半快啊
做不动了,咕了
Luogu分析根据二项式定理有所以我们只要把边权设成 $e^{a_ix}$,然后直接矩阵树定理即可。因为数据范围很小,所以多项式乘法和求逆可以直接暴力,NTT 甚至会慢。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==========...