基本做题知识

我们的题目的测试用例一般有多组，所以在输入的处理上有一些处理方法：1.题目的数据第一行给出数据组数T，然后每组每组给出数据这种可以用以下代码处理：IntT；Scanf(“%d”,&T);While(T--){处理}2.题目有多组数据，要求处理到文件结尾例如每一行一个数字代表一组输入数据这时使用While(scanf(“%d”,&n)!=EOF){处理}这里的EOF表示文件结束标志，其它同类型的输入自行思考3.题目有多组数据，最后以0/-1或者神马的结尾比如每一行一个数字代表一组输入数据While(scanf(“%d”,&n)!=EOF&&n=0){处理}其它同类型输入自行思考一些程序运行结果的意义：Pending:Thejudgeissobusythatitcan'tjudgeyoursubmitatthemoment,usuallyyoujustneedtowaitaminuteandyoursubmitwillbejudged.PendingRejudge:Thetestdatashasbeenupdated,andthesubmitwillbejudgedagainandallofthesesubmissionwaswaitingfortheRejudge.Compiling:Thejudgeiscompilingyoursourcecode.Running&Judging:YourcodeisrunningandbeingjudgingbyourOnlineJudge.Accepted:OK!Yourprogramiscorrect!.PresentationError:Youroutputformatisnotexactlythesameasthejudge'soutput,althoughyouranswertotheproblemiscorrect.Checkyouroutputforspaces,blanklines,etcagainsttheproblemoutputspecification.WrongAnswer:Correctsolutionnotreachedfortheinputs.Theinputsandoutputsthatweusetotesttheprogramsarenotpublic(itisrecomendabletogetaccustomedtoatruecontestdynamic;-).TimeLimitExceeded:Yourprogramtriedtorunduringtoomuchtime.MemoryLimitExceeded:Yourprogramtriedtousemorememorythanthejudgedefaultsettings.OutputLimitExceeded:Yourprogramtriedtowritetoomuchinformation.Thisusuallyoccursifitgoesintoainfiniteloop.Currentlytheoutputlimitis1Mbytes.RuntimeError:AlltheotherErrorontherunningphrasewillgetRuntimeError,suchas'segmentationfault','floatingpointexception','usedforbiddenfunctions','triedtoaccessforbiddenmemories'andsoon.CompileError:Thecompiler(gcc/g++/gpc)couldnotcompileyourANSIprogram.Ofcourse,warningmessagesarenoterrormessages.Clickthelinkatthejudgereplytoseetheactualerrormessage.用BFS求最短路如果图的所有的边的边权（即边的长度）相等，则可以用BFS来求最短路。BFS遍历到的某节点的层数乘边权一定是从源点到达该点的最短路径。若所有边的边权并不是都相等呢，这就不能用BFS来求解了，以后会专门讲解求最短路的算法。怎么记录节点的层数在结构中新开一个变量来记录层数。structNODE{intx,y,cnt;};具体实现只需把前面的代码稍加改动。next.cnt=now.cnt+1;DFS模板/*该DFS框架以2D坐标范围为例，来体现DFS算法的实现思想。*/#includecstdio#includecstring#includecstdlibusingnamespacestd;constintmaxn=100;boolvst[maxn][maxn];//访问标记intmap[maxn][maxn];//坐标范围intdir[4][2]={0,1,0,-1,1,0,-1,0};//方向向量，(x,y)周围的四个方向boolCheckEdge(intx,inty)//边界条件和约束条件的判断{if(……&&!vst[x][y])//满足条件return1;else//与约束条件冲突return0;}voiddfs(intx,inty){vst[x][y]=1;//标记该节点被访问过if(map[x][y]==G)//出现目标态G{......//做相应处理return;}for(inti=0;i4;i++){if(CheckEdge(x+dir[i][0],y+dir[i][1]))//按照规则生成下一个节点dfs(x+dir[i][0],y+dir[i][1]);}return;//没有下层搜索节点，回溯}intmain(){......return0;}八皇后#includeiostreamusingnamespacestd;staticintgEightQueen[8]={0};staticintgCount=0;voidprint(){intouter;intinner;for(outer=0;outer8;outer++){for(inner=0;innergEightQueen[outer];inner++)printf(*);printf(#);for(inner=gEightQueen[outer]+1;inner8;inner++)printf(*);printf(\n);}printf(=====================================\n);}intcheck_pos_valid(intloop,intvalue){intindex;intdata;for(index=0;indexloop;index++){data=gEightQueen[index];if(value==data)return0;if((index+data)==(loop+value))return0;if((index-data)==(loop-value))return0;}return1;}voideight_queen(intindex){intloop;for(loop=0;loop8;loop++){if(check_pos_valid(index,loop)){gEightQueen[index]=loop;if(7==index){gCount++,print();gEightQueen[index]=0;return;}eight_queen(index+1);gEightQueen[index]=0;}}}intmain(intargc,char*argv[]){eight_queen(0);printf(total=%d\n,gCount);return1;}最短路Dijikstra算法（1）S：已求出最短路径的顶点的集合（初始时只含有源点V0）（2）T：尚未确定最短路径的顶点集合核心：1.从T中选择距离最小的点w加入S中；2.对其余T中顶点的距离值进行修改（若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值）现在想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？输入包括多组数据。每组数据第一行是两个整数N、M（N=100，M=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1=A,B=N,1=C=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。输入保证至少存在1条商店到赛场的路线。3312523531200/*qsort与sort调用细则*///sort调用细则#includealgorithm//对vector...sort(v.begin(),v.end());//对普通数组inta[1000];boolcmp(inta,intb){returnab;//当满足当前顺序，返回1，不满足当前顺序，返回0}sort(a+x,a+y,cmp);//x,y确定范围//对结构排序structedgetype{inta;intb;intlen;}edge[5000];boolcmp(structedgetypea,structedgetypeb){returna.lenb.len;//当满足当前顺序，返回1，不满足当前顺序，返回0}sort(edge+x,edge+y,cmp);//二次排序structTYPE{intx;inty;}node[n];intcmp(TYPEa,TYPEb){if(a.x==b.x)returna.yb.y;elsereturna.xb.x;}sort(n,n+k,cmp);//x从小到大排序，若x相等，y从小到大排序。//qsort#includestdlib.h#includestdio.h#includestring.h//普通数组a[1000];intcomp(constvoid*a,constvoid*b){return*(int*)a-*(int*)b;//(int*)表示把（constcoid*a）强制准换成int型指针外边的*是取内容}qsort(a,k,sizeof(int),comp);//对double型结构intcomp(constvoid*a,constvoid*b){if((((structTYPE*)a)-x)-(((structTYPE*)b)-x)0)return1;elseif((((structTYPE*)a)-x)-(((structTYPE*)b)-x)==0)return0;elseif((((structTYPE*)a)-x)-(((structTYPE*)b)-x)0)return-1;}//对结构体排序structedgetype{inta;intb;intlen;}edge[5000];intcomp(constvoid*a,constvoid*b){return(((structedgetype*)a)-len)-(((structedgetype*)b)-len);}qsort(edge,k,sizeof(structedgetype),comp);//对doubleintcomp(constvoid*a,constvoid*b){if((((structedgetype*)a)-len)-(((structedgetype*)b)-len)0)return1;elseif((((structedgetype*)a)-len)-(((structedgetype*)b)-len)==0)return0;elseif((((structedgetype*)a)-len)-(((structedgetype*)b)-len)0)retur