1 相中人

尚未进行身份认证

我要认证

Bug绝缘体. Bug绝缘体. Bug绝缘体.

等级
TA的排名 22w+

可持久化线段树(To the moon)

理解:可持久化线段树,对一组数据建立多棵线段树来维护其状态,在建立新的线段树时可以合用不变的部分以减小内存开销。多棵线段树能确保将多种状态保存,互不影响。To the moon题意:给一组数,m次操作:C l r d 将l ~ r区间的数加上d,操作一次时间t加一。Q l r 查询l ~ r区间和。H l r t 查询第t次l ~ r区间和。B t 回到第t次,t次之后的作废;这道题在处理线段树lazy标记时没有将其向下压,因为为了不对前面线段树产生影响只能在每一个更改区间新建树才可以,内存

2020-07-22 21:07:04

扫描线——Colourful Rectangle

Colourful RectangleHDU4419题意:给定矩形坐标(左下,右上)和颜色属性,颜色一共有三种单一颜色及其混合颜色。分别为R、G、B、RG、RB、GB、RGB七种。求给定矩形所组成图形的每种颜色的面积。分析:题目中给了三种颜色和它们的混合色,故需要用数字来代替它们并可以相互转换。用1,2,4代表三种单一的颜色R、G、B,那么1|2,1|4,2|4,1|2|4,分别代表了RG、RB、GB、RGB四种颜色,十进制值为3,5,6,7。利用扫描线解决该问题主要需要解决在线段树上保存每一个颜

2020-07-18 22:49:53

扫描线模板代码详讲Atlantis

HDU1542Atlantis题意:求矩形块总面积,给定n个矩形坐标(左下角和右上角坐标),坐标有可能是小数。分析:本题是一道扫描线模板问题。扫描线就是按照x轴或者y轴的一个方向去扫描维护整个y值或x值所对应的线段总长。例如:矩形a:(1,1)(3,3)矩形b:(4,1)(6,3),当y=1时线段总长度为4,y=3时总长度为4;利用线段树来维护,线段的长度。有些情况需要对数据离散化处理。在本题中只需要对y轴进行扫描即可,再利用线段树维护区间的长度,面积直接用线段的长度乘上高就行了。#incl

2020-07-16 22:09:31

莫队板子

HDU-4638题意:给定n个数,值为1~n。m次询问,每次询问一个区间内拥有连续数段有多少个。解法:1、利用树状数组可以做。2、利用莫队暴力访问(更简单);莫队做法:我们知道莫队是对询问区间进行处理的,因此需要去寻找区间变化过程中的情况和对答案的影响。假定区间(l,r),若要加一个数x进去则只需判断x-1,x+1在(l,r)分布即可。有四种情况:a、x+1,x-1两个都没有在(l,r)则新增了一组数,故cnt++;b、x+1,x-1两个都在(l,r)则该数将两组数连在一起了减少了一组

2020-07-15 23:30:56

RMQ算法模板题

poj3264题意:给定一个长度为n的数组,m次访问,每次访问一段数组区间的最大值和最小值之差。这道题可以运用线段树解决,也可以用RMQ解决:1.线段树#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <cmath>#include <queue>#include <vector>#def

2020-07-08 18:56:52

Codeforces Round #641(Div 2)

