kuangbin专题

概率DP总结 by kuangbin

http://www.cnblogs.com/kuangbin/archive/2012/10/02/2710606.html 概率DP主要用于求解期望、概率等题目。转移方程有时候比较灵活。一般求概率是正推，求期望是逆推。通过题目可以体会到这点。首先先推荐几篇参考的论文：《信息学竞赛中概率问题求解初探》《浅析竞赛中一类数学期望问题的解决方法》《有关概率和期望问题的

[kuangbin带你飞]专题一简单搜索 A - 棋盘问题

简单的DFS，不过还是挺开心的！哈哈！ POJ宕机了，在OpenJ_Bailian上提交的（ https://vjudge.net/problem/OpenJ_Bailian-1321 ）可以先看一下N皇后问题再做这道题，N皇后问题最初是八皇后问题，很经典的问题，可以百度一下背景故事，蛮好玩的：题目： https://vjudge.net/problem/HDU-2553 题解： N

Phalanx [kuangbin带你飞]刷题记录

Phalanx 题目链接核心思想 : dp 我们可以观察出一个结论 : 以点(i,j)为左下角的边长为k对称矩阵那么以点(i-1,j+1)为左下标边长为k-1的矩阵一定对称 , 而我们只有推出了点(i-1,j+1)为左下标边长为k-1的矩阵是对称矩阵那么就只需要检查下边和左边就知道点(i,j)为左下角的边长为k对称矩阵是否存在了 AC代码 #include<iostream>

Doing Homework [kuangbin带你飞]刷题记录

Doing Homework 题目链接核心思想: 状压dp 我们将做完的作业弄成一个集合 , 比如是[1,2,4] 那么最后做完集合[1,2,3,4,]=max{ ( [2,3,4]+最后做1 ) , ( [1,3,4]+最后做2 ) , ( [1,2,4]+最后做3 ) ( [1,2,3]+最后做4 )} 同理每个集合的最优状态一定是上一个状态最优解分+最后做的这个元素的分用2机制

Making the Grade [kuangbin带你飞]刷题记录

Making the Grade 题目链接核心思想 : 暴力枚举版的dp 我们可以发现一个结论 : 只要a[i]需要改变 , 那么它一定会等于它前面那个最终确定值或者后面那个最终确定值即就是这个 :只要a[i]需要改变那么b[i]==b[i-1]或者a[i-1]或者b[i+1]或者a[i+1] 推到这里了我们就可以直接dp枚举出答案了 AC代码 #include<iostrea

The Shortest Path in Nya Graph [kuangbin带你飞]刷题记录

- The Shortest Path in Nya Graph 核心思想,将每一层建立俩个辅助点,如图,让该层的所有点与这两个点相连,边权分别为c与0,就成功地把建边的时间复杂度大大缩小了,如图 AC代码 #include<iostream>#include<queue>#include<string>#include<string.h>#include<algori

kuangbin专题八 SPOJ - HIGH Highways

题解：生成树模板题。题外话：我好悲哀，现在只会做一些模板题，一遇到经典的题就一脸蒙，而且还看不懂，哎。 #include<stdio.h>#include<string.h>#include<algorithm>using namespace std;#define LL long long int const int MAXN=15;LL B[MAXN][MAXN];

kuangbin专题八 HDU4305 Lightning（生成树计数+三点共线）

题意：给出n个点的坐标，距离不超过r的点如果中间没有其它点则可以连一条边，最后求生成树的数量，对10007取模。题解：这道题，，实在强大，我完全一脸蒙逼，看了大佬的题解之后，我也不想写啥了，以后回来看题解的话，还是直接去看大佬写的博客吧，这道题也逼着我去学了一回逆元，但是我那个生成树计数模板好像是不需要逆元的。。。ORZ P1(x1,y1)、P2(x2,y2)、P3(x3,y3)三点

kuangbin专题八 URAL1627 Join（生成树计数）

题意：给出一个图,’.’表示卧室,’*’表示储藏间,每个格子上下左右都有一堵墙,然后需要打通一些卧室的墙（只能是相邻房间才能打通）使得卧室之间联通的方案数. 给每个卧室编个号,给可以打通的卧室加边,就是裸的生成树计数了. 题解：打通一些卧室的墙之后，卧室之间就会变成一棵树，那么我们只要计算生成树的方案数就好了，怎么做呢，给每个卧室编个号,然后就是计算他们的联通边，写出邻接矩阵，然后弄个

