hzwer.com - Page 98

「CF425D」Sereja and Squares
Serejahaspainted n distinctpointsontheplane.Thecoordinatesofeachpointareintegers.Nowheiswondering:howmanysquaresaretherewithsidesparalleltothecoordinateaxesandwithpointspaintedinallitsfourvertexes?Helphim,calculatethisnumber.InputThefirstlinecontainsinteger n (1 ≤ n ≤ 105).Eachofthenext n linescontainstwointegers xi, yi (0 ≤ xi, yi ≤ 105),theintegersrepresentthecoordin...
02014年4月28日4,401二分法

「CF425A」Sereja and Swaps
Asusual,Serejahasarray a,itselementsareintegers: a[1], a[2], ..., a[n].Let'sintroducenotation:Aswapoperationisthefollowingsequenceofactions:choosetwoindexes i, j (i ≠ j);performassignments tmp = a[i], a[i] = a[j], a[j] = tmp.Whatmaximumvalueoffunction m(a) canSerejagetifheisallowedtoperformatmost k swapoperations?InputThefirstlinecontainstwointegers n and k (1 ...
02014年4月28日3,532贪心
NOI2005聪聪和可可
DescriptionInput数据的第1行为两个整数N和E，以空格分隔，分别表示森林中的景点数和连接相邻景点的路的条数。第2行包含两个整数C和M，以空格分隔，分别表示初始时聪聪和可可所在的景点的编号。接下来E行，每行两个整数，第i+2行的两个整数Ai和Bi表示景点Ai和景点Bi之间有一条路。所有的路都是无向的，即：如果能从A走到B，就可以从B走到A。输入保证任何两个景点之间不会有多于一条路直接相连，且聪聪和可可之间必有...
02014年4月27日7,617广度搜索,概率与期望
「BZOJ2257」[JSOI2009] 瓶子和燃料
Descriptionjyy就一直想着尽快回地球，可惜他飞船的燃料不够了。有一天他又去向火星人要燃料，这次火星人答应了，要jyy用飞船上的瓶子来换。jyy的飞船上共有N个瓶子(1<=N<=1000)，经过协商，火星人只要其中的K个。jyy将K个瓶子交给火星人之后，火星人用它们装一些燃料给jyy。所有的瓶子都没有刻度，只在瓶口标注了容量，第i个瓶子的容量为Vi（Vi为整数，并且满足1<=Vi<=1000000000）。火星人比较吝啬，他们并不...
72014年4月27日4,961最大公约数与最小公倍数
「BZOJ2245」[SDOI2011] 工作安排
Description你的公司接到了一批订单。订单要求你的公司提供n类产品，产品被编号为1~n，其中第i类产品共需要Ci件。公司共有m名员工，员工被编号为1~m员工能够制造的产品种类有所区别。一件产品必须完整地由一名员工制造，不可以由某名员工制造一部分配件后，再转交给另外一名员工继续进行制造。我们用一个由0和1组成的m*n的矩阵A来描述每名员工能够制造哪些产品。矩阵的行和列分别被编号为1~m和1~n，Ai,j为1表示员工i能够制造产...
02014年4月27日5,049费用流
「BZOJ1853」[SCOI2010] 幸运数字
Description在中国，很多人都把6和8视为是幸运数字！lxhgww也这样认为，于是他定义自己的“幸运号码”是十进制表示中只包含数字6和8的那些号码，比如68，666，888都是“幸运号码”！但是这种“幸运号码”总是太少了，比如在[1,100]的区间内就只有6个（6，8，66，68，86，88），于是他又定义了一种“近似幸运号码”。lxhgww规定，凡是“幸运号码”的倍数都是“近似幸运号码”，当然，任何的“幸运号码”也都是“近似幸运号码”，比...
02014年4月27日15,736容斥原理
「BZOJ2393」Cirno的完美算数教室
Description~Cirno发现了一种baka数，这种数呢~只含有2和⑨两种数字~~现在Cirno想知道~一个区间中~~有多少个数能被baka数整除~但是Cirno这么天才的妖精才不屑去数啦只能依靠聪明的你咯。Input一行正整数LR(1<L<R<10^10)Output一个正整数，代表所求的答案SampleInput1100SampleOutput58HINT此题数据范围应该是10^910^9中只含2和9的数，且不被其它这样的数整除的baka数只有30个左右于是我们可以利用容斥原...
42014年4月26日5,360容斥原理
「BZOJ2120」数颜色
Description墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会像你发布如下指令：1、QLR代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。2、RPCol把第P支画笔替换为颜色Col。为了满足墨墨的要求，你知道你需要干什么了吗？Input第1行两个整数N，M，分别代表初始画笔的数量以及墨墨会做的事情的个数。第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。第...
12014年4月26日8,258二分法,分块
「BZOJ2453」维护队列
Description你小时候玩过弹珠吗？小朋友A有一些弹珠，A喜欢把它们排成队列，从左到右编号为1到N。为了整个队列鲜艳美观，小朋友想知道某一段连续弹珠中，不同颜色的弹珠有多少。当然，A有时候会依据个人喜好，替换队列中某个弹珠的颜色。但是A还没有学过编程，且觉得头脑风暴太浪费脑力了，所以向你来寻求帮助。Input输入文件第一行包含两个整数N和M。第二行N个整数，表示初始队列中弹珠的颜色。接下来M行，每行的形式为...
52014年4月26日7,714二分法,分块
「CF424C」Magic Formulas
PeopleintheTomskayaregionlikemagicformulasverymuch.Youcanseesomeofthembelow.Imagineyouaregivenasequenceofpositiveintegernumbers p1, p2,..., pn.Letswritedownsomemagicformulas:Here,"mod"meanstheoperationoftakingtheresidueafterdividing.Theexpression meansapplyingthebitwise xor (excluding"OR")operationtointegers x and y.Thegivenoperationexistsinallmodernprogramminglanguages.Forex...
02014年4月26日2,583其它
「BZOJ3343」教主的魔法
Description教主最近学会了一种神奇的魔法，能够使人长高。于是他准备演示给XMYZ信息组每个英雄看。于是N个英雄们又一次聚集在了一起，这次他们排成了一列，被编号为1、2、……、N。每个人的身高一开始都是不超过1000的正整数。教主的魔法每次可以把闭区间[L, R]（1≤L≤R≤N）内的英雄的身高全部加上一个整数W。（虽然L=R时并不符合区间的书写规范，但我们可以认为是单独增加第L（R）个英雄的身高）CYZ、光哥...
22014年4月26日9,171分块,二分法
「BZOJ2038」[2009国家集训队] 小Z的袜子(hose)
Description作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命……具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。你的任务便是告诉小Z，他有多大的概率抽到两只颜色...
212014年4月26日31,417莫队算法