- 博客(76)
- 收藏
- 关注
RSS订阅原创 动态DP入门&线性动态DP
OI-WiKi上有一个动态DP讲解，直接讲到了树型DP领域，同时需要树链剖分，门槛有点高。本文针对线性DP做一个动态DP的讲解。首先当然要懂得一定的DP的相关知识，然后需要知道DP方程的矩阵表达。可以看这里——根据递推公式构造系数矩阵用于快速幂。很多DP的状态转移方程都可以写成矩阵形式，由此就有了矩阵快速幂优化和动态DP的基础。特别是本文专门举例的线性DP。
2024-02-19 21:40:32
863
原创 CDQ分治处理多维偏序基础
CDQ分治处理多维偏序基础多维偏序问题逆序对的两种解法逆序对的分治解法逆序对的树状数组解法二维偏序的解法二维偏序的分治解法二维偏序的树状数组解法三维偏序的解法三维偏序的分治套分治解法CDQ分治是一种离线处理多维偏序问题的算法框架。它不是一个具体的算法，但是为多维偏序问题提供了一个框架结构。以下首先介绍多维偏序问题的CDQ分治框架，从低维到高维；然后介绍几个简单的可以被抽象为多维偏序的修改查询操作的问题。多维偏序问题要想使用CDQ分治解决多维偏序问题，首先还是要从基础的逆序对问题说起，然后再到高维。逆
2021-08-24 17:58:15
297
原创 Polya定理与Burnside引理及其应用
Polya定理及其应用群与置换群群与置换群群是近世代数的一个概念，简单的说，群就是集合配运算，如果运算满足：封闭性结合性双元存在（即幺元和逆元）例如：全体偶数集合配上算术加法就构成一个群。而全体偶数集合配上算术乘法就不是一个群。置换群是非常重要的一类群。首先介绍置换，假设有(1,...,n)(1,...,n)(1,...,n)的数，将其变为(a1,...,an)(a_1,...,a_n)(a1,...,an)，其中aia_iai只能在[1,n][1,n][1,n]中取值且不重复，这种
2021-08-05 11:09:45
585
原创 湖南师范大学2021年4月15日蓝桥冲刺赛解题报告与标程
湖南师范大学2021年4月15日蓝桥冲刺赛解题报告与标程A题目描述解法标程B题目描述解法标程C题目描述解法标程D题目描述解法标程E题目描述解法标程F题目描述解法标程G题目描述解法标程H题目描述解法标程I题目描述解法标程J题目描述解法标程A题目描述给一个阶幻方的残余，对齐进行还原。如果答案不止一个，输出`Too Many·解法显然深搜即可。原题没有说失败如何，应该是保证至少有一组解。另外需要注意如果输入本来就是完整的幻方，要能正确输出。标程#include <bits/stdc++.h
2021-04-15 19:40:50
363
2
原创 湖南师范大学2021年4月1日愚人赛解题报告与标程
湖南师范大学2021年4月1日愚人赛解题报告与标程欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题，有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表如何创建一个注脚注释也是必不可少的KaTeX数学公式新的甘特图功能，丰富你的文章UML 图表FLowchart流程图导出与导入导出导入欢迎使用Markdown编辑器你好！ 这是你第一次使用 Markdown编辑器 所展示的欢迎
2021-04-01 22:55:16
245
原创 湖南师范大学2021年3月25日蓝桥杯热身赛解题报告与标程
湖南师范大学2021年3月25日蓝桥杯热身赛解题报告与标程A题目描述解法标程B题目描述解法标程C题目描述解法标程D题目描述解法标程E题目描述解法标程F题目描述解法标程G题目描述解法标程A题目描述解法标程A题目描述解法标程A题目描述解法标程A题目描述链接：https://ac.nowcoder.com/acm/contest/13543/A来源：牛客网寛神去鹅厂做项目经理去了，他带领3个开发组。工期紧，今天都在加班呢。为鼓舞士气，他打算给每个组发一袋核桃（据传言能补脑）。他的要求是：各组的核桃
2021-03-25 17:29:11
2931
原创 SVFTools的约束图CG
文章目录指针分析的Andersen规则与SVF中的规则第零个例子第一个例子第二个例子第三个例子第四个例子SVFTools的约束图ConstraintGraphConstraintGraphConstraintGraph简称CG，是用来做指针分析的。根据四条规则，在PAG的基础上建立。在这个过程中，PAG是不变的，而CG则是有可能改变的。指针分析的Andersen规则与SVF中的规则使用集合符号，令ppp是一个指针，则pts(p)pts(p)pts(p)是ppp所有可能指向的对象的集合。例如源代码in
2021-03-23 09:16:26
744
原创 SVFTools的PAG图
SVFTools的PAG图第一个例子a+b第二个例子if第三个例子forPAG称为程序赋值图，记录了LLVMIR中变量的赋值依赖关系。本文通过若干个例子观察IR代码和PAG之间的关系。第一个例子a+b源代码void f(){ int a,b,c; a = 3; b = 5; c = a + b;}LLVMIR文件define dso_local void @f() #0 !dbg !7 {entry: %a = alloca i32, align 4
2021-03-16 11:26:01
1011
原创 SVFTools的SymbolTableInfo与PAG
文章目录SymbolTableInfo第一个例子第二个例子PAGPAG示例SymbolTableInfoSymbolTableInfo是SVFTools中的一个类，本文以下称为符号表。顾名思义，根据LLVMIR记录了一些东西。最主要的私有数据成员如下，注意这里简化了一些东西，去除了一些typedf和const，源代码其实并不完全是这样。 map<Value*, uint> valSymMap; ///< map a value to its sym id map<
2021-03-15 10:23:30
298
原创 SVFTools与LLVM的Basic Blocks实验
SVFTools与LLVM的Basic Block实验LLVM BB与Control Flow GraphSVFTools生成自定义的BB图本文根据南京大学静态程序分析课程中关于Control Flow Analysis的Basic Blocks的片段，对给定的源代码进行有关BB的实验。南京大学静态程序分析课程课件，其中第二课 Intermediate Representation有关于Basic Block与控制流的讲解。课件中给出了三地址码与BB控制流图，以下为课件中的截图。LLVM BB与Co
2021-03-08 17:36:31
991
原创 SVFTools图基类的简单使用
文章目录SVFTools 图有关的基类三个基类工具模板自建图与SCC自建点边图子类SVFTools 图有关的基类三个基类SVFTools为图提供了三个基类，均为模板类，分别是GenericNode,GenericEdge,GenericGraphGenericNode, GenericEdge, GenericGraphGenericNode,GenericEdge,GenericGraph，对应节点、边与图类型（图是有向图）。其中边类最为简单，主要包含3个成员：template<class
2021-02-18 18:01:47
833
原创 SVF-tools安装笔记
SVF-tools安装笔记新的改变功能快捷键合理的创建标题，有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表如何创建一个注脚注释也是必不可少的KaTeX数学公式新的甘特图功能，丰富你的文章UML 图表FLowchart流程图导出与导入导出导入你好！ 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章，了解一下Ma
2020-12-26 11:32:19
2636
原创 NEERC 2014 D题 Damage Assessment
NEERC 2014 D题 Damage Assessment题目描述直接计算定积分辛普森方法Romberg方法题目描述这里是NEERC2014的相关资料，包括榜、题目、标程，但是好像没有解题报告。这是CF上的重现Gym100553。当然在ICPC Live Archive上也有，这里是链接，但是好像不能提交了。所以去CF上比较好。牛客网上也有这道题，但是数据与CF上的好像不同，有的代码两边都能过，但有的代码只能过其中一边。数据应该是一样的，也许是SPJ与时限写的不同。如图，一个油罐，两端是球缺
2020-11-02 22:26:07
338
原创 定积分的计算与辛普森积分及龙贝格积分
自适应辛普森积分辛普森积分公式辛普森积分公式∫abf(x)dx≈b−a6(f(a)+4f(a+b2)+f(b))\int_a^b{f(x)dx}\approx\frac{b-a}{6}\Bigg(f(a)+4f\big(\frac{a+b}{2}\big)+f(b)\Bigg)∫abf(x)dx≈6b−a(f(a)+4f(2a+b)+f(b))其来源是使用过三点的二次曲线去逼近源曲线，从而得到一个数值结果。...
2020-11-02 22:22:06
2177
原创 树状数组与前缀和差分数组以及二维树状数组
树状数组与前缀和差分数组以及二维树状数组树状数组基本思想树状数组基本思想树状数组有称作Binary Index Tree，顾名思义，就是一种以二进制为索引的数据结构。另源数组记作AAA。考虑需要求取Σ\SigmaΣ...
2020-03-13 11:19:41
844
原创 POJ2528线段树区间合并加离散化
POJ2528Mayor’s posters就只支持一种操作，一次性的给一段区间涂上颜色，且每次颜色均不一样。问最后一共可以看到多少种颜色。关于线段树的更详细实现请参考线段树解决区间问题包括延迟操作以及离散化/* 在数轴上，一次给一个线段涂上颜色 后面的颜色会覆盖前面的颜色 问最后能看到多少个颜色 显然是成段更新，线段树 区间范围是1千万，需要离散化...
2020-03-10 20:22:28
225
原创 POJ3667线段树区间合并
POJ3667Hotel要求支持两种操作：成段分配与成段回收。/* 1 a:找一段空间有连续a个空，分配出去 2 a b: 从a开始的b个位置回收*/#include <stdio.h>int const SIZE = 50010;//ST[t]表示t节点中最长的可用空间int ST[SIZE<<2];//Start[t]表示最长可用空间的...
2020-03-10 19:51:49
144
原创 hdu4578线段树多种延迟标记
hdu4578Transformation，要求支持3种修改操作与3种查询操作。/* 数组A[1...N]，一共有4种操作 1 x y c：A[x...y]增加c 2 x y c：A[x...y]乘以c 3 x y c：A[x...y]全都变成c 4 x y p：求SIGMA(Ai^p) x<=i<=y,1<=p<=3 建...
2020-03-10 19:48:00
371
原创 线段树解决区间问题包括延迟操作以及离散化
线段树解决区间问题包括延迟操作以及离散化线段树简介与分治策略线段树简介分治策略线段树不能解决的问题线段树的基本操作线段树的简单示例线段树的基础代码实现辅助操作建树查询修改延迟操作延迟操作思想延迟操作代码实现线段树简介与分治策略线段树简介线段树是一棵二叉树，用来解决区间问题。线段树的每个节点均保存有源数组中某个区间的特征值（最值、区间和、……）。本质上说，线段树是区间问题分治策略的实现模板。...
2020-03-08 13:45:36
441
原创 多边形与圆相交求面积题目POJ2986&&hdu2892
多边形与圆相交求面积题目POJ2986&&hdu2892POJ2986hdu2892具体思路可以参考简单多边形与圆相交求面积POJ2986/** 三角形与圆相交求面积*/#include <stdio.h>#include <math.h>using namespace std;double const PI = acos(-1.0...
2019-12-24 16:37:36
772
原创 简单多边形与圆相交求面积
简单多边形与圆相交求面积简单多边形的有向面积简单多边形与圆相交的有向面积圆心三角形与圆相交求面积简单多边形的有向面积所谓简单多边形，就是指不相邻的边不相交，且每个顶点只跟2条边相邻。一般而言，除非题目要求判断是否为简单多边形，否则给出的数据肯定都是简单多边形。以下将简单多边形简称为多边形。多边形一般都是以点集的形式给出，顺时针或者逆时针。另外一个需要注意的概念就是多边形的凹凸性。一般而言，凸多...
2019-12-24 16:32:40
2012
5
原创 莫比乌斯反演入门题目
莫比乌斯反演入门题目整除分块[洛谷P2568: GCD](https://www.luogu.org/problem/P2568)[SPOJ VLATTICE](https://www.spoj.com/problems/VLATTICE/en/)[hdu1695: GCD](http://acm.hdu.edu.cn/showproblem.php?pid=1695)[BZOJ 2005: 能量...
2019-11-07 15:43:39
213
原创 狄利克雷卷积与莫比乌斯函数
狄利克雷卷积与莫比乌斯函数数论函数狄利克雷卷积莫比乌斯函数若想使用莫比乌斯反演，则熟练掌握狄利克雷卷积包括定义、记号以及相关的性质、证明等是非常有好处的。数论函数数论函数也称作算术函数，就是定义在正整数上的函数，也可看作是一个数列。例如：f(n)=2n−1f(n)=2n-1f(n)=2n−1就表示了一个数论函数，其实就是：[1,3,5,7,9,...][1,3,5,7,9,...][1...
2019-11-05 15:43:18
1787
原创 POJ2891
求解线性同余方程组，模数可能不两两互质，因此需要使用合并方程的方法。#include &lt;stdio.h&gt;typedef long long int llt;//The extended Euclidean algorithm implemented by iteration//returns gcd(a,b), and x, y are satisfied with ax...
2018-07-06 13:18:16
731
2
原创 中国剩余定理与线性同余方程组求解
线性同余方程组中国剩余定理线性同余方程组实际上一元一次线性同余方程组，形式如下： ⎧⎩⎨x≡r0(modm0)x≡r1(modm1)⋯{x≡r0(modm0)x≡r1(modm1)⋯\begin{cases}x\equiv{r_0}({\rm{mod}}\,m_0) \\x\equiv{r_1}({\rm{mod}}\,m_1) \\\cdots\end{ca...
2018-07-06 13:06:56
4498
2
原创 欧几里德算法与扩展的欧几里德算法及乘法逆元
欧几里德算法扩展的欧几里德算法数学公式欧几里德算法欧几里德算法用于求解最大公倍数，也就是辗转相除法。其结论非常简洁，对任意整数aaa、bbb，有： gcd(a,b)=gcd(b,a%b)gcd(a,b)=gcd(b,a%b)gcd(a,b)=gcd(b,a\%b) 其中，%代表取模运算，也就是C++语言中的运算符。因此，欧几里德算法实现起来也非常简单。...
2018-07-05 23:25:10
1667
原创 数位DP模板
数位DP问题数位DP指一类问题：给定正整数区间[s, e]，问符合条件的数一共有多少个。例如hdu2089以及hdu3555等。 其中，hdu2089的条件为数字中不含4且不含62，hdu3555的条件为数字中包含49。一般而言，这类条件中至少有一个是与整个数的数值无关的，而是与每一位的数字有关。例如上面2道题的条件就与整个数的数值无关。 因此这类问题实际上是数位有关的问题，另一方面，这类问题通
2017-08-06 11:21:15
950
原创 hdu5953 三维空间旋转
题目大意给定若干个3×33\times3的旋转矩阵，对每个矩阵求一个到其他矩阵的最短距离。 两个旋转矩阵的距离做如下定义：对单位球上的任意点PP，经过第一个旋转矩阵的旋转后得到的点为P1P_1，经过第二个旋转矩阵的旋转得到的点为P2P_2，则P1P_1和P2P_2在单位球上有一个距离。对单位球上所有的点PP，P1P_1和P2P_2的最大距离称为两个旋转矩阵之间的距离。思路将第一个旋转记作R1R_1
2017-02-09 13:19:38
916
1
原创 树上莫队算法
江湖传闻，莫队算法能够解决一切区间查询问题。这样说来，莫队算法也能够解决一切树上路径查询问题，将树上操作转化为DFS序列上的区间操作即可。当然考虑到，树上路径在DFS序列中的性质，还要会求LCALCA。考虑上图中的树，其DFS序为其任意点对aa、bb之间的路径，具有如下性质，令lcalca为aa、bb的最近公共祖先：若lcalca是aa、bb之一，则aa、bb之间的InIn时刻的区间或者OutOu
2017-01-05 16:25:58
5531
10
原创 树的DFS序
树是一种非线性结构，一般而言，我们总是想办法将其转化为线性结构，将树上操作包括子树操作、路径操作等转化为数组上的区间操作，从而在一个较为理想的复杂度内加以解决。将树“拍平”的方法有很多，例如欧拉序、HLD等。实际上欧拉序也是在DFS过程中得到的。不过通常而言，我们所说的DFS序是指：每个节点进出栈的时间序列。 考虑上图中树的DFS序，应为 其中，每个节点均会出现2次，第一次是进入DFS的时刻，第
2017-01-04 21:58:55
4089
1
原创 莫队算法
莫队算法是一个非常好的算法。最简单的莫队算法用于解决一类序列上无修改只查询的区间问题。经过不同改进后，还可以解决树上路径查询问题，带修改的区间查询问题……总之，莫队算法可以解决一切区间问题。当然，莫队算法还有一个显著特征——莫队算法是一个离线算法。考虑SPOJ3267，给定一个数组，在数组上进行qq次询问。每次问区间[i,j][i,j]中不同元素的总数有多少。显然暴力法非常容易写，但复杂度绝对不理想
2017-01-03 17:03:07
2800
1
原创 树链剖分HLD解决子树问题
树链剖分HLD可以将非线性的树结构转换为由若干条树链构成的数组，并对数组采用线段树等手段，在一个令人比较满意的时间复杂度内完成树上路径操作，包括路径查询和路径修改。实际上，树链剖分也可以完成子树相关的操作，而且只需稍许改进即可。 考虑这样一个树以及剖分出的树链数组，可以非常明显的看到，任意节点及其子树在数组中均是连续的，而且一定以该节点开头。例如CC子树为CHLNGIMCHLNGIM，BB子树为B
2017-01-02 16:21:18
1040
原创 树链剖分之HLD
树链剖分的原理对于数组这样的线性结构，要在其上实现区间查询（和与最值）、区间修改甚至是区间增删都是有办法的。例如Sparse Table算法、树状数组、线段树以及伸展树等。而树是一种非线性结构，为了高效的实现在树上的路径查询、路径修改操作，基本做法是将树按照某种方式剖成若干条链，再将这些链按照顺序组成数组，最后在数组上采用线段树等手段实现操作。 考虑如下一棵树： 可以把它剖成6条链，分别是A
2017-01-02 13:51:09
2200
原创 hdu3483——利用递推公式得到系数矩阵再进行快速幂
系数矩阵的推导过程请看《根据递推公式构造系数矩阵用于快速幂》。import java.util.Scanner;public class Main{ static long [][] C = new long [51][51];//Pascal's triangle static Matrix [] Matrices = new Matrix[51]; public sta
2016-08-16 22:13:33
577
原创 根据递推公式构造系数矩阵用于快速幂
简单的例子FibonacciFibonacci数列考虑FibonacciFibonacci数列， F(n)=F(n−1)+F(n−2)F(n)=F(n-1)+F(n-2) 将右边两项看做是一个列向量的形式，令 Xn−1={Fn−1Fn−2}X_{n-1}=\left\{\begin{matrix}F_{n-1}\\F_{n-2}\end{matrix}\right\} 很容易得到XnX_n的
2016-08-16 21:51:59
5813
2
原创 自动机初步之NFA及ACM中常见的自动机
NFA也是自动机的一种，与DFA对应。对于DFA来说，在指定状态，经过指定字母，会到达唯一确定的状态。对于NFA而言，在指定状态经过指定字母，到达的是一个状态的集合。换种说法，经过某个字母到达的状态不是唯一确定的，候选集合中的状态都存在可能。特别的，NFA存在ϵ{\epsilon}边，即不需任何字母即可从一个状态去往另一个状态。考虑仅由字母{a,b}\{a,b\}构成的字符串。要求字母bb必须连续出
2016-08-02 22:09:24
3190
3
原创 自动机初步之DFA
自动机是一种非常有力的工具，其完备的理论可以参考编译原理或者形式语言与自动机等相关教材。从某种定义角度而言，图灵机也是自动机的一种。这里提到的自动机特指有限状态自动机，简称为FA，根据状态转移的性质又分为确定的自动机（DFA）和非确定的自动机（NFA）。FA的表达能力等价于正规表达式或者正规文法。FA可以看做是一个有向带权图，图的顶点集合称为自动机的状态集合，图的权值集合为自动机的字母集合，图的边代
2016-08-02 16:12:36
5184
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人