- 博客(224)
- 资源 (6)
- 收藏
- 关注
RSS订阅原创 POJ 3694 Network(割边+LCA)
<br />//Tarjan求桥 + LCA//蛋疼题目，确实想不到用LCA这个如此巧妙的方法，主要也就写下求桥，对Tarjan的DFN,LOW值再加深下理解//重点是对桥的记录，本来想通过用边来记录，后来发现这是无解的，用桥与点对应就可以了//一开始还想实践下LRJ书里面说的，缩点后形成的树每条边都是桥，后来觉得太难打了..就我这么渣的代码能力，打起来太蛋疼了- -|||#include<iostream>#include<cstdio>#include<cstring>#in
2011-05-05 21:14:00
2800
原创 SYSU/ICPC 2011校赛总结
<br /><br />一年前的那个时候，我神马常见算法都不会，就只会调用下STL，就和ZMQ组队去校赛，校赛预选赛就0题被刷掉了。那年的悲剧是相当正常的，我们连Standing都不会刷，都不知道是干嘛的，看哪题做的人比较多也不会看，就傻傻的看一题写一题，不会做跳过，不过还是得吐槽下，2010年校赛预选赛的题也太难了吧！严重打击新手啊！不过最最悲剧的是，我们连他加了一题超级水题都不知道.....我还以为是大家太牛逼了，题目都给做光了！不得不补一道难一点的，免得人家提前走人侮辱出题方！后来才发现，原来是因为题
2011-04-04 14:19:00
3942
8
原创 Sicily 1135 飞越原野(BFS宽度优先搜索)
<br />//BFS宽度优先搜索//G[x][y][k]表示走到(x,y)后还能飞k步的最优值#include<cstdio>#include<iostream>#include<cstring>#include<queue>using namespace std;const int MAX = 102;const int dir[4][2] = {1,0,-1,0,0,1,0,-1};int N,M,D,ans;int G[MAX][MAX][MAX];boo
2011-04-01 16:04:00
3390
转载 微软、google、雅虎、百度等各大著名公司的经典面试题
<br /><br />微软十五道面试题<br />1、有一个整数数组，请求出两两之差绝对值最小的值,<br />记住，只要得出最小值即可，不需要求出是哪两个数。<br />2、写一个函数，检查字符是否是整数，如果是，返回其整数值。<br />（或者：怎样只用4行代码编写出一个从字符串到长整形的函数？）<br />3、给出一个函数来输出一个字符串的所有排列。<br />4、请编写实现malloc()内存分配函数功能一样的代码。 <br />给出一个函数来复制两个字符串A和B。字符串A的后几个字节和字符串B的
2011-03-24 01:02:00
3354
原创 Sicily 1140 国王的遗产(搜索|图论)
<br />//搜索，暴力//这题卡了我几天，检查到最后，居然是我的minID维护错误！我艹！这种错误居然卡了我几天！！！我就是一个超级无敌大水人！//不过卡了这几天也好，程序也经过不断优化//做法是预处理出以每个结点为根的子树有多少个结点cnt，以每个结点为根的子树最小编号minID//接着枚举所有边，暴力找出每个可行方案//在搜寻每一个可行方案，都以编号最小的结点作为根，这一个优化方案，可以省去搜索比较上下两部分的最小编号值//这题有几个重要结论是需要证明的//1、在树中仅存
2011-03-23 16:40:00
5325
2
原创 Sicily 1089 Farey Sequence(欧拉公式)
<br />//欧拉函数是少于或等于n的数中与n互质的数的数目//通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数，x是不为0的整数。//φ(1)=1（唯一和1互质的数就是1本身）。//知道了这个还不一定做出来，他编程实现还需要用筛选法那种方式，才能大大降低实现复杂度#include<iostream>#include<cstdio>#include<cstring>#include
2011-02-27 21:11:00
2884
原创 POJ 2817 WordStack(状态压缩DP)
<br />#include<iostream>#include<cstdio>#include<cstring>using namespace std;int pow[15];int dp[1<<12][10],N;char word[15][25];int W[15][15];void init(){ int w; memset(W,0,sizeof(W)); for(int i = 0;i < N;++i) { for(int j = 0;j
2011-02-27 14:13:00
2422
原创 POJ 1837 Balance(DP动态规划)
//DP，动态规划求组合数,dp[i][j]表示前i个重锤获得重量j有几种方式//转移方程dp[i][j+k] += dp[i-1][j];k为新添加第I个重锤的质量//对重锤对应钩子将其分组后来处理#include#include#includeusing namespace std;int dp[25][1000];int C[25],G[25];int N,M;const int mid = 500;void DP(){ dp[0][mid] = 1
2011-02-25 00:10:00
2261
原创 POJ 3107 Godfather(DFS)
//DFS水题，在树中找到满足下条件的点集，若删除当前点集的点，则将树划分成的最大连通块最小，DFS统计即可//统计方式只需要记录以当前结点为根的子树的结点数num，若要求父亲那一坨连通块只需要用N个点减去他所有儿子的num值即可#include#include#include#includeusing namespace std;const int MAX = 50005;const int INF = 200000000;int V[2*MAX],next[2*MAX
2011-02-24 22:24:00
2475
原创 POJ 2761 Feed the dogs(Treap求第K小数)
//TREAP求第K小数//感谢JSH大牛的指点//这道题之所以可以用TREAP做是因为题意中有个条件，询问区间不会出现包含的情况，因此通过对询问区间进行排序//然后通过插入和删除的方法，来维护区间的第K小//平衡树的话自然首选TREAP了，TREAP中比较难的就在于删除那里，删除的方式是通过将要删除的结点通过左右旋的方式，在维护LEV为堆的同时，将要删除结点旋到叶子结点处，然后删除#include#include#include#includeusing namespa
2011-01-29 00:34:00
3736
1
转载 JAVA多线程编程总结
<br />一、认识多任务、多进程、单线程、多线程要认识多线程就要从操作系统的原理说起。 以前古老的DOS操作系统（V 6.22）是单任务的，还没有线程的概念，系统在每次只能做一件事情。比如你在copy东西的时候不能rename文件名。为了提高系统的利用效率，采用批处理来批量执行任务。 现在的操作系统都是多任务操作系统，每个运行的任务就是操作系统所做的一件事情，比如你在听歌的同时还在用MSN和好友聊天。听歌和聊天就是两个任务，这个两个任务是“同时”进行的。一个任务一般对应一个进程，也可能包含好几个进程。比如
2011-01-21 11:16:00
2187
原创 Sicily 1033 City Road(递推)
//模拟+递推，感觉这种题不能称之为动态规划，只能叫递推因为每个点只调用了一次，不存在所谓的转移//题意是从起点到终点，有多少种不同的走法，图中有些路有障碍//注意到规模是M*N #include#includeusing namespace std;int M,N,B;int x,y,dx,dy;bool X[2000000],Y[2000000];long long A[20
2010-12-27 20:00:00
2905
1
原创 Sicily 1039 Phone Home(DFS染色)
//dfs染色+二分答案#include#include#include#includeusing namespace std;const double MAX = 400;struct coord{ double x,y;}P[15];double calDis(coord a,coord b){ return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}vector E[15];int G[15];//
2010-12-26 19:58:00
2723
原创 Sicily 1050 Numbers & Letters(DFS)
//DFS回溯，其实就是24点游戏的问题//没想到那么蛋疼，居然卡了我很久，显然的深搜题//回溯思路是这样的，5个数，先任意找2个数进行加减乘除，把这2个数运算后的结果当做一个数，按相同的方法搜下去//把4个数任取2个然后合并成3个，再继续搜下去//搜索树的深度为5， 第一层最多有C(2,5)*5种分支,这里5表示两个数做运算最多能产生5种结果//第二层C(2,4)*5...显然搜索树规模挺小的，加上除法这一运算产生的几率更小，因此这样搜过去必然没问题//我WA了很久的一个原因是初始
2010-12-26 00:43:00
5004
原创 ZOJ 3324 Machine(线段树)
给定操作有2种，一种是让[X,Y]下压1格，一种是让[X,Y]向上恢复1格，恢复操作必定是之前下降过的。初始状态在LEVEL=0处，对每个操作回答LEVEL=0处有几块连续的方块。首先这道扑街题的规模高达10^8，因此还要对区间进行离散化。离散化过程中还要保存被操作结点之间相对位置，即之间是否有空格存在。幸亏用SET判重+MAP离散对应还不慢，使代码简洁了很多。接下来总结下这道题对标记域使用。cnt是必要的，记录当前区间的连续块数。为了合并区间，还要记录区间的左连续和右连续情况。再用cov记录当前区间被覆盖
2010-12-06 01:18:00
3581
2
原创 POJ 1080 Human Gene Functions(动态规划——LCS问题变形)
//DP动态规划，LCS问题变形。根据LCS经典模型，我们就用dp[I,j]表示匹配到i和j的最优值.最终答案就是DP[LEN1][LEN2]//显然有两种情况：//一、s1[i] == s2[j],也就是遇到相同字母的，状态转移自然是dp[i][j] = 5 + dp[i-1][j-1]//二、s1[i] != s2[j],遇到不同的呢，有这么几种匹配情况：// 1、硬将s1[i]和s2[j]匹配上去 // 2、不匹配，拿他们去和空格匹配，这样就有2种匹配方案//
2010-10-21 02:26:00
2360
原创 Sicily 1802 Atomic Nucleus Investigation(线段树)
新手赛的题目，让我回想起打酱油的时光//线段树#include#include#include#define INF 100000000using namespace std;int T,M;char cmd[10],n;bool R[100005],G[100005];struct seg{ int l,r,_max,_min,delta;//记录最大值，最小值，最优差值，_max,_min为0表示不存在这个数}tree[100005*4];void u
2010-10-14 21:59:00
2874
3
原创 Sicily 1828 Minimal(动态规划)
//动态规划//这题的关键在于先排序，只有先排序，后面动规的思路才能出来，我就是想不到得先排序，卡了好久还得别人提醒//我是NC不解释//题意是对2个集合寻找N对数对，使得数对的距离之和最小//如果你先排好序，那么用DP(i,j)表示A集合的前i个点与B集合前j个点的最优值//那么对于第i+1个A集合的点而言，他的最优解就是前i个点与B集合前j个点的最优值加上第i+1个点与第j+1个点的距离//或许i+1与j+1配对不是最好的，它可能比上一个状态DP(i+1,j)要差//综上
2010-09-29 01:14:00
3520
原创 Sicily 1034 Forest(DFS)
//图的遍历，DFS,统计森林的宽度和深度，加上对环的判断//一道这么简单的题我一开始用BFS,结果WA到吐血，唉，我这个大水人#include#include#includeusing namespace std;bool vis[105],ok;int width[105];vector E[105];//邻接表int N,M,W,D,in[105];void dfs(int u,int d){ if(vis[u])//发现已搜过的点，证明存在环 {
2010-09-19 00:15:00
4110
原创 POJ 3414 Pots(BFS倒水问题)
//BFS倒水问题,对于需要打印解得广搜题，必须保存搜索状态和状态的父亲指针，然后逆推，根据状态和状态之间的关系//判断属于那一种情况，并将解记录，还有POJ的1606也是同样类型的题，只不过要求有点点不一样，规模也有点点不一样//代码也就不重复贴了~#include#include#include#includeusing namespace std;bool vis[105][105];int A,B,C;vector ans;struct State{
2010-09-18 15:21:00
3427
原创 Sicily 1153 马的周游问题(DFS深度优先搜索)
//经典的深度优先搜索，必须剪枝才能通过，而且剪枝策略十分神奇，先走下一步可行拓展数最少的，看了大牛的题解才会的//也就是说假如当前结点有8个可以走的拓展点，对每个可行拓展点再计算它的可行拓展数，然后排序，先走那个可行拓展数最小的//就是先走那个最没前途的点，这样会更快，因为它这么没前途，要从其它点到达它就更难了，所以先走#include#include#include#includeusing namespace std;int dir[8][2] = {-1,-2,-1,
2010-09-18 01:29:00
4213
1
原创 POJ 3311 Hie with the Pie(Floyd+状态压缩DP)
//Floyd + 状态压缩DP//题意是有N个城市(1~N)和一个PIZZA店(0),要求一条回路，从0出发，又回到0，而且距离最短//也就是TSP(旅行商)问题，首先不难想到用FLOYD先求出任意2点的距离dis[i][j]//接着枚举所有状态，用11位二进制表示10个城市和pizza店，1表示经过，0表示没有经过//定义状态DP(S,i)表示在S状态下，到达城市I的最优值//接着状态转移方程:DP(S,i) = min{DP(S^(1#define INF 100000000
2010-09-17 14:11:00
4985
原创 POJ 1077 Eight(BFS八数码问题)
#include#includeusing namespace std;typedef int State[9];const int MAXS = 1000003;State st[MAXS],goal = {1,2,3,4,5,6,7,8,0};int dir[4][2] = {-1,0,1,0,0,-1,0,1};int head[MAXS],next[MAXS],fa[MAXS];//父亲指针用来记录状态之间的关联，方便打印解vector ans;//保存方案voi
2010-09-16 10:41:00
1172
原创 POJ 1657 Distance on Chessboard(搜索题)
//搜索题，王用宽搜解决，后用点和点的斜率解决，只有两种情况，要么1，要么2。//车直线判断即可，要么1，要么2。//象斜率判断加所在格子的黑白情况进行判断，我想出了一个好方法。行列同奇同偶，为白色，行列奇偶互异为黑色。//象如果在黑色格子上，他永远到不了白色格子，这是性质。#include#includeusing namespace std;bool vis[64];int dir[8][2] = {-1,-1,-1,0,-1,1,0,-1,0,1,1,-1,1,0,1,
2010-09-12 17:05:00
843
原创 POJ 1102 LC-Display(模拟题)
//模拟题//将每个数字从上到下划分成5个部分，将打印分为5种类型//1：空白 2：- 3：左| 4：右| 5：| |两竖，同时设置5个部分的打印接口//接着LCD数组存放这个每个数字每个部分的打印类型#includeusing namespace std;int S,N,len;int data[10];int LCD[10][5] = {1,4,0,4,1, 0,3,0,3,0, 1,3,1,2,1, 1,3,1,3,1, 0,4,1,3,0, 1,2,
2010-09-10 14:04:00
954
原创 POJ 1157 LITTLE SHOP OF FLOWERS(动态规划)
//动态规划//设S[i,k]表示第i种花束摆在第k个之前(包括第k个)的任意某个花瓶中，前i种花束能够获得的最大美学值(之和)//原问题的最优值即为S[F,V]//S[i,k] = max{S[i-1,k-1]+A(i,k),S[i,k-1]}，(i>1，k>i);//初始条件为：//S[1,1] = A[1,1]; //S[1,k] = max{A(1,k),S[1,k-1]}，(k>1);//S[i,i] = S[i-1,i-1]+A(i,i)， (i>1) //要点，
2010-09-09 23:01:00
849
转载 sscanf 用法详解
<br /> <br /> <br /> <br />名称:<br />sscanf() - 从一个字符串中读进与指定格式相符的数据.<br /> <br />函数原型:<br />Int sscanf( string str, string fmt, mixed var1, mixed var2 ... );<br />int scanf( const char *format [,argument]... );<br /> <br />说明：<br />sscanf与scanf类似
2010-09-08 00:01:00
900
原创 POJ 1160 Post Office(动态规划)
//经典动态规划//dp(i,j)表示用i个邮局，从1到j村庄的最优解//dis(i,j)表示只用1个邮局从i到j村庄的最优解,显然取i,j中点的村庄作为邮局点是最优的//动态转移方程：dp(i,j) = min{dp(i-1,k) + dis(k+1,j)}(i #define INF 1000000000using namespace std;int d[305];int dp[35][305],dis[305][305];int n,m;void init(){
2010-09-07 16:09:00
3378
原创 ZOJ 3368 Trick or Treat(二分答案)
//二分答案，注意精度只需要满足1e-5，无需跟sample一样也可AC//题意是求一个点(x,0)使得其他点到它的最大距离最小#include#includeusing namespace std;struct coord{ double x,y;}A[50005];double ans,l,r,mid,X;int ansP,n;const double eps = 1e-6;//精度设置void cal(double mid){ ans = 0;
2010-08-28 21:00:00
1214
原创 POJ 2488 A Knight's Journey(DFS——骑士周游问题)
//要按字典序输出，所以要注意搜索顺序//最后一行不能留空行//唉，搜都要写这么久，还WA了那么多次，太弱了我#includeusing namespace std;int Case,X,Y;bool vis[50][50],ok;int dir[8][2] = {-1,-2,1,-2,-2,-1,2,-1,-2,1,2,1,-1,2,1,2};int path[30][2];bool legal(int x,int y){ if(x X || y Y)
2010-08-24 00:54:00
1219
原创 POJ 2594 Treasure Exploration(传递闭包+最小路径覆盖)
//传递闭包的建立(Floyd) + 最小路径覆盖//这题有别于1422，原因在于它是一个有向图，而非DAG，机器人可以绕一圈回来在走其他路//the roads of two different robots may contain some same point.//例如1->2,2->3,3->4,4->2,2->5这一个有向图，这个图只要1个机器人就可以走完所有路，但如果不建立传递闭包//直接根据边进行匹配，那样得出来的结果是不正确的，因为平时所指的路径覆盖，顶点最多只经过一次，而这
2010-08-18 09:35:00
1533
1
原创 POJ 3216 Repairing Company(Floyd + 二分图最大匹配)
//Floyd + 二分图最大匹配//将任务抽象为点，如果任务i完成后还能够赶上任务j的开始时间，则在i-->j连上一条边//题意是要求分配最少的维修工完成维修工作，那么最坏情况就是每个任务分配一个，共M个//但是有时多个任务能够由一个维修工完成，如果任务i和任务j之间有边相连，意味着i,j可以同时完成//那么可以减少一个维修工，这样一来，寻找最大的匹配，再用M减去最大匹配数，所得的结果就是最少的维修工数量了//前面必须用Floyd算法求出任意两点的最短距离，将-1转化为INF再处理即可
2010-08-18 08:23:00
1453
原创 POJ 2135 Farm Tour(最小费用流)
//最小费用流//构图关键是添加超级源点，超级汇点//题意是要找一条可以再终点往返的路，这2条路距离之和最短且每条路只能经过一次//第一步将问题转化为找2条从起点到终点//第二步与费用流挂钩，将距离当做费用，将容量设置为1是为了保证每条路只经过一次//超级源点和起点的容量为2，终点和超级汇点容量为2，使得最多找2条路//最终的mincost即为答案//注意双向边这个条件，当出现双向边或多重边时，就得用邻接表储存了#include#includeusing namesp
2010-08-17 01:34:00
856
原创 ZOJ 3362 Beer Problem(最小费用流)
//最裸的最小费用流#include#includeusing namespace std;const int MAXN = 105;const int MAXM = 8100;const int INF = 1000000000;int mincost,maxflow;int N,M;int U[MAXM],V[MAXM],cap[MAXM],flow[MAXM],cost[MAXM],next[MAXM];int head[MAXN],pre[MAXN],Edge
2010-08-17 01:27:00
898
原创 POJ 2516 Minimum Cost(二分图最小权匹配——KM算法)
//最小权匹配(KM算法)//构图是关键，又是拆点这个思想。因为商品数量很少，最多才3，所以将一个商品拆成3个点//一开始我将K种商品全部拆出来，想一次KM解决，结果构出来的图最坏情况是50*50*3 和50*50*3 的二部图来匹配最优权值//在经过O(n^3)的KM + 多组数据，结果毫无疑问的TLE了//此题的关键是将K种商品独立出来求解，因为K种商品相互无影响//将他们独立出来分别进行K次KM算法，大大降低了时间和空间//50*3和50*3的二部图最小权匹配//复杂度是O
2010-08-15 02:26:00
2431
2
原创 POJ 2455 Secret Milking Machine(二分答案+最大流)
感谢怀哥提供的经典好题，让我学会了二分答案这个思想!//二分答案+最大流//终于见识到传说中的二分答案这个方法了//如果没有二分答案这个提示，这道题我怎么也不会往最大流去想//思路是这样的，将所有边权值排序，记录边权值的上界和下界//接着开始二分答案，依照枚举的这个答案构图，即将边权值最大值小于等于枚举的这个答案的边加进图中//（双向边）并将他们的容量设为1，有多重边就将容量再+1，接着FF最大流，如果最大流>=T，则说明答案是满足条件的//记住此时未必是正确答案，答案还可以再小。继
2010-08-15 02:16:00
1641
1
原创 POJ 2195 Going Home(KM算法——二分图最小权匹配)
//最小权匹配(KM算法)#include#include#includeusing namespace std;const int MAX = 105;const int INF = 2147483647;char G[MAX][MAX];int lx[MAX],ly[MAX],xMatch[MAX],yMatch[MAX];bool vis_x[MAX],vis_y[MAX];int W[MAX][MAX];int slack,ans,N,R,C;stru
2010-08-13 18:11:00
915
转载 KMP算法详解(转自Matrix67大牛)
如果机房马上要关门了，或者你急着要和MM约会，请直接跳到第六个自然段。 我们这里说的KMP不是拿来放电影的（虽然我很喜欢这个软件），而是一种算法。KMP算法是拿来处理字符串匹配的。换句话说，给你两个字符串，你需要回答，B串是否是A串的子串（A串是否包含B串）。比如，字符串A="I'm matrix67"，字符串B="matrix"，我们就说B是A的子串。你可以委婉地问你的MM：“假如你要向你喜欢的人表白的话，我的名字是你的告白语中的子串吗？” 解决这类问题，通常我们的方法是枚举从A串的什么位置起
2010-08-07 00:06:00
1026
原创 POJ 1971 Parallelogram Counting(枚举+HASH)
//枚举 + HASH//和2002很像，这次是找平行四边形，规模1000，因此只能采用O(N^2)//一开始我是想到枚举3个点确定2条边，由这2条边确定第4的点，再用HASH判断是否存在，但是O(n^3)绝对TLE//再想了一下，发现可以枚举对角线，进而确定中点，2条直线如果中点相同，那么必定确定一个平行四边形//根据这个性质来对边的中点值进行HASH就可以了，发现一个中点值就插入，并计数，最后答案就是这些计数的总和//效率的关键是HASH函数的设计，我用折叠法的HASH随便搞了一通，
2010-08-06 12:28:00
2159
4
原创 POJ 2263 Heavy Cargo(图的遍历)
//图的遍历//CITY记录到当前城市的的最大运载量//状态转移方程，city[y] = max(city[y],min(r[x->y],city[x]);#include#include#include#includeusing namespace std;const int MAX = 205;const int MAXM = 40000;const int INF = 1000000000;int W[MAXM],V[MAXM],next[MAXM],hea
2010-08-06 02:46:00
973
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人