申屠志刚

申屠志刚的ACM之路

ACM(1) C(128) C++(380) C.++(1) CTF(44) C语言(34) DP(4) JAVA(2) Python(1) 博弈论(1) 并查集(2) 最小生成树(1) 最短路(2) 未归档(435) 浙江理工大学2018年10月赛(2) 生成树(1) 申屠志刚的CTF之路(2) 矩阵(1) 线段树(1) 经典问题(1) 背包问题(1) 语法(1)

/ 注册

全部文章 / 申屠志刚的ACM之路（共37篇）

线段树合并

一、基本概念线段树合并：将已有的两棵线段树合并为一棵，相同位置的信息整合到一起，通常是权值线段树比较裸的，就是将一棵线段树的每一个位置取出来插入另一棵中，但比较高效的线段树合并可以参照可并堆的合并方式二、算法假设两棵线段树树：合并线段树合并的原理：对...

2019-07-10

0 1875

ACM/OI中C++常用优化(实用/调试/技巧)代码(语法)

一、C++万能编译头文件 #include<bits/stdc++.h> 从 #include <iostream> #include <cstdio> #include <fstream> #include <algorithm...

2019-06-01

1 2110

网络流24题

HDU版本问题编号问题名称问题模型转化模型题解 1 飞行员配对方案问题二分图最大匹配网络最大流题解 2 太空飞...

2019-05-22

0 1475

线段树——区间离散化/压缩

一、基本概念线段树：线段树基本概念离散化：把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。例如：原数据：1,999,100000,15；处理后：1,3,4,2；原数据：{100,2...

2019-04-30

0 1287

欧几里得算法和扩展欧几里得算法(Euclidean_Algorithm and Extended_Euclidean_Algorithm)

一、基本概念欧几里得算法：又名辗转相除法，计算两个整数a,b的最大公约数。扩展欧几里得算法：对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。二、基本性质 gcd函数的基本性质：gcd(a,b...

2019-04-25

0 855

ACM基础知识及算法

ACM 算法难度数据结构栈栈 1 单调栈队列一般队列 1 优先队...

2019-04-14

0 603

RMQ问题

一、基本定义 RMQ (Range Minimum/Maximum Query)问题是指：对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在i,j里的最小(大）值，也就是说，RMQ问题是指求区间最值的问题。二、算法（1）朴素复杂度：O(n)...

2019-03-27

0 813

强连通分量(Strongly_Connected_Components)

一、基本概念强连通图（Strongly Connected Graph）是指在有向图G中，如果对于每一对vi、vj，vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。有向图中的极大强连通子图称做有向图的强连通分量。连通分量：对于图G来的一个子图中，任意两个点都可以彼此到...

2019-03-14

0 703

欧拉路径(Euler_Path)和欧拉回路(Euler_Loop)

一、基本概念欧拉路径：欧拉路是指从图中任意一个点开始到图中任意一个点结束的路径，并且图中每条边通过的且只通过一次。欧拉回路：欧拉回路是指起点和终点相同的欧拉路。二、存在欧拉路的条件 1.无向连通图存在欧拉路的条件：所有点度都是偶数，或者恰好有两个点度是奇数，则有欧拉路。若有...

2019-03-14

0 1262

ST表

一、定义 ST表的功能很简单它是解决RMQ问题(区间最值问题)的一种强有力的工具它可以做到O(nlogn)预处理，O(1)查询最值二、算法 ST表是利用的是倍增的思想拿最大值来说我们用Max[i][j]表示，从i位置开始的2j个数中的最大值，例如Max[i][1]表示的是i位...

2019-03-10

0 605