- 博客(86)
- 收藏
- 关注
RSS订阅原创 博客已搬家
即日起该博客不再更新。欢迎大家访问我的新博客：http://acm.nbu.edu.cn/SwordHoly/ ，欢迎大家跟我交换链接。
2011-09-26 17:06:54
1151
原创 Dome of Tuxville [UVALive 3347] 模拟退火
<br />题意：有n个楼，给定xy坐标和高度，有一个防护盾核心，以他为球心的半球内的都处于他的保护之下，求他的坐标，使得他需要覆盖全部楼的半径最小。<br />题解：<br />模拟退火。<br /> <br />第一个模拟退火，哈哈。<br />传统的模拟退火如果当前状态更有就接受，否则以一定概率接受，概率的存在保证不会跳进局部最优而出不来。<br />不过用概率搞貌似效果不是很好，然后就初始生成100组解，对着100组并行操作，只在更优的时候接受，这样每组解最后都会到达他所在区域的局部最优解，而全局最
2011-04-24 19:36:00
1220
2
原创 Perfect Domination on Trees [UVALive 3346] 树形DP
题意：给你一棵树，用黑白染色，求最少的染黑的个数，使得每个白点都与且只与1个黑点相连。题解： dp[x][f]表示将x染成f状态最少需要染多少黑点，f有三种状态:0,1,2 0：表示该点为白色，且他的所有儿子都为白色。 1：表示该点为黑色。 2：表示该点为白色，且他有一个儿子为黑色。 dp[x][1]=sigma(min(dp[son(x)][1],dp[son(x)][0])); dp[x][0]=sigma(dp[son(x)][2]);
2011-04-24 19:15:00
1426
原创 Lego Bricks [2011 浙江省赛I题] 计算几何
<br /> <br />省赛的时候没发现这道水题，发现了的话会毫不犹豫的上去写这道的，虽然估计也写不完，但至少算法是很清楚的。写完的时候都有300来行了= =！<br />题意：<br />给定n个园和m个线段,初始圆已经被固定住，要求把m个线段放上去，能否使m个线段都被固定。如果有线段已经被固定，这可以用这些线段来固定剩下的线段。<br />题解：<br />被固定的意思显然是重心被支撑住，可以有一半以上架在圆上，或者两端都有支撑点。<br />转化成算法就是把线段平均分成两段，如果两段都能被固定则整个
2011-04-21 18:19:00
1324
2
原创 Awkward Lights [UVALive 5070] 高斯消元
<br />题意:<br /> 一个0/1矩阵,表示开关,0关,1开,按(i,j)这个开关后则跟他曼哈顿距离为d的开关改变状态.<br /> 问能否将改状态变为全0.<br />题解:<br /> 首先逆向思维,题目要求等价于将全0变为所求矩阵.<br /> 然后对于每一个开关,要么按一次,要么不按,按两次以上等价于按了%2次,设未知数x(i,j)表示按1次或0次.<br /> 则可以列n*m个方程:<br /> x(i,j)+sigma(x(ii,jj))=a[i][j] (a[i][j]为给
2011-04-08 19:40:00
1396
原创 Fire Drill [UvaLive 5064] BFS+0/1背包
<br /> <=写成<<检查了好久= =!<br />题意:<br /> 给你一个多层迷宫,每层迷宫有向上或者向下的楼梯,有些人被困在迷宫里面,每救一个人获得一定分数,不带人每走一格花费时间1,带人花费时间2,问在s秒内最多获得多少分数.<br />题解:<br /> 关键是人跟人之间没影响,所以先BFS预处理出跟每个人的最短距离,然后距离*3即为就这个人的花费时间,做一遍0/1背包即可.<br /> <br />代码:<br />/* * File: main.cpp * Author: s
2011-04-06 15:10:00
940
原创 Just Sum It [UvaLive 5063] DP+组合数
<br />TLE到死,加了n多优化才过,泪流满面.<br />题意:<br /> 给你a1,a2..a9,ai表示有ai个i,问用这些数字组成的不同的数的和MOD 1000000007以后是多少.<br />题解:<br /> 首先方法显然:<br /> 枚举位数,枚举某个数在哪个位上,假设有l位,数i在第j位上,则i在这个位上贡献的值为i*10^(j-1)*(剩下的数排列成l-1位的不同排列个数).<br /> 在所有不同的位数下,所有数在不同位置上贡献的值求和即是所求结果.
2011-04-06 14:59:00
1293
原创 HDU 3804 Query on a tree 非递归深搜 STL应用
<br /><br />题意:<br /> 给定一颗树,边有权值,有q个查询,每次查询,x,y求1到x直接的所有不大于y的边的最大值.<br />题解:<br /> 离线,先读入所有查询,再深度遍历这棵树,遍历到一条边就把边的权值扔到set里,返回的时候再把这条边的权值删掉.<br /> 如果遍历到的当前点有询问,则对set进行upbounder,找到比当前y大的第一个位置,对迭代器--即可.<br />/* <br /> * File: main.cpp<br /> * Author: swordho
2011-03-30 16:14:00
1506
原创 POJ 3525 半平面交
<br /><br />题意:<br />求凸包内切圆最大半径<br />题解:<br /> 二分半径,将凸包所有边往凸包内平移这么半径长度,看平移后是否能围成凸包.<br />/* <br /> * File: main.cpp<br /> * Author: swordholy<br /> *<br /> * Created on 2011年3月25日, 下午7:56<br /> */<br />//求凸包内切圆最大半径<br />#include <cstdlib><br />#include <
2011-03-29 20:58:00
1442
原创 Europe - Southwestern - 2006/2007 简明解题报告
<br />A:<br />求N由每堆只能n^3,n*(2n+1)*(n+1)/6,构成的最少堆数,简单DP,先预处理所有结果,再读入一个输出一个,否则要超时.<br />B:<br />Undo<br />C:<br />并查集合<br />D:<br />网络流,对每个航班拆点,拆掉的两点间容量为航班人数,所有航班间满足时间条件和有公共位置连边,容量inf,超级源连起点,容量inf,终点连超级汇,容量inf.<br />E:<br />DP,注意数据里有空格,用scanf超时,cinWA,gets才是A
2011-03-27 21:01:00
941
2
原创 Tarjan算法拾遗
<br />1.求割点的时候根节点为什么要特判?<br /> 1-> 2 -> 3<br /> /|/ |<br /> -----<br />弱1为根节点,dfn[1]=1,永远dfn[1]<=low[v],不特判的话根节点就永远是割点了.<br />但是当根节点只有一个儿子的时候他就不一定是割点了,所以只有跟节点有两个儿子以上才是割点.<br /> <br />2.求强连通的时候为什么要v在队列中才能跟新low[u]=min(low[u],dfn[v])?<
2011-03-25 14:38:00
806
2
原创 Trade HDU 3401 单调队列DP
<br />题意:<br /> 给定每天的股票买进上限,买进价格,卖出上限,卖出价格,每两次买卖操作中间必须间隔w天,每天最多持有maxp个股票,问n天后最大收益是多少<br />题解:<br /> DP方程显然:<br /> dp[i][j]=max(不买不卖,买入操作,卖出操作)<br /> 不买不卖<br /> dp[i][j]=max(dp[i][j],dp[i-1][j])<br /> 买<br /> dp[i][j]=max(dp[pre][k]-(j-k)*AP[
2011-03-16 18:07:00
1627
原创 Cross the Wall HDU3669 斜率优化DP
<br />纠结了近一个星期,泪奔~~<br />题意:<br />给你n个矩形,长宽已知,求用不超过k个大矩形包含所有给定矩形,使得大矩形总面积和最小.<br />题解:<br /> 首先DP显然,有状态转移方程:dp[i][k]=min(dp[j][k-1]+w[j+1].y*w[i].x) (k-1<=j<=i-1)<br /> 令w[j+1].y=y,dp[j][k-1]=x,w[i].x=k;<br /> yy=x+ky,求min yy<br /> y=-
2011-03-14 18:38:00
2488
2
原创 People like People ZJU 2682 强联通+记忆化搜索
<br />题意:<br /> 给定一个有向图.<br /> 求一个最大的集合,是所有属于这个集合的点都满足以下条件:<br />1.出度不为0<br />2.指向的点都在这个集合内<br />3.有属于这个集合的点指向这个点<br />题解:<br /> 我的做法是:对图缩点后,枚举每个点,以这个点作起点,并且这个点是由大于等于2个点缩点而得到的,然后这个点为根,以他能访问到的点构成树,如果所有叶子都是大于等于两个点以上缩点得到的,则说明该树构成一个合法的集合.取最大的合法集合即可.<br />/*<br
2011-03-07 16:57:00
843
原创 KTX Train Depot [UVAlive 4852]
<br />题意:<br /> 有很多火车会从东西两个方向进入轨道,进入时间小于0,出去时间大于0,问最少要多少轨道使得轨道之间不互相堵塞.堵塞是指一辆火车要往西另一辆要往东,两个互相堵塞都出不去,或者两个都向一个方向,但是在门口的出去时间比他的后面的出去时间晚.<br />题解:<br /> 首先考虑一个方向的,比如都是从东进从东出,按进入时间排序是显然的,比方说按时间从小到大排,那么一辆火车想进入一个轨道的话它的出去时间必然要比已有轨道的出去时间小,否则堵塞了,然后他必定接在跟他时间最接近的轨道上
2011-03-02 19:34:00
1007
原创 Tour Belt [UVALive 4848] 并查集+枚举边长
<br />题目要求:<br /> 求出满足以下两个条件的子图数:<br /> 1.子图定点数大于等于2<br /> 2.子图中的所有边都大于(所有子图外的(与子图中的点有公共点的的边的长))<br />题解:<br /> 将边的长度离散化,从大到小枚举边长,每次统计最小边边长为枚举的边长的子图,累加即可.<br />/* <br /> * File: main.cpp<br /> * Author: swordholy<br /> *<br />
2011-03-02 14:42:00
1079
原创 Matrix Revolution BFS HDU 1759
<br />题意：<br /> 对于给定的一个矩阵A，A+A^2+A^3+...+A^K 是多少呢？<br />其中A^2 表示两个矩阵的乘积A*A，A^3表示三个矩阵的乘积A*A*A，依此类推。<br />求结果中的非0元素个数。<br />题解：<br /> 逆向思维：平时一般都用矩阵来表示一个图，这里用图来表示一个矩阵。A^K中A[i][j]表示从在这个图上i走了K步后可达到j。<br />代码：<br /> /* <br /> * File: main.cpp<br /> * A
2011-01-19 17:39:00
1459
原创 Fix 状态压缩DP HDU 3362
<br />题意：<br />给n个点（n<=18）,有些点固定了，有些点没固定。每个点都有坐标，目标是把所有点都固定住，一个未固定的点至少要跟两个点相连才算被固定。<br />题解：<br />由于n不大，所以可以用二进制位表示该点是否被固定，一遍DP即可。<br />代码：<br /><br />int main(int argc, char** argv)<br />{<br /> int i,j,m,x,y,sum;<br /> double l1,l2;<br /> while(
2011-01-17 13:02:00
1329
原创 In Action 最短路加背包 HDU 3339
<br />题意：<br /> AC大神要引爆核弹毁灭世界，他有n个电站，每个电站有一定电量，引爆需要至少一半的电量。<br /> 从原点0可以派出足够多的tank去占领，占领电站就能切断该电站对引爆核弹电量的供应。原点与电站之间构成一副无向带权图，权表示从一个点到另一个点tank的耗油量，求拯救世界需要最少的油耗。<br />题解：<br /> 一遍最短路，算出占领每个点最少需要油耗。<br /> 然后一个点有两个属性，油耗和电量，将油耗当重量，电量当价值，0/1背包即可。<br />代码：<br
2011-01-17 10:42:00
768
原创 WuKong 最短路加DP HDU 2833
<br />题意：<br /> 给定一个无向图，和两对起点终点，求两条最短路上的最多公共交点数。<br />题解：<br />首先有个很强的性质：<br /> 所有公共点必定连续。<br />可以用反证法证明：<br />若a,b 为公共点，且他们不连续。<br />因为他们不连续，所以a到b至少有两条长度不同都路<br />与a，b为最短路上的公共点矛盾，最短路长度必然是确定的。<br /> <br />用cnt[i][j]在做最短路的时候记录下从i到j的包含节点数最多的最短路。<br />因为公共点是
2011-01-16 21:08:00
1182
原创 zz一辈子的好人
<br /><br />/*<br /> *转自Roba‘s Blog.<br /> */<br />好人们其实就在你我身边。<br /> <br />他们一般说来长相普通（长得太帅的通常当不了好人），个性温和且忠厚老实，往往有一项特殊的专长和技能，好比说是会修计算机，有设计专长，学问渊博爱读书…等等，但是在与陌生人交往时显得有点害羞。<br /> <br />有些好人热心助人，在同侪团体之间是大家都乐于来往的对象，不过只要一遇到漂亮的或自己喜欢的女生，好人马上就变成哑巴。他们的原则是，人与人之间本来就应该
2010-11-23 19:59:00
686
原创 ZJU 3433 Gu Jian Qi Tan 贪心 优先队列
<br /><br />跟前一次月赛的算法类似，能打就打，不能打就用当前的替换原来打过的花费最大的怪，贪心好题，开始往DP上想了好久，复杂度怎么都降不下来，贪心才是王道啊。<br />#include<iostream><br />#include<stdio.h><br />#include<algorithm><br />#include<queue><br />using namespace std;<br />int spe[1005][1005];<br />int add[1005];<br /
2010-11-15 12:30:00
852
原创 Food combination ZJU2861 组合数学
<br />转化为模型即为求最多含有L个1的N位二进制数中的第M大的数<br />#include<stdio.h><br />#include<iostream><br />#include<memory.h><br />using namespace std;<br />#define MAXN 63<br />long long a[MAXN]; <br />long long b[MAXN]; <br />long long c[MAXN][MAXN];<br />long long gcd
2010-11-09 19:37:00
786
1
原创 子阵最小值查询_二维RMQ
给定一个n*n的矩阵，有q次查询，每次查询一个子矩阵最小值YY了一个n^2log(n)+n*q 的算法:建了n个一维RMQ，预处理n*n*log(n),每次查询复杂度O（n）,果断TLEGoogle了一下才发现还有二维RMQ这种东西。。。对代码用类封装了下。。。RMQ_2D(O(n*n*log(n)*log(n)预处理，O(1)查询，查询以(x1,y1)，(x2,y2)为对角的矩形最小值)<br />class RMQ_2D<br />{<br /> int dMin[MAXF][MAXF][MAXN][M
2010-11-09 18:13:00
1054
3
转载 ZZ博弈论和纳什平衡
<br /><br />搜索：博弈论与纳什平衡<br />作者：车东 发表于：2005-04-12 20:04 最后更新于：2006-01-08 23:01<br />版权声明：可以任意转载，转载时请务必以超链接形式标明文章原始出处和作者信息及本声明。<br />http://www.chedong.com/blog/archives/000728.html<br />博弈论（game theory）对人的基本假定是：人是理性的（rational，或者说自私的）,理性的人是指他在具体策略选择时的目的是使自己
2010-11-07 20:52:00
2222
转载 zz来自圣经的算法
<br /><br />《来自圣经的证明》收集了数十个简洁而优雅的数学证明，迅速赢得了大批数学爱好者的追捧。如果还有一本《来自圣经的算法》，哪些算法会列入其中呢？最近，有人在 StackExchange 上发起了提问，向网友们征集那些来自圣经的算法。众人在一大堆入围算法中进行投票，最终得出了呼声最高的五个算法：<br /> <br />第五名： BFPRT 算法<br /> 1973 年， Blum 、 Floyd 、 Pratt 、 Rivest 、 Tarjan 集体出动，合写了一篇题为 “Tim
2010-11-02 15:02:00
870
原创 无聊贴个KMP模板
<br />快退化到连KMP都不会了，重写个KMP复习下<br />int next[MAXN],F[MAXN],S[MAXN];<br />void get_next(int *s,int l)<br />{<br /> int i,j;<br /> memset(next,0,sizeof(next));<br /> i=-1;next[0]=-1;j=-1;<br /> for(i=1;i<=l-1;i++)<br /> {<br /> while(s[j+1]!=s[i]&&j!
2010-10-26 18:59:00
697
原创 杭州现场J题_Infinite monkey theorem
<br />构造一个DFA， 对于样例：<br />2 100<br />a 0.312345<br />b 0.687655<br />abab<br />即：<br /> (b)<br />-----------<br /> | /<br /> | /<br /> | /<br />// /<br /> (a) (b) (a) (b) <br />NULL--
2010-10-26 18:56:00
1132
原创 PKU 1091 跳蚤 数论 容斥原理
#include#includeusing namespace std;#define MAXN 20#define MAXP 200000__int64 p[MAXP],tp,ans,n,m;void get_pri(__int64 x) //求素因子{ int i; tp=0; for(i=2;i*i { if (x%i==0) { while(x%i==0) x/=i; p[++tp]=i; } } if (x!=1) p[++tp]=x;}__
2010-10-21 23:55:00
1114
2
原创 HDU 3221 上海09 B题 矩阵乘法 数论
用到一个公式A^x%C=A^(x%phi(C)+phi(C))%C (x>=phi(C))#includeusing namespace std;#define MAXN 20__int64 Modal;bool flag;__int64 eular(__int64 n)//取出1到n中跟n互质的数的个数{ __int64 ret = 1,i; for (i = 2;i * i 1) ret *= (n - 1); return ret;}class
2010-10-09 11:38:00
1016
原创 HDU 3076 ssworld VS DDD DP 概率水题
<br />题意：<br /> A,B掷骰子，对于每一次点数大者胜，平为和，A先胜了m次A赢，B先胜了n次B赢。<br />题解：<br /> 先将平局情况处理出来，让他们一定要分出胜负，对于每一次p1表示A赢，p2表示B赢，p=1-p1-p2表示平局，所以在不死不休的情况下，A赢的概率为p1+p*p1+p^2*p1+...p^n*p1,n->无穷，即a_win=q1/(1-p);b_win=q2/(1-p);<br />然后在他们一定会分出胜负的情况下就可以dp了：<br /> dp[i][j]=dp
2010-10-06 20:42:00
2568
5
原创 HDU 3074 Multiply game 逆元 树状数组
<br />题意：<br /> 求一个区间内所有数的积模一个素数的值，会动态改变其中的值。<br />题解：<br /> 可以用线段树，网上大部分搜到的都是线段树。<br /> YY的一个方法：对所有数取对数，放进树状数组里，对于求[l,r]的积可以e^( (q(r)-q(l-1)) fmod log(MOD) ),极大的精度误差基本上一个点都过不了，= =！<br /> 多校的解题报告里：<br /> 对于求[l,r]的积可以q(r)*inv(q(l-1)),inv(x)为求x关MOD的逆元，注意更新
2010-10-06 20:30:00
1086
1
原创 HDU 3072 Intelligence System 强连通 最小树形图
<br />由于环内传递不需要费用，求最小树形图就变的很简单，在缩点过的图中取出每个点的最小入边求和即可。<br />///////////////////////////////*HDU 3072 Intelligence System 强连通分量 重构图 最小树形图*//////////////////////////////#include<iostream>#include<vector>using namespace std;#define MY_MAX 10
2010-10-06 20:18:00
1946
1
原创 HDU 3070 有度限制的生成树的个数
<br />首先有个现成结论，根据pseudo code，可以把n个点无度数限制的生成树的个数映射到n个数放到n-2个位置上的个数，即n^(n-2);但是当每个点的度数被限制为d时，即每个数最多能放在d个位置上，这时候就没有直接公式了。<br />先看下那个公式：n^(n-2)是从每个位置考虑过来，每个位置有n种可取，做n-2次这样的操作n^(n-2)。<br />换个角度思考：<br /> 从每个数考虑过来，即是每个数最多能被d个位置使用。<br /> 这时候就可以得出递推公式：<br />
2010-10-06 20:15:00
1466
原创 HDU 3069 Arrest
<br />题意：<br /> 最小要多少警察能把一棵树中所有小偷抓出来。<br />思路：<br /> 派一个警察守住路口，别的警察把这颗子树除了最大的一棵以外的都搜一遍，再一起往最大的那一颗子树过去，这时候就不需要派人守住路口了。<br />代码：<br />#include<iostream>#include<vector>#include<iterator>using namespace std;#define MAXN 1005vector<int> map[MAXN];
2010-10-06 19:58:00
1062
1
原创 哈尔滨水题报告
<br />在网上观战的时候群里算法都说的差不多了，然后杭电把题目挂出来以后和君爷又去做了下，据tracyzhu说知道算法以后再去做要损RP的，希望RP别降太多。基本把水题搞完了，还剩下一个3D凸包，一个DLX和一个O（n）DP，有空再去搞，斜率优化DP基本看完了，过几天估计就能a掉了。<br />A：<br />树形DP，treedp(cur,flag)表示访问到cur点，flag为1Alice走取最小的，0表示Bob走取最大的。<br />做的时候被时限恶心到了，用vectorTLE，改成临接表还是TL
2010-10-06 19:49:00
1405
1
原创 HDU 3183 RMQ
<br />题意：<br /> 在一个n位数中删除m位使其值最小。<br />解法：<br /> 题目要求与从n位数中取出n-m位使其最小等价，然后就很简单了，每次RMQ出(l+1,n-(n-m-i)-1)最小值输出即可,l为前一次最小值位置，i为当前在取第i位，n-(n-m-i)-1是为了保证取出这个最小值后加上后面的位数保证能构成n-m位。<br />代码：<br /> #include<iostream>#include<string>using namespace std;cons
2010-10-06 18:37:00
1421
2
原创 二分答案全攻略
<br />当直接求解答案比较困难时，可以枚举答案，再判断枚举得到的这个答案是否合法。<br />如果这个答案还具有单调性，就可以用二分加速枚举过程。<br />Kth Largest(http://acm.hrbeu.edu.cn/index.php?act=problem&id=1005&cid=14)(二次二分)<br />题意:<br /> A,B两个数组，求出两个数组互相乘以后生成的n*n个数中的第k大的数。<br />解法:<br /> 对A，B从小到大排序。<br /> 二分第k大的数的值
2010-09-10 14:47:00
3869
1
原创 Splay大功告成
写的时候很纠结，磕磕绊绊的，断断续续的搞了好几天，其实前几天就写完了的，不过没a过题，正确性没经过历史的检验。今天无聊在杭电找了道Splay的入门题a了下，情况竟然出奇的顺利，除了因为内存泄露超内存了几次，改正后竟然一次AC了，RP啊，这次终于爆发了，从来都没这么顺利过= =！既然有Splay了，平衡树什么的也就懒的去搞了，，先将就着用了= =！（指针版的，数组版的内存维护太麻烦，指针版好写点）//hdu1754#includeusing namespace std;#define MAXN 1
2010-09-07 13:13:00
881
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人