zhanGTao_

分类

未归档(1) 题解(4)

/ 注册

全部文章（共5篇）

寻找奇数

时间最优 #include<stdio.h> inline int read(){ int x=0;char c=getchar(); while (c<'0'||c>'9') c=getchar(); while (c>='0'&&a...

C++

2021-11-19

0 309

题解 | #数轴覆盖#

前缀和做法使用一个 dpdpdp 数组记录前缀和，dpidp_idpi 表示在 [0,i][0,i][0,i] 中有多少个点。枚举起点 iii 即可得到线段终点 i+k−1i+k-1i+k−1 , 使用 dpi+k−1−dpi−1dp_{i+k-1}-dp_{i-1}dpi+k−1−dpi−...

C++ 前缀和双指针动态规划

2021-10-20

0 443

题解 | #旅游#

非树形DP做法（贪心）由于整个图是一个树形结构，且起点固定为 sss 那么与 sss 相邻的点就必然不去，于 sss 距离为 222 的点可选择是否去。贪心的思路是叶子节点必选，往上可选节点必选一定可以构造出最优解（最优解不唯一但能保证是其中一个最优解）。证明如下： ①树形结构中的叶子节点是...

C++ 贪心深度优先搜索

2021-10-19

0 385

题解 | #小红的树#

非树形DP做法知识点：DFS序维护子树信息，前缀和由于DFS过程是遍历当前节点的全部子节点后返回当前节点，所以利用这个性质可以有效维护子树信息。 DFS过程中使用一个时间戳 dfndfndfn 并记录进入某个节点的时间 ininin 和出这个节点的时间 outoutout 。我们记录一个DFS序...

C++ 深度优先搜索前缀和

2021-10-19

0 549

北京信息科技大学第十三届程序设计竞赛暨ACM选拔赛 A题题解

瞎bb 这题在现场想到了贪心部分，也想到了优化要用到线段树/树状数组。时间不太够我码了，就直接放弃思考了，现在看来当时想的思路是正确的，码一下树状数组说不定能过2。赛后补题，思路代码几乎都对了，然后一个小细节给我绕进去了，卡了半天，好歹最后和lzh讨论了一下，改了一个参数过了...

贪心数据结构

2021-05-20

2 733