Author: void_struct

本人为一名KFCer 专注于肯德基三人篮球竞赛 喜欢唱、跳、rap、KFC,不喜欢篮球。 是HOMO,今年24岁,事学生。

31 篇文章

关于斜率优化
前言 其实这篇文章早就想写了,只不过一直咕咕咕着,咕了一年(大雾。 现在对于斜率优化已经产生了十分深刻的李姐了,所以可以放心大胆地胡扯了。 正文 关于一个$DP$方程,如果它的形式如$F[i]=max(or min)(F[j]+(一堆只关于j的式子)+(一堆只关于i的式子))$那么这样我们是可以对其进行单调队列优化的,把复杂度降低一维。但是如果形式…
容斥原理与广义容斥原理
前言 这是我在中考结束后写的第一篇博客,关于中考他死了。 接下来还有FFT等一众博客要更新,只能慢慢来了。 部分算法为中考前集训学的,现在需要回忆下才能口胡出来,所以先更这篇昨天学习的容斥及广义容斥的姿势。 本文有部分参考于Parsnip的博文可以去他那里补充看看。 正文 容斥原理 这个大家或多或少都接触过,就是给出一些不同性质包含不同数量元素的集…
BZOJ1016 [JSOI2008]最小生成树计数
题面 现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树,而希望知道这个图中有多少个不同的最小生成树。(如果两颗最小生成树中至少有一条边不同,则这两个最小生成树就是不同的)。由于不同的最小生成树可能很多,所以你只需要输出方案数对$31011$的模就可以了。(具有相同权值的边不会超过10条) 思路 这题有点ex啊,不知道矩阵树定理或者最小…
BZOJ2085 [Poi2010]Hamsters
题面 给出 $n$个互不包含的字符串,要求你求出一个最短的字符串 $S$,使得这 $n$ 个字符串在 $S$ 中总共至少出现$m$次,问 $S$ 最短是多少。 思路 把题目转化一下,求出$F[i][j]$表示把$S[j]$接在$S[i]$后面的代价,这个用$substr…
BZOJ1706 [usaco2007 Nov]relays 奶牛接力跑
题面 FJ的N(2 <= N <= 1,000,000)头奶牛选择了接力跑作为她们的日常锻炼项目。至于进行接力跑的地点 自然是在牧场中现有的T(2 <= T <= 100)条跑道上。 农场上的跑道有一些交汇点,每条跑道都连结了两个不同的交汇点 I1_i和I2_i(1 <= I1_i <= 1,000; 1 <…
BZOJ4128 Matrix矩阵BSGS模板题
题面 给定矩阵A,B和模数p,求最小的x满足 A^x = B (mod p) 思路 一眼看去就是BSGS,很显然这个结论在矩阵中也同样适用,那么把乘法替换成矩阵乘法然后矩阵HASH判重即可。(就这么简单) 代码 #include<bits/stdc++.h> #define LL long long #define Mod 998244353…
动态点分治(点分树)学习笔记
前言 别问我为啥不和点分治写一块。。。内容过多了。。。所以分开写 正文 我们知道,在处理树上问题的时候,点分治是一个很好用的算法,但是倘若是多次询问或者是带修改操作,那么就需要重新点分治,这样的效率极其低下,那么我们就考虑重构这整棵树。把每个点与他的子树中的重心(或者假重心,可以看看我点分治那篇的最后update有提到)相连,也就是建father。…
BZOJ2741【FOTILE模拟赛】L
题面 $FOTILE$得到了一个长为$N$的序列$A$,为了拯救地球,他希望知道某些区间内的最大的连续$XOR$和。即对于一个询问,你需要求出$max(Ai xor Ai+1 xor Ai+2 ... xor Aj)$,其中$l<=i<=j<=r$。为了体现在线操作,对于一个询问$(x,y)$: $l = min ( ((x+la…
NOI Online #3提高组题解
T1水壶 和名字一样水,双指针移动或者前缀和爆草就行。 #include<bits/stdc++.h> #define LL long long using namespace std; inline void read(LL &x) { LL f=1;x=0;char ch=getchar(); while (!isdigit(ch…
BZOJ3166 [HEOI2013]ALO
题面 Welcome to ALO ( Arithmetic and Logistic Online)。这是一个 VR MMORPG, 如名字所见,到处充满了数学的谜题 现在你拥有 n 颗宝石,每颗宝石有一个能量密度,记为 ai,这些宝石的能量 密度两两不同。现在你可以选取连续的一些宝石(必须多于一个)进行融合,设 为 ai, ai+1, …, a…