sun897949163-CSDN博客

原创 ????(1):???(???)

?????????,???????????????[a,b]?a,b??????????????????????(???1)????????????????[a,b],??????????[a,(a+b)/2],?????????[(a+b)/2+1,b](??????)???:1.????????????????2.???????1,??????3.???????????[a,b],?????

2016-08-02 10:49:24 638

原创搜索（4）：A*

启发式搜索算法(A算法)先来回忆BFS算法在BFS中，每当我们找到一个节点，我们就将这个节点压入队列中，然后每次开始搜索是我们就从队列中拿出第一个元素，继续开始上述的操作。但是这里有一个问题，虽然这里从对头拿元素这个操作可以满足当前最短这个条件但在队列中有多个长度相同的当前最短的边的时候，队列只能按照压入的顺序弹出，不能判断这几个当前最短点中的优劣性为此我们就引入了A*算法，对每一步搜

2016-08-01 11:54:06 769

原创搜索（3）：重复性剪枝（poj1011）

POJ 1011在民国某年，少林寺被军阀炮轰，这些棍子被炸成 N 节长度各异的小木棒战火过后，少林方丈想要用这些木棒拼回原来的棍子可他记不得原来到底有几根棍子了，只知道古人比较矮，且为了携带方便，棍子一定比较短他想知道这些棍子最短可能有多短分析· ·尝试 (枚举) 什么?枚举所有可能的棍子长度从最长的那根木棒的长度一直枚举到木棒长度总和的一半对每个假设的棍子长度，试试看能否拼齐若干根棍子· ·

2016-08-01 09:52:52 678

原创搜索（2）：估值型剪枝

总时间限制: 1000ms 内存限制: 65536kB 描述 “我是要成为海贼王的男人！”，路飞一边喊着这样的口号，一边和他的伙伴们一起踏上了伟大航路的艰险历程。路飞他们伟大航路行程的起点是罗格镇，终点是拉夫德鲁（那里藏匿着“唯一的大秘宝”——ONE PIECE）。而航程中间，则是各式各样的岛屿。因为伟大航路上的气候十分异常，所以来往任意两个岛屿之间的时间差别很大，从A岛到B岛可能需要1天，

2016-08-01 09:18:10 474

原创搜索（1）：剪枝

