搜索+拓扑排序+欧拉回路+二分+三分+stl+概率算法

1、搜索+拓扑排序+欧拉回路+二分+三分+stl+杂碎知识+概率算法 手动扩栈#pragma comment(linker, /STACK:,)三分查找和二分查找有什么区别呀?二分是要满足在二分的区间单调才行，而三分可以除了单调还适用先增后减或先减后增（y=x*x）的情况。大致的流程是，开始l=a,h=b;令 m1=l+(h-l)/3 ,m2=l+2*(h-l)/3 ，即3等分（l，h) (这个可以随意不必要等分）如果f(m1)=f(m2) 证明m1一定在最小值的左边 （否则在(m1,m2)区间的单调递增的），这样就可以令l=m1, 新的(l,h)同样包含最小值点得到新的(l,h)之后重复上述步骤

2、，直到l与h相差很小zoj 1649 bfs/*步数最小的不一定是时间最少的常规的bfs只能求出步数最少的。而在这题中一个点可以多次走，所以必须记录最优的那个值*/#include#include#includeusing namespace std;#define inf 0x3fffffff#define N 300char sNN;struct node int x,y,step,time;ss,tt,next;int n,m;int mintimeNN;int dis42=1,0,-1,0,0,1,0,-1;int judge(int x,int y) if(x=1&x=1&y=m&s

3、xy!=#) return 1;return 0;int bfs() queueq; q.push(ss); int i; ss.step=0; ss.time=0; q.push(ss); mintimess.xss.y=0; while(!q.empty() ss=q.front(); q.pop(); for(i=0;i4;i+) int xx=next.x=ss.x+disi0; int yy=next.y=ss.y+disi1; next.step=ss.step+1; next.time=ss.time+1; if(judge(xx,yy) if(sxxyy=x)next.time

4、+=1; if(next.timemintimexxyy) /重点 mintimexxyy=next.time; q.push(next); return mintimett.xtt.y;int main() int i,j,k; while(scanf(%d%d,&n,&m)!=EOF) for(i=1;i=n;i+) scanf(%s,si+1); for(i=1;i=n;i+) for(j=1;j=inf) printf(Poor ANGEL has to stay in the prison all his life.n); else printf(%dn,k); return 0;h

5、du 5040bfs+优先队列 需要存状态/*剪枝：四秒后状态会变得和原来一样，所以四秒后如果再经过这个点肯定不是最优的舍去易错点：在一个是从.到.这两个点都没有被照到并且不是摄像机，也可能需要等3秒，因为后面的结果可能再这三秒中发生改变，要单独判断*/#include#include#include#include#includeusing namespace std;#define N 510char sNN;struct node int x,y,time; friend bool operatorb.time;/从小到大出队 ss,tt,next,cu;int maNN4,n;int

