hzwer.com - Page 97

「BZOJ3275」Number
Description有N个正整数，需要从中选出一些数，使这些数的和最大。若两个数a,b同时满足以下条件，则a,b不能同时被选1:存在正整数C，使a*a+b*b=c*c2:gcd(a,b)=1Input第一行一个正整数n，表示数的个数。第二行n个正整数a1,a2,?an。Output最大的和。SampleInput534567SampleOutput22HINTn<=3000。题解将所有点拆成2个0向i连权为a[i]的边，a[i]向T连权为a[i]的边有关系的点互相连边，权为inf答案是tot-ans/2[crayon-6...
52014年5月1日5,289最小割

「BZOJ1426」收集邮票
Description有n种不同的邮票，皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买，每次只能买一张，并且买到的邮票究竟是n种邮票中的哪一种是等概率的，概率均为1/n。但是由于凡凡也很喜欢邮票，所以皮皮购买第k张邮票需要支付k元钱。现在皮皮手中没有邮票，皮皮想知道自己得到所有种类的邮票需要花费的钱数目的期望。Input一行,一个数字NN<=10000Output要付出多少钱.保留二位小数SampleInput3SampleOutp...
52014年5月1日6,063概率与期望
「BZOJ3212」Pku3468 A Simple Problem with Integers
DescriptionYouhaveNintegers,A1,A2,...,AN.Youneedtodealwithtwokindsofoperations.Onetypeofoperationistoaddsomegivennumbertoeachnumberinagiveninterval.Theotheristoaskforthesumofnumbersinagiveninterval. InputThefirstlinecontainstwonumbersNandQ.1≤N,Q≤100000.ThesecondlinecontainsNnumbers,theinitialvaluesofA1,A2,...,AN.-1000000000≤Ai≤1000000000.EachofthenextQlinesreprese...
32014年4月30日4,303线段树
「BZOJ2748」[HAOI2012] 音量调节
Description一个吉他手准备参加一场演出。他不喜欢在演出时始终使用同一个音量，所以他决定每一首歌之前他都要改变一次音量。在演出开始之前，他已经做好了一个列表，里面写着在每首歌开始之前他想要改变的音量是多少。每一次改变音量，他可以选择调高也可以调低。音量用一个整数描述。输入文件中给定整数beginLevel，代表吉他刚开始的音量，以及整数maxLevel，代表吉他的最大音量。音量不能小于0也不能大于maxLevel。输入文件...
02014年4月30日5,369背包动规
「BZOJ2768」[JLOI2010] 冠军调查
Description一年一度的欧洲足球冠军联赛已经进入了淘汰赛阶段。随着卫冕冠军巴萨罗那的淘汰，英超劲旅切尔西成为了头号热门。新浪体育最近在吉林教育学院进行了一次大规模的调查，调查的内容就是关于切尔西能否在今年问鼎欧洲冠军。新浪体育的记者从各个院系中一共抽取了n位同学作为参与者，大家齐聚一堂，各抒己见。每一位参与者都将发言，阐述自己的看法。参与者的心里都有一个看法，比如FireDancer认为切尔西不可能夺冠，而W...
02014年4月30日4,496最小割
「BZOJ1858」[SCOI2010] 序列操作
Descriptionlxhgww最近收到了一个01序列，序列里面包含了n个数，这些数要么是0，要么是1，现在对于这个序列有五种变换操作和询问操作：0ab把[a,b]区间内的所有数全变成01ab把[a,b]区间内的所有数全变成12ab把[a,b]区间内的所有数全部取反，也就是说把所有的0变成1，把所有的1变成03ab询问[a,b]区间内总共有多少个14ab询问[a,b]区间内最多有多少个连续的1对于每一种询问操作，lxhgww都需要给出回答，聪明的程序员们，你们能帮助他吗...
02014年4月29日5,315线段树
「BZOJ2396」神奇的矩阵
Description 给出三个行数和列数均为N的矩阵A、B、C，判断A*B=C是否成立。Input 题目可能包含若干组数据。对于每组数据，第一行一个数N，接下来给出三个N*N的矩阵，依次为A、B、C三个矩阵。Output 对于每组数据，若A*B=C成立，则输出Yes，否则No。每个答案占一行。SampleInput122100SampleOutputNoHINT 对于90%的数据，N不超过100；对于100%的数据，N不超过1000，矩阵中的数字...
12014年4月29日4,031随机化
「BZOJ1984」月下“毛景树”
Description毛毛虫经过及时的变形，最终逃过的一劫，离开了菜妈的菜园。毛毛虫经过千山万水，历尽千辛万苦，最后来到了小小的绍兴一中的校园里。爬啊爬~爬啊爬~~毛毛虫爬到了一颗小小的“毛景树”下面，发现树上长着他最爱吃的毛毛果~~~“毛景树”上有N个节点和N-1条树枝，但节点上是没有毛毛果的，毛毛果都是长在树枝上的。但是这棵“毛景树”有着神奇的魔力，他能改变树枝上毛毛果的个数：Changekw：将第k条树枝上毛毛果的...
02014年4月29日6,238线段树,树链剖分
「BZOJ3450」JoyOI1952 Easy
Description某一天WJMZBMR在打osu~~~但是他太弱逼了，有些地方完全靠运气:(我们来简化一下这个游戏的规则有n次点击要做，成功了就是o，失败了就是x，分数是按comb计算的，连续a个comb就有a*a分，comb就是极大的连续o。比如ooxxxxooooxxx，分数就是2*2+4*4=4+16=20。Sevenkplus闲的慌就看他打了一盘，有些地方跟运气无关要么是o要么是x，有些地方o或者x各有50%的可能性，用?号来表示。比如oo?xx就是一个可能的输入。那么W...
12014年4月28日4,649概率与期望
「BZOJ1901」Zju2112 Dynamic Rankings
Description给定一个含有n个数的序列a[1],a[2],a[3]……a[n]，程序必须回答这样的询问：对于给定的i,j,k，在a[i],a[i+1],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1)，并且，你可以改变一些a[i]的值，改变后，程序还能针对改变后的a继续回答上面的问题。你需要编一个这样的程序，从输入文件中读入序列a，然后读入一系列的指令，包括询问指令和修改指令。对于每一个询问指令，你必须输出正确的回答。第一行有两个正整数n(1≤n≤...
12014年4月28日8,899主席树,树状数组
「BZOJ1977」[BJ2010组队] 次小生成树 Tree
Description小C最近学了很多最小生成树的算法，Prim算法、Kurskal算法、消圈算法等等。正当小C洋洋得意之时，小P又来泼小C冷水了。小P说，让小C求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说：如果最小生成树选择的边集是EM，严格次小生成树选择的边集是ES，那么需要满足：(value(e)表示边e的权值) 这下小C蒙了，他找到了你，希望你帮他解决这个问题。Input第一行包含两个整数N和...
12014年4月28日7,350kruskal,树上倍增
「BZOJ2326」[HNOI2011] 数学作业
Description题解(F[n]) (10^k 1 1 )(F[n-1])( n )=( 0 1 1 )( n-1 )( 1 ) ( 0 0 1 )( 1 )然后分段矩阵乘法0-9,10-99…10^k-n[crayon-67d75f08bf7f1827966961/] ...
52014年4月28日7,354递推与动规,矩阵乘法