kuangbin专题八 SPOJ DETER3 (矩阵行列式模p)

题意: n是n行n列，模p,求矩阵的行列式模p. 题解：矩阵行列式的模板题，这个模板如果要模数的话，就需要用到逆元，但是我还不会，到时候再学吧。 #include<stdio.h>#include<string.h>#include<algorithm>using namespace std;#define INF 0x3f3f3f3f#define LL long long

kuangbin专题八 UVA10766 （生成树计数）Organising the Organisation（请无视这篇文章）

题意：给出n,m,k,代表一家公司有n个部门，编号1到n,有m组关系，表示i和j不能直接联通，k代表主管部门，问你有多少种分层方案。另外，这道题的k可以忽略掉，所以他的范围完全是吓唬人的。题解：抱歉，这道题我真的无法弄的通俗的说出来，因为这个设计线性代数，我线性代数考试的时候完全是临时抱佛脚的，导致我不太弄懂怎么个弄法，尽管是那个道理，那个意思，但是感觉矩阵没好好懂，还是不明白，所以这

kuangbin专题八 HDU4009 Transfer water （无定根最小树形图）

题意：在山上有N户人家，每家的坐标为(xi, yi, zi)。每户人家要吃水，要么自己打井，花费为X*zi，要么从别人的家引水渠代价为两家的曼哈顿距离*Y，如果这家的海拔比供水的低，还要另外再买一个价值为C的水泵。然后有N个k,表示的是每户人家可以引水渠到哪一家，现在问每家都有水喝的最低花费是多少。题解：一开始我纠结于如何在最小树形图中判断水泵到底安不安装，后来别人说直接把水泵的价格

kuangbin专题八 HDU2121 Ice_cream’s world II（不定根的最小树形图）

题意：一个国家有N个城市，M条有向道路，女王想要选一个城市为首都，使得这个城市既能连接所有的城市，而且总的路程最短。若能找到这个城市，则输出最短路程和最小的城市编号。题解：最小树形图+超级源点，因为是不定根，我一开始是想暴力枚举的，然后发现复杂度爆炸了，就放弃了，后来才知道这道题可以用超级源点，怎么用超级源点呢？如果要用超级源点的话，肯定得在用完它之后删除掉这个点和与它有关的边之后对图

kuangbin专题八 UVA11183 Teen Girl Squad（最小树形图）

题意：给你N个点，编号为0到N-1，M条边的信息，边为单向边，问联通所有点的最小代价是多少。题解：最小树形图模板上，上代码就行了。 #include<stdio.h>#include<string.h>#include<algorithm>using namespace std;#define INF 0x3f3f3f3fconst int MAXN=1000+7;str

kuangbin专题八 POJ3164 Command Network（最小树形图的理解+模板）

题意：给你N个点的坐标，然后给你M条单向边的信息，A,B表示A指向B，从1开始，1的信息能传达到所有的点。题解：一开始这道题我看到了单向边，还想着怎么把他变成双向边来做prim算法，后来实在想不到，去看了题解，发现这道题原来是一个最小树形图。。。ORZ，对于这个算法的理解我还是看了别的大佬的博客才弄懂的，看算法的话可以参考一下这个大佬的：http://blog.csdn.net/wsn

kuangbin专题十四 POJ2478 欧拉函数模板题

题意：给定一个数n，求在[1,n]这个范围内两两互质的数的个数。题解：欧拉函数模板题。题外话：哎，数论数学不好，思维不太好真的不适合学，果然只能是到达数论只会GCD的地步吗？凄凉，kuangbin的这套数论基础题我只是会哪些模板题。。其他都阵亡了，哎。 #include<stdio.h>#include<string.h>#include<algorithm>using

kuangbin专题十四 HDU2161 素数打表

题意：输入一个数字，判断这个数字是不是素数，n<=0时,输入结束。题解：素数打表就好了，还有就是这道题2不是素数。。。 #include<stdio.h>#include<string.h>#include<math.h>#include<algorithm>using namespace std;#define LL long long int const int MA

kuangbin专题十四 LightOJ1213 规律+快速幂

