申屠志刚

申屠志刚的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篇）

拓扑排序(Topology_Sort)

基本思想对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列...

2019-02-25

0 0

莫队算法(Mo's_Algorithm)

一、定义二、应用莫队算法可用于解决一类可离线且在得到区间[l,r]的答案后，能在O(1)或O(log2⁡n)得到区间[l,r+1]或[l−1,r]的答案的问题三、分析 http://www.cnblogs.com/hzf-sbit/p/4056874.html https://zhu...

2019-01-21

0 650

最小公倍数(Least_Common_Multiple)

一、定义几个数共有的倍数叫做这几个数的公倍数，其中除0以外最小的一个公倍数，叫做这几个数的最小公倍数。自然数a、b的最小公倍数可以记作[a、b],自然数a、b的最大公最小公倍数因数可以记作(a、b)，当(a、b)=1时,[a、b]= a×b。如果两个数是倍数关系，则它们的最小公倍数就是较大的...

2019-01-18

0 645

最大公约数(Greatest_Common_Divisor)

一、定义如果有一个自然数a能被自然数b整除，则称a为b的倍数，b为a的约数。几个自然数公有的约数，叫做这几个自然数的公约数。公约数中最大的一个公约数，称为这几个自然数的最大公约数。二、性质重要性质： gcd(a,b)=gcd(b,a) （交换律） gcd(-a,b)=gcd(...

2019-01-18

0 1779

斯特林数(Siteling_Number)

一、基本概念斯特林数出现在许多组合枚举问题中. 第一类斯特林数 StirlingS1[n,m]，给出恰包含 m 个圈的 n 个元素的排列数目. 斯特林数满足母函数关系 . 注意某些的定义与 Mathematica 中的不同，差别在于因子 . 第二类斯特林数 StirlingS2[n,...

2019-01-17

0 620

巴什博奕(Bash_Game)

一、定义只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。二、分析我们从最简单的情景开始分析当石子有1−m1−m个时，毫无疑问，先手必胜当石子有m+1m+1个时，先手无论拿几个，后手都可以拿干净，先手必败当石子有m+2−2mm+2...

2019-01-07

0 0

SG函数和SG定理(Sprague_Grundy)

一、必胜点和必败点的概念 P点：必败点，换而言之，就是谁处于此位置，则在双方操作正确的情况下必败。 N点：必胜点，处于此情况下，双方操作均正确的情况下必胜。必胜点和必败点的性质： 1、所有终结点是必败点 P 。（我们以此为基本前提进行推理，换...

2019-01-07

0 716

多边形面积(Area_Of_Polygons)

原理：任意多边形的面积可由任意一点与多边形上依次两点连线构成的三角形矢量面积求和得出。分析：由于给出的点是相对于我们的坐标原点的坐标，每个点实际上我们可以当作一个顶点相对于原点的向量，如下图所示： P(0,0)对应的顶点向量分别为：A(x0,y0),B(x1,y1),…,G...

2019-01-04

0 859

圆周率π的精确计算

一、圆周率π计算 /* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> using namespace std; long a=10000,b,c=56000,d,e,f[56001],g; int main...

2019-01-01

0 632

组合数(Combinatorial_Number)

定义：从n个不同元素中，任取m(m≤n)个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合;从n个不同元素中取出m(m≤n)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数。公式：在线性写法中被写作C(m,n)。 c(m,n)=p(m,n)/n!=m!/((m-...

2018-12-28

0 428