- 博客(13)
- 收藏
- 关注
RSS订阅原创 CCPC-wannafly Camp Day2 讲课内容总结（杜瑜皓-数据结构）
·栈、单调栈1.栈的特点与基本操作2.单调栈单调栈是一种特殊的栈，其栈内的元素都保持一个单调性（单调递增或者递减）。 ·单调递增栈,从栈底到栈顶依次递增（单调非递减栈:允许有相等） ·单调递减栈,从栈底到栈顶依次递减（单调非递增栈:允许有相等）qes1.给一个序列，求对于每个数左边第一个比它大的数做法：维护一个单调栈①如果当前栈顶的元素比自己小，则将栈顶元素不断弹出，直到遇到第...
2020-01-15 18:51:03
520
原创 CCPC-Wannafly Winter Camp Day 1
B. 密码学题意告诉你关于字符串加密的方法，然后给你一些加密操作和加密后的字符串，让你求原来的串思路知道被加密后的串与加密字符可以向前推出被加密之前的串，不断向前模拟即可#include<iostream>#include<algorithm>#include<cstring>#include<cstdio> using names...
2020-01-12 23:49:30
113
原创 （树形DP入门题）Anniversary party（没有上司的舞会） HDU - 1520
题意有个公司要举行一场晚会。为了让到会的每个人不受他的直接上司约束而能玩得开心，公司领导决定：如果邀请了某个人，那么一定不会再邀请他的直接的上司，但该人的上司的上司，上司的上司的上司等都可以邀请。已知每个人最多有唯一的一个上司。已知公司的每个人参加晚会都能为晚会增添一些气氛，求一个邀请方案，使气氛值的和最大。思路树形DP入门题①先设定：数组dp[i][0]为第i个人参加了舞会的时候这个...
2020-01-09 17:17:30
216
原创 （树形DP）Strategic game POJ - 1463
题意给你一棵树，树的每一个节点可以守护与其相连的所有边，问你最少用多少个节点可以守护这整棵树思路仔细思考不难发现，要想守护一条边，边的两个端点必须有一个可以被选（两个都选也可以），然后这个问题就变成了翻版的没有上司的舞会定义:dp[i][0]表示不选i，守护其子树需要多少点 dp[i][0]表示选上i，守护其子树需要多少点状态转移方程： dp[i][0] = ∑dp[j...
2020-01-09 17:15:03
79
原创 (分块)Holes CodeForces - 13E
题意n(n≤105)个洞排成一条直线，第ii个洞有力量值ai，当一个球掉进洞ii时就会被立刻弹到i+ai，直到超出n。进行m(m≤105)次操作：·修改第i个洞的力量值ai。·在洞xx上放一个球，问该球几次后被哪个洞弹飞出界。思路分块暴力，每个块内维护两个信息(块内DP可以求出)：①从当前位置跳出块内需要跳几次num[i]②从当前块内跳出的下一个位置jump[i]修改：只需要将修...
2020-01-09 11:51:41
92
原创 （分块）GukiZ and GukiZiana CodeForces - 551E
题意给你一段序列，并且有两种操作操作①：将序列中从l-r每个元素加上x操作②：在序列中找到ai=aj=y，j-i的最大值，如果找不到则输出-1思路直接分块暴力即可对于区间加，普通标记加暴力即可对于找最大值，直接在每个块中二分找y，找不到即为-1代码#include<iostream>#include<algorithm>#include<set&...
2020-01-08 23:14:21
74
原创 （分块暴力）Time to Raid Cowavans CodeForces - 103D
题意给你一段长度为n(1 ≤ n ≤ 3·1e5)的序列，m (1 ≤ p ≤ 3·1e5)个询问，每次询问a,a+b,a+2b+…<=n的和思路一开始一直想也想不到怎么分，去维护哪些信息，看了题解才知道 其实分块不仅仅可以将一列序列分块，还可以将数据进行分块，下面讨论具体做法首先这道题不是在线询问，可以离线做，先读入所有的询问，将询问从小到大排序①当b＜√n时，对于每一个b我们可...
2020-01-08 17:39:12
113
原创 （分块）楼房重建 HYSBZ - 2957
题意：长度为n的坐标轴上，从1-n上的每一点都有一栋楼房，楼房的初识高度都为0，每一天都有一栋楼房的高度被修改（也可以不变），一栋楼房能被看见当且仅当其最高点与远点的连线不会与其他之前连线相交，问你每天能看见的楼房数是多少。思路：其实这道题也可以用线段树做，但是感觉更复杂。预处理首先我们还是将整个打的区间分块成根号N块，每一段维护两个值，区间楼房高度的最大值，以及区间能被看到的楼房数目，...
2020-01-08 17:19:29
141
原创 数据结构——分块算法
可能涉及的名词解释①区间：数列中连续的一段元素②区间操作：将某个区间[a,b]的所有元素进行某种改动的操作③块：我们将数列划分成若干个不想交的区间，每个区间成为一个块④整块：一个区间操作时，完整包含于区间的块⑤：不完整的块什么是分块？分块其实就是将一个连续的序列分成若干段长度相等的片段，这些片段我们称之为块.。一般用于解决区间修改与询问，它可以解决以下一些问题：1.给出一个长为n...
2020-01-08 16:57:17
565
原创 Educational Codeforces Round 77 (Rated for Div. 2)
A. Heating题意：你要给n间房进行加热，对于每间房，你可以买c个加热器，每个加热器可以配置k个装置，一个加热器的价格为k²。给你每间房最多可以放c个加热器，总共要装最少sum个装置，问你每间房最少要花多少钱。思路很容易就能想出，每间房花费的最少钱就是(sum%c)(sum/c+1)²+(n-sum%c)*(sum/c)²。代码如下：#include<iostream>...
2019-11-28 16:09:55
165
原创 Codeforces Round #601 (Div. 2) 2019.11.19
A. Changing Volume题意：给定两个数a和b，与六种操作(−5,−2,−1,+1,+2,+5)。问a通过多少次操作可以变成b。思路：因为无论是想让a变大还是变小，都有三种相同的操作，所以就不用分类讨论a是否大于b了。读入a跟b后直接取他们相差的绝对值。根据贪心先将差值除上5，再加上对5取模的结果除2，再加上差值对5取模后再对2取模的结果就是答案了。代码如下：#includ...
2019-11-20 17:54:47
153
原创 树链剖分 详解 模板
·定义：树链剖分，它可以对一棵树进行轻重链剖分后用数据结构来维护每条重链,树链剖分的主要做法就是先把这颗树拆成一条一条链，那么对于每一条链，我们可以用线段树来维护，那么怎么拆这颗树呢，这才是树链剖分的要点。·用途： 已知一棵包含N个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：操作1： 将树从x到y结点最短路径上所有节点的值都加上z操作2： 求树从x到y结点最短路径上所有...
2019-10-04 15:26:48
221
原创 POJ-2155 Matri （二维树状数组，区间更新，单点查询）详解
DescriptionGiven an N*N matrix A, whose elements are either 0 or 1. A[i, j] means the number in the i-th row and j-th column. Initially we have A[i, j] = 0 (1 <= i, j <= N).We can change the m...
2019-10-03 11:30:40
158
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人