10 ChinaCzy

尚未进行身份认证

SYSU

等级
TA的排名 7k+

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

SYSU/ICPC 2011校赛总结

<br/><br/>一年前的那个时候,我神马常见算法都不会,就只会调用下STL,就和ZMQ组队去校赛,校赛预选赛就0题被刷掉了。那年的悲剧是相当正常的,我们连Standing都不会刷,都不知道是干嘛的,看哪题做的人比较多也不会看,就傻傻的看一题写一题,不会做跳过,不过还是得吐槽下,2010年校赛预选赛的题也太难了吧!严重打击新手啊!不过最最悲剧的是,我们连他加了一题超级水题都不知道.....我还以为是大家太牛逼了,题目都给做光了!不得不补一道难一点的,免得人家提前走人侮辱出题方!后来才发现,原来是因为题

2011-04-04 14:19:00

Sicily 1135 飞越原野(BFS宽度优先搜索)

<br/>//BFS宽度优先搜索//G[x][y][k]表示走到(x,y)后还能飞k步的最优值#include<cstdio>#include<iostream>#include<cstring>#include<queue>usingnamespacestd;constintMAX=102;constintdir[4][2]={1,0,-1,0,0,1,0,-1};intN,M,D,ans;intG[MAX][MAX][MAX];boo

2011-04-01 16:04:00

微软、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

Sicily 1140 国王的遗产(搜索|图论)

<br/>//搜索,暴力//这题卡了我几天,检查到最后,居然是我的minID维护错误!我艹!这种错误居然卡了我几天!!!我就是一个超级无敌大水人!//不过卡了这几天也好,程序也经过不断优化//做法是预处理出以每个结点为根的子树有多少个结点cnt,以每个结点为根的子树最小编号minID//接着枚举所有边,暴力找出每个可行方案//在搜寻每一个可行方案,都以编号最小的结点作为根,这一个优化方案,可以省去搜索比较上下两部分的最小编号值//这题有几个重要结论是需要证明的//1、在树中仅存

2011-03-23 16:40:00

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

POJ 2817 WordStack(状态压缩DP)

<br/>#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;intpow[15];intdp[1<<12][10],N;charword[15][25];intW[15][15];voidinit(){ intw; memset(W,0,sizeof(W)); for(inti=0;i<N;++i) { for(intj=0;j

2011-02-27 14:13:00

POJ 1837 Balance(DP动态规划)

//DP,动态规划求组合数,dp[i][j]表示前i个重锤获得重量j有几种方式//转移方程dp[i][j+k]+=dp[i-1][j];k为新添加第I个重锤的质量//对重锤对应钩子将其分组后来处理#include#include#includeusingnamespacestd;intdp[25][1000];intC[25],G[25];intN,M;constintmid=500;voidDP(){ dp[0][mid]=1

2011-02-25 00:10:00

POJ 3107 Godfather(DFS)

//DFS水题,在树中找到满足下条件的点集,若删除当前点集的点,则将树划分成的最大连通块最小,DFS统计即可//统计方式只需要记录以当前结点为根的子树的结点数num,若要求父亲那一坨连通块只需要用N个点减去他所有儿子的num值即可#include#include#include#includeusingnamespacestd;constintMAX=50005;constintINF=200000000;intV[2*MAX],next[2*MAX

2011-02-24 22:24:00

POJ 2761 Feed the dogs(Treap求第K小数)

//TREAP求第K小数//感谢JSH大牛的指点//这道题之所以可以用TREAP做是因为题意中有个条件,询问区间不会出现包含的情况,因此通过对询问区间进行排序//然后通过插入和删除的方法,来维护区间的第K小//平衡树的话自然首选TREAP了,TREAP中比较难的就在于删除那里,删除的方式是通过将要删除的结点通过左右旋的方式,在维护LEV为堆的同时,将要删除结点旋到叶子结点处,然后删除#include#include#include#includeusingnamespa

2011-01-29 00:34:00

JAVA多线程编程总结

<br/>一、认识多任务、多进程、单线程、多线程要认识多线程就要从操作系统的原理说起。 以前古老的DOS操作系统(V6.22)是单任务的,还没有线程的概念,系统在每次只能做一件事情。比如你在copy东西的时候不能rename文件名。为了提高系统的利用效率,采用批处理来批量执行任务。 现在的操作系统都是多任务操作系统,每个运行的任务就是操作系统所做的一件事情,比如你在听歌的同时还在用MSN和好友聊天。听歌和聊天就是两个任务,这个两个任务是“同时”进行的。一个任务一般对应一个进程,也可能包含好几个进程。比如

2011-01-21 11:16:00

Sicily 1033 City Road(递推)

//模拟+递推,感觉这种题不能称之为动态规划,只能叫递推因为每个点只调用了一次,不存在所谓的转移//题意是从起点到终点,有多少种不同的走法,图中有些路有障碍//注意到规模是M*N#include#includeusingnamespacestd;intM,N,B;intx,y,dx,dy;boolX[2000000],Y[2000000];longlongA[20

2010-12-27 20:00:00

Sicily 1039 Phone Home(DFS染色)

//dfs染色+二分答案#include#include#include#includeusingnamespacestd;constdoubleMAX=400;structcoord{ doublex,y;}P[15];doublecalDis(coorda,coordb){ return(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}vectorE[15];intG[15];//

2010-12-26 19:58:00

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

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

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

Sicily 1802 Atomic Nucleus Investigation(线段树)

新手赛的题目,让我回想起打酱油的时光//线段树#include#include#include#defineINF100000000usingnamespacestd;intT,M;charcmd[10],n;boolR[100005],G[100005];structseg{ intl,r,_max,_min,delta;//记录最大值,最小值,最优差值,_max,_min为0表示不存在这个数}tree[100005*4];voidu

2010-10-14 21:59:00

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

Sicily 1034 Forest(DFS)

//图的遍历,DFS,统计森林的宽度和深度,加上对环的判断//一道这么简单的题我一开始用BFS,结果WA到吐血,唉,我这个大水人#include#include#includeusingnamespacestd;boolvis[105],ok;intwidth[105];vectorE[105];//邻接表intN,M,W,D,in[105];voiddfs(intu,intd){ if(vis[u])//发现已搜过的点,证明存在环 {

2010-09-19 00:15:00

POJ 3414 Pots(BFS倒水问题)

//BFS倒水问题,对于需要打印解得广搜题,必须保存搜索状态和状态的父亲指针,然后逆推,根据状态和状态之间的关系//判断属于那一种情况,并将解记录,还有POJ的1606也是同样类型的题,只不过要求有点点不一样,规模也有点点不一样//代码也就不重复贴了~#include#include#include#includeusingnamespacestd;boolvis[105][105];intA,B,C;vectorans;structState{

2010-09-18 15:21:00

查看更多

勋章 我的勋章
    暂无奖章