题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5001 题目大意：一个人随即从一个点出发，到达邻接点的概率相同，求出走d步都不会到达1~n点的每一项的概率（这里第一次随即取的点是要求的点也算到达过了） 记得去年网的时候最开始直接算到某一个点的概念然后减掉，然后发现样例过不了，才意识到这样会把多次到达的概率重复计算… f[i][j] 仍然表示i步走到j的概率，但是是对于每个点都求一遍，且对于点x求f[i][j]时一直保证不经过x，然后再算再减就好了 记得网赛的时候过了样例还wa了一发，然后我研究了半个多小时，之后偶然发现居然输出了-0.000000...

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5000 题目大意：有n种属性，每种属性的数值可以是0-T[i]，当一个人属性全部小于等于另一个人的属性时，小的那个人会被淘汰，问最多同时存在多少人 思路： 如果我们设sum为一个人的属性和，显而易见的， 人数最多的情况下这些人的sum是相同的，因为一个属性减少另一个属性一定需要增加，然后我们可以知道， sum=0的方案数和sum=ΣT[i]的方案数相同（一个），因此可以猜测到 sum=(ΣT[i])/2取得最大值（这是一个猜测，恩）。。。 问题转化为n个数，每个数可以取0-T[i]，和为(ΣT[i]...

题目链接：http://codeforces.com/problemset/problem/513/G2 题目大意：给定有n个数的一个数列，每次操作是等概率翻转一个区间，这样操作k次，求逆序数对个数的期望。 （1 ≤ n ≤ 30, 1 ≤ k ≤ 200） 思路： f[k][i][j] 表示k次翻转以后a[i] 在a[j] 前面的概率,初始化条件是 f[0][i][j] = 1 f[0][j][i] = 0 ( i < j ) 另外翻转区间 [i, j]的概率P = 1 / ( n * (n+1)  / 2) 由于 翻转时[i, j]内元素位置都会交换， 所以枚举翻转时的要循环枚举区间...

题目链接：http://codeforces.com/problemset/problem/507/C 题目大意： 高度为h的满二叉树，从根节点出发，按照"LRLRLRLR...."的方式往下走，走到第n个叶子结点结束。如果走到了非n的叶子结点，那么就跳过下一个指令，回溯然后按照指令继续走没有走过的结点。问到达第n个叶子结点之前，有多少个结点被走过。 思路： 先设置一个初始方向。 高度一层一层减小，判断所走方向的子树包不包含叶子节点n。 如果不包含，那么可以知道那个方向的子树的所有结点都会走一遍的，于是直接把这个树的节点数加上就行然后往另外一个方向走！ 如果包含，就往下走就...

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3812 题目大意：给出n个物品，每个物品有两种属性Wi,Ti，有q组查询，每组查询要求在n个物品中选出一些，并使得两个属性的和为Mi，Si。 思路：二维费用的背包，但是太大了会TLE或者mle…… 我们来观察一下状态 dp[i][j][k]表示使用前i个物品，是否可以凑出第一个属性j，第二个属性k， 注意第一个属性最多只有50，那么可以用一个二进制数来表示是否能凑出第一个属性的情况（unsigned long long）第i位为1表示可以凑出i。 然后再加上就地...

1854: [Scoi2010]游戏 Time Limit: 5 Sec   Memory Limit: 162 MB  Submit: 3683   Solved: 1398  [ Submit][ Status][ Discuss]  Description  lxhgww最近迷上了一款游戏，在游戏里，他拥有很多的装备，每种装备都有2个属性，这些属性的值用[1,10000]之间的数表示。当他使用某种装备时，他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。 游戏进行到最后，lxhgww遇到了终极boss，这个终极boss很奇怪，攻击他的装备所使用的属性值必须从1开始连续递增地攻击...

dp进阶之路(二)——线性dp（2） 例2：顺序对齐 题目大意：虑两个字符串右对齐的最佳解法。例如，有一个右对齐方案中字符串是aaddefgghc和adcdegh。第一行:第二行: 每一个数值匹配的位置值2分，一段连续的空格值-1分。所以总分是匹配点的2倍减去连续空格的段数，在上述给定的例子中，6个位置(A,D,D,E,G,H)匹配，三段空格，所以得分，注意，我们并不处罚左边的不匹配位置。若匹配的位置是两个不同的字符，则既不得分也不失分。请你写个程序找出最佳右对齐方案。（字符串长度小于等于50）思路：状态设计为：f[i][j]表示两个字符串的后i，j个字符对应的最大值转移分成三种情况：1.直接...

dp进阶之路(二)——线性dp（1） 一点说明 个人其实对线性dp、区间dp、背包dp这样的分法有所怀疑，因为有的题真的很难说清楚是哪一类，但不可否认的是，对于初学者入门来说，这样分是很愉快的也是很有用的。然而我需要提醒大家的是，不要被这些分类束缚了思路，“阵而后战,兵法之常,运用之妙,存乎一心”，如果分类的讲解就是阵法的话，做题就是运用，你需要做的是了解它并超越它！ 线性dp的经典例题有：最长上升子序列（LIS），最长公共子序列（LCS），最大子串和等等（本文的前置知识，需要大家自行学习）。在会了这几个题之后我们就可以来看今天的问题啦! 例1：三个串的最长公共子序列 题意： 给你三个串， 求...

dp进阶之路(一)——概念与方法 前言——一点说明 本系列底稿为本人所写的同名pdf，本次更新措辞上会有一些修改，为了方便大家提交代码，题目也会进行一些更换，但基本思路不变。在阅读过程当中遇到任何问题欢迎大家留言，发现bug也非常欢迎指正！ 基本思想 动态规划是多阶段决策问题求最优解的算法（有时也计数求和），其核心是将一个问题分解为若干步的若干子问题，每一阶段都进行最优决策，来得出一个最优解。（看起来非常像贪心——事实上他就是分步的贪心）。在我看来，dp的核心原理是分类加法原理和分步乘法原理，通过这两个原理，在当状态的上一个或几个状态中找出最优解求得当前状态， 而对于前一个或者几个状态有采用同...

有没有那么一道题，让你眼前一亮？      欢迎来推荐你喜欢的题目与大家分享~   推荐方式：     在题库中打开你要推荐的题目->题解->写题解  题解内需要包含题号，题目难度，推荐理由（选填），题目知识点，题意描述，解题思路+代码  在本贴下回复题解地址   注：推荐题目不接受每日一题和算法周周练已选题目或者近3个月内的比赛题目~     活动奖励：   对于每道符合格式的推荐题目，我们将发放10-50牛币奖励   如果推荐的题目被收纳为每日一题且题解也被采纳为每日一题的官方题解，我们将额外发放100牛币奖励    如果推荐的题目被收纳为每日一题但题解未被采纳，我们将额外发放...

一点说明 是的，你现在看到的是一个理论ac选手的题解，换句话说，本人并没有写过这个题的代码，只是靠嘴ac，但我会尽我所能把这个题的从一头雾水到找到解法的可能的思路说清楚，如果你觉得没ac不配写题解请点叉（其实我也觉得的自己没ac写题解怪怪的，但是实在是时间有限，为了多贡献出一点题解就这样吧）。如果有什么bug欢迎大家指正，如果有什么疑问也欢迎提出一起探讨哇！  题目描述 给定两个整数 l 和 r ，对于所有满足1 ≤ l ≤ x ≤ r ≤ 10^9 的 x ，把 x 的所有约数全部写下来。对于每个写下来的数，只保留最高位的那个数码。求1～9每个数码出现的次数。(1 ≤ l ≤ r ≤ 10^...

  “我要走了……”做了很久的心里建设之后，时夏终于还是在决定离开之后就对着学生们说出这句话，她虽然害怕别离，却不想拖到临走再告诉他们，他们是朋友不应该瞒着。然而在这之后她和孩子们都说了什么，她根本不记得了……   是夜，她有对着论坛上“什么样的人不适合当老师”的帖子，看着那条“没有控制欲的人不适合当老师”的高赞回答，久久的沉默……   一年多之前，时夏来到这所学校，带着一个不愿说也不可说的梦想——这里的算法竞赛啊，虽说这几年发展的不错，但是之前都不是很好，不论是中学还是大学。时夏在大学见证了其算法竞赛的艰难发展，并有幸参与其中。在这个过程中她付出了很多也收获了很多，她热爱算法竞赛给她带来的快...

可能用牛客的博客更小说的我还是第一个？大概在牛客博客更小说且在还在没更的时候就说要坑的我也是第一个？然而我确实有很多话想说却不知道怎么说出口，所以就这样啦！故事如有雷同纯属巧合，但是感情都是真的！楔子早就写了大半年了今天终于见了天日，后面的更新待定（我努力争取不要今天发完就坑，不过估计也没什么读者啦）。不接受催更哦，因为对于一个对自己的文字有强迫症的人来说催也没用（估计也没有人催）。当然，如果你在刷题之余看到这个小说，我也真心希望它能带给你片刻的思考，换换脑子嘛！