位运算总结Word格式.docx
- 文档编号:3182284
- 上传时间:2023-05-01
- 格式:DOCX
- 页数:15
- 大小:95KB
位运算总结Word格式.docx
《位运算总结Word格式.docx》由会员分享,可在线阅读,更多相关《位运算总结Word格式.docx(15页珍藏版)》请在冰点文库上搜索。
1,101101->
10110
2、最最后一位加0:
x<
1011010
3、最最后一位加1:
1+1,101101->
1011011
4、把最后一位变成1:
x|1,101100->
101101
5、把最后一位变成0:
x|1-1,101101->
101100
6、最后一位取反:
x^1,101100->
101101,101101->
7、把右数第k位变成1:
x|(1<
(k-1))
8、把右数第k位变成0:
x&
~(1<
9、把右数第k位取反:
x^(1<
10、取末k位:
(1<
k-1)
11、把右边连续的1变0:
(x+1),100101111->
100100000
12、把右边第一个0变成1:
x|(x+1),100101111->
100111111
13、把右边第一个1变成0:
(x-1),10010100->
10010000
14、把右边连续的0变成1:
x|(x-1),11011000->
11011111
15、取右边连续的1:
(x^(x+1))>
1,100101111->
1111
16、去掉右边第一个1的左边:
(x^(x-1)),100101000->
1000
17、判断奇偶:
1
王特:
1324
HoledoxMoving
Description
Duringwinter,themosthungryandseveretime,Holedoxsleepsinitslair.Whenspringcomes,Holedoxwakesup,movestotheexitofitslair,comesout,andbeginsitsnewlife.
Holedoxisaspecialsnake,butitsbodyisnotverylong.Itslairislikeamazeandcanbeimaginedasarectanglewithn*msquares.Eachsquareiseitherastoneoravacantplace,andonlyvacantplacesallowHoledoxtomovein.Usingorderedpairofrowandcolumnnumberofthelair,thesquareofexitlocatedat(1,1).
Holedox'
sbody,whoselengthisL,canberepresentedblockbyblock.AndletB1(r1,c1)B2(r2,c2)..BL(rL,cL)denoteitsLlengthbody,whereBiisadjacenttoBi+1inthelairfor1<
=i<
=L-1,andB1isitshead,BLisitstail.
Tomoveinthelair,Holedoxchoosesanadjacentvacantsquareofitshead,whichisneitherastonenoroccupiedbyitsbody.Thenitmovestheheadintothevacantsquare,andatthesametime,eachotherblockofitsbodyismovedintothesquareoccupiedbythecorrespondingpreviousblock.
Forexample,intheFigure2,atthebeginningthebodyofHoledoxcanberepresentedasB1(4,1)B2(4,2)B3(3,2)B4(3,1).Duringthenextstep,observingthatB1'
(5,1)istheonlysquarethattheheadcanbemovedinto,HoledoxmovesitsheadintoB1'
(5,1),thenmovesB2intoB1,B3intoB2,andB4intoB3.Thusafteronestep,thebodyofHoledoxlocatesinB1(5,1)B2(4,1)B3(4,2)B4(3,2)(seetheFigure3).
GiventhemapofthelairandtheoriginallocationofeachblockofHoledox'
sbody,yourtaskistowriteaprogramtotelltheminimalnumberofstepsthatHoledoxhastotaketomoveitsheadtoreachthesquareofexit(1,1).
Input
Theinputconsistsofseveraltestcases.Thefirstlineofeachcasecontainsthreeintegersn,m(1<
=n,m<
=20)andL(2<
=L<
=8),representingthenumberofrowsinthelair,thenumberofcolumnsinthelairandthebodylengthofHoledox,respectively.ThenextLlinescontainapairofrowandcolumnnumbereach,indicatingtheoriginalpositionofeachblockofHoledox'
sbody,fromB1(r1,c1)toBL(rL,cL)orderly,where1<
=ri<
=n,and1<
=ci<
=m,1<
=i<
=L.ThenextlinecontainsanintegerK,representingthenumberofsquaresofstonesinthelair.ThefollowingKlinescontainapairofrowandcolumnnumbereach,indicatingthelocationofeachsquareofstone.Thenablanklinefollowstoseparatethecases.
Theinputisterminatedbyalinewiththreezeros.
Note:
BiisalwaysadjacenttoBi+1(1<
=L-1)andexitsquare(1,1)willneverbeastone.
Output
ForeachtestcaseoutputonelinecontainingthetestcasenumberfollowedbytheminimalnumberofstepsHoledoxhastotake."
-1"
meansnosolutionforthatcase.
SampleInput
564
41
42
32
31
3
23
33
34
444
13
14
24
4
21
22
000
SampleOutput
Case1:
9
Case2:
-1
胡化藤:
3460
Booksort
TheLeidenUniversityLibraryhasmillionsofbooks.Whenastudentwantstoborrowacertainbook,heusuallysubmitsanonlineloanform.Ifthebookisavailable,thenthenextdaythestudentcangoandgetitattheloancounter.Thisisthemodernwayofborrowingbooksatthelibrary.
Thereisonedepartmentinthelibrary,fullofbookcases,wherestilltheoldwayofborrowingisinuse.Studentscansimplywalkaroundthere,pickoutthebookstheylikeand,afterregistration,takethemhomeforatmostthreeweeks.
Quiteoften,however,ithappensthatastudenttakesabookfromtheshelf,takesacloserlookatit,decidesthathedoesnotwanttoreadit,andputsitback.Unfortunately,notallstudentsareverycarefulwiththislaststep.Althougheachbookhasauniqueidentificationcode,bywhichthebooksaresortedinthebookcase,somestudentsputbackthebookstheyhaveconsideredatthewrongplace.Theydoputitbackontotherightshelf.However,notattherightpositionontheshelf.
Otherstudentsusetheuniqueidentificationcode(whichtheycanfindinanonlinecatalogue)tofindthebookstheywanttoborrow.Forthem,itisimportantthatthebooksarereallysortedonthiscode.Alsoforthelibrarian,itisimportantthatthebooksaresorted.Itmakesitmucheasiertocheckifperhapssomebooksarestolen:
notborrowed,butyetmissing.
Therefore,everyweek,thelibrarianmakesaroundthroughthedepartmentandsortsthebooksoneveryshelf.Sortingoneshelfisdoable,butstillquitesomework.Thelibrarianhasconsideredseveralalgorithmsforit,anddecidedthattheeasiestwayforhimtosortthebooksonashelf,isbysortingbytranspositions:
aslongasthebooksarenotsorted,
takeoutablockofbooks(anumberofbooksstandingnexttoeachother),
shiftanotherblockofbooksfromtheleftortherightoftheresulting‘hole’,intothishole,
andputbackthefirstblockofbooksintotheholeleftopenbythesecondblock.
Onesuchsequenceofstepsiscalledatransposition.
Thefollowingpicturemayclarifythestepsofthealgorithm,whereXdenotesthefirstblockofbooks,andYdenotesthesecondblock.
Ofcourse,thelibrarianwantstominimizetheworkhehastodo.Thatis,foreverybookshelf,hewantstominimizethenumberoftranspositionshemustcarryouttosortthebooks.Inparticular,hewantstoknowifthebooksontheshelfcanbesortedbyatmost4transpositions.Canyoutellhim?
Thefirstlineoftheinputfilecontainsasinglenumber:
thenumberoftestcasestofollow.Eachtestcasehasthefollowingformat:
Onelinewithoneintegernwith1≤n≤15:
thenumberofbooksonacertainshelf.
Onelinewiththenintegers1,2,…,ninsomeorder,separatedbysinglespaces:
theuniqueidentificationcodesofthenbooksintheircurrentorderontheshelf.
Foreverytestcaseintheinputfile,theoutputshouldcontainasingleline,containing:
iftheminimalnumberoftranspositionstosortthebooksontheiruniqueidentificationcodes(inincreasingorder)isT≤4,thenthisminimalnumberT;
ifatleast5transpositionsareneededtosortthebooks,thenthemessage"
5ormore"
.
6
134625
5
54321
10
68534729110
2
5ormore
乐思文:
1079
Ratio
Ifyoueverseeatelevisedreportonstockmarketactivity,you'
llheartheanchorpersonsaysomethinglike``Gainersoutnumberedlosers14to9,'
'
whichmeansthatforevery14stocksthatincreasedinvaluethatday,approximately9otherstocksdeclinedinvalue.Often,asyouhearthat,you'
llseeonthescreensomethinglikethis:
Gainers1498
Losers902
Asapersonwithaheadfornumbers,you'
llnoticethattheanchorpersoncouldhavesaid``Gainersoutnumberedlosers5to3'
whichisamoreaccurateapproximationtowhatreallyhappened.Afterall,theexactratioofwinnerstolosersis(tothenearestmillionth)1.660754,andhereportedaratioof14to9,whichis1.555555,foranerrorof0.105199;
hecouldhavesaid``5to3'
andintroducedanerrorofonly1.666667-1.660754=0.005913.Theestimate``5to3'
isnotasaccurateas``1498to902'
ofcourse;
evidently,anothergoalistousesmallintegerstoexpresstheratio.So,whydidtheanchorpersonsay``14to9?
Becausehisalgorithmistolopoffthelasttwodigitsofeachnumberandusethoseastheapproximateratio.
Whattheanchormanneedsisalistofrationalapproximationsofincreasingaccuracy,sothathecanpickonetoreadontheair.Specifically,heneedsasequence{a_1,a_2,...,a_n}wherea_1isarationalnumberwithdenominator1thatmostexactlymatchesthetrueratioofwinnerstolosers(roundingupincaseofties),a_{i+1}istherationalnumberwithleastdenominatorthatprovidesamoreaccurateapproximationthana_i,anda_nistheexactratio,expressedwiththeleastpossibledenominator.Giventhissequence,theanchorpersoncandecidewhichratiogivesthebesttradeoffbetweenaccuracyandsimplicity.
Forexample,if5stocksroseinpriceand4fell,thebestapproximationwithdenominator1is1/1;
thatis,foreverystockthatfell,aboutonerose.Thisanswerdiffersfromtheexactanswerby0.25(1.0vs1.25).Thebestapproximationswithtwointhedenominatorare2/2and3/2,butneitherisanimprovementontheratio1/1,soneitherwouldbeconsidered.Thebestapproximationwiththreeinthedenominator4/3,ismoreaccuratethananyseensofar,soitisonethatshouldbereported.Finally,ofcourse,5/4isexactlytheratio,andsoitisthelastnumberreportedinthesequence.
Canyouautomatethisprocessandhelptheanchorpeople?
inputcontainsseveralpairsofpositiveintegers.Eachpairisonalinebyitself,beginninginthefirstcolumnandwithaspacebetweenthetwonumbers.Thefirstnumberofapairisthenumberofgainingstocksfortheday,andthesecondnumberisthenumberoflosingstocksfortheday.Thetotalnumberofstocksneverexceeds5000.
Foreachinputpair,thestandardoutputshouldcontainaseriesofapproximationstotheratioofgainerstolosers.Thefirstapproximationhas'
1'
asdenominator,andthelastisexactlytheratioof
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运算 总结