九宫重排

发表于 搜索 分类,标签:
 问题描述  如下面第一个图的九宫格中,放着1~8的数字卡片,还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动,可以形成第二个图所示的局面。  我们把第一个图的局面记为:12345678.  把第二个图的局面记为:123.46758  显然是按从上到下,从左到右的顺序记录数字,空格记为句点。  本题目的任务是已知九宫的初态和终态,求最少经过多少步的移动可以到达。如果无论多少步都无法到达,则输出-1。输入格式  输入第一行包含九宫的初态,第二行包含九宫的终态。输出格式  输出最少的步数,如果不存在方案,则输出-1。样例输入12345678.123.46758样例输出3样例输入13524678.46758123.样例输出22思路:这是一个八数码问题,用bfs+状态压缩水过了。代码:#include<bits/stdc++.h>usi...

L2-020. 功夫传人(2017年天梯赛初赛)

发表于 搜索 分类,标签: 天梯赛
 一门武功能否传承久远并被发扬光大,是要看缘分的。一般来说,师傅传授给徒弟的武功总要打个折扣,于是越往后传,弟子们的功夫就越弱……直到某一支的某一代突然出现一个天分特别高的弟子(或者是吃到了灵丹、挖到了特别的秘笈),会将功夫的威力一下子放大N倍——我们称这种弟子为“得道者”。这里我们来考察某一位祖师爷门下的徒子徒孙家谱:假设家谱中的每个人只有1位师傅(除了祖师爷没有师傅);每位师傅可以带很多徒弟;并且假设辈分严格有序,即祖师爷这门武功的每个第i代传人只能在第i-1代传人中拜1个师傅。我们假设已知祖师爷的功力值为Z,每向下传承一代,就会减弱r%,除非某一代弟子得道。现给出师门谱系关系,要求你算出所有得道者的功力总值。输入格式:输入在第一行给出3个正整数,分别是:N(<=105)——整个师门的总人数(于是每个人从0到N-1编号,祖师爷的编号为0);Z——祖师爷的功力值(不...

5-21 二分法求多项式单根 (20分)

发表于 搜索 分类,标签:
 二分法求函数根的原理为:如果连续函数f(x)f(x)在区间[a,b][a,b]的两个端点取值异号,即f(a)f(b)<0f(a)f(b)<0,则它在这个区间内至少存在1个根rr,即f(r)=0f(r)=0。二分法的步骤为:检查区间长度,如果小于给定阈值,则停止,输出区间中点(a+b)/2(a+b)/2;否则如果f(a)f(b)<0f(a)f(b)<0,则计算中点的值f((a+b)/2)f((a+b)/2);如果f((a+b)/2)f((a+b)/2)正好为0,则(a+b)/2(a+b)/2就是要求的根;否则如果f((a+b)/2)f((a+b)/2)与f(a)f(a)同号,则说明根在区间[(a+b)/2,b][(a+b)/2,b],令a=(a+b)/2a=(a+b)/2,重复循环;如果f((a+b)/2)f((a+b)/2)与f(b)f(b)同号,则...

L2-016. 愿天下有情人都是失散多年的兄妹

wang 发表于 搜索 分类,标签: 天梯赛
 呵呵。大家都知道五服以内不得通婚,即两个人最近的共同祖先如果在五代以内(即本人、父母、祖父母、曾祖父母、高祖父母)则不可通婚。本题就请你帮助一对有情人判断一下,他们究竟是否可以成婚?输入格式:输入第一行给出一个正整数N(2<=N<=104),随后N行,每行按以下格式给出一个人的信息:本人ID性别父亲ID母亲ID其中ID是5位数字,每人不同;性别M代表男性、F代表女性。如果某人的父亲或母亲已经不可考,则相应的ID位置上标记为-1。接下来给出一个正整数K,随后K行,每行给出一对有情人的ID,其间以空格分隔。注意:题目保证两个人是同辈,每人只有一个性别,并且血缘关系网中没有乱伦或隔辈成婚的情况。输出格式:对每一对有情人,判断他们的关系是否可以通婚:如果两人是同性,输出“NeverMind”;如果是异性并且关系出了五服,输出“Yes”;如果异性关系未出五服,...

1103. Integer Factorization (30)(pat甲级)

发表于 搜索 分类,标签: pat
 TheK-PfactorizationofapositiveintegerNistowriteNasthesumoftheP-thpowerofKpositiveintegers.YouaresupposedtowriteaprogramtofindtheK-PfactorizationofNforanypositiveintegersN,KandP.InputSpecification:EachinputfilecontainsonetestcasewhichgivesinalinethethreepositiveintegersN(<=400),K(<=N)andP(1<P<=7).Thenumbersina...

1107. Social Clusters (30)(pat甲级练习)

发表于 搜索 分类,标签: pat
 Whenregisteronasocialnetwork,youarealwaysaskedtospecifyyourhobbiesinordertofindsomepotentialfriendswiththesamehobbies.A"socialcluster"isasetofpeoplewhohavesomeoftheirhobbiesincommon.Youaresupposedtofindalltheclusters.InputSpecification:Eachinputfilecontainsonetestcase.Foreachtestcase,thefirstlinecontainsapositiveinte...

1091. Acute Stroke (30)(肿瘤诊断)(pat甲级练习)

发表于 搜索 分类,标签: pat天梯赛
 题目Oneimportantfactortoidentifyacutestroke(急性脑卒中)isthevolumeofthestrokecore.GiventheresultsofimageanalysisinwhichthecoreregionsareidentifiedineachMRIslice,yourjobistocalculatethevolumeofthestrokecore.InputSpecification:Eachinputfilecontainsonetestcase.Foreachcase,thefirstlinecontains4positiveintegers:M,N,LandT,whereMandNare...

Ancient Go

发表于 搜索 分类,标签:
 ProblemDescriptionYuZhoulikestoplay Go withSuLu.Fromthehistoricalresearch,wefoundthattherearemuchdifferenceontherulesbetweenancientgoandmoderngo.Hereistherulesforancientgotheywereplaying:⋅Thegameisplayedona 8×8 cellboard,thechesscanbeputontheintersectionoftheboardlines,sothereare 9×9 differentpositionsto...

Divide Groups

发表于 搜索 分类,标签:
 Description  Thisyearisthe60thanniversaryofNJUST,andtomakethecelebrationmorecolorful,Tom200isgoingtoinvitedistinguishedalumnusbacktovisitandtakephotos.   Aftercarefullyplanning,Tom200announcedhisactivityplan,onethatcontainstwocharacters:   1.Whethertheeffectoftheeventaregoodorbadhasnothingtodowitht...

Stealing Harry Potter's Precious(BFS+状态压缩)

发表于 搜索 分类,标签:
 Description  HarryPotterhassomeprecious.Forexample,hisinvisiblerobe,hiswandandhisowl.WhenHogwartsschoolisinholiday,HarryPotterhastogobacktouncleVernon'shome.Buthecan'tbringhispreciouswithhim.Asyouknow,uncleVernonneverallowssuchmagicthingsinhishouse.SoHarryhastodeposithispreciousintheGringottsWizardingBankwhichisownedb...