对于各种并查集写法速度的研究

2018.3.3:更新了测试代码,加入了更多写法,修复了一些致命错误 测试机CPU为Intel® Celeron® Processor G3900,内存为8GB DDR4,系统为Debian 9。 编译命令为g++ test.cpp -o test -O3。 先放测试代码: ```c++ #include #include #include #include #define N 1024 #define T 100000 int fa[N+233],st[N+233],sz[N+233]; int find1(int x) { return x==fa[x]...

BZOJ 3160: 万径人踪灭

###Description 略。见[BZOJ3160][1] ###Solution 对于“不能是连续的一段”,可以先计算所有答案,然后减去连续一段的,即回文串,这个用回文自动机或者manacher可以得出 考虑以每个位置为中心的对称元素对个数f[i],那么i位置对答案的贡献是$$2^{f[i]}-1$$ 如果把a视为1,b视为-1,然后把原串长度\*4,卷积,那么以i为中心的元素对如果相同,则贡献1,否则贡献-1 ###Code ```c++ #include typedef double lf; #define fo0(i,n) for(int i=...

BZOJ 2989: 数列 & 4170: 极光

###Description 给定一个长度为n的正整数数列a[i]。 定义2个位置的graze值为两者位置差与数值差的和,即graze(x,y)=|x-y|+|a[x]-a[y]|。 2种操作(k都是正整数): 1.Modify x k:将第x个数的值修改为k。 2.Query x k:询问有几个i满足graze(x,i)

BZOJ 4750: 密码安全

###Description 有些人在社交网络中使用过许多的密码,我们通过将各种形式的信息转化为 01 信号,再转化为整数,可以将这个人在一段时间内使用过的密码视为一个长度为 n 的非负整数序列 A_1,A_2,...,A_n 。一个人相邻几次在社交网络中使用的密码很有可能是类似的,这使得密码并不是足够安全。为了检验某些人在某些时间段内是否可能受到不安全的影响,我们需要计算上述序列的复杂程度。 ![aa.jpg][1] 的值,这将作为我们评估密码复杂程度的一个部分。由于答案可能很大,你只需要给出答案对10^9+61 取模的值即可。 ###Input 第一行包含一个正整数 T...

BZOJ 2958&3269: 序列染色

###Description 给出一个长度为N由B、W、X三种字符组成的字符串S,你需要把每一个X染成B或W中的一个。 对于给出的K,问有多少种染色方式使得存在整数a,b,c,d使得: 1

BZOJ 4398: 福慧双修

###Description 菩萨为行,福慧双修,智人得果,不忘其本。 ——唐朠立《大慈恩寺三藏法师传》 有才而知进退,福慧双修,这才难得。 ——乌雅氏 如何福慧双修?被太后教导的甄嬛徘徊在御花园当中。突然,她发现御花园中的花朵全都是红色和蓝色的。她冥冥之中得到了响应:这就是指导她如何福慧双修的! 现在御花园可以看作是有N块区域,M条小路,两块区域之间可通过小路连接起来。现在甄嬛站在1号区域,而她需要在御花园中绕一绕,且至少经过1个非1号区 域的区域。但是恰好1号区域离碎玉轩最近,因此她最后还是要回到1号区域。由于太后教导她要福慧双修,因此,甄嬛不能走过任何一条她曾经走过的路。...

BZOJ 2432: [Noi2011]兔农

###Description 农夫栋栋近年收入不景气,正在他发愁如何能多赚点钱时,他听到隔壁的小朋友在讨论兔子繁殖的问题。 问题是这样的:第一个月初有一对刚出生的小兔子,经过两个月长大后,这对兔子从第三个月开始,每个月初生一对小兔子。新出生的小兔子生长两个月后又能每个月生出一对小兔子。问第n个月有多少只兔子? 聪明的你可能已经发现,第n个月的兔子数正好是第n个Fibonacci(斐波那契)数。栋栋不懂什么是Fibonacci数,但他也发现了规律:第i+2个月的兔子数等于第i个月的兔子数加上第i+1个月的兔子数。前几个月的兔子数依次为: 1 1 2 3 5 8 13 21 34 …...

BZOJ 3552: 最右非零的数

###Description 给出正整数N(可能有前导0),请求出N!最右非零的数位的值。 ###Input 第一行一个数T表示数据组数 下接T行每行一个数N表示一组数据 ###Output 对于每组数据,输出一行一个数表示这组数据的答案 ###Sample Input 2 5 4 ###Sample Output 2 4 ###Solution 随便lucas一下就好了,然而懒得写高精,就用了python,于是实力rank last ###Code ```python T=int(raw_input()) for I in ...

BZOJ 4539: [Hnoi2016]树

###Description 小A想做一棵很大的树,但是他手上的材料有限,只好用点小技巧了。开始,小A只有一棵结点数为N的树,结点的编号为1,2,…,N,其中结点1为根;我们称这颗树为模板树。小A决定通过这棵模板树来构建一颗大树。构建过程如下:(1)将模板树复制为初始的大树。(2)以下(2.1)(2.2)(2.3)步循环执行M次(2.1)选择两个数字a,b,其中1=k)return kth(s[a].lc,s[b].lc,l,f,k); return kth(s[a].rc,s[b].rc,f+1,r,k-t); } int root[N+1]; } int...

BZOJ 1176&2683&4066

[传送门][1] [传送门][2] [传送门][3] 题目大意:单点加,矩阵查询 直接上kdtree就好了,定期暴力重构 1176题代码: ```c++ #include typedef unsigned char uchar; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ldb; #define xx first #define yy second ...