mcfx's blog

题解、Writeup、游记和碎碎念

BZOJ 3552: 最右非零的数

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

BZOJ 1176&2683&4066

单点加,矩阵查询。

BZOJ 3697: 采药人的路径

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

BZOJ 4700: 适者

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

BZOJ 3113: Toy

外面有一圈 N 个结点,中心有一个结点与 N 个结点都相连,总共就是 2N2\cdot N 条边,删除 N 条边,使 N+1 个点连通,旋转相同视为等价,问有多少种情况。
1.jpg

BZOJ 4722: 由乃

给一个长为 n 的序列 a,每个数在 0 到 v - 1 之间,有 m 次操作。
操作 1:每次询问一个区间中是否可以选出两个下标的集合 X,Y,满足:
1.X 和 Y 没有交集 2.设集合 X 中有一个元素是 i,则其对集合 X 的贡献是 a[i] + 1,要求集合 X 的元素的总贡献和集合 Y 的元素的总贡献
相等如果可以选出这两个集合,输出 Yuno 否则输出 Yuki
操作 2:修改一个区间 l,r 之间的数,使得所有 l <= i <= r,a[i] = a[i] * a[i] * a[i] % v ,即区间立方

BZOJ 3196: Tyvj 1730 二逼平衡树

您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作: 1.查询 k 在区间内的排名 2.查询区间内排名为 k 的值 3.修改某一位值上的数值 4.查询 k 在区间内的前驱(前驱定义为小于 x,且最大的数) 5.查询 k 在区间内的后继(后继定义为大于 x,且最小的数)

BZOJ 3343: 教主的魔法

分块

BZOJ 3163: [Heoi2013]Eden的新背包问题

“寄没有地址的信,这样的情绪有种距离,你放着谁的歌曲,是怎样的心心静,能不能说给我听。” 失忆的 Eden 总想努力地回忆起过去,然而总是只能清晰地记得那种思念的感觉,却不能回忆起她的音容笑貌。 记忆中,她总是喜欢给 Eden 出谜题:在 valentine’s day 的夜晚,两人在闹市中闲逛时,望着礼品店里精巧玲珑的各式玩偶,她突发奇想,问了 Eden 这样的一个问题:有 n 个玩偶,每个玩偶有对应的价值、价钱,每个玩偶都可以被买有限次,在携带的价钱 m 固定的情况下,如何选择买哪些玩偶以及每个玩偶买多少个,才能使得选择的玩偶总价钱不超过 m,且价值和最大。众所周知的,这是一个很经典的多重背包问题,Eden 很快解决了,不过她似乎因为自己的问题被飞快解决感到了一丝不高兴,于是她希望把问题加难:多次 询问,每次询问都将给出新的总价钱,并且会去掉某个玩偶(即这个玩偶不能被选择),再问此时的多重背包的答案(即前一段所叙述的问题)。 这下 Eden 犯难了,不过 Eden 不希望自己被难住,你能帮帮他么?

BZOJ 4668: 冷战 LCT

1946 年 3 月 5 日,英国前首相温斯顿·丘吉尔在美国富尔顿发表“铁幕演说”,正式拉开了冷战序幕。
美国和苏联同为世界上的“超级大国”,为了争夺世界霸权,两国及其盟国展开了数十年的斗争。在这段时期,虽然分歧和冲突严重,但双方都尽力避免世界范围的大规模战争(第三次世界大战)爆发,其对抗通常通过局部代理战争、科技和军备竞赛、太空竞争、外交竞争等“冷”方式进行,即“相互遏制,不动武力”,因此称之为“冷战”。
Reddington 是美国的海军上将。由于战争局势十分紧张,因此他需要时刻关注着苏联的各个活动,避免使自己的国家陷入困境。苏联在全球拥有 N 个军工厂,但由于规划不当,一开始这些军工厂之间是不存在铁路的,为了使武器制造更快,苏联决定修建若干条道路使得某些军工厂联通。
Reddington 得到了苏联的修建日程表,并且他需要时刻关注着某两个军工厂是否联通,以及最早在修建哪条道路时会联通。具体而言,现在总共有 M 个操作,操作分为两类:
• 0 u v,这次操作苏联会修建一条连接 u 号军工厂及 v 号军工厂的铁路,注意铁路都是双向的;
• 1 u v, Reddington 需要知道 u 号军工厂及 v 号军工厂最早在加入第几条条铁路后会联通,假如到这次操作都没有联通,则输出 0;
作为美国最强科学家, Reddington 需要你帮忙设计一个程序,能满足他的要求。

1
2
3
4
5
6
7
8

Older →