POJ 1190要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。设从下往上数第i(1 <= i <= M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i < M时，要求Ri > Ri+1且Hi > Hi+1。由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。令Q = Sπ 请编程对给出的N和M，找出蛋糕的制作方案（适当的Ri和Hi的值），使S

2016-08-01 09:05:17 600

Map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。这里说下map内部数据的组织，map内部自建一颗红黑树(一种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的，后边我们会见识到有序

2016-08-01 08:28:00 453

原创题解：整数划分问题（DP）

总时间限制: 200ms 内存限制: 65536kB 描述将正整数n 表示成一系列正整数之和，n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ，k>=1 。正整数n 的这种表示称为正整数n 的划分。输入标准的输入包含若干组测试数据。每组测试数据是一行输入数据,包括两个整数N 和 K。 (0 < N <= 50, 0 < K <= N)输出对于每组测试数据，输出

2016-07-31 21:11:16 3995

原创动态规划（5）：状态压缩

总括有时，状态相当复杂，看上去需要很多空间，比如一个数组才能表示一个状态，那么就需要对状态进行某种编码，进行压缩表示。比如：状态和某个集合有关，集合里可以有一些元素，没有另一些元素，那么就可以用一个整数表示该集合，每个元素对应于一个bit，有该元素，则该bit就是1。例题：bailian：海贼王之伟大航路描述 “我是要成为海贼王的男人！”，路飞一边喊着这样的口号，一边和他的伙伴们一起踏上了伟大航

2016-07-31 20:40:23 747

原创动态规划（4）：消除后效性

无后效性：这是DP中最重要的一点，他要求每个子问题的决策不能对后面其他未解决的问题产影响，如果产生就无法保证决策的最优性，这就是无后效性。往往需要我们找到一个合适的状态。上述的问题还有另外一个描述方式，对于后一个节点的判断不能以前面节点的路径为依据。例：POJ 1037 一个美妙的栅栏N 个木棒, 长度分别为1, 2, …, N.构成美妙的栅栏要求1.除了两端的木棒外，每一跟木棒，要么比它左

2016-07-31 20:17:51 4645 1

原创动态规划（3）：熟练度练习（POJ 1458、最佳加法表达式、bailian2755、POJ3624、bailian1088）

最长公共子序列Language:DefaultCommon SubsequenceTime Limit: 1000MSMemory Limit: 10000KTotal Submissions: 47599Accepted: 19562DescriptionA subsequence of a given sequence is the given sequence with some elemen

2016-07-31 14:49:06 3083 1

原创动态规划(2)：动态规划的三种形式

例：数字三角形（POJ 1163）Language:DefaultThe TriangleTime Limit: 1000MSMemory Limit: 10000KTotal Submissions: 45053Accepted: 27208Description73 88 1 02 7 4 44 5 2 6 5(Figure 1)Figure 1 show

2016-07-31 11:41:51 2542

原创动态规划(1)：基本思路以及步骤

基本思想动态规划是针对一类求最优解的问题的算法，其核心是将一个问题分解成为若干个子问题（这里对应下文的子问题使用条件），部分类似于分治的思想（不懂得可以参考归并排序），通过求每一次的最优决策，来得到一个最优解。在这里最重要的就是子问题的思想。另一种理解方式数是DP的核心是加法原理（下文的人人为我形递归）和乘法原理（下文的我为人人形递归），通过这两个原理，在当状态的前有限多个状态中找到最优

2016-07-31 11:05:11 28199 6

原创理论： STL（2）： bitset

有些程序要处理二进制位的有序集，每个位可能包含的是0（关）或1（开）的值。位是用来保存一组项或条件的yes/no信息（有时也称标志）的简洁方法。标准库提供了bitset类使得处理位集合更容易一些。要使用bitset类就必须要包含相关的头文件。在本书提供的例子中，假设都使用了std::bitset的using声明：＃i nclude using std::bitset;3.5.1 bitset的定义

2016-07-21 09:07:09 590

原创理论：数论（4）：素数举例

有多少个素数？在很久之前欧拉在定理中说“存在比任何给定的素数集合更多的素数”。现在我们来证明这个结论：假设只有有限多个素数，比如K个， 2，3，5，7，……，Pk。然后欧拉说：我们令 .设K个素数没有一个能整除M，因为他们都能整除M-1，于是必定有另一个素数整除M，或许M本身就是个素数，这两种可能都与我们假设仅有2，3，5，7……，Pk，这K个素数相矛盾。欧几里得的证明提醒我们使用如下

2016-07-14 19:44:20 1497

原创理论：数论（3）：素数基础

素数定义正整数1只有一个正整数因子，任意其他的正整数至少有两个正整数因子，因为它一定可以被1和他本身整除。只有两个正因子的整数称之为素数。素数的性质定义2.1：素数是大于1的正整数，并且除了1和他本身之外不崩被其他正整数整除，大于1的非素数称之为合数素数具有以下的性质：（1）.a>1是合数，当且仅当a = bc，其中 1 < b < a, 1 < c < a; （2）.合数必有素

2016-07-13 10:52:59 2258

原创题解： poj 1061 nefu 84(拓展欧几里得)

POJ1061Language:Default青蛙的约会Time Limit: 1000MSMemory Limit: 10000KTotal Submissions: 105002Accepted: 20595Description两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一

2016-07-13 08:12:39 6065 1

原创理论：数论（2）：拓展欧几里得算法及其证明

拓展欧几里得算法算法描述定义1.7 .算法证明记,对a，b使用欧几里得定理得： . 在这里我们代入，将上式改写成：. 我们将上式逐一向前代回，就将得到rk关于a和b的线性组合。 .算法推论拉梅定理：用欧几里得算法计算两个正整数的驻地啊公因子时，所需的除法次数不会超过连个整数中较小的那个十进制数的5倍 · 拉梅定理推论：求两个正整数a，b（a>b）的最大公因子需要O（log2a3）

2016-07-13 06:49:24 1396

原创题解：两仪剑法（nefu116）（欧几里得算法）

两仪剑法 Problem:116Time Limit:1000msMemory Limit:65536KDescription 两仪剑法是武当派武功的高级功夫，且必须2个人配合使用威力才大。同时该剑法招数变化太快、太多。设武当弟子甲招数变化周期为M，武当弟子乙招数变化周期为N，两弟子同时使用该剑法，当2人恰好同时达到招数变化周期结束时，威力最大，此时能将邪教妖人置于死地。请你计算威力最大时，每人

2016-07-12 21:38:24 1205

原创理论：数论（1）：整除、gcd以及lcm

整除整除的性质设a, b是两个整数，并且b ≠ 0. 如果存在整数c，使得 a = b * c ，则称a被b整除，或者b整除a，记作b |a（这里是a 被 b整除， a >= b）此时又称a是b的倍数， b是a的因子。如果b不整除a，记作 ·整除基本定义定义1.1：如果n被2除的余数为 0，则对于某个整数k，有n = 2k，我们称n为偶数；而如果n被2除的余数为1，我们则对

2016-07-12 20:54:41 2934 1

原创 c++考试复习（3）：函数基础

函数的定义、声明和调用与C语言基本相同1.函数声明和首部的不同（1）.两者的函数名、函数类型完全相同。（2）.两者中形参的数量、次序、类型完全相同。（3）.函数声明中的形参可以省略名称，只声明形参类型，而函数首部不行（4）.函数声明是语句，而函数首部不是（5）.如果函数定义在调用他的函数前时，函数声明不是必须的。2.传值调用（1）.形参在调用之前不占用储存空间。只有

2016-06-27 01:45:25 815

原创 C++考试复习（2）：c++标识符和命名规则

字符集C++的字符集有下面的字符集组成：（1）52个大小写英文字母；（2）10个数字字符（3）其他字符：空格！ # % ……＆ * _等等标识符含义：由若干个字符构成的具有一定意义的最小单词单元，通常用来定义函数名、类名、对象名、变量名、常量名等。注意：（1）标识符区分大小写： Name、name 是两个不同的标识符（2）标识符的长度是不受限制的，但是在某些系统上

2016-06-27 01:28:49 2575

原创 C++考试复习（1）：面向对象程序设计

结构化程序设计方法定义：任何程序都可以由顺序、选择、循环三种基本结构来表示。优点： 1.自顶而下，逐步细化。 2.模块化设计 3.结构化编码 4分块编程，便于阅读、理解、调试、修改。 `面向对象程序设计方法程序 = 类 + 继承 + 对象 + 消息通信 `面向对象的基本特点抽象找出对象的公共性质，并加以提炼和描述封装把对象属性和操作合成一个独立的系统，

2016-06-27 00:51:17 1403

原创数据结构：链表（指针+游标）

指针实现链表没什么好废话的，注释在代码中#include<cstdio>#include<cstring>#include<algorithm>using namespace std;typedef int ElementType;//元素类型typedef node* PtrToNode;//指向元素的指针typedef PtrToNode List;//链表的表头的指针typedef

2016-06-19 21:03:28 2023

原创时间复杂度：理论定义

函数的渐近增长：给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有的n > N，f(n)总是比g(n)大，那么，我们说f(n)的增长渐近快于g(n)。算法时间复杂度定义在进行算法分析时，语句总的执行次数T(n）是关于问题规模n的函数，进而分析T(n）随n的变化情况并确定T(n）的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n)=O(f(n))。它表示随问题规模n的增

2016-06-17 17:24:03 5587

原创 c++学习（x.x）总括

第一章文件头及声明关于extern使用extern 声明而不定义，它是说明变量定义在程序其他地方全局不初始化的extern int i; 是声明不定义；只要声明并且有初始化式，那么就是定义；带有extern且有初始化的声明（也是定义），比如extern float fval =2.34; 这种必须放在函数外面，否则出错文件B要访问另外一个文件A中定义的变量，那么在B中必须先extern声明一下，并

2016-05-02 21:28:59 3932

原创 c++学习（2.3）引用

复合类型是指基于其他类型定义的类型。 c++语言有几种复合类型，这里将介绍其中的两种：引用和指针。引用基础引用在c++11版本中引入了“右值引用”，关于这个我们在这里先不讲解。这种引用主要作用于内置类型。严格的来说，我们使用术语“引用”的时候，默认的就是左值引用。引用就像是为对象起了另外一个名字，引用类型引用另外一种类型。我们通过将声明写成&d的形式来定义引用，其中d是声明

2016-04-28 12:20:27 1837

原创 c++学习（2.2）变量

2.2.1 变量定义变量定义的基本形式是：首先是类型说明符，随后紧跟着一个或者多个变量名组成的列标，其中变量名以逗号分隔，最后以分号结束。列表中，每个变量名的类型都有特定的类型说明符决定。定义时，还可以给一个或者多个变量赋初值。int sum = 0, valus, units_sold = 0;Sale_item item;std::string book{"asdfghj

2016-04-02 11:16:03 946

原创理论：图论（14）：最大强连通图算法 tarjan

最大强连通图定义在有向图G中，如果两个顶点间至少存在一条路径，称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。非强连通图有向图的极大强连通子图，称为强连通分量(strongly connected components)。朴素算法根据定义我们不难想到，对同一张图同时进行正反两次遍历，对两次的遍历结果取交集，这里得到的便是强连通图。

2016-03-31 20:47:35 12803

原创数据结构：链表基础

3.1.1表的简单数组实现对表的所有操作都可以通过数组来实现。虽然数组是动态指定的，但是还是需要对表的大小进行估值。通常需要估计的大一些，从而会造成空间的浪费。这是严重的局限，特别是在存在许多未知大小的表的情况下。数组实现的printlist和find正如所预期的那样，以线性的时间来执行，而findth这花费数倍的时间。然而插入和删除的操作花费的时间是高昂的。例如在位置O插入首先需

2016-03-31 17:37:52 687

原创欧拉函数o(n)求素数

欧拉函数的定义: E（N）= ( 区间[1,N-1] 中与 N 互质的整数个数).　　对于积性函数 F（X*Y），当且仅当 GCD（X，Y）= 1 时， F（X*Y） = F（X）* F（Y）　　任意整数可因式分解为如下形式：　　　其中( p1, p2 … pk 为质数, ei 为次数 )　　　所以　　　　　　因为欧拉函数 E（X）为积性函数，所以　　　　　　对于，我

2016-03-30 22:00:54 3288

原创 C++学习（2.1）：基本内置类型

2.1 基本内置类型C++ 中定义了一套包括算数类型（arithmetic type）和空类型（void）在内的基本数据类型。其中数据类型包含了字符、整型数、浮点数和布尔值。空类型不对应具体的值，仅仅用于一些特定的场合，例如最常见的是，当函数不返回任何值得时候，使用void来作为函数返回值类型。2.1.1 算数类型·算术类型分为两类，整型（integral type）和浮点型。

2016-03-29 20:24:02 1463

转载理论：博弈4 ：威佐夫博奕（Wythoff Game）

威佐夫博奕（Wythoff Game）个人理解：有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。这种情况下是颇为复杂的。我们用（ak，bk）（ak ≤ bk ,k=0，1，2，…,n)表示两堆物品的数量并称其为局势，如果甲面对（0，0），那么

2016-01-30 20:41:32 1015

原创理论：博弈3： Nim博弈

Nim博弈原型个人定义：有n堆石头，每ai颗石头。 Alice和Bob分别从非空的石头堆中取走至少一颗石子。Alice先取，取光所有的石头即为获胜。当双方都采取最优策略的时候，谁会获胜？严谨定义：有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。

2016-01-30 20:22:08 722

原创理论：博弈2：巴什博奕（Bash Game）

巴什博奕基础情形只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。如果n = m + 1；我们假设第一个人拿走了k个，还剩下 m + 1 - k。因为1<=（m + 1 - k）<= m, 所以，剩下的部分一定可以被第二个人一次性取走。现在我们将上述规律加一推广：如果n=（m+1）r+s（r∈ N，s<= m)；那么先取者要拿走s个

2016-01-30 00:08:15 4143

原创理论：博弈1：术语讲解

博弈概述博弈论又被称之为对策论（game thery），是研究独有斗争或者竞争性质现象的理论和方法，它既是线代数学的一个新分支，也是运筹学的一个重要学科。博弈论是指在某个个人或是组织，面对一定的环境条件，在一定的规则约束下，依靠说掌握的信息，从各自选择的行为或者是策略进行选择并加以实施，并从格子去的相应结果或收益的过程。博弈术语 P-position N-position定义P-po

2016-01-27 19:13:06 1221

原创题解：POJ 3279 Fliptile （BFS）

D - Fliptile Time Limit:2000MS Memory Limit:65536KB 64bit IO Format:%I64d &%I64u Description Farmer John knows that an intellectually satisfied cow is a happy cow who will gi

2016-01-25 21:56:27 1406

原创题解： HDU 4004 The Frog's Games （二分搜索）

The Frog’s Games Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others) Total Submission(s): 5157 Accepted Submission(s): 2513 Problem Description The an

2016-01-25 21:35:18 847

原创理论：二分查找（2）：假定一个解并判断是否可行

例题有N条绳子，他们的长度分别为Li。如果他们中切割出k条长度相同的绳子的话，这K条绳子每条最长能有多长？答案精确到小数点后两位。二分查找分析这个问题用二分查找可以非常容易的求得答。然我们套用二分搜索的模型试着解答这个问题。令：条件C（x）：= 可以得到K条程度为X的绳子则问题就变成了满足c（x）条件的最大x的问题。在初始化区间的时候，只需要使用充分大的数INF作为上界即可。（设置一

2016-01-23 10:38:06 827

原创理论：二分查找（1）：基础样例

概述二分搜索法，是通过不断缩小接的可能存在的范围，从而求得问题最优解的方法。在程序竞赛中，经常可以见到二分搜索算法和其他算法结合的题目。接下来给大家介绍经典的二分搜索的题目。基础样式讲解例题： lower_bound函数手动实现；给定一个非严格单调的递增数列{a0, a1, a2…… an-2, an-1}和一个整数K。求满足 ai >= k 条件的最小的i。在不存在的

2016-01-23 10:02:45 446

转载理论： STL（1）： set

SET 集合百度百科中说集合中的元素有三个特征： 1.确定性（集合中的元素必须是确定的） 2.互异性（集合中的元素互不相同。例如：集合A={1，a}，则a不能等于1） 3.无序性（集合中的元素没有先后之分。）而STL中的集合set ,按照定义保证了元素的确定性，互异性，神奇的是其中的元素却是有序的！卓越的前辈们在c++里为我们封装好了set，只需要在头文件里#include<set>

2016-01-22 19:16:20 380

空空如也

空空如也