pibaixinghei-CSDN博客

原创 C++面向对象程序设计复习

第8章虚函数与多态性向上类型转换：派生类转换为基类类型静态绑定，早绑定实现多态用动态绑定，绑定推迟到程序运行时，C++中用虚函数实现非静态成员函数可以声明为虚函数，虚函数绑定是根据对象类型确定的派生类定义的虚函数参数表与基类不同，在派生类中会隐藏基类的虚函数。函数名与参数表相同，返回类型不同，编译器报错构造函数与析构函数中调用虚函数时，被调用的只是这个虚函数的本地版本构造函

2017-05-10 16:15:35 1166 1

原创计算机网络复习（第五章运输层）

课后答案：https://wenku.baidu.com/view/c12f74a5b52acfc788ebc98b.html5.运输层5.1运输层协议概述5.1.1进程之间的通信用户功能中的最低层。运输层功能：复用和分用。网络层为主机之间提供逻辑通信，运输层为应用进程之间提供端到端的逻辑通信。运输层进行差错检测。5.1.2运输层的两个主要协议1.用户数据报协议UDP 2.传输控制协议

2017-04-11 15:39:57 2016

原创计算机网络复习（第一章概述）

第一章概述1.1计算机网络在信息时代中的作业三网：电信网络、有线电视网络、计算机网络。计算机网络最重要两个功能：连通性，共享。1.2因特网概述1.2.1网络的网络网络由若干结点和连接这些结点的链路组成。网络把许多计算机连接在一起，而因特网则把许多网络连接在一起。1.2.2因特网发展的三个阶段1.单个网络ARPANET向互联网发展过程分组交换网络到研究多种网络互联的技术。因特网的雏形。

2017-04-09 13:36:09 845

原创计算机操作系统复习（第三章处理机调度与死锁）

概括但又不失完整性第三章处理机调度与死锁3.1处理机调度的层次和调度算法的目标调度实质之一种资源分配，处理及调度是对处理机资源进行分配3.1.1处理机调度的层次1.高级调度：长作业调度或作业调度，决定将外存上处于后备队列中的哪几个作业调入内存，分配资源，放入就绪队列。主要用于多批道处理程序。 2.低级调度：进程调度或短程调度，决定就绪队列中哪个进程获得处理机。最基本的调度，多批道处理，分时和实时

2017-04-04 13:49:04 1440 1

原创 PCA笔记

PCA　　之前有看过PCA，但还只是浅显的了解了一下，现在在这里顺着思路再整理一下，方便自己以后回顾，参考的这位博主http://blog.codinglabs.org/articles/pca-tutorial.html，十分感谢他写的这么仔细。　　1.什么是PCA　　PCA（Principal Component Analysis）是一种常用的数据分析方法。PCA通过线性变换将原始数据变换为

2017-02-10 14:12:56 770

原创 51node 1509 加长棒|codeforces571A（组合数）

51node 1509题目中文题目思路http://blog.csdn.net/thy_asdf/article/details/49362035 直接算方案数比较困难，可以先求出不成立的方案数，再拿总方案数去减. 总方案数根据插板法C(l+4-1,4-1) a+x+b+y<=c+z又x+y+z<=l 得到x+y<=min(c+z-a-b,l-z)，枚举z即可，方案数同样可以用插板法代码#i

2016-10-28 11:42:51 278

