mcfx's blog

题解、Writeup、游记和碎碎念

包含标签 BZOJ 的文章

BZOJ 4926: 皮皮妖的递推

YOUSIKI 学习了递推,于是他请皮皮妖给他出道题,皮皮妖说:
f(1)=1,f(i)=i-f(i-1),求 f(n)
YOUSIKI 看了一眼把它秒切了,于是他要求皮皮妖加大难度,皮皮妖想了想,说:
f(1)=1,f(i)=i-f(f(i-1)),求 f(n)
YOUSIKI 看了两眼把它秒切了,于是他要求皮皮妖加大难度,皮皮妖想了想,说:
f(1)=1,f(i)=i-f(f(f(i-1))),求 f(n)
YOUSIKI 看了三眼把它秒切了,于是他要求皮皮妖加大难度,皮皮妖想了想,说:
...
...
...
YOUSIKI 看了 m 眼,但是没有能秒切,于是他找到你,请你帮他解决这个问题。

BZOJ 2694 & 4659 Lcm

fa(1).jpg

BZOJ 3926: [Zjoi2015]诸神眷顾的幻想乡

幽香是全幻想乡里最受人欢迎的萌妹子,这天,是幽香的 2600 岁生日,无数幽香的粉丝到了幽香家门前的太阳花田上来为幽香庆祝生日。
粉丝们非常热情,自发组织表演了一系列节目给幽香看。幽香当然也非常高兴啦。
这时幽香发现了一件非常有趣的事情,太阳花田有 n 块空地。在过去,幽香为了方便,在这 n 块空地之间修建了 n-1 条边将它们连通起来。也就是说,这 n 块空地形成了一个树的结构。
有 n 个粉丝们来到了太阳花田上。为了表达对幽香生日的祝贺,他们选择了 c 中颜色的衣服,每种颜色恰好可以用一个 0 到 c-1 之间的整数来表示。并且每个人都站在一个空地上,每个空地上也只有一个人。这样整个太阳花田就花花绿绿了。幽香看到了,感觉也非常开心。
粉丝们策划的一个节目是这样的,选中两个粉丝 A 和 B(A 和 B 可以相同),然后 A 所在的空地到 B 所在的空地的路径上的粉丝依次跳起来(包括端点),幽香就能看到一个长度为 A 到 B 之间路径上的所有粉丝的数目(包括 A 和 B)的颜色序列。一开始大家打算让人一两个粉丝(注意:A,B 和 B,A 是不同的,他们形成的序列刚好相反,比如红绿蓝和蓝绿红)都来一次,但是有人指出这样可能会出现一些一模一样的颜色序列,会导致审美疲劳。
于是他们想要问题,在这个树上,一共有多少可能的不同的颜色序列(子串)幽香可以看到呢?
太阳花田的结构比较特殊,只与一个空地相邻的空地数量不超过 20 个。

BZOJ 3160: 万径人踪灭

https://darkbzoj.tk/problem/3160

BZOJ 2989: 数列 & 4170: 极光

给定一个长度为 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)<=k。因为可持久化数据结构的流行,询问不仅要考虑当前数列,还要考虑任意历史版本,即统计任意位置上出现过的任意数值与当前的 a[x]的 graze 值<=k 的对数。(某位置多次修改为同样的数值,按多次统计)

BZOJ 4750: 密码安全

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

BZOJ 4398: 福慧双修

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

BZOJ 2958&3269: 序列染色

给出一个长度为 N 由 B、W、X 三种字符组成的字符串 S,你需要把每一个 X 染成 B 或 W 中的一个。
对于给出的 K,问有多少种染色方式使得存在整数 a,b,c,d 使得:
1<=a<=b<c<=d<=N
Sa,Sa+1,...,Sb 均为 B
Sc,Sc+1,...,Sd 均为 W
其中 b=a+K-1,d=c+K-1
由于方法可能很多,因此只需要输出最后的答案对 109+7 取模的结果。

BZOJ 2432: [Noi2011]兔农

农夫栋栋近年收入不景气,正在他发愁如何能多赚点钱时,他听到隔壁的小朋友在讨论兔子繁殖的问题。
问题是这样的:第一个月初有一对刚出生的小兔子,经过两个月长大后,这对兔子从第三个月开始,每个月初生一对小兔子。新出生的小兔子生长两个月后又能每个月生出一对小兔子。问第 n 个月有多少只兔子?
聪明的你可能已经发现,第 n 个月的兔子数正好是第 n 个 Fibonacci(斐波那契)数。栋栋不懂什么是 Fibonacci 数,但他也发现了规律:第 i+2 个月的兔子数等于第 i 个月的兔子数加上第 i+1 个月的兔子数。前几个月的兔子数依次为:
1 1 2 3 5 8 13 21 34 …
栋栋发现越到后面兔子数增长的越快,期待养兔子一定能赚大钱,于是栋栋在第一个月初买了一对小兔子开始饲养。
每天,栋栋都要给兔子们喂食,兔子们吃食时非常特别,总是每 k 对兔子围成一圈,最后剩下的不足 k 对的围成一圈,由于兔子特别害怕孤独,从第三个月开始,如果吃食时围成某一个圈的只有一对兔子,这对兔子就会很快死掉。
我们假设死去的总是刚出生的兔子,那么每个月的兔子数仍然是可以计算的。例如,当 k=7 时,前几个月的兔子数依次为: 1 1 2 3 5 7 12 19 31 49 80 …
给定 n,你能帮助栋栋计算第 n 个月他有多少对兔子么?由于答案可能非常大,你只需要告诉栋栋第 n 个月的兔子对数除 p 的余数即可。

BZOJ 4539: [Hnoi2016]树

小 A 想做一棵很大的树,但是他手上的材料有限,只好用点小技巧了。开始,小 A 只有一棵结点数为 N 的树,结点的编号为 1,2,…,N,其中结点 1 为根;我们称这颗树为模板树。小 A 决定通过这棵模板树来构建一颗大树。构建过程如下:(1)将模板树复制为初始的大树。(2)以下(2.1)(2.2)(2.3)步循环执行 M 次(2.1)选择两个数字 a,b,其中 1<=a<=N,1<=b<=当前大树的结点数。(2.2)将模板树中以结点 a 为根的子树复制一遍,挂到大树中结点 b 的下方(也就是说,模板树中的结点 a 为根的子树复制到大树中后,将成为大树中结点 b 的子树)。(2.3)将新加入大树的结点按照在模板树中编号的顺序重新编号。例如,假设在进行 2.2 步之前大树有 L 个结点,模板树中以 a 为根的子树共有 C 个结点,那么新加入模板树的 C 个结点在大树中的编号将是 L+1,L+2,…,L+C;大树中这 C 个结点编号的大小顺序和模板树中对应的 C 个结点的大小顺序是一致的。下面给出一个实例。假设模板树如下图:
11(4).png
根据第(1)步,初始的大树与模板树是相同的。在(2.1)步,假设选择了 a=4,b=3。运行(2.2)和(2.3)后,得到新的大树如下图所示
22(2).png
现在他想问你,树中一些结点对的距离是多少。

1
2
3
4

Older →