_LRJ_

分类

题解(29)

/ 注册

全部文章（共29篇）

【每日一题】黑白树

这个题可以用贪心的思想。我们要想染色最少次数，那么就一定要从叶子节点开始，因为有可能使得叶子结点的k[i]用得上。这个题目还有最重要的一点是要更新k[i],就是在dfs的时候，用儿子节点去更新该节点的k[i]，最远染色距离。那么我们就dfs来维护当前的最远染色距离，从儿子节点转移来的要记得减一，因为...

2020-04-11

1 604

【每日一题】Shortest Path

这个题看起来无从下手，但是仔细分析会发现，我们dfs得出每个子树的节点个数，如果是奇数，那么我们就需要加上这条连向这个点的边权值，因为奇数个点不可能完成题目要求两两分组。如果节点个数为偶数就不用管。 #include<bits/stdc++.h> using namespace std;...

2020-04-11

0 600

【每日一题】数码

题目大意是给你两个整数l,r，对于所有满足1 ≤ l ≤ x ≤ r ≤ 10^9 的 x ，把 x 的所有约数全部写下来。对于每个写下来的数，只保留最高位的那个数码。求1～9每个数码出现的次数。这个题我们可以考虑枚举因子，我们考虑从1-r段所有的数码出现次数，我们假设a和b是因子，那么a最大取，...

2020-04-11

0 622

三角形

题意是：给你n个背包，每个背包装了mi个物品，每个背包选一个，要求出选出物品价值前k小的不同方案种数，很容易联想到背包dp。那么怎么做呢？我们可以考虑dp[i][j]表示前i个背包选出来价值和为j的方案个数，则有 dp[i][k]+=dp[i-1][k-a[i][j]];这个是状态转移方程，具体看...

2020-04-08

4 514

咪咪游戏

这个题简单，只要暴力的去判断是否是由连续的mq组成的，那么如果长度为奇数一定不可以，那么对于偶数长度，我们两个两个看，如果出现两个不是mq的就输出No，否则输出Yes code #include<bits/stdc++.h> using namespace std; const int ...

2020-04-08

0 666

【每日一题】Running Median

这个题仔细分析观察，应该是要线性的时间复杂度，那么如何做呢？我们可以发现，我们要的是每一次加入元素后的中位数的值，那么我们就可以联想到使用堆来存储，这样就可以在线性时间复杂度求解。我们定义两个堆，一个是前半段q1，一个是后半段q2。在构造优先队列的时候，我们要把前半段定义成大根堆，后半段定义成小根堆...

2020-04-08

0 707

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

这道题千万别看错题误以为是kmp，其实不是的！！注意题目说的是子序列而不是子串，所以kmp不行那么这道题该怎么做呢？仔细想想，既然它给定了你一开始那个s字符串，就是待匹配的字符串，那么我们要做的就是去预处理一下。用一个dp数组，dp[i][j]代表第i个字符后面最近的'a'+j字符的位置，我们从后...

2020-04-08

0 571

【每日一题】Rinne Loves Edges（dfs+dp求解)

首先我们可以注意到最后一行m=n-1,那么这个无向连通图就是一棵树了。那么再仔细的分析下，题目要求除了s之外度为1的点都不能到达s，那么除了s之外的度为1 的点就是叶子节点了，那么问题转化为了如何删掉边权最短的一些边，从而使得s到不了任何一个（注意是任何一个）叶子节点。思索了一下，这个题应该可以...

2020-04-07

2 761

【每日一题】树（组合数学)

我们要考虑的是把这棵树分成最多min(n,k)个块，因为要保证每个块颜色不同最多有k种颜色，所以不能超过k，又因为最多有n个点，所以也不能超过n，因此最多分min(n,k）个块。如果知道这个思路就好做了，我们只要分的块数用组合数公式 C(k,x)表示从k种颜色里挑出来x种颜色，C(n-1,x-1...

2020-04-07

1 757