Rewinner

分类

ACM(1) dfsdd(1) DP(6) hash(1) STL(1) 图论(24) 小技巧(4) 思维(6) 搜索(2) 数学(5) 数据结构(16) 未归档(70)

/ 注册

全部文章（共136篇）

[CQOI2015]任务查询系统【可持久化线段树+差分】

传送门最开始思路都想到差分了，但是没有继续想下去。解题思路：利用差分来解决区间的问题，因为最多有 1e5 个任务，所以最多有 2e5 次修改，利用时间戳来建树，首先让新建的这棵树等于上一颗树，如果这次没有修改操作，就跳过，否则就在这一棵树上进行修改。坑点：在进行询问时，如果碰到递归终点，不能返回...

2019-04-29

0 482

SPOJ D-query 【可持久化线段树】

传送门题目描述：多次询问一个区间内不同数的数量。解题思路：一个区间内存在相同的数，所以我们的线段树就不能维护数，应该去维护下标?为什么去维护下标呢，就算一个数相同，但是它们的下标肯定是不同的，我们的线段树维护下标存在的情况。如果区间内存在重复的数，意味着不同下标对应相同的数，如果我们记录多个下...

2019-04-25

0 475

Count on a tree SPOJ - COT 【可持久化线段树树上第K小】

传送门题目描述：给你一个树，每个点有权值，多次询问两点之间的链的第k小权值掉入的坑：必须离散化，不离散化过不了，(第一反应用的二分答案，发现没有题目上没给数据范围，不离散化，会RE到死。。。)解题思路：我们每次儿子的状态室友父亲更新过来，我们要如何得到这条链的信息呢？首先LCA我们肯定是会用到的...

2019-04-24

0 557

2019年ICPC南昌网络赛 J. Distance on the tree【树链剖分/DFS序+可持久化线段树】

传送门题目描述：给你一个树，多次询问一条链上边权小于等于 k 边的数量。解题思路：树链剖分+可持久化线段树：主要是两个模板的合并使用，主要细节即可（可持久化主席树查询时注意时间戳）。 DFS序+可持久化线段树：每个儿子的状态都是由父亲得到的，我们只需要用父亲的状态来更新儿子即可，最后求一个L...

2019-04-24

0 454

美味佳肴【思维+可持久化线段树】

传送门题目描述：众所周知，天才程序员菜哭武是一个伟大的厨师。这天，张老师和石头来到菜哭武家做客，想尝一尝菜哭武的手艺。菜哭武手上有n种食材，每种食材个数无限多，编号为i的食材有一个美味度ai。一道菜中，每种编号的食材至多有一个，而这道菜的美味度是这道菜包含的食材的美味度之和。每次张...

2019-04-23

0 437

Minieye杯 Mex【思维】

传送门题目描述：给你一个大小为 n 的数组，问你这个数组里面不能组成的数中，最小的一个是什么？解释说明：输入: 3 1 2 5 输出： 4 样例说明： S'=(), ∑S'=0 S'=(1), ∑S'=1 S'=(2), ∑S'=2 S'=(1,2), ∑S'=3 ...

2019-04-23

0 533

牛客Wannafly挑战赛4 树的距离【DFS序+可持久化线段树】

传送门题目描述： wyf非常喜欢树。一棵有根数树上有N个节点，1号点是他的根，每条边都有一个距离，而wyf是个爱问奇怪问题的熊孩子，他想知道对于某个点x,以x为根的子树上，所有与x距离大于等于k的点与x的距离之和。输入描述: 第一行一个正整数N 接下来N-1描述这棵树，每行两个数第i行...

2019-04-22

0 491

Chino with Rewrite 【树链剖分+并查集+状压线段树】

传送门中文题面就不在阐述解题思路：题目上的操作2 对一棵树的一条链进行操作，很容易想到树链剖分。由操作1给的叙述，我们能够想到并查集离线建树。要求一个链上知识点种类的数量，而且 wi 不超过60，利用状压来解决。 ///#include<bits/stdc++.h> /...

2019-04-21

0 584

南华大学第十五届ACM 神秘的字符串【区间DP】

传送门思路：很容易想到这是一道区间DP的题，但是如何写区间DP方程，二维好像表示不了，那三维呢？好像也不好想，那就四维。，表示区间中 u 字符连着消去 k 长度的最大价值( 只有两个字符，即 0和1 ) s 表示区间的一个点，如果那么dp 转移方程表示区间的最大价值细节见代码： ...

2019-04-21

0 565

Power OJ 2853 小Z的糖果店【树的中心+DP+优先队列】

传送门思路：要求找一个最小Gg值，当 K = 1 时，我们知道这个点一定在直径上面，要使 Gg 最小，则该点到直径的两个端点距离的最大值最小。 DFS求直径：随意找一个点为起点，距离这个点最远的点就是直径的一个端点S，然后在以S为起点DFS，距离S距离最远的点就是直径的另一个端点E。我们要记录...

2019-04-20

0 487