LB_tq

题解

/ 注册

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

【每日一题】Shortest Path

Solution 由题意可知是一个树形结构。若要使两两之间边权最小，尽量不能选重边，也就是说尽可能在节点所在子树里寻找答案。显然与叶子节点相连的边必须选。然后考虑其他边：若一棵子树中的节点有偶数个，那么两两配对即可，不用添加新的边权。若一棵子树有奇数个节点，那么根节点要和其他子树连边，所以还...

2020-04-02

4 1019

【每日一题】月月查华华的手机

Solution 直观的想法是直接扫描两个字符串进行比较。这样的复杂度是的。然后可以发现子序列中字母的相对位置是不变的，所以可以维护一个数组，表示第个位置之后最近的字母所在的位置。这个数组可以处理：，然后在倒序循环一遍即可预处理出数组。对于每个要判断的字符串，建...

2020-04-01

4 1046

【每日一题】Rinne Loves Edges

Solution 由题意可知给定的图是一棵树。树上的最优化问题可以想到树形。按照常用的状态设计方式，可以设为根节点为的最少代价。使以为根的子树的叶子节点无法到达的方式有两种：割断与直接相连的边割断与的子节点直接相连的边两种方式取最小值即可。故状态转移方程为其...

2020-03-31

1 902

【比赛】牛客OI周赛14-提高组

T1 Solution 的部分可以用的解决。到一个点的所有方案数等于。先将障碍点按坐标排序，记为到第个点的合法方案数，则当且仅当由的定义可知不会重复排除非法情况。所以可以线性求逆元，再进行的。 Code #include <iostream>...

2020-03-30

1 553

【每日一题】城市网络

Solution 题目中有两个关键信息： 1号节点是根节点。节点在节点到根节点的最短路径上。由于是树形结构，所以从到一定是不断地将，也就是是的祖先。于是可以先进行一次预处理出每个节点的父节点，之后回答询问。只有当某个节点的珠宝比手中的都值钱是才会采购，所以一...

2020-03-30

3 1367

【每日一题】滑动窗口

Solution 单调队列模板题。具体思想：从前到后遍历序列，维护一个队列，使队列的队首一直是窗口中的最值。以最小值为例，若序列当前位置的数比队列中的队尾小，那就意味着当前位置的数贡献更大，即更有可能成为之后的最小值，于是就可以弹出队尾元素将新元素插入。注意及时从队首排除不符合范围的元素。由于每...

2020-03-29

1 603

【比赛】牛客练习赛60

大吉大利 Solution 位运算常用的优化技巧就是按位计算。用表示第位为的数的个数。由与运算的性质可以得到，两个数二进制第位都为时，会使答案加。因此便可以边读入边处理，最后将答案乘并加上数本身即可。时间复杂度： Code #include <iostream&...

2020-03-29

3 719

【每日一题】数学考试

Solution 由题意可知需要求两段不连续区间，使和最大。区间求和问题可以想到一个常用算法：前缀和。区间的和可以用方便地求出。预处理序列的前缀和后，如何得知某个位置之前和之后的和最大的区间呢？我们可以使用线性求得。设表示位置之前的最大区间和，表示位置之后的最大区间和。...

2020-03-26

15 1872

【每日一题】合并回文子串

Solution 看到数据范围可以想到区间。由题意可知字串是连续的。设为在中选取到，在中选取到是否能构成回文串。转移方程如下：（，) （，) （，，) （，，）利用或运算可以方便的转移。当两个字符串最多选出一个字符时，此时显然有，作为边界条件。时间复...

2020-03-25

16 2563

【每日一题】tokitsukaze and Soldier

Solution 由题目可知要求一个集合，使集合大小满足元素的限制且元素之和最大。一个显然的贪心思想：在满足条件的前提下使得和最大。要求和最大，就可以使用堆来维护。因此，可以先按从大到小排序，维护一个小根堆，每插入新元素之前，将堆的大小调整至符合条件。再实时维护一个集合内元素的最大值即可。 ...

2020-03-24

4 1106