P4597 序列sequence 题解
题意 题目链接。 给定一个序列,每次操作可以把某个数 $+1$ 或 $-1$。要求把序列变成非降数列。而且要求修改后的数列只能出现修改前的数。 解析 给出一种该题题解区中都没有提到的做法:整体二分。 对于整个区间按照值域进行二分,初始值域为负极大值到正极大值,每次二分都找出 $mid$ 值的分界线,然后对于左右两个区间依次二分。由于分界线左侧的那个…
AT2335 [ARC069C] Frequency 题解
题目链接。 题意不多赘述。 解析 由于每次会将石子最多的那堆的序号加入 $S$ 中,我们考虑将原始的石子堆从大到小排序。首先我们发现如果有一堆比其他都要高,我们可以将他取到与第二高的一样高,这样的话结果只可能会更优(因为相同时优先取小的)。 依照这个思路,我们考虑按照高度一层一层取下来,这样答案会越来越优(若存在多个高度相同的,你只需要认为在取的过…
CF746F Music in Car 题解
题意 题目链接。 给定一个序列,包含 $n$ 个有重量和价值的物品。需要找出一个连续区间,可以选择其中的至多 $w$ 个物品令其重量减半(向上取整)而价值不变,然后该区间重量和须不大于 $k$。求满足这样条件的总价值最大的区间。 解析 求区间最大价值容易想到双指针。考虑如何维护重量减半(以下简称打折)的 $w$ 个物品。 由于元素会有重复,考虑用两…
提线木偶
文/流凡 你有一群提线木偶, 整整齐齐的都是一种颜色, 你将他们看作无敌的大军, 成为你永世的骄傲。 有的木偶光泽褪了, 或是沾上了其他色彩, 你就将他们扔进箱子里, 暗无天日。 有的木偶变畸形了, 歪歪斜斜得个性十足, 你就将他们一一拆卸, 四分五裂。 有的木偶绳线断了, 自主地奋起舞蹈, 你就将他们扔进火里, 魂飞魄散。 于是, 你再去看看你的…
CF1536D Omkar and Medians 题解
题意 题目链接。 记 $b_i$ 为 $a_1 \sim a_{2i-1}$ 的中位数,给定序列 $b$,询问是否存在合法的序列 $a$。 解析 考虑 $b_i$ 和 $b_{i-1}$ 的关系。我们先假设 $b_1 \sim b_{i-1}$ 均合法。 若 $b_{i-1}=b_i$,则新增的两个数只需一大一小地取即可,$b_i$ 也一定合法。 …
AT2063 [AGC005E] Sugigma: The Showdown 题解
题意 题目链接。 有一棵红树和一棵蓝树,结点相同而边不同。双方各在某一点,只能在自己颜色的树上移动,红方先手。红方需要最大化游戏轮数,蓝方则需要最小化游戏轮数。求最终游戏轮数。 解析 首先发现,如果存在一条连接 $u,v$ 的红边,且 $u,v$ 两点在蓝树上的距离不小于 $3$,则若红方到达其中某一点且蓝方下一步抓不住他,游戏就会进行无限轮。画图…
[ABC202E] Count Descendants 题解
题意 题目链接 给定一棵树,每次询问给出一个点 $u$ 和深度 $d$,询问深度为 $d$ 的点中有多少个点祖先包含 $u$。 解析 考虑用一个时间戳,记录每一个点的入栈时间 $in_i$ 和出栈时间 $out_u$,发现每一个符合条件的点 $x$ 满足 $in_u \le in_x < out_u$。由此,用 vector 维护每一层所有点…
你用爱,给了我拥抱世界的力量|母亲节的一篇短文
这篇文章实际上写成于母亲节,一直忘了发出,今日方想起。 我觉得,我母亲——或者我更习惯于称之为妈妈,约莫也不会看到这篇文章吧,但是无所谓了,这一切,仅仅是我于母亲节的独白而已。 我的妈妈,真真切切是我最想要感谢的人,感谢她的抚养,感谢她的温柔,更重要的是感谢她的支持。 一直以来,她都给了我充分的选择机会,因而我才得以自己决定自己的发展方向,得以去寻…
CF1019C Sergey’s problem 题解
题意 题目链接。 给定一张有向无自环图,求一个点集满足: 点集内任意两个不同点距离不小于 $2$(即无边相连)。 对于任意一个不在点集内的点,存在一个点集内的点到它的距离不大于 $2$(即两步能达)。 解析 算法实现与 @Mickey_snow、@_Anchor 等题解类似,本篇题解主要重申一种可能更清晰的证明以及错解的 Hack。 简单阐述解法:…
「MCOI-05」追杀 题解
题意 题目链接。 题意有点复杂,大意是有一个猎杀游戏,有 $m$ 名玩家,每名玩家初始有 $3$ 点生命。有 $n$ 个时刻,每个时刻会发生形如 $u_i$ 杀 $v_i$ 的事件,若 $u_i$ 和 $v_i$ 都存活,则 $v_i$ 生命值减 $1$,若生命值为 $0$ 则死亡。现在发生了一次特殊事件:穿越者穿越到某一次追杀后(可以是第 $0$…