子谦。

分类

入门教程(10) 未归档(52)

/ 注册

全部文章（共61篇）

洛谷 P1560 蜗牛的旅行

明显这是一道搜索题，其他题解写的有点复杂，我有更简便的写法既然题目说走到不能再走，那我们就干脆一点，一条路走到黑，不到南墙不回头，一下把要走的路都走完，不但效率高，也好写，关键是大大节省了系统栈一口气走很多点的关键在于如何记录一个点是否遍历过呢？退出后又如何删除标记呢？或许正是这两个问题...

2018-11-07

0 326

主席树入门详解+题目推荐

主席树学名可持久化线段树，就是这个可持久化，衍生了多少数据结构为什么会有主席树这个数据结构呢？它被发明是用来解决什么问题的呢？给定n个数，m个操作，操作类型有在某个历史版本下单点修改，输出某个历史版本下某个位置的值的值，n和m小于等于1e6 乍一看是不是一点头绪也没有...

入门教程数据结构主席树

2018-11-06

0 573

洛谷 [USACO09OPEN]工作调度

题面读完题，我们会发现有一个很重要的信息，每件物品代价相同，但价值不同。那么我们很容易想到，在满足限制的情况下，我们肯定会选择价值尽可能大的物品。我们可否用背包来实现呢，答案是否定的，或者说我不会QwQ 那么，我们来看看贪心由于物品的代价相同，那么当物品之间冲突时，我们留下价值大者，必...

2018-10-30

0 415

状压DP入门详解+题目推荐

在动态规划的题型中，一般叫什么DP就是怎么DP，状压DP也不例外所谓状态压缩，一般是通过用01串表示状态，充分利用二进制数的特性，简化计算难度。举个例子，在棋盘上摆放棋子的题目中，我们可以用1表示当前位置摆放棋子，用0表示当前位置不摆放棋子。这样的话，就能够直接运用许多二进制运算的特...

入门教程动态规划状压DP

2018-10-17

0 678

洛谷 P3177 树上染色

题面题目要求将k个点染成黑色，求黑点两两距离及白点两两距离，使他们之和最大。我们可以将距离转化为路径，然后再将路径路径拆分成边，就可以记录每条边被经过的次数，直接计算即可。很简单对吧？那么问题来了，距离转化为路径好理解，路径拆为边也好说，可是每条边被经过的次数怎么计算呢？我们可以这样...

2018-10-15

0 415

树形DP入门详解+题目推荐

树形DP。这是个什么东西？为什么叫这个名字？跟其他DP有什么区别？相信很多初学者在刚刚接触一种新思想的时候都会有这种问题。没错，树形DP准确的说是一种DP的思想，将DP建立在树状结构的基础上。既然说了这是一种思想，那么单讲的话，也讲不出什么东西来。所以我们结合具体题目进行讲解...

入门教程动态规划树形DP

2018-10-15

0 481

杂记

\(To~be~continued\) 2019年8月15日回来学文化课已经四个多月了，这四个月我几乎没有再碰过曾经令我留下无数遗憾的OI。当然，生计所迫嘛，菜鸡的我还要回来拿个省一才能维持未来的生活。经过四个月的沉淀，我变得稳重了许多，这次一定不会留下遗憾！希望在接下来的NOIP2019里，...

2018-10-14

0 510

单调队列/单调栈入门详解+题目推荐

以前一直以为这两个是很高级的东西，这段时间用到了才开始学，发现实际上非常简单下面我们以单调队列为例进行讲解，单调栈自行类比顾名思义单调队列这个名字就指明了它的性质——单调性我们来看一道例题——滑动窗口题面在此不再赘述，大意就是有一个长度为\(n\)的数列，一...

入门教程数据结构单调队列/单调栈

2018-09-09

0 499

树链剖分入门详解+入门题推荐

以前没有接触过树链剖分的同学们看到这个东西是不是觉得很高大上呢，下面我将带你们进入树的世界（讲得不好别打我）首先我们来看一道题软件包管理器这道题的大意是，每个软件有一个父软件（除根节点外）。要安装一个软件必须先安装它的父软件，要卸载一个软件必须先卸载它的所有子软件，模拟对软...

入门教程数据结构树链剖分

2018-09-03

0 370

P1314 聪明的质监员

我是题面读完题后，我们会发现这道题的题意非常简单，大意就是有n件物品，m个区间，求每个区间检验值之和，通过改变参数使标准值与检验值的差的绝对值最小很明显，检验值的变动只与参数有关，我们可以二分参数来搜索答案由题意可知，参数至小为0，至大为所有物品中最大的重量，再大则与至大值意义相同那么每...

2018-09-02

0 345