题意：告诉你一段代码，然后要你找规律进行优化。题解: 一看这道题就知道是有规律的但是硬是想了一下午都没想出来，结果上手打代码模拟一番之后就得出了答案，ORZ，不禁感叹实践出真理。这道题是怎么个规律呢？公式为：sum*k*n^(k-1).这个公式怎么的出来的呢？首先sum就是数组的总和，k就是多少行，n是数组的长度。好，现在来推导规律，首先我们看到代码就应该知道最里面那一行肯定是进行了n^

kuangbin专题十四 LightOJ 1214 大数除法

题意：要你求大数除法，其中b会爆int，都是32位有符号来坑人的。。int31位有符号。题解：一个大数除法模板题 #include<stdio.h>#include<string.h>#include<algorithm>using namespace std;#define LL long long intconst int MAXN=200+7;char s[MAXN

kuangbin专题十四 LightOJ1220 分解质因数

题意：给你一个数n = b^p,求p的最大值。题解：分解质因数，一开始我以为是找到x = p1^x1*p2^x2*p3^x3*…*pk^xk中指数的最大值，后来我错了。。原来是要找他们的最大公约数，ORZ，因为n = b^p是由一个数和一个指数组成的，所以相当于要求出他们所有的指数的最大公约数得出一个数b,例如6=2^1*3^1应该是得到6=6^1吧，为什么呢？因为gcd(2,3)=1

kuangbin专题十四 LightOJ1234 打表

题意：给你一个n,让你求1/1+1/2+1/3+..1/n。题解：直接打表，但是double会爆空间的，然后在网上学了一招。。每100个分一组，这样就不会爆空间了，然后让我蛋疼的是怎么清空后面的零，结果我看网上的题解都是不用清空的。。what? 其实这道题还有个数论的解法，大家可以去看看这个博客： http://blog.csdn.net/newproblems/article/d

kuangbin专题十四 LightOJ1259 素数筛

题意： T组询问，每组询问是一个偶数n，验证哥德巴赫猜想，回答n=a+b 且a，b(a<=b)是质数的方案个数。题解：用素数筛做这道题就可以了，然后这道题的内存好像不够开太多int，所以再判断素数的时候用bool，然后存放的数组要/10就可以过了。 #include<stdio.h>#include<string.h>#include<math.h>#include<algori

kuangbin专题十四数论基础 LightOJ 1282

题意：给定两个数n,k 求n^k的前三位和最后三位。题解：后面三位可以用快速幂求，难就难在前面的三位怎么做了，看了很多，发现有个大佬用除法去求出前三位，ORZ，有个坑点就是后三位记得补零，和如果你是用除法去求前面三位的记得用double去做，因为你如果用long long int 去做的话，除的时候会去掉小数部分的，会导致后面的数无法进位的。然后再你返回double值的时候可以有两种操

kuangbin专题十四 LightOJ 1341 分解质因数

题意：给一对数字 a，b ，a是一个长方形的面积，问有多少种整数的边的组合可以组成面积为a的长方形，要求最短的边不得小于b,其中a不能是正方形的面积。题解：分解质因数的应用，有两个公式：（1）一个整数ｎ可以表示为若干素数乘积：n = p1^a1 * p2^a2*…*pk^ak; （2） n 的正因数的个数可以表示为： num = (a1+1)*(a2+1)…(ak+1); 又因

kuangbin带你飞-K - 迷宫问题 -BFS

K - 迷宫问题定义一个二维数组： int maze[5][5] = {0, 1, 0, 0, 0,0, 1, 0, 1, 0,0, 0, 0, 0, 0,0, 1, 1, 1, 0,0, 0, 0, 1, 0,}; 它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。 Input 一个5 × 5的

【前后缀DP】Kuangbin 超级跳跳跳

10分钟速切，感觉已经掌握这种DP了，嘻嘻 4550. 超级跳跳跳 - AcWing题库题意：思路：因为我们跳的那个点其实是路径的中间点，因此我们需要知道从开始到该点+从该点到结束的最短路径因此就是个很典的前后缀DP dp[i]表示从开始到该点的最短距离 dp2[i]表示从该点到结束的最短距离然后就可以转移了，类似于最长上升子序列 Code： #include <bits