mcfx's blog

题解、Writeup、游记和碎碎念

2016 年 12 月

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
现在他想问你,树中一些结点对的距离是多少。

BZOJ 3552: 最右非零的数

给出正整数 N(可能有前导 0),请求出 N!最右非零的数位的值。

BZOJ 1176&2683&4066

单点加,矩阵查询。

BZOJ 3697: 采药人的路径

采药人的药田是一个树状结构,每条路径上都种植着同种药材。
采药人以自己对药材独到的见解,对每种药材进行了分类。大致分为两类,一种是阴性的,一种是阳性的。
采药人每天都要进行采药活动。他选择的路径是很有讲究的,他认为阴阳平衡是很重要的,所以他走的一定是两种药材数目相等的路径。采药工作是很辛苦的,所以他希望他选出的路径中有一个可以作为休息站的节点(不包括起点和终点),满足起点到休息站和休息站到终点的路径也是阴阳平衡的。他想知道他一共可以选择多少种不同的路径。

BZOJ 4700: 适者

敌方有 n 台人形兵器,每台的攻击力为 Ai,护甲值为 Di。我方只有一台人形兵器,攻击力为 ATK。战斗看作回合制, 每回合进程如下:
·1 我方选择对方某台人形兵器并攻击,令其护甲值减少 ATK,若护甲值<0 则被破坏。
·2 敌方每台未被破坏的人形兵器攻击我方基地造成 Ai 点损失。
但是,在第一回合开始之前,某两台敌方的人形兵器被干掉了(秒杀)。问最好情况下,我方基地会受到多少点损 失。