《对弈程序基本技术》专题 ** Alpha-Beta ** 搜索 Bruce Moreland / 文 ** 最小 ** ** - ** ** 最大的问题 **Alpha-Beta 同“ 最小 - 最大 ”非常相似，事实上只多了一条额外的语句。最小最大运行时要检查整个博弈树，然后尽可能选择最好的线路。这是非常好理解的，但效率非常低。每次搜索更深一层时，树的大小就呈指数式增长。 通常一个

《对弈程序基本技术》专题 最小 - 最大搜索 Bruce Moreland / 文 ** 从浅显的地方开始 **在国际象棋里，双方棋手都知道每个棋子在哪里，他们轮流走并且可以走任何合理的着法。下棋的目的就是将死对方，或者避免被将死，或者有时争取和棋是最好的选择。 国际象棋程序通过使用“搜索”函数来寻找着法。搜索函数获得棋局信息，然后寻找对于程序一方来说最好的着法。 一个浅显的搜索函数用“树状

题目链接： [ kuangbin带你飞 专题六 最小生成树 K - The Unique MST](http://acm.hust.edu.cn/vjudge/contest/view.action?cid=66965#problem/K) 题意 给定一无向图，判断最小生成树是否唯一。 思路 先求出最小生成树，记录结果，依次删除树中各边，再求最小生成树，看与最初结果是否相同，若相同则不唯一 代

题目链接： [ kuangbin带你飞 专题六 最小生成树J - Borg Maze](http://acm.hust.edu.cn/vjudge/contest/view.action?cid=66965#problem/J) 题意 题目好难懂啊，英文题读起来好痛苦。大概意思就是，给定一起点，和n个点有外星人，你有一个搜索集团，让你去同化这些外星人。在起点和每同化一个外星人时，该集团可能会分裂成

题目链接： [ kuangbin带你飞 专题六 最小生成树 H - Highways](http://acm.hust.edu.cn/vjudge/contest/view.action?cid=66965#problem/H) 题意 n个城市，需要修高速公路，将所有城市联通，已经修建好了m条高速公路，剩下未修的公路，怎样修能够使长度最小，输出这些公路的左右两端城市 思路 典型的最小生成树，因为

题目链接： [ kuangbin带你飞 专题六 最小生成树 G - Arctic Network](http://acm.hust.edu.cn/vjudge/contest/view.action?cid=66965#problem/G) 题意 n个前哨，s个卫星频道。任意两个前哨可以通过卫星频道或者无线电来通信，前者无视距离，后者最大距离为d，与无线电装置的能量相关。每个前哨的无线电能量都相同

题目链接： [ kuangbin带你飞 专题六 最小生成树 F - Truck History](http://acm.hust.edu.cn/vjudge/contest/view.action?cid=66965#problem/F) 题意 英语不好，看题好费劲，大概意思是：一个汽车公司每个卡车都用一个长度为7的字符串来表示，每个卡车之间都可以进行派生，而且派生会有代价A ： aaaaaaaB

压缩原理及步骤&&压缩比的计算压缩原理及步骤压缩的第一步： 将一个文件以各个字符出现的次数为权值建立哈夫曼树，这样每个字符可以用 ** _ 从树根到该字符所在到叶子节点的路径 _ ** 来表示。(左为0,右为1) 压缩第二步： 哈夫曼编码有一个很重要的特性： ** _ 每个字符编码不会成为另一个编码的前缀 _ **。这个特性保证了即使我们把不同长度的编码存在一起，仍然也可以把它们

很久很久以前，有一群人，他们决定用8个可以开合的晶体管来组合成不同的状态，以表示世界上的万物。他们认为8个开关状态作为原子单位很好，于是他们把这称为”字节”。 再后来，他们又做了一些可以处理这些字节的机器，机器开动了，可以用字节来组合出更多的状态，状态开始变来变去。他们看到这样是好的，于是它们就这机器称为”计算机”。 开始计算机只在美国用。八位的字节一共可以组合出256（2的8次方）种不同的状态。

** _ 题外话 _ ** 大数除法无疑是大数操作里最麻烦的一项，写大数不实现除法无异于画龙无鳞。 ** _ 思路 _ ** 最原始的，脑子最容易冒出来的思路，是一下一下的减，看能累计减多少次，最后的总次数就是结果，但这样的效率实在太慢。但我们可以一次性减去除数的1，10，100，1000倍，只要它在当前倍数下比被除数小。例如 1210 3 ，121大于300，我们直接剪去300，给结果加1

** _ 思路 _ ** 第i位数乘第j位数，乘积是第i+j位数(从0开始)如123＊456乘积各位数为个位 3＊6十位 2＊6 ＋ 3＊5百位 2＊5 ＋ 1＊6 ＋ 3＊4千位 1＊5 ＋ 2＊4万位 1＊4然后从后往前，取余更新。 ** _ 代码 _ ** #include <stdio.h> #include <iostream> #include <ve

** _ 题外话 _ ** 一直想好好的把所有大数操作好好敲一遍，都止于惰性，碰到一个要用到大数的题，索性就由此开始吧。大数加法写过太多次了，含负数的第一次写，用运算符重载的形式实现，挺有意思。 ** _ 思路 _ ** 当两数符号相同时，相加即可，重点内容结果符号不变。不同时，需要对两数的绝对值进行比较，结果符号与绝对值大的数符号相同，然后用大的减去小的。 ** _ 代码 _ ** #i

1454 升排列 题目来源： CodeForces 基准时间限制：1 秒 空间限制：131072 KB 分值: 80 难度：5级算法题 收藏 关注 定义长度为n的排列为数组 p = [ p 1 , p 2 , . . . , p n ]，这个数组包含n个整数，他们都在1到n之间，并且两两不同。我们说这个排列把1映射到 p 1 ，2映射到 p

** _ 题目链接 _ ** ： 消灭兔子 ** _ 题目大意 _ ** n个兔子，每个兔子都有一个血量b[i]m种箭(每种各一支)，每种箭都有伤害值d[i]和价格p[i]每个兔子只能被射一次，伤害值大于血量则死，每种箭只能用一次问杀死所有兔子需要的最小价格为多少，若不能杀死，则No Solutionm,n小于50000) ** _ 思路 _ ** 典型的贪心，每个兔子只能射一次，所以只

题目链接： 最高的奖励 ** _ 题目大意 _ ** 有N个任务，每个任务有一个最晚结束时间以及一个对应的奖励。在结束时间之前完成该任务，就可以获得对应的奖励。完成每一个任务所需的时间都是1个单位时间。有时候完成所有任务是不可能的，因为时间上可能会有冲突，这需要你来取舍。求能够获得的最高奖励。Input第1行：一个数N，表示任务的数量(2 <= N <= 50000)第2 - N

题目链接 最长递增子序列的题做过不少，让求数量的还是第一次，O(n^2)的代码很好写，但数据范围50000，故无情超时，想了很久，总算有所得。 ** _ 时间: O(nlog(n)) 空间: O(2*n) _ ** ** _ 思路 _ **O(n^2)的思路中，每次求以第i个数结尾的最大长度和记录总数都要对前i－1个数进行遍历比较，如果能把这个比较过程转化为对前i项对求和，就可以用树状数组或线

以前所接触过的最短路径算法是dijkstra或floyd之类的，都是在已知每两点之间距离的情况下求最短路的。 那么想一下这样的案例 给你一个地图，类似于迷宫一样，中间有些障碍物，再给定起点终点，求该两点间最短路，显然，上述两种算法就不适用了，因为提到的迷宫，我们可能会很容易想到广搜bfs，但一次bfs下来实际上求出了起点到所有点的最短路径，但我们只想知道它与终点间的最短路径，也就是说这个方案里有

石子归并以前做过好几次，是经典划分型dp题之一，一直用的O(n3)的正常dp方法，也从未想过该怎么去优化它。 直到昨天做这道题，n的范围由往常的100改为了1000，老方法一直超时，苦不堪言，搜到有个四边形不等式的优化方法，看帖子，画式子，拉着学长帮忙推导，总算是大概弄明白了一点。 dp(i,j) = min(dp(i,k)+ dp(k+1,j) ) + w(i,j);(i < j, i

题目链接： [ 迷宫游戏](http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1459) ** _ 题目 _ ** 你来到一个迷宫前。该迷宫由若干个房间组成，每个房间都有一个得分，第一次进入这个房间，你就可以得到这个分数。还有若干双向道路连结这些房间，你沿着这些道路从一个房间走到另外一个房间需要一些时间。游戏规定了你的起点

G - 免费馅饼 ** Time Limit: ** 1000 MS ** Memory Limit: ** 32768 KB ** 64bit IO Format: ** %I64d & %I64u Submit Status Practice HDU 1176 Description 都说天上不会掉馅饼，但有一天gameboy正走在回家的小径上，忽然天上掉下大把大把的