6、judge(int x,int y) if(x=1&x=1&y=n) return 1; return 0;void update(int i,int j,char ch) /存关于时间的状态 if(ch=N) if(judge(i-1,j)mai-1j0=1; if(judge(i,j+1)maij+11=1; if(judge(i+1,j)mai+1j2=1; if(judge(i,j-1)maij-13=1; if(ch=W) if(judge(i,j-1)maij-10=1; if(judge(i-1,j)mai-1j1=1; if(judge(i,j+1)maij+12=1; if(

7、judge(i+1,j)mai+1j3=1; if(ch=S) if(judge(i+1,j)mai+1j0=1; if(judge(i,j-1)maij-11=1; if(judge(i-1,j)mai-1j2=1; if(judge(i,j+1)maij+13=1; if(ch=E) if(judge(i,j+1)maij+10=1; if(judge(i+1,j)mai+1j1=1; if(judge(i,j-1)maij-12=1; if(judge(i-1,j)mai-1j3=1; int dis42=1,0,-1,0,0,1,0,-1,visNN5;int bfs() int i,

8、xx,yy; priority_queueq; memset(vis,0,sizeof(vis); ss.time=0; q.push(ss); while(!q.empty() ss=q.top(); q.pop(); if(ss.x=tt.x&ss.y=tt.y)return ss.time; /if(ss.time=)break cu=ss;cu.time+;/考虑不够完善，刚开始写的时候写到了for循环里面，这是不对的，因为。到。 等不超过四秒可能会有不同结果。 if(viscu.xcu.ycu.time%4=0) /等待，最多不超过三秒 viscu.xcu.ycu.time%4=1;

9、 q.push(cu); ; for(i=0;i4;i+) next.x=xx=ss.x+disi0; next.y=yy=ss.y+disi1; if(judge(xx,yy)&sxxyy!=#) / printf(%d %dn,xx,yy); if(sss.xss.y!=.|mass.xss.yss.time%4|maxxyyss.time%4|sxxyy!=.) /如果当前点或者下一个点被照到，或者当前点和下一个点都是摄像机，那么移动的话需要时间+3 next.time=ss.time+3; if(visnext.xnext.ynext.time%4=0) visnext.xnext.y

10、next.time%4=1; q.push(next); continue; next.time=ss.time+1; if(visxxyynext.time%4=0) /如果是.到.的话也可以不等待 visxxyynext.time%4=1; q.push(next); return -1;int main() int i,j,t,f=0; scanf(%d,&t); while(t-) scanf(%d,&n); for(i=1;i=n;i+) scanf(%s,si+1); memset(ma,0,sizeof(ma); for(i=1;i=n;i+) for(j=1;j=n;j+) i

11、f(sij=M) sij=.; ss.x=i; ss.y=j; else if(sij=T) sij=.; tt.x=i; tt.y=j; else if(sij!=.) update(i,j,sij); printf(Case #%d: %dn,+f,bfs(); return 0; hdu 4857 逆向拓扑排序+反向输出题目要求要求在满足约束条件的情况下，使小的序号尽力靠前。坑点就在这里，小的序号尽量靠前并不是代表字典序，它要求多种情况时，先使1靠前（可能1只能在第2或第3位 那么就要使它在第2位），其次2，3。而不是在当前情况下，该位最小是哪个就输出哪个/*一组测试实例4 4 23 1

12、2 4*/#include#include#includeusing namespace std;#define N 31000struct node int u,v,next;bianN*10;int headN,yong,indegreeN,n,fN,len;void init() memset(head,-1,sizeof(head);yong=0;memset(indegree,0,sizeof(indegree);void addedge(int u,int v) bianyong.u=u;bianyong.v=v;bianyong.next=headu;headu=yong+;vo

13、id bfs() priority_queueq; int i,cur; for(i=1;i=1;i-) printf(%d ,fi); printf(%dn,fi); return 0; poj 2404 中国邮递员问题 欧拉回路判定+状压dp/*状压dp邮递员问题：求经过任意点出发经过每一条边一次并回到原点。解法：1、如果是欧拉回路那么就是所有的边的总和。 2、一般的解法，找出所有的奇度顶点，任意两个顶点匹配，即最小完美匹配，可用状压dp。*/#include#include#define N 20#define inf int maNN;int lowerN;int dp116;/注意这

14、里数组要开够void floyd(int n) int i,j,k; for(k=1;k=n;k+) for(i=1;i=n;i+) for(j=1;j=inf|makj=inf)continue; if(maijmaik+makj) maij=maik+makj; return ;int visN;int judge(int n) int k=0,num=0; while(n) visk=n%2; if(visk) num+; n/=2; k+; return num;int main() int n,m,i,j,k,sum,degreeN,f,toN,low,last; lower0=1;

15、 for(i=1;i=17;i+)/二进制 loweri=loweri-1*2; while(scanf(%d,&n),n) scanf(%d,&m); for(i=1;i=n;i+) for(j=1;jk) maij=maji=k; degreei+;/求解度数 degreej+; sum+=k; f=0; for(i=1;i=n;i+) if(degreei%2=1) tof+=i; if(f=0) /判断是否是欧拉回路 printf(%dn,sum); continue; floyd(n);/求解任意两点的距离实际用的只有奇度顶点 / printf(zn); low=1f; for(i=

16、1;ilow;i+)/初始化 dpi=inf; dp0=0; /printf(%dn,f); for(i=1;ilow;i+) memset(vis,0,sizeof(vis); if(judge(i)%2=1)continue;/如果是奇数不符合 for(j=0;jf;j+) for(k=0;kdplast+matojtok)/当前的状态=去掉j和k的状态+j和k的最短路 dpi=dplast+matojtok; / printf(%dn,dplow-1); printf(%dn,sum+dplow-1);/奇度顶点的总的最小匹配为重复边+总的边数 return 0;poj 3621最优比例

17、生成环（01分数规划问题）/*和求最小生成树差不多转载思路：/wally/p/.html思路：之前做过最小比率生成树，也是属于0/1整数划分问题，这次碰到这道最优比率环，很是熟悉，可惜精度没控制好，要不就是wa,要不就是tle，郁闷啊！实在是懒得码字，直接copy吧：题目的意思是：求一个环的点权和除以边权和，使得那个环在所有环中点权和除以边权和最大。令在一个环里，点权为vi，对应的边权为ei， 即要求：（i=1，n）vi/（i=1，n)ei最大的环（n为环的点数）， 设题目答案为ans， 即对于所有的环都有 （i=1，n）（vi）/（i=1，n)（ei

18、）=（i=1，n）（vi） 再得 （i=1，n）（ans*ei-vi） =0 稍分析一下，就有： 当kans时，就存在至少一个环（i=1，n）（k*ei-vi）=ans时，就对于所有的环（i=1，n）（k*ei-vi）=0，即没有负权回路。 然后我们就可以使新的边权为k*ei-vi，用spfa来判断付权回路,二分ans。*/#include#include#include#includeusing namespace std;#define N 1100#define eps 1e-3#define inf 0x3fffffffstruct node int u,v,w,next;bianN*

19、5*2;int headN,yong,fN,n;void init() yong=0;memset(head,-1,sizeof(head);void addedge(int u,int v,int w) bianyong.u=u;bianyong.v=v;bianyong.w=w;bianyong.next=headu;headu=yong+;int spfa(double m) queueq; int visN,v,couN; double disN; int i; memset(vis,0,sizeof(vis); memset(cou,0,sizeof(cou); for(i=1;i=

20、n;i+) disi=inf; dis1=0; cou1+; q.push(1); while(!q.empty() v=q.front(); q.pop(); visv=0; for(i=headv;i!=-1;i=biani.next) int vv=biani.v; double tmp=m*biani.w-fvv;/构造新边 if(disv+tmpn)/ return 1; q.push(vv); return 0;int main() int m,i,a,b,c; while(scanf(%d%d,&n,&m)!=EOF) init(); for(i=1;ieps) /结束条件为lr

21、 mid=(r+l)/2; if(spfa(mid) ans=mid; l=mid+0.00001; else r=mid-0.00001; printf(%.2fn,ans); return 0; hdu 4941 stl的map用法#include#include#include#includeusing namespace std;typedef struct node int x,y; bool operator(const node &b)const if(x=b.x) return yb.y; else return xb.x; node;int main() mapma; map

22、f,ff; node e; int n,m,i,j,k,t,id,idd,ss,s,num=0; scanf(%d,&t); while(t-) scanf(%d%d%d,&n,&m,&k); id=0;idd=0; while(k-) scanf(%d%d%d,&i,&j,&s); if(fi=0) fi=+id; if(ffj=0) ffj=+idd; e.x=fi; e.y=ffj; mae=s; scanf(%d,&j); printf(Case #%d:n,+num); while(j-) scanf(%d,&i); if(i=1) scanf(%d%d,&id,&idd); ss=

23、fid; fid=fidd; fidd=ss; if(i=2) scanf(%d%d,&id,&idd); ss=ffid; ffid=ffidd; ffidd=ss; if(i=3) scanf(%d%d,&id,&idd); e.x=fid; e.y=ffidd; / printf(%d %dn,fid,ffidd); printf(%dn,mae); return 0; 模拟退火法模板#includestring.h#includestdio.h#includeiostream#includequeue#includestack#define M 10009#define N #incl

24、udestdlib.h#includemath.h#define inf #define eps 1e-8#define PI acos(-1.0)using namespace std;struct node double x,y,dis;p6,q100;double max(double x,double y) return xy?x:y;double min(double x,double y) return xy?x:y;double len(node a,node b) return sqrt(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);double

25、 fun(node q) double sum=0; for(int i=0;i4;i+) sum+=len(q,pi); return sum;int main() int i,j; while(scanf(%lf%lf%lf%lf%lf%lf%lf%lf,&p0.x,&p0.y,&p1.x,&p1.y,&p2.x,&p2.y,&p3.x,&p3.y)!=-1) int flag=0; for(i=0;i4;i+) if(fabs(pi.x+1)eps&fabs(pi.y+1)eps) flag+; if(flag=4) break; node a,b; a.x=a.y=inf; b.x=b

26、.y=-inf; for(i=0;i4;i+) a.x=min(a.x,pi.x); a.y=min(a.y,pi.y); b.x=max(b.x,pi.x); b.y=max(b.y,pi.y); for(i=1;ieps) for(i=1;i=20;i+) for(j=0;j25;j+) double rad=(rand()%1000+10)/1000.0*PI*10; node cur; cur.x=temp*cos(rad); cur.y=temp*sin(rad); if(cur.xa.x|cur.yb.x|cur.xb.y)continue; cur.dis=fun(cur); i

27、f(cur.disqi.dis) qi=cur; temp*=0.981; double mini=q1.dis; for(i=2;iqi.dis) mini=qi.dis; printf(%.4lfn,mini); poj 1379 模拟退火法/*模拟退火法： 找到一些随机点，从这些点出发，随机的方向坐标向外搜索； 最后找到这些随机点的最大值； 坑：/if(xx-eps&xx-eps&yyeps+y) 不知道为什么这个判断方式错误？*/#include#include#include#include#define pi acos(-1.0)#define N 1100#define inf

28、00#define eps 1e-8using namespace std;double x,y;int n;struct node double u,v,dis;fN,endd,ffN;double diss(double x,double y,int i) return sqrt(x-fi.u)*(x-fi.u)+(y-fi.v)*(y-fi.v);double Mindis(double x,double y) double minn=1.0*inf,ss; int i; for(i=1;iss) minn=ss; return minn;void compute() int i,j;

29、double xx,yy; for(i=1;ieps) for(i=1;i=20;i+)/对于这些点分别向外搜 for(j=1;j-eps&xx-eps&yyeps+y) 不知道为什么这个判断方式错误？ if(xxx|yyy)continue; double di=Mindis(xx,yy); if(ffi.disdi) ffi.dis=di; ffi.u=xx; ffi.v=yy; T*=rate;/退火率 for(i=1;i=20;i+)/找到最大的一个 if(endd.disffi.dis) endd=ffi; return ;int main() / printf(%dn,(rand(

30、)%1000+1)/1000.0*2*pi); int m,i,j,k,t; scanf(%d,&t); while(t-) scanf(%lf%lf%d,&x,&y,&n); for(i=1;i=n;i+) scanf(%lf%lf,&fi.u,&fi.v); endd.dis=-1; compute(); printf(The safest point is (%.1f, %.1f).n,endd.u,endd.v); return 0;poj 2420 模拟退火法基础/*题意：给n个电脑，求一个点到这n个电脑的距离和最小。模拟退火法：和poj1379的方法类似因为坐标范围是0-10000

31、不妨把它看成是10000*10000的正方形来做*/#include#include#include#include#define inf 000using namespace std;#define N 110#define eps 0.1#define pi acos(-1.0)struct node double x,y,dis;fN,ffN;int n;double dd,x,y;double diss(double x,double y) double sum=0; int i; for(i=1;i=n;i+) sum=sum+sqrt(x-fi.x)*(x-fi.x)+(y-fi.

32、y)*(y-fi.y); return sum;void slove() int i,j; double xx,yy; for(i=1;ieps) for(i=1;i=20;i+) for(j=1;j=30;j+) double ran=(rand()%1000+1)/1000.0*pi*10; xx=ffi.x+cos(ran)*T; yy=ffi.y+sin(ran)*T; double dis=diss(xx,yy); if(xx10000.0|yy10000.0)continue; if(disffi.dis) ffi.dis=dis; T*=rate; dd=inf; for(i=1

33、;iffi.dis) dd=ffi.dis; return ;int main() int i; while(scanf(%d,&n)!=EOF) x=inf; y=-1; for(i=1;i=n;i+) scanf(%lf%lf,&fi.x,&fi.y); slove(); printf(%.0fn,dd); return 0; C+标准库：bitset 用法整理&zoj 3812转载: /blog/static/2/头文件:#include std:bitset是STL的一部分，准确地说，std:bitset是一个模板类，它的模板参数不是类型，而整形的数值（这一特性是ISO C+2003的新特性），有了它我们可以像使用数组一样使用位。下面看一个例子：#includestd:bitset bs;/它是一个模板，传递的参数告诉编译器bs有8个位。我们接着看上面的代码，通过上面两行的代码我们得到一个bitset的对象bs，bs可以装入8个位，我们可以通过数组的下标运算符来存取：bs0=1;/把第0位设置为1bs3=true;/把第3位设置为1,因为true可以转换为1bs7=0;/这个大家都明白了bitset被设计为开放的，也就是说一个bitset对象可以转换为其它类型的值，典型的，我们想把一个整数设置成具有特定的位模式，我