Zechariah

题解

/ 注册

全部文章 / 题解（共19篇）

题解 | J. Serval and Essay

J. Serval and Essay 题解考虑通过“x确定y”这种关系将x和y进行合并，因为如果确定了x就能确定y，那么贪心地想肯定是确定x能得到更大的答案，那么就没有必要再去考虑从y出发了，所有从y连出去的边改成从x连出去。当“x to y”这条边被合并之后，原本由y指向的点就变成了由x指向...

启发式合并

2022-07-19

20 1115

题解 | I. Chiitoitsu

I. Chiitoitsu 题意分析字母和数字是什么不重要，重要的是字母或数字不同就能区别不同的牌，那么实际上就是34种不同的牌，每种牌都有4张。起手牌不会有超过两张相同的牌，那么在这种情况下，我们将手上的牌分为pair和single两个种类，当抽到一张pair中的牌时，由于这个pair已经存在...

动态规划数学期望

2022-07-18

6 468

题解 | 排名

H. 排名看起来好复杂好复杂，其实很暴力。考虑这样一个tot序列，tot[x]表示cnt[y]=x的y的个数，很容易发现我们只要遍历一遍tot序列中不为0的部分就可以很容易求出答案。而tot序列中不为0的部分不会超过O(n)O(\sqrt n)O(n)，所以只要维护一个链表，每个节点表示一个...

2021-11-27

10 418

题解 | #小䓤的一些数字#

k=1的时候明显答案是(l+r)(r−l+1)2\dfrac{(l+r)(r-l+1)}{2}2(l+r)(r−l+1) k>=3的时候可以枚举值域，算出对应的长度然后把贡献加起来 k=2的时候推式子，考虑计算[1,l−1],[1,r][1,l-1],[1,r][1,l−1],[1,r]的答...

2021-11-19

11 363

题解 | E. Eert Esiwtib

E. Eert Esiwtib Solution 由于值域很小，考虑对每个更新整棵树计算对应的询问。设表示以为根的子树得到的三种答案分别是什么，容易发现i连的若干个子树的对答案的贡献互不影响，那么来看看如何转移：如果当前点连到子节点的边是对于答案，有，所以可以直接对于答案，有，所以...

2021-08-24

3 523

题解 | G. Greater Integer, Better LCM

G. Greater Integer, Better LCM 前言题解有点看不懂，自己想了个比较直接的做法。 Solution 考虑和的因数是由哪些组成的，于是发现这两个数选到的最终要包含所有，所以直接考虑枚举其中一个数，那么另一个数能取的范围就是“至少包含当前数的补集的所有数”，换句话说，我们选...

2021-08-23

2 498

题解 | J. Defend Your Country

J. Defend Your Country 前言思维题，主要是要猜结论证结论。 Solution 对于n是偶数的情况，显然不需要删边。对于n是奇数的情况，删去非割点显然只用删一个，主要是考虑删掉割点的情况。假设删除了偶数个割点使得答案最优，由于剩下的联通块必然都是偶数个点（否则继续删奇数联通...

2021-08-03

6 815

题解 | D. Rebuild Tree

D. Rebuild Tree 前置芝士：prufer序列 prufer序列是将n个点的标号的无根树对应到长度为n-2，每个位置值域为[1,n]的序列。 prufer序列的构造方法是每次将树中编号最小的树叶删除，将树叶连接的点加入prufer序列。树上点x的度数=prufer序列中x出现的...

2021-07-27

8 560

题解 | G.League of Legends

Solution 这个题的转换还是有难度的。我们观察一下，对于可以包含其他区间的大区间，要使得答案最优无非就是两种分组方式：单独一组或者与被包含的区间一组。因为根据题意，如果有多个区间，添加区间实际上是添加限制，会使得答案变小，于是能包含其他区间的这些区间实际上是可以独立出来的，我们把这部分区间去...

2021-07-21

16 1167