算法 - Page 110 - hzwer.com

「BZOJ3171」[TJOI2013] 循环格
DescriptionInput第一行两个整数R，C。表示行和列，接下来R行，每行C个字符LRUD，表示左右上下。Output一个整数，表示最少需要修改多少个元素使得给定的循环格完美SampleInput34RRRDURLLLRRRSampleOutput2HINT1<=R,L<=15题解可知每个点的出度=入度=1二分图+费用流S向每个点连容量1费用0的边每个点拆出的点向T连容量1，费用0的边每个格子向四周连费用0或1的边[crayon-6847b56c818dc973411...
02014年3月18日4,841费用流

「POJ2392」Space Elevator
DescriptionThecowsaregoingtospace!Theyplantoachieveorbitbybuildingasortofspaceelevator:agianttowerofblocks.TheyhaveK(1<=K<=400)differenttypesofblockswithwhichtobuildthetower.Eachblockoftypeihasheighth_i(1<=h_i<=100)andisavailableinquantityc_i(1<=c_i<=10).Duetopossibledamagecausedbycosmicrays,nopartofablockoftypeicanexceedamaximumaltitudea_i(1<=a_i<=40000).Helptheco...
02014年3月18日3,694贪心,背包动规
「BZOJ2190」[SDOI2008] 仪仗队
Description　　作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N*N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。　　　　现在，C君希望你告诉他队伍整齐时能看到的学生人数。Input　　共一个数N。Output　　共一个数，即C君应看到的学生人数。SampleInput　　4SampleOutput　　9HINT「数据规模和约定」　　对...
22014年3月18日5,225筛法,欧拉函数
「BZOJ3211」花神游历各国
Description Input Output每次x=1时，每行一个整数，表示这次旅行的开心度 SampleInput4 1100555112212112223114SampleOutput101 1111HINT对于100%的数据，n≤100000，m≤200000,data[i]非负且小于10^9题解同上帝造题的七分钟[crayon-6847b56c826b1771050584/] ...
02014年3月17日6,346线段树
「POJ3164」Command Network
DescriptionAfteralonglastingwaronwords,awaronarmsfinallybreaksoutbetweenlittleken’sandKnuthOcean’skingdoms.AsuddenandviolentassaultbyKnuthOcean’sforcehasrenderedatotalfailureoflittleken’scommandnetwork.Aprovisionalnetworkmustbebuiltimmediately.littlekenorderssnoopytotakechargeoftheproject.Withthesituationstudiedtoeverydetail,snoopybelievesthatthemosturgentpointistoenablelittenken’sco...
02014年3月17日4,637其它
「BZOJ1934」[SHOI2007] Vote 善意的投票
Description幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉。对他们来说，这个问题并不是很重要，于是他们决定发扬谦让精神。虽然每个人都有自己的主见，但是为了照顾一下自己朋友的想法，他们也可以投和自己本来意愿相反的票。我们定义一次投票的冲突数为好朋友之间发生冲突的总数加上和所有和自己本来意愿发生冲突的人数。我们的问题就是，每位小朋友应该怎样投票，才能使冲突数最小？Input第一行只有两个整数n，m，保证有2...
22014年3月17日5,111最小割
「BZOJ2178」圆的面积并
Description给出N个圆，求其面积并Input先给一个数字N,N<=1000接下来是N行是圆的圆心，半径，其绝对值均为小于1000的整数Output面积并，保留三位小数SampleInput721...SampleOutput12707279.690题解辛普森积分法[crayon-6847b56c8354c169774423/] ...
62014年3月17日9,759几何
「BZOJ2424」[HAOI2010] 订货
Description某公司估计市场在第i个月对某产品的需求量为Ui，已知在第i月该产品的订货单价为di，上个月月底未销完的单位产品要付存贮费用m，假定第一月月初的库存量为零，第n月月底的库存量也为零，问如何安排这n个月订购计划，才能使成本最低？每月月初订购，订购后产品立即到货，进库并供应市场，于当月被售掉则不必付存贮费。假设仓库容量为S。 Input第1行：n,m,S(0<=n<=50,0<=m<=10,0<=S<=100...
02014年3月17日4,430费用流
「CF402A」Nuts
Youhave a nutsandlotsofboxes.Theboxeshaveawonderfulfeature:ifyouput x (x ≥ 0) divisors(thespacialbarsthatcandivideabox)toit,yougetabox,dividedinto x + 1 sections.Youareminimalist.Therefore,ontheonehand,youareagainstdividingsomeboxintomorethan k sections.Ontheotherhand,youareagainstputtingmorethan v nutsintosomesectionofthebox.Whatistheminimumnumberofboxesyouhavetouseifyouwant...
02014年3月17日2,983模拟
「CF402B」Trees in a Row
TheQueenofEnglandhas n treesgrowinginarowinhergarden.Atthat,the i-th (1 ≤ i ≤ n) treefromthelefthasheight aimeters.TodaytheQueendecidedtoupdatethesceneryofhergarden.Shewantsthetrees'heightstomeetthecondition:foralli (1 ≤ i < n), ai + 1 - ai = k,where k isthenumbertheQueenchose.Unfortunately,theroyalgardenerisnotamachineandhecannotfulfillthedesireoftheQueenin...
02014年3月17日2,562模拟
「BZOJ1412」[ZJOI2009] 狼和羊的故事
Description“狼爱上羊啊爱的疯狂，谁让他们真爱了一场；狼爱上羊啊并不荒唐，他们说有爱就有方向．．．．．．”Orez听到这首歌，心想：狼和羊如此和谐，为什么不尝试羊狼合养呢？说干就干！Orez的羊狼圈可以看作一个n*m个矩阵格子，这个矩阵的边缘已经装上了篱笆。可是Drake很快发现狼再怎么也是狼，它们总是对羊垂涎三尺，那首歌只不过是一个动人的传说而已。所以Orez决定在羊狼圈中再加入一些篱笆，还是要将羊狼分开来养。...
02014年3月16日6,891最小割
「BZOJ1385」[Baltic2000] Division expression
Description除法表达式有如下的形式:X1/X2/X3.../Xk其中Xi是正整数且Xi<=1000000000(1<=i<=k,K<=10000)除法表达式应当按照从左到右的顺序求，例如表达式1/2/1/2的值为1/4.但可以在表达式中国入括号来改变计算顺序，例如(1/2)/(1/2)的值为1.现给出一个除法表达式E，求是告诉是否可以通过增加括号来使其为E',E'为整数Input先给出一个数字D，代表有D组数据.每组数据先给出一个数字N，代表这组数据将有N个...
02014年3月16日3,517扩展欧几里得算法