三金老师

分类

题解(25)

/ 注册

全部文章（共25篇）

【每日一题】Shortest Path (dfs+思维)

Solutionn个点n-1条双向边明显是树，而且保证必定是偶数个节点，那么就肯定是两两配对。就一个节点来说，跟兄弟节点配对，或者跟父亲节点配对肯定是最优的。所以只需要判断节点所在子树里面的节点数是否为偶数，如果是偶数说明不用和此节点的父亲节点配对，若为奇数则需要加上这条边，那么可设 dp[i] 为...

每日一题树形DP

2020-04-02

1 754

【每日一题】月月查华华的手机 (序列自动机)

Solution判断子序列的话让我想起了上次cf的一道C题，哪一场已经忘了，但是做法的话不外乎两种：1.二分查找2.序列自动机因为上次是二分过的，这次就写一下序列自动机。nexts[i][j]表示的是i位置之后j字符在原串中的索引，那么预处理nexts数组之后，直接对输入的每个串遍历判断 i 位置之...

每日一题序列自动机

2020-04-01

0 551

【每日一题】Rinne Loves Edges (树形DP)

Solution简单来说题目就是求在有根树中，每个叶子节点到根节点的路径上的边权最小值之和，很典型的树形DP。s为根，考虑 dp[s] 为答案，即每个叶子节点到s的路径上的边权最小值之和，那么 dp[s]= Σ min（dp[s.son] , s->s.son的边权) 。最后注意一下叶子节点是...

每日一题树形DP

2020-03-31

0 592

【每日一题】城市网络 (dfs)

Solution 求树上的简单路径很明显是LCA的题目，那么：直接预处理父节点数组和深度数组直接暴力把 u 和 v 往上提？那就错了。其实题目里有保证 v 在 u 前往首都的最短路径上，所以只需要直接把 u 向上遍历就可以了。而珠宝购入的前提是当前城市的珠宝严格大于手中的所有珠宝，所以只需要再用两...

2020-03-30

0 1016

【每日一题】滑动窗口 (单调队列)

3月30日每日一题 : https://ac.nowcoder.com/discuss/394776 Solution 滑动窗口最值问题，就是单调队列的模板题。先讲一下个人对单调队列的理解：举个维护区间最小值的例子，主要就是用 head 和 tail 双指针来对队列里的元素进行维护，当 q[he...

每日一题单调队列

2020-03-29

0 1021