题目链接 1002. Phone Numbers 题意 现实生活中，你时常会遇到许多许多而且越来越长的电话号码。你需要记住这类型的号码。例如按下面的图示，把字母划分到特定的数字上，是一种很容易就能把数字记住的方法： 1 ij 2 abc 3 def 4 gh 5 kl 6 mn 7 prs 8 tuv 9 wxy 0 oqz 按这种方法：每个字或一个词组可被代替

题目链接： 1029 遍历问题 题意题目描述 Description 我们都很熟悉二叉树的前序、中序、后序遍历，在数据结构中常提出这样的问题：已知一棵二叉树的前序和中序遍历，求它的后序遍历，相应的，已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序，你却不能确定其中序遍历序列，考虑如下图中的几棵二叉树： 所有这些二叉树都有着相同的前序遍历和后序

题目链接： 1012: [JSOI2008]最大数maxnumber 题意 中文题，点链接看吧，就不copy了。 思路 打眼一看立刻就想到线段树，但本题的区间最值查找每次都是在查后L位，感觉用线段树有些大材小用了。再仔细想想，发现，如果倒数第i个比倒数第i+1个数小，那么第i个数是没有用的，任意查询的最值都不会是它，因为查的是后L个嘛。所以呢，我们我以维护一个栈，每次添加新元素时，将其与栈顶

前言 改了又改，查了又查，想了又想，我真的不知道怎样让它再聪明了，大多时候走的都是正确的，但偶尔会蹦出那么一步臭棋，全盘皆输。 **希望有相关经验的道友看到后可以指出原因和不足。 ** 效果图 按钮什么的还未完成，只是能实现正常的下棋了。 完成过程UI部分 本来准备找张棋盘图片做背景，想了下我们还有人机界面课呢，权当复习一下javaGUI了，事实上过程比我想象中简单许多。现在界面部分输出游戏结

前言 关于快慢指针找环入口的这个问题，之前巴特跟我聊到过，印象比较深，今晚看学长在做的面试题，里面就出现了这个小知识。发现有些东西不经意间就会用到，于是便出现此文。以后要努力做到善于总结，乐于总结。 概念 快慢指针，所谓的快慢，就是指 ** 指针每次移动的步长 ** ，通常使快指针每次向前移动两步，慢指针每次向前移动一步。 判断链表环及找环入口操作 从链表头节点开始，快慢指针同时开始移动，快指

