heartのc

题解

ACM(4) LeetCode(1) 笔试(1) 面经(1)

/ 注册

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

[每日一题]maze

传送门题意的地图，表示可走，表示起点，终点，向上下左右走的花费都是1，有个传送阵，可以传送到对应的点，花费为3。问到终点的花费最少是多少。分析经典的为题，只需要构造一个优先队列，存放路径和步数，用map映射下传送阵的坐标。然后标记是否访问过点即可。时间复杂度：参考代码 #include ...

每日一题 bfs

2020-05-13

0 720

[每日一题]模拟战役

传送门简单题意一张的地图，表示齐齐和司机 2个人的地形布局，一门大炮可以大对方的大炮，并且会影响3*3的区域，如果区域内同样有大炮，则继续受影响，问齐齐如果要摧毁所有司机的大炮后，最多可以保留多少自己的大炮。分析我们可以按照题意求出每个大炮受到影响的范围，本题中即是连通块的个数和大小...

dfs 每日一题贪心

2020-05-12

0 625

[每日一题]「火」皇家烈焰

传送门分析简单的线性，可以知道当前第位的答案是从位递推出来的，而每一个状态都和其左右两边是否存火有关系，所以可以设计一个三维的DP数组：，表示第位是否存在火，并且第位是否存火，这样就可以把所有的状态表示出来了。而通过题意可以得到以下的方程：所以最后的...

每日一题 DP

2020-05-08

0 756

[每日一题]codeJan与旅行

传送门题意描述有n个城市在数轴上，当前的位置是，p不和任何的城市重合，你现在需要经过个城市，每过城市可以多次经过，求最小的总距离。 Tags 贪心数学分析本题的巧妙之处在于，第一次看起来，有3种可行的方案：从起点的左/右出发，一直到访问了个城市。从如果到了起点或终点依...

每日一题贪心数学

2020-05-08

2 648

[每日一题]子序列

传送门思路若，则可以通过化简取取对数，得到。所以本题同理，这样化简后，就转成了，以结尾的子序列个数有多少，所以可以枚举起点和终点。时间复杂度： Tags DP 数学参考代码 //#include <bits/stdc++.h> #include <bitset> #...

每日一题数学 DP

2020-05-02

0 635

[每日一题]滑雪与时间胶囊

传送门分析本题的要点在于i到j有通路必须所有我们可以根据给出的建图。那么第一个问题就是求从1出发，最多可以经过多少个点，这个问题用BFS/DFS统计下点的个数即可。主要问题在于第二个问题，因为题目说不考虑时间胶囊的消耗，而且可以连续食用，所以最后走出来的形状一定是树的样子。但是由于路线方向是根据...

最小生成树每日一题

2020-05-01

0 712

[每日一题]糖糖别胡说，我真的不是签到题目

传送门题意有个人，分成2个队伍，每个人都有一个战力值第秒，第个人会消灭前面不属于同一个队伍，且战力值小于他的所有人。与此同时，有m次机会，第每次前个人的战力都会增加1，问你第秒存活的人数与此同时，有m次机会，每次前个人的战力都会增加1，问你第n秒存活的人数。分析从后向前遍历，若当前为第个人，...

模拟暴力

2020-04-21

0 637

[每日一题200416]华华给月月准备礼物

传送门题意更定n段长度为的木棍，问若把他们分成k个相同长度的，最大长度是多少 tags 二分分析可以对长度进行二分。二分下届为1，上界为max(a[i])。用贪心的方法经行检查。每个对于答案的贡献是。所以若说明mid的取值大了可以减少，否则需要增大。check函数复杂度：，总复杂度：参考...

二分每日一题

2020-04-16

1 672

[每日一题200414]Treepath

传送门题意给定一棵n个点的树，问其中有多少条长度为偶数的路径。 tags dfs/bfs 思维分析以节点开始，记录每个点的深度。设奇偶深度的点个数分别为：和，则ans=。具体证明过程如下图：参考代码 #include <bits/stdc++.h> using nam...

dfs 每日一题思维 dp

2020-04-14

0 619

[每日一题200408]Running Median

分析动态处理中位数，对顶堆的模板题。本质是维护了两个堆，设当前元素个数为：大根堆：序列中从小到大的数字小根堆：序列中从小到大的数字两个堆始终保证着元数个数相差不超过1的性质。如果在某一个时刻，打破了这一个性质，那么就讲元素多的堆顶元素插入到另外一个堆中。这样一来中位数就是小根堆的对...

每日一题堆蓝书

2020-04-08

0 608