原创 51node 1672 区间交(线段树）

51node题目中文题目思路首先将区间按照左端点排序，然后寻找满足要求的右端点，因为排序后再插入的，所以ans一定是左端点与找到的右端点内数字的和，因为之前区间的左端点都比当前枚举的小。对于找右端点，要找尽量右且剩k个区间这种，用线段树实现与维护。代码#include <cstdio>#include <algorithm>#define lson l, m , rt << 1#define r

2016-10-27 15:22:33 250

原创 51node1476 括号序列的最小代价（贪心）

51node1476题目中文题目思路先假设所有的？都是），记s是前缀和，遇到（+1，遇到）-1，如果s小于0，那么表示必须要有变化了，而且这样之前累计的？最多，取优先队列中存的最小的从右括号变到左括号的值，并且s+=2即可。代码#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#include<cmath>

2016-10-16 16:22:19 470

hdu4035题目一颗树形的迷宫，对于每个房间，有几率被杀回到房间1，有几率逃出去，有几率随机到相邻的房间，问逃出去的概率。思路http://www.cnblogs.com/kuangbin/archive/2012/10/03/2711108.html 推公式的概率dp，精妙之处在于E[i] = ki*E[1] + ei*0 + (1-ki-ei)/m*( E[father[i]]+1 + ∑(

2016-10-11 19:59:27 372

原创 hdu4336 Card Collector（期望dp）

hdu4336题目就是小时候的集卡，有N张卡，给出每张卡获得的概率，有可能没有卡，问开包的期望。思路概率正推期望逆推，开一个 1<代码#include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>using namespace std;typedef long long

2016-10-11 15:23:07 372

原创 hdu5378 Leader in Tree Land（概率dp+逆元）

hdu5378题目一棵n个节点的有根树。对其节点进行标号(1~n)。求恰好存在k个节点的标号是其节点所在子树的最大值的方案数。思路这都能用概率，真是厉害了。借用这微博主的话http://blog.csdn.net/moguxiaozhe/article/details/47439691 令dp[i][j]表示考虑编号从1到i的点，其中恰好有j个点是其子树最大值的概率。很容易得到如下转移方程

2016-10-11 00:14:55 273

原创 hdu4800 Josephina and RPG（概率dp）

hdu4800题目告诉你有m个人物，三个人可以组一个队，那么有C(m,3)种组队方法，给一个矩阵列出每个队伍之间的胜率，再告诉你有n支ai队伍以及他们的队伍编号，现在你一开始可以任选一支队伍，然后按顺序和每支ai进行比赛，你赢了ai可以选择要不要与它换队伍来进行下一场的比赛，求最大的胜率。思路还是好菜啊，一开始状态就设计错了，没有体现后效性，dp[i][j]表示打赢第i支ai队伍的是第j队，这样就保

2016-10-10 19:12:15 540

原创 hdu5236 Article（贪心+概率dp）

hdu5236题目（抄别人的http://www.cnblogs.com/qscqesze/p/4543740.html）要求输入一篇N个字符的文章，对所有非负整数i：每到第i+0.1秒时可以输入一个文章字符每到第i+0.9秒时有P的概率崩溃（回到开头或者上一个存盘点）每到第i秒有一次机会可以选择按下X个键存盘，或者不存打印完整篇文章之后必须存盘一次才算完成输入多组N,P,X选择

2016-10-10 13:06:43 305

原创 hdu5117 Fluorescent(数学+状压dp)

hdu5117题目就是告诉你有n盏灯，有m个开关，每个开关关联了几个灯，按下开关的话灯的状态会发生变化，求对于每个开关按或不按的所有情况下的每种状态亮灯的个数的立方的和。思路http://blog.csdn.net/tianji_fange_tuhao/article/details/51760690 学到了（x1+x2+x3+…xn）^3展开后相当于许多个xi*xj*xk带上他们各自系数的和，

2016-10-09 23:55:26 218

原创 hdu5917 Instability(ramsey定理)

hdu5917题目给你一个无向图，问图中有多少个符合条件的集合？条件为这个集合里面存在一个子集(大小>=3)为团或者都是孤立点。答案mod1e9+7思路Ramsey定理的通俗表述： 6 个人中至少存在3人相互认识或者相互不认识。该定理等价于证明这6个顶点的完全图的边，用红、蓝二色任意着色，必然至少存在一个红色边三角形，或蓝色边三角形。超过6就用定理 3-5就枚举所有情况来判断。代码#incl

2016-10-08 23:57:28 919

原创 hdu5916 Harmonic Value Description（构造）

hdu5916题目给两个数n，k（1<= k < 2*k <=n），然你构造一组1-n数列，使得相邻两数gcd的和为所有排列可能中的第k小个排列思路相邻的互质，不动的话就是k=1，所以把偶数凑一起，凑几个就是第几小，把它们放到1与2之间。代码#include <cstdio>#include <iostream>#include <algorithm>#include <cstring>usi

2016-10-08 20:27:57 341

原创 hdu5914 Triangle（思路）

hdu5914题目1到n的长度的木棍去掉多少根可以所有棍子组不成三角形思路结合斐波纳契数列考虑。代码#include <iostream>#include <cstdio>#include <cstring>#include <queue>#include <algorithm>#include <cstring>#include <vector>using namespace std;

2016-10-08 16:38:02 323

原创 hdu5920 Ugly Problem（构造）

hdu5920题目给你一个可能有1000位的数字，让你用不超过50个的回文串数字的和来表示它。思路整体思路就是对于一个数字，尽量把它构造成很长的回文数字，然后减去这个数字，最后一定能化成“x0000000。。。”这样的数字，而这样的数字一定能够化成3个回文数字的和，例如80000=77777+2222+1. 对于第一个尽量构造最长的回文串，例如5234247，中间位是4，我构造出5234325，但

2016-10-08 16:28:02 335

原创 hdu5919 Sequence II（主席树，区间第k大）

hdu5919题目给你n个数字,和m个查询.将[l,r]之间数第一次出现的位置信息弄成一个新的数组,然后找出其中k/2大的数.(k为位置的数量)思路主席树，倒着插入保证数字第一次出现的位置。强行学习了一波。（借鉴别人的代码）代码#include <cstdio>#include <algorithm>#include <cstring>using namespace std;const int

2016-10-08 16:15:05 656

原创 51node1371 填数字(dp)

51node1371题目中文题目思路dp[i][j][k]表示第i行填完之后有j列的和是1,k列的和是2，我们枚举每行的最后一个为0，1，2时的情况分类讨论。具体看代码，注意注释是有层次的。（感觉状态设计得很好，学到了）代码#include <iostream>#include <algorithm>#include <cmath>#include <vector>#include <s

2016-10-08 16:06:29 412

原创 hdu5245 Joyful（概率dp）

hdu5245题目进行K次染色，每次染色会随机选取一个以(x1,y1),(x2,y2)为一组对角的子矩阵进行染色，求K次染色后染色面积的期望值(四舍五入)。思路http://blog.csdn.net/Tc_To_Top/article/details/47681573 考虑某个小方格不被染色的概率，就是所选的矩形区域在他的上下左右的情况，不过四个角会被多算，所以减去，乘以k次表示染k次色，再用1

2016-10-08 15:57:53 293

原创 hdu5724 Chess（博弈+状态压缩）

hdu5724题目就是说有一个n行20列的棋盘，每行上有些许棋子，规则是取一个棋子向右走一步，如果右边有子就跳过他，如果到底了就不能走了，有人不能进行操作就输了，两个人都会走最有步骤，问Alice是否会赢得胜利。思路第一次看了博弈以及sg函数，感觉很棒。 http://www.cnblogs.com/hchlqlz-oj-mrj/p/5687492.html这位博主讲的不错学习了。这道题首先就

2016-10-01 15:07:07 373

原创 hdu4511 小明系列故事——女友的考验（AC自动机+dp）

hdu4511题目中文题目思路AC自动机好久以前看的了，都要忘了。。。。正好复习以下。 dp[i][j] 表示在i点，状态在j的距离，转移比i大的点k，判断下一个状态ss是否可行，可行则转移到dp[k][ss]代码#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>#include <cmath>

2016-10-01 10:22:02 498

原创 hdu5120 Intersection(平面几何+圆相交面积)

hdu512题目求两个给定圆环相交部分的面积思路最终面积就是大圆相交部分+小圆相交部分-2*大小圆相交的部分，然后就是模版了代码#include <iostream>#include <algorithm>#include <cmath>#include <vector>#include <string>#include <cstring>#include <cstdio>using n

2016-10-01 08:33:15 251

原创 51node1439 互质对（容斥原理）

51node1439题目中文题目思路引用2997ms的话： “如果已知当前集合中互质的个数为ans，那么加入或者删除某个元素最后的结果也就是ans加上或减去该元素与集合中元素互质的个数。所以要求的就是一个数与集合中各个数之间互质的个数。做法是把每一个数拆成各个质数因子的乘积，然后对这些质数进行排列组合，那6来说，先假设将所有元素都是与6互质的，然后这里面减去因子有2的(与6一定不互质了)，

2016-09-29 16:55:31 994

原创 hdu5468 Puzzled Elena（容斥原理+dfs序）

hdu5468题目给一棵树，每个结点有一个值，现在求以每个结点为根的子树中与其互质的结点的个数思路这位博主讲的很好http://www.cnblogs.com/program-ccc/p/5813771.html 首先我们是可以用容斥求出集合中不互素的元素个数，用总个数减一下就行了。具体就是：①将元素进行质因数分解。②将质因数可能产生的乘积的出现次数加1。最后利用容斥原理求解。见代码。用到

2016-09-29 16:50:17 365

原创 51node1693 水群（最短路）

51node1693题目中文题目思路http://blog.csdn.net/mrazer/article/details/51512088这个博主讲的不错。算是学习了，首先将问题转化为：操作1是s*=k代价为k，操作2是s–代价为1 求把s从1变到n的最小代价紧接着将k质数分解，让i连接到质数p 再接着找规律（。。。）发现i→i-1的边不会连续出现4次以上而且i→i*p的边只有当p<=13

2016-09-28 18:43:23 322

原创 hdu2202 最大三角形（旋转卡壳）

hdu2202题目中文题思路学习了什么是旋转卡壳，求三角形面积的话就是多加了一个底边是哪两个点组成的。代码#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#define pi acos (-1)#define rotate Rotateusing namesp

2016-09-27 15:27:37 555

原创 poj1228 Grandpa's Estate(凸包)

poj1228题目给你一些肯定在凸包上的点，问这些点构成的凸包是不是稳定的凸包。思路稳定凸包的话每条边上至少三个给定点。代码#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#define pi acos (-1)#define rotate Rotateusi

2016-09-27 14:30:58 279

原创 hdu4946 Area of Mushroom（凸包）

hdu4946题目有n个人，每个人有一个坐标和速度，平面上如果的点如果他到达的时间严格的比其他任何人都快，那么这个点就属于他管辖。问每个人的管辖区域是不是无穷大。思路首先只有速达最大的那批人才有可能，把他们处理出来，然后对他们求凸包，在凸包里面的人是不可能的，在凸包边和顶点上的人是可以的，如果这些点钟有几个重合的，也要去掉。还有就是速度为零的点，不能算进去。代码#include <iostream>

2016-09-27 11:02:45 260

原创 Lightoj1203 Guarding Bananas(凸包)

Lightoj1203题目有一片香蕉园，一只猴子想知道能看到所有香蕉的最小角度。思路求凸包，枚举角度。代码#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#define pi acos (-1)#define rotate Rotateusing namesp

2016-09-27 09:06:52 223

原创 uva10256 The Great Divide（凸包+判断）

uva10256题目就是给你一些点，一些点支持点A，另一些支持点B，现在问能不能画一条直线使得两个阵营的人正好在两边。思路还是凸包，但是注意一个点和两个点的情况，同时注意判断一个凸包在另一个凸包里面的情况，其他时候就暴力判断直线是否相交即可。代码#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>

2016-09-27 08:29:32 266

原创 uva11168 Airport(凸包)

uva11168题目就是说有很多的居民点，现要建一条直线跑道，使得每个居民点到跑道的平均距离最小。思路求凸包，注意1个点和2个点的情况。代码#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#define pi acos (-1)using namespace

2016-09-26 21:03:26 525

原创 uva10652 Board Wrapping（凸包）

uva10652题目就是给你几个长方形，并且要旋转一定角度，用一个凸包把它们包起来并且求长方形面积总和与凸包面积之比。思路模版题，多了个求凸包面积和向量的旋转。代码#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#define pi acos (-1)usi

2016-09-26 20:23:14 237

原创 hdu5802 Windows 10(贪心)

hdu5802题目就是要求调到目标音量的最小步数，如果向上调的话每次只能一步，向下的话，如果上一次也是像下，这次是上次的*2，如果停顿或者向上的话就是1步。思路朴素的bfs会超时，应该是贪心，以尽快的逼近目标位置为目的，同时注意，向上走和停顿是可以合并的，最后向上赶的步数可以抵消掉之前下降过程中停顿的次数，细节看代码。代码#include <iostream>#include <cstdio>#

2016-09-25 14:21:04 259

原创 hdu5800 To My Girlfriend（dp）

hdu5800题目给定n个数，其中选定若干数，这若干数的权值和为m，且这些数中没有下标为i,j的数，有下标为k,l的数的集合个数。思路dp[i][j][s1][s2]，代表的是前i个物品，总权值为j，已有s1个必选，s2必不选的方案数。有四种转移方式，记得最后*4。代码#include <iostream>#include <cstdio>#include <cstdlib>#include

2016-09-25 10:00:49 243

原创 hdu1348 Wall（凸包）

hdu1348题目求把给定点围起来的最小周长，其中围墙离点要有L的距离。思路挺近凸包，从（抄）模版做起！代码#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;typedef long long ll;const int m

2016-09-23 21:26:27 254

原创 hdu5642 King's Order(dp)

hdu5642题目就是说一段小写字母序列，相同的字母不能连续出现超过3次就是合法的，问长度为n的序列有多少种合法的序列。思路dp[i][j][k]表示第i位是j字母并且连续了k次，接下来就很简单了。关键还是要抓住不能超过3次这个特点来列状态方程，谨记。代码#include <iostream>#include <cstdio>#include <cstring>#include <algo

2016-09-23 20:44:25 274

原创 hdu5416 CRB and Tree(树型dp)

hdu5416题目给你一棵树，树上两点的f值就是他们路径上边权的异或，现在给定s，求f值等于s的点对。思路由于异或两次相当于没有异或，我们记录每个点到根节点的路径异或值，对于任意两点之间的路径异或值只要吧到根节点的值异或一下就可以了，最后相当于枚举符合情况的个数，如果s=0，还要把不走的n个情况加上去。（maxn大小开的不一样会WA，不知道为什么。。。）代码#include <iostream>#

2016-09-23 10:32:54 243

原创 hdu5893 List wants to travel（树链剖分+线段树）

hdu5893http://blog.csdn.net/carryheart/article/details/52625012 参考队友的博客，总算看懂了，二次学习了，留个记录。

2016-09-22 19:41:45 306

空空如也

空空如也