lightoj专题
LightOJ 1068 Investigation (数位dp)
http://www.lightoj.com/volume_showproblem.php?problem=1068 求出区间[A,B]内能被K整除且各位数字之和也能被K整除的数的个数。（1 ≤ A ≤ B < 231 and 0 < K < 10000） 算是最简单的数位dp了，k在这里是10000，三维数组都开不开。但是想想会发现A,B最多有10位，各位数字之和不会超过90，那么当
lightoj 1050 - Marbles （概率DP）
思路：定义dp[i][j] 为 袋子中有i个红球和j个红球时获胜的概率 那么根据题意我只可以任意拿而对手只拿蓝球。那么 dp[i][j] = （拿到红球的概率） * dp[i-1][j-1] + (拿到蓝球的概率) * dp[i][j-2]; 边界：当红球没有时，获胜的概率为1 注意点：T比较大，需要把所有数据预处理出来直接查询，否则超时 /*********************
lightoj 1047 Neighbor House(Dp)
思路：定义dp[i][j] 为粉刷第i个房子用的颜色j dp[i][j] = min(dp[i-1][(j+1)%3] , dp[i-1][(j+2) % 3]); 一共有三种颜色{0, 1, 2}，任取一种颜色{j}，那么和颜色j不同的颜色就为{(j + 1) % 3 , (j + 2) % 3}; /******************************************
lightoj 1044 Palindrome Partitioning(dp)
题意:给定字符串S，问可以划分的最小回文串数量 思路：定义dp[i]为以i开头的字符串中回文串的最小划分数. dp[i] = min(dp[j] + 1 | i <= j < n && S[i...j]是回文串) 边界,dp[i] = n-i+1. /************************************************ Author: fisty* Crea
lightoj 1037 - Agent 47 （状压DP）
题意：你现在需要消灭n个敌人，n个敌人的血量已知，你的普通攻击力为1，但是如果你杀死敌人i可以用它的武器去杀死其他敌人，p[i][j] 表示用敌人i的武器射杀敌人j会减p[i][j]滴血.问你最少可以攻击多少次可以将敌人杀死。 思路: 定义集合s为死亡敌人的集合。 dp[s] 为让集合为s的人死亡最小需要的攻击次数。 如果现在想要消灭敌人i 并且敌人i不属于s 那么dp[s | (1<<
lightoj 1032 - Fast Bit Calculations （数位DP）
记忆花搜索：dp[len][num][last] : 现在处理第len位，前面有num个11，并且最后一位为last。 /************************************************ Author: fisty* Created Time: 2015-08-18 20:18:09* File Name : 1032.cpp***************
[LightOJ 1292] Laser Shot （几何，判断共线）
LightOJ - 1292 刚开始写的时候是O( n3log(n) n^3log(n))的，枚举两个点，得到一条直线，用set记录下来，然后再 O( n n)地计数，居然没有卡过 orz 听了学长的教导，get到一个几何常用思路，正确解法如下 枚举一个点，再枚举其他点，计算到这个点的斜率，make_pair(dx,dy)塞到map里，把相同斜率的计数一下 这样时间复杂度为 O(n2log
[LightOJ 1364] Expected Cards （高维期望DP）
LightOJ - 1364 一副扑克牌，不断地从中抽牌 要求四种花色都至少要有给定的张数 其中如果抽到了王牌，可以将其变为任意花色 求满足条件时，抽出的期望张数 刚开始想错了，两张王牌并非在一开始就给定了 而是在游戏中可以视当前情况选择着变的 这两种方式是不一样的 由于牌数其实并不会很多， 复杂度乘一乘发现才 107 10^7级别的，所以直接暴力DP 将两张王牌当
[LightOJ 1342] Aladdin and the Magical Sticks （期望的线性性质+几何分布+邮票收集问题）
LightOJ - 1342 有 N根棍子，每根棍子都有一个权值 其中有若干根可识别的，若干根不可识别的 抽到了可识别的棍子，就不放回，抽到了不可识别的，就要放回 问所有棍子都至少被抽过一次后的期望权值和 根据期望的线性性， E(CX)=CE(X) E(CX) = CE(X) 所以可以对每根棍子求一下它被抽到的期望次数，再乘以它的权值 对于不可识别的棍子，由于它被抽到的概率
[LightOJ 1321] Sending Packets （SPFA+概率DP）
LightOJ - 1321 给定一张无向图，每条边都有一个通过的概率 如果无法通过，那么就要回到起点重新出发 从起点到终点的时间固定为 K K，如果成功到达， 又需要额外花费 KK的时间，问走 S S次的最小期望时间首先可以跑一遍SPFA求出一次通过的最大概率 pp 设跑一次的最小期望时间为 E E，E=p×2K+(1−p)×(E+2K)E = p\times 2K + (1-
[LightOJ 1274] Beating the Dataset （期望DP）
LightOJ - 1274 题目等价于，给定一个开头为 1的 01串， 求其中相邻两个字符不相等的期望对数 一开始煞笔了，其实 YES和 NO的个数是可以直接算出来的 算出来之后，设 dp[i][j][k] dp[i][j][k]为第 i i位，jj表示当前是 YES(1)或 NO(0) k k表示 ii位及以前一共有多少个 YES，然后倒着就推出来了 下一位出现 0
[LightOJ 1265] Island of Survival （概率）
LightOJ - 1265 一个岛上有若干只虎，若干只鹿，一个人 每天只有两个动物会相见 如果人和虎相见，人死 如果鹿和虎相见，鹿死 如果虎和虎相见，虎死 其他情况均没有伤亡，各种情况均等概率 问人活到虎全死光的概率有多少 感觉二维dp直接搞正确性很显然 但是网上有另一种做法，就是直接忽略掉鹿的存在，当没有鹿 不是很懂这样做的正确性，网上的解释是鹿吃与被吃， 与人
Lightoj 1031 - Easy Game DP
题目链接 dp[i][j] 表示区间i到j先手取比后手取多多少 #include <stdio.h>#include <string.h>#include <math.h>#include <iostream>#include<functional>#include <queue>#include <string>#include <algorithm>using n
lightoj 1428 Melody Comparison 后缀数组
题意：给定一个字符串A和字符串B，求A的不包含B的不同子串个数。 思路：首先把B串接到A串后面中间用一个A、B中均未出现的字符隔开，构成字符串s。求出每个字符对应的height[ i ]、sa[ i ]、rank[ i 。我们开一个rmax数组，rmax[ i ]存的是从A串的第i个字符向右能不形成包含B串的串的最长长度，那么我们必须先知道A串哪些位置 开始能形成B串。假设A串的长度为l
lightoj 1137 Expanding Rods | 二分+几何
题意： 一根棍子，受热后长度会改变。L' = (1+n*C)*L 问你受热后棍子的中点距离地面的高度h为多少。 思路： 推公式， L' = p*r ——p为弧度 r = （L/2）/sin（p/2） 两式联立，二分p即可。 AC代码： [cpp] view plain copy #include <cstring> #include
lightoj 1307 Counting Triangles | 二分/暴力
题意： 给你N条边，问你能组成三角形的方法数。 思路： 判断三条边能否组成三角形，根据任意两条边的和大于第三边。 实际上，在确定A<=B<=C的情况下，只要A+B的和大于C即可认为ABC能组成三角形。 这题可以不用二分，用二分速度反而变慢了。排好序后乱搞就可以了。 AC代码： #include <cstring>#include <cstdlib>#include <cstd
*lightoj 1138 Trailing Zeroes (III) | 二分+数学
这题问了杰神才知道怎么做。 题意： 给你Q，表示N！的结果后面有Q个零，让你求出最小的N为多少。若无法找到则输出impossible 思路： 根据唯一分解定理，一个自然数可以写成质数的幂次方的乘积。例如10 = 2^1 * 5^1 因为是尾部有Q个零，所以N！的结果中5的幂必须等于Q（此时，2的幂肯定比Q大）。 那么我们如果要求一个数的阶乘的结果5的幂次方是多少。 譬如30！的结果中
lightoj 1127 Funny Knapsack | 二分+折半枚举
折半枚举这个概念在watashi所翻译的书上有介绍过。 所谓的折半枚举：把所要枚举的值，先把前部分的值所有情况枚举出来，再把后部分的值所有情况枚举出来并排序，结合二分搜索进行查找的想法。（主要是应对直接暴力枚举会超时的情况）。看完这题估计就懂了。 题意： 给你n个数，每个数都有可以取或者不取，使它们的和<=W。让你求出总的方法数。 思路： n最大为30，如果直接枚举，时间复杂度为2^30
lightoj 1072 Calm Down | 二分
与lightoj 1048 基本一样，不过是这题是弱化版，不用输出方案。 http://blog.csdn.net/u011580493/article/details/38958267 #include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>usin
lightoj 1062 Crossed Ladders | 二分
题意： 给你两个相交的梯子。现已知道它们的长度以及相交点距离地面的高度c，现在让你求出梯脚间的距离。 思路： 二分梯脚间的距离即可。运用几何知识求出相交点的距地的高度进行比较。 AC代码： #include <cmath>#include <cstring>#include <cstdlib>#include <cstdio>#include <iostream>
LightOJ 1057 - Collecting Gold（dp）
题目链接：LightOJ 1057 - Collecting Gold 代码 #include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn = 55;const int maxs = 1<<17;const int inf = 0x3f3f3f3f;int N, M,
LightOJ 1051 - Good or Bad（dp）
题目链接：LightOJ 1051 - Good or Bad 代码 #include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn = 55;int N;char S[maxn];bool dp[maxn][10][10];bool isvowel(char ch)
LightOJ 1050 - Marbles（dp）
题目链接：LightOJ 1050 - Marbles 代码 #include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn = 505;int R, B;double dp[maxn][maxn];void init () {memset(dp, 0, sizeof(d
LightOJ 1047 - Neighbor House（dp）
题目链接：LightOJ 1047 - Neighbor House 代码 #include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn = 30;const int inf = 0x3f3f3f3f;int N, dp[maxn][3];int main () {in
LightOJ 1038 - Race to 1 Again（dp）
题目链接：LightOJ 1038 - Race to 1 Again 代码 #include <cstdio>#include <cstring>#include <vector>#include <algorithm>using namespace std;const int maxn = 1e5;double dp[maxn + 5];vector<int> G[maxn +
LightOJ 1037 - Agent 47（dp）
题目链接：LightOJ 1037 - Agent 47 代码 #include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn = (1<<15) + 5;const int maxm = 20;const int inf = 0x3f3f3f3f;int N, H[m