原理 现在有两个数组a, b，都是有序的，要你将他们合并成一个数组，你会怎么做呢，当然不会直接合并再排序了，而是如下操作 1. 设两标志指针分别指向a,b的首元素。 2. 比较当前a,b当前首位元素，选择较小的加入临时数组t，相应的标志指针后移。 3. 重复2过程，知道a.b任一方已全部加入t，然后到步骤4 4. 将未完全加入的数组剩余元素全部加入。 这样合并两个数组的时间复杂度是O(len(

ps：今天和战友聊到矩阵快速幂，想到前几天学长推荐去刷矩阵专题，挑了其中唯一一道中文题，没想到越过山却被河挡住去路。。。题目链接： [kuangbin带你飞]专题十九 矩阵 R - M斐波那契数列 Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u 题意Description M斐波那

ps 昨晚看了紫书上的最优配对问题，对于上面没有对i判断就直接取异或操作百思不得解，本想今天问学长，百度了下，才知道那里是作者写错了，唉，有点唏嘘，学的越多，对待权威越不敢坚信自己了。。。 题意 空间里有n个点P0,P1,…,Pn-1，你的任务是把它们配成n/2对（n是偶数），使得每个点恰好在一个点对中。所有点对中两点的距离之和应尽量小。 思路 因为是对集合进行配对，自然需要记录当前集合的状态

** 题目链接 ** ： [kuangbin带你飞]专题十五 数位DP D - Bomb 题意 输入n,m，求n～m范围内的所有数字中，分别输出0～9出现的总数是多少。 思路 和 POJ 3286 How many 0’s? (数位dp) 的思路基本是一样的，只是略有区别。0和1～9要分开处理，是因为前缀0的问题。因为当某一位取0时，前面部分的数是不能为0的，而取1～9是可以前面为0的。

** 题目链接 ** ： POJ 3286 How many 0’s? 题意 输入n,m，求n～m范围内的所有数字中，0出现的总数是多少。 思路 用2034做个例子。枚举0在个十百千位上出现的次数个：个位为0时，后面不需要考虑，只需考虑前面，因为0比4小，所以前面即使取到最大也不会过限，所以前面可以是1~203(因为当前位是0，所以前面不能是0)。一共203种。十：十位为0时，前面取1～20

** 题目链接 ** ： UVA - 10003 Cutting Sticks 题意 给一长度为L的棍子，和n个切割点，每次切割的代价为当前的棍子的长度，问最少的总切割代价是多少。 思路 典型的区间dpdp[i][j] = min(dp[i][k]+dp[k][j]+a[j]-a[i]) |i 代码递推#include <iostream> #include <algor

** 题目链接 ** ： [kuangbin带你飞]专题十五 数位DP F - Balanced Number 题意 给定区间[a,b]，求区间内平衡数的个数。所谓平衡数即有一位做平衡点，左右两边数字的力矩想等。 思路 遍历每一位做为平衡点，进行搜索，sum保存数字乘以距离的和，若sum为0，则说明平衡。要注意因为遍历了len次，所以0多加了len－1次。还有个小技巧是当sum<0时就

** 题目链接 ** ： [kuangbin带你飞]专题十五 数位DP J - 吉哥系列故事――恨7不成妻 题意Time Limit:500MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u Description 单身!依然单身！吉哥依然单身！DS级码农吉哥依然单身！所以，他生平最恨情人节，不管是214还是77，他都讨厌！ 吉

** 题目链接 ** ： [kuangbin带你飞]专题七 线段树 C - A Simple Problem with Integers 题意 给定n个数及m个操作。操作分两种：1. C a b c，表示对区间ab整体全部加上c2. Q a b ，对区间ab求和并输出。 思路 看到段更新，第一反应是给点更新外面加个for，但显然不可行。了解到有个Lazy思想，即 ** 记录每一个线段树节点的

** 题目链接 ** ： [kuangbin带你飞]专题七 线段树 B - I Hate It Time Limit:3000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u 题意Description 很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。这让很多学生很反感。

** 题目链接 ** ： [kuangbin带你飞]专题七 线段树 A - 敌兵布阵 前言 最近看到有些大牛代码里有句** ios_base::sync_with_stdio(false); **不免好奇，百度了下，才知道是可以加快io操作时间。cin，cout速度慢，是因为先把要输出的东西存入缓冲区，再输出，导致效率降低，而这段ios_base::sync_with_stdio(false)

** 题目链接 ** ： [kuangbin带你飞]专题三 Dancing Links D - 神龙的难题 题意Description 这是个剑与魔法的世界.英雄和魔物同在,动荡和安定并存.但总的来说,库尔特王国是个安宁的国家,人民安居乐业,魔物也比较少.但是.总有一些魔物不时会进入城市附近,干扰人民的生活.就要有一些人出来守护居民们不被魔物侵害.魔法使艾米莉就是这样的一个人.她骑着她的坐骑,

** 题目链接 ** ： [kuangbin带你飞]专题三 Dancing Links B - Treasure Map 题意 给一矩形和k个小矩形，问选取最小数量为多少的小矩形可以对大矩形进行精确覆盖。 思路 仍然是个模版题，把二维的nm的大矩形看作是一维的nm的一条线。k个小矩形同理，那么就转化成01矩阵精确覆盖的问题了。 代码#include <iostream> #in

** 题目链接 ** ： [kuangbin带你飞]专题三 Dancing Links A - Exact cover 题意 给定一01矩阵，问是否能够精确覆盖(就是选取任意行，这些行的1所在的列互不冲突且完整覆盖所有列)，若有输出行号(要按递增顺序输出)，否则输出NO。 思路ps：两个礼拜前大略看了下舞蹈链(虽然英文名听起来更高端，但还是更喜欢它的中文名字)，很精妙但也让人一看就惰性必生不

** 题目链接 ** ： [kuangbin带你飞]专题十六 KMP & 扩展KMP & Manacher V - 吉哥系列故事――完美队形II 题意 吉哥又想出了一个新的完美队形游戏！假设有n个人按顺序站在他的面前，他们的身高分别是h[1], h[2] …h[n]，吉哥希望从中挑出一些人，让这些人形成一个新的队形，新的队形若满足以下三点要求，则就是新的完美队形： 1、