- 博客(39)
- 收藏
- 关注
RSS订阅原创 汇编代码分析
代码如下：该代码运行中主要涉及以下寄存器ebp(指向栈底),esp(指向栈顶),eax(存放返回值),eip(指向运行代码)接下来按运行顺序来分析(假定ebp，esp开始指向0，并将堆栈每隔32位从高到底依次命名为1,2,3...)pushl %ebp 在1位置存入ebp地址0，esp指向1movl %esp, %ebp 使ebp指向esp指向地址(
2015-03-03 00:49:39
828
原创 poj3468（线段树区间修改）
题意很简单，标准的线段数区间修改的题目。代码：#include #include #include #include #define N 100005#define l(x) x<<1#define r(x) (x<<1)|1#define MID(x,y) ((x+y)>>1)using namespace std;struct Node{ int l,r;
2014-03-06 20:51:30
537
原创 hdu1698（线段树，区间着色）
题意：一个长度为n的数组，开始时价值均为1，之后有m次操作，修改一定区间的价值（1-3），最后求总价值思路：lazy的思想：每次处理的时候不需要修改到最根部，只需要修改到某个区间，每次都判断一下该区间是否是杂色的。杂色的在下次的访问的时候会修改子区间的值代码：#include #include #include #include #define N 100005#define l
2014-03-06 20:50:09
517
原创 hdu1754（线段树）
标准的范围最小值+单点修改，直接贴代码。。。#include #include #include #include #define N 200005using namespace std;struct Node{ int maxn,l,r;};int n,m;int p,q;Node node[N<<2];int num[N];void built(int
2014-03-05 19:13:01
464
原创 hdu1166（线段树）
题意：给出一列数，之后做四种操作中的一种(1) Add i j,i和j为正整数,表示第i个营地增加j个人（j不超过30）(2)Sub i j ,i和j为正整数,表示第i个营地减少j个人（j不超过30）;(3)Query i j ,i和j为正整数,i(4)End 表示结束，这条命令在每组数据最后出现;每组数据最多有40000条命令思路：先建立线段树，之后相应的进行点修改，qu
2014-03-05 18:29:48
428
原创 hdu2444（二分匹配）
题意：给出一些点以及一些边，问是否可分成二分图，如果可以输出大的集合的个数思路：先判断是否是二分图，之后用匈牙利算法求最大匹配#include #include #include #include #include #define N 205using namespace std;int n,m,head[N],size,hd[N];int vis[N];stru
2014-02-25 14:04:12
504
原创 hdu3631（floyd）
题意：给出M条有向线段，开始的时候所有点不可用，依次给出一些可用点，中间会有提问是否可从A到B点，给出最短路的值。思路：一开始我的思路是用dijkstra，最坏情况是10w的数据，所以我用邻接表+优先队列优化了，但是还是超时了，果断把这个否决掉了。之后我觉得floyd很好使，（个人感觉floyd有点离线的味道），因为不管查询多少次，Floyd相当于只执行了一次，最后都存在了map里了嘛，而
2014-02-12 21:49:14
563
原创 hdu2807（floyd +快速矩阵计算）
题意：给出n个m×m的矩阵，若矩阵a×b=c，则a与c之间距离为1，给出k个问题，求出最小步数，若没有，输出sorry。思路：本身很简单的Floyd可以解决，但是在矩阵计算的时候将二维矩阵化为一位矩阵，具体操作方法是给不同列（或者行）的数一个权值，将行的总权值求出来，存为一位数组，之后比较数组就只要一个for循环就行了。#include #include #include #incl
2014-02-06 16:37:11
799
原创 hdu3339（dijkstra+dp）
题意是有人有n个能量站，需要你关闭其中的一部分能量站，使总能量少于一半就可以避免爆炸，给出一些线路的消耗，以及站点的能量值，求最小消耗。思路：先求出0到达其他所有点最短路，之后就简单01背包就行了。#include #include #include #include #include #include #define N 105#define inf 0x7ffffffu
2014-02-05 14:22:44
542
原创 hdu1535（dijkstra+反向）
需要从每个点出发到达各个站台各一人，然后还要回到ccs。思路：出发的时候，正常用dijkstra做，返回时的最短路径可以将原map反转一下之前都是用的二维数组，此题点是1e6，所以我用的vector，不过对时间和空间都不是很满意。。。。#include #include #include #include #include #include #include #defin
2014-01-29 22:24:02
719
原创 hdu1217（map+floyd）
该题只要能围成一个圈，而且能够通过操作获利就输出yes，不然就输出no思路也很简单，即通过floyd算法获取个点最大获利，最后比较一下mp[i][i]是否存在大于1的点就行了#include #include #include #include #include #include #include #define N 35using namespace std;doubl
2014-01-26 22:44:47
495
原创 hdu2112（map+最小生成树）
这道题先用map将字符串映射到int上，之后与常见的dijkstra算法相同。#include #include #include #include #include #include #define N 155#define inf 1000000using namespace std;int n,t,mp[N][N],num[N];bool vis[N];in
2014-01-26 21:05:01
873
1
原创 hdu3038（加权并查集）
这已经是我做的第三道加权并查集，感觉很顺手，只要在权值的设置方面画个草图，这种问题还是很简单的。#include #include #include #include #include #include #include #define N 200005using namespace std;int G[N],Rank[N],m,n,ans;void Set(){
2014-01-18 13:34:50
606
原创 hdu3635（并查集）
这是我做的亚洲赛里的最简单的一道了.....快被之前的一道亚洲赛的题目弄出阴影了，不过，这道题倒是可以给我们初学者一点信心。这道题的难点在于如何记录转移的次数，我们可以想到find函数里面会遍历到根节点的translate次数，所以，我们可以在find的时候修改访问的值。其他没有什么难点，简单的并查集处理就好#include #include #include #include
2014-01-17 15:21:25
490
原创 hdu3367(最大生成树)
题目思路很清晰：求最大生成树，但是题意中提及，一个点可以有且仅有在一个环内，所以只要加点处理就行了，是一道水题#include #include #include #include #include #include #include #define N 10005using namespace std;typedef long long ll;int m,n,G[
2014-01-17 12:06:52
577
原创 hdu1558（并查集）
这道题的难点在于如何判断两条线段是否有交点首先，我们可以想象一下，两个线段如果相交，则从一条线段可以看到一个另一个线段的点在其两侧如果设横向的为ab线段，cd为另一条边，可以发现abc与abd的旋转方向不相同。由此我们得到以下算法double imem(node a,node b,node c){ return (b.x-a.x)*(c.y-a.y)-(b
2014-01-16 21:43:28
566
原创 hdu1829（并查集）
题意是判断是否存在同性恋（吐槽：这题意真是开放啊），所以这道题的并查集需要记录其属性，我通过rank1数组的0，1来区分性别是否相同。注意输出格式最后还需要输出一个空格....#include #include #include #include #include #include #include #define N 2005using namespace std
2014-01-16 15:33:14
383
原创 hdu4081（最小生成树变形）
本题的题意是某一条路可以不用花钱，这条路所连接的两个城市权值之和为A，然后求出最小生成树所需要的代价B，求出最大的A/B思路很清楚，因为有了这条路之后这两个点已经连通了，其他的线段肯定是最小生成树的线段（因为所需要花费的代价少于最小生成树的代价）。我们可以先将最小生成树的线段列举出来，然后将某一条边去掉，这样B的值确定，然后确定A的值，即找两个集合各自最大的节点值。#include
2014-01-16 13:01:57
637
原创 hdu2489（DFS+最小生成树）
题意很简单：要求一个比值最大的情况，因为节点的个数最多只有15个，所以我们可以暴力枚举所有的情况，然后对每一种情况求出最小生成树，最后输出结果就好了。另外这道题还有个很奇葩的东西，就是比值的小数点要到1e-9，正常的比较大小无法满足需要，我们需要通过if(wei1-answ#include #include #include #include #include #
2014-01-15 21:39:39
648
原创 hdu3938（并查集+离线）
这道题的第一个难点在于题目，对于我等英语菜B来说，理解这个题意还真是有点难......理解了题意之后，可以发现，用最小生成树的思路理解，如果可以加入某一条边使两个集合联通，那么增加的路径个数就是num【a】×num【b】。所以我第一次写的代码如下：#include #include #include #include #include #define N 10
2014-01-15 18:37:38
831
2
原创 hdu3926（同构图）
这道题的题意很简单，判断两个图是否是同构的。因为我的经验比较匮乏，首先想到比较度数，然后默默的WA了....之后想到了并查集一个一个判断，接着WA，此时我才想到一个人只能和其他两个人握手，所以只需要判断一下各个并查集匹配的状态，可以想到一个并查集内的点状态只有两种，1.环，2.链。所以我们可以用0，1来表示这两种状态。因为是匹配并查集，所以我通过优先队列来直接省略了排序环节（有点懒....）
2014-01-15 12:42:55
638
原创 hdu1811（拓扑排序）
本题大意是给出一定的等式，判断能否排名次，对于“=”的，我们可以将用并查集将它们放到一起，然后对所有的进行拓扑排序。拓扑排序：对于一个有向图，每次取出入度为0的点，然后将与这个点有关的线连接的点入度全部减一。#include #include #include #include #include #include #include #include #define N 10
2014-01-14 18:30:08
665
原创 hdu1272 （无向图）/1325（有向图）
这道题题目是中文的，所以无需多解释了，就是一个图是否能成为一个迷宫，重点是从任意一点到另一点只能有一条道，而且所有点是联通的。所以这道题的思路就很清晰了，只要连通的，放入集合中，如果两个节点的父节点相同，即这两点之间存在别的道路可到达，即不成立。最后，搜索一下，如果所有节点父节点一致，即都是连通的，可成立。附上代码：#include #include #include
2013-11-25 21:10:36
590
原创 树形DP入门————hdu1520
这道题目题意不难理解，给出一个关系树，每个节点有相应的权值，相邻的节点不能同时出现，求最大权值。这是一道标准的树形DP问题，只需要先构造一颗树，然后用深搜找到结果。因为每个节点有选和不选两个状态。dp[n][0]=max(dp[m][1],dp[m][0]);///当当前节点不被选中，将所有子节点的最大的取出来dp[n][1]=dp[m][0]///如果选中当前节点，只能选择子节点
2013-11-06 21:24:42
618
原创 最近AC的一部分题目（水题一堆啊）
hdu1029，一个简单的dp问题（虽然这个问题貌似不用do唉，囧）#include #include #include #include #define MAXN 500000using namespace std;int main(){ int num,n,index,max; while(scanf("%d",&num)!=EOF) {
2013-11-05 08:18:35
578
转载 母函数 入门 + 模板
在数学中，某个序列的母函数(Generating function，又称生成函数)是一种形式幂级数，其每一项的系数可以提供关于这个序列的信息。使用母函数解决问题的方法称为母函数方法。母函数可分为很多种，包括普通母函数、指数母函数、L级数、贝尔级数和狄利克雷级数。对每个序列都可以写出以上每个类型的一个母函数。构造母函数的目的一般是为了解决某个特定的问题，因此选用何种母函数视乎序列本身的特性和
2013-11-05 08:02:50
589
原创 KMP模式匹配算法
在写KMP之前，先把暴力匹配，也就是BF算法先写一下int BF(string s,string t){ unsigned int i,j; i=j=0; while(i<=s.size()-t.size()) { for(int k=i;j<t.size();) { if(s[k]==t[j])
2013-10-26 22:02:31
558
原创 逆波兰表达式学习日记（2）
鉴于今天星期三，下午常规没课。而且后缀求结果也挺简单的，就先把这个写完吧。之前已经转化完了表达式，现在只要把一群数字和加减乘除运算一下就OK了（说实话，有点懒了，最近长春PM2.5有点高，我根本就没有兴趣搞ACM嘛）int change(char *a){ stack t; int i=0; while(a[i]!='\0') {
2013-10-23 15:10:09
700
原创 hdu1312（又是简单搜索题）
A水题，找手感。这一题也好简单，就是找一个区域内所有点的个数，边界有围墙，思路就是找到一个，就把它变成围墙，然后num+1，最后输出num，得到结果话不多说，直接贴代码吧#include using namespace std;char arr[25][25];int m,n,num,dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};void d
2013-10-22 19:06:00
1796
原创 逆波兰表达式学习日记（1）
先看了一下栈的基本原理，也就是所谓的后进先出，然后就想完整的学习一下逆波兰表达式。下午刚上完工程制图（工程制图没认真听啊orz.....），回来就想着先写第一部分吧。前面说了一堆废话，先给个例子9+（3-1）×3+10/2 --------> 931-3*+102/+将中缀表达式转化成后缀表达式，原理很简单，我先做一个关于没有“（”与“）”的例子，来简单的解释一下这个过程。
2013-10-22 17:01:30
698
原创 hdu1241（最简单的搜索）
这是标准的dfs搜索问题，问题要求找到所有的油田的个数，油田连在一起的算一个，所以我们可以用遍历的方法，搜到一片油田就将这一片油田变为"*",这样就可以很轻松的A掉了。代码：#include using namespace std;char arr[101][101];int m,n,dir[8][2]={{-1,-1},{-1,0},{-1,1},{0,1},{0,-1},{
2013-10-21 21:02:47
1632
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人