A. Orac and Factors题目描述:For n≥2, we will denote as f(n) the smallest positive divisor of n, except 1.定义f(n) 为n的最小因子,除1以外。Now, for two positive integers n and k, Orac asked you to add f(n) to n exactly k times (note that n will change after each operation

2020-05-13 15:56:57

CF_Constant Palindrome Sum(差分维护区间和)

题目传送门这道题需要转化成区间问题:对于任意一对(a[i],a[n-i+1]),当假定和X在(min(a[i],a[n-i+1)+1,max(a[i],a[n-i+1])+k)里面时只需改变一个数,+1,特殊的x=a[i]+a[n-i+1]时不需要改变+0,其余的都需要+2;这就变成了区间问题,利用差分维护和就行了。#include <bits/stdc++.h>using na...

2020-04-29 11:24:43

莫比乌斯反演+整除分块

莫比乌斯反演:若:F(n)=∑d|n {f(d)}则:f(n)=∑d|n {μ(d)*F(⌊n/d⌋)}或者是:若:F(n)=∑n|d {f(d)}则:f(n)=∑n|d {μ(d/n)F(d)}两种情况。题目:洛谷P3455莫比乌斯反演模版题:求满足 1≤x≤a,1≤y≤b且 gcd(x,y)=k 的二元组 (x,y) 的数量。gcd(x,y)==k 推出 gcd(...

2020-04-07 19:22:07

欧拉函数

欧拉函数φ(x): 表示小于等于x的与x互为质因子的个数;φ(x)=x(1-1/p(1))(1-1/p(2))(1-1/p(3))(1-1/p(4))……(1-1/p(n)) 其中p(1),p(2)…p(n)为x的所有质数因数;x是正整数; φ(1)=1(唯一和1互质的数,且小于等于1)。注意:每种质数因数只有一个。#include <iostream>#include &lt...

2020-04-03 18:57:29

滑动窗口,单调队列

牛客滑动窗口算法思想:利用双端队列(deque)维护一个单调队列,再利用滑动区间遍历就可以了;#include <bits/stdc++.h>using namespace std;const int N=1e6+66;int a[N];int n,k;void get_max(){ deque<int > q; for(int i=0;i...

2020-03-29 13:41:02

悬线dp(HDU1505)

HDU 1505算法思想:对于每一点面积=up[i][j]*(r[j]-l[j]+1);算法步骤:1.统计每一层的最高长度up[][];2.利用up[][]维护r[]数组和l[]数组;#include <bits/stdc++.h>using namespace std;const int N=1234;int H[N][N],l[N],r[N];int main()...

2020-03-29 12:49:09

gcd(最大公约数)

#include <iostream>#include <algorithm>#include <cstdio>using namespace std;int gcd(int a, int b){ return !b? a:gcd(b,a%b);}int main(){ int a,b; while(scanf("%d%d...

2020-03-17 10:37:12

线性筛素数

void deal(){ int N=1e5+55,cnt=0; bool p[N]; int num[N]; for(int i=0;i<N;++i) p[i]=false; for(int i=2;i<N;++i){ if(!p[i]) num[cnt++]=i; for(int j=0;j&...

2020-03-17 10:29:18

最小费用最大流(板子)

最小费用最大流步骤:1.spfa()找最小费用的路径,并记录;2.利用最大流维护路径;模板题:洛谷P3381#include <bits/stdc++.h>using namespace std;const int N=5020;const int maxn=1e5+55;const int inf=0x3f3f3f3f;int dis[N],head[maxn],...

2020-03-13 18:21:52

最大流dinic(模板)

最大流(Dinic)算法思想1.bfs()从起始节点开始找到点的深度,以离s起点最近为标准;2.dfs()找流量正向减去多少,反向加上多少;例题洛谷P3376*代码#include <bits/stdc++.h> //代码实现;using namespace std;const int N=1e5+55;const int inf=0x3f3f3f3...

2020-03-13 13:20:21

带权二分图最优匹配KM算法

KM算法思想设有A[],B[]二分图,贪心的去找与A[i]的最大匹配,若没有找到就增加边,直到找到最优为止;实现步骤1.初始化l[],r[],数组,设置顶标,即找到与A[i]最大匹配的B[],存在l[]数组中,r[]数组初始化为0;2.dfs()寻找增广路径(最大匹配),和匈牙利类似;a.如果找到匹配点就进入下一匹配点;b.如果没有找到就增加新的路径;注意:在实现最小匹配时,将两...

2020-03-13 12:21:36

匈牙利算法

匈牙利二分图:二部图又叫二分图,是图论中的一种特殊模型。设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B),则称图G为一个二分图。最大匹配: 当节点之间匹配到最大时,为最大匹配;匈牙利算法思想通过不停地找增广路来增加匹配中的匹配边和匹配点。找不到增广路时,达到...

2020-03-03 18:22:12

最小生成树prim(优先队列优化)算法+Kruskal算法

最小生成树1.prim算法算法思想:从任意一点出发,记录点的最小权值,每一次将最小边的结点标记一下,直到所有的点都被加到树里面。优先队列将边按从小到大的顺序排列,队首为最小的边。板子题:HUD-1863#include <iostream>#include <algorithm>#include <cstdio>#include <cstri...

2020-02-28 13:04:11

带权并查集(模板)

带权并查集算法思想:维护节点到前导节点的距离;HDU3047#include <bits/stdc++.h>using namespace std;const int N=54321;int dis[N],pre[N];inline int find(int x) //find()函数,寻找根节点+路径压缩(前导节点,维护路径);{ if(x==pre[x]...

2020-02-27 14:07:15

拓扑排序

拓扑排序算法思想1.入度数组ru[],记录是否存在环的情况;2.利用bfs()将入度为0的依次压入队列,将其所指向的点入度减一;3.在排序的过程中实现题目目的;例题HDU2647思路:1.先反向建边,x比y多则将y指向x;2.用一个val[]数组记录每一个点最大需要多花费的钱,依次向上更新,排序的过程就完成了,数据的更新;## 代码#include <bits/stdc...

2020-02-22 20:13:11

查看更多

勋章 我的勋章
  • 领英
    领英
    绑定领英第三方账户获取
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 阅读者勋章Lv1
    阅读者勋章Lv1
    授予在CSDN APP累计阅读博文达到3天的你,是你的坚持与努力,使你超越了昨天的自己。
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv2
    勤写标兵Lv2
    授予每个自然周发布4篇到6篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。