fuhaitao9999的博客

原创 树状数组维护区间最值问题

使用树状数组需要理解其具体原理。，记住其维护的区间是。

原创 Go并发编程

在Go语言中，每一个并发执行的活动成为goroutine。通道则是每一个goroutine之间传递消息的工具。

原创 Golang结构体按某一成员变量排序

结构体排序使用sort包中的函数。该函数需要传入一个结构体数组参数和一个匿名函数（排序方式）e.g.

原创 Golang结构体

Golang结构体的使用

原创 Golang Map的使用

Go map数据结构的使用

原创 Golang数组和slice

golang的数组及切片原理及使用方法

原创 Golang字符串类型原理及其使用方法

Golang中字符串的操作区别于其他语言，拥有自己的一套操作方法

原创 Golang常量iota

iota基本使用规则

原创 Golang基本的网络编程

使用golang中原生的工具包，构建一个基础的Web服务器

原创 正则表达式

正则表达式基础知识

原创 Golang字符串基本处理方法

Golang中字符串拼接问题

原创 Golang参数输入

golang常用工具包总结

原创 dp题

执行乘法运算的最大分数题目链接分析数据：nums长度为n;multipliers长度为m;1<=m<=1000;1<=n<=100000;nums和multipliers都在(-1000,1000);对于每一个multipliers[i]都需要和nums左右两端的数字组合，需要求得最大的匹配值。设dp[]i[j]状态为左边取i个，右边取j个。i=0时， dp[0][j]=dp[0][j-1]+nums右边第j个乘上multipliers[];j=0时，dp[i]

原创 Java/IDEA/MyBatis 框架不用（getMapper）的使用

MyBatis框架STEP1.1.在IDEA中添加数据库，注意自己数据库的版本号等信息。MySQL连接教程2.创建数据库

原创 Java线程——wait()和sleep()；

原创 家庭作业——并查集+贪心

题目链接：家庭作业贪心解题：对于每一个作业肯定是要完成分数最大的，因此只需要在小于等于规定时间内完成即可，并且需要保证尽量在靠近规定时间的时候完成最好，少占用前面的时间。并查集优化：使用并查集来记录前面最近的空余时间。#include <bits/stdc++.h>using namespace std;const int N=1e6+75;int fa[N]; //父类数组；int dfs(int x){ //dfs查询根节点（即最近的空余

原创 数据库基本常用语言一直加

数据库——常用基本语言//数据类型 字符串（varchar）、整数(tiny int、int 、bigint)、浮点数(float)、日期(date, datetime);//创建数据库；create database; drop database;//在创建时，希望指定编码语法；例如： create database 库名 character set utf8;//建表：create table 表名（ 字段名1 数据类型, 字段名2 数据类型

原创 可持久化线段树（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标记时没有将其向下压，因为为了不对前面线段树产生影响只能在每一个更改区间新建树才可以，内存

原创 扫描线——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。利用扫描线解决该问题主要需要解决在线段树上保存每一个颜

原创 扫描线模板代码详讲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

原创 莫队板子

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）则该数将两组数连在一起了减少了一组

原创 RMQ算法模板题

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

原创 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

原创 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...

原创 莫比乌斯反演+整除分块

莫比乌斯反演：若：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（...

原创 欧拉函数

欧拉函数φ(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...

原创 滑动窗口，单调队列

牛客滑动窗口算法思想：利用双端队列（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...

原创 悬线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()...

原创 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...

原创 线性筛素数

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&...

原创 最小费用最大流（板子）

最小费用最大流步骤：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],...

原创 最大流dinic（模板）

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

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

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

原创 匈牙利算法

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

原创 最小生成树prim（优先队列优化）算法+Kruskal算法

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

原创 带权并查集（模板）

带权并查集算法思想：维护节点到前导节点的距离；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]...

原创 拓扑排序

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

原创 最短路三种算法（Floyd+dij（优先队列优化版）+spfa）

单源最短路Floyd（纯暴力）思想：贪心+暴力枚举；看代码就能理解了void Floyd(){ //初始化dis[][]为很大的值； //注意在输入时需要将dis[x][y],dis[y][x],都录入； for(int k=1;k<=n;++k) for(int i=1;i<=n;++i) for(int j=1;j<=n;++j){ dis[i][j]...

原创 KMP(模板)

Oulipo The French author Georges Perec (1936–1982) once wrote a book, La disparition, without the letter 'e'. He was a member of the Oulipo group. A quote from the book: Tout avait Pair nor...

原创 AC自动机（初学模板）

Keywords SearchIn the modern time, Search engine came into the life of everybody like Google, Baidu, etc.Wiskey also wants to bring this feature to his image retrieval system.Every image have a lon...