hzwer.com - Page 44

「BZOJ4014」[FJOI2014] 病毒防护带
根据点到直线距离公式ans=min(Σ(kxi-yi+b)^2/(k^2+1))这个可以三分套三分算。。。我不会偏导不会证展开->(k^2x^2-2*k*x*y+y^2+2*b*k*x-2*b*y+b^2)/(k^2+1)预处理出Σxi、Σxi、Σyi、Σxi^2、Σyi^2、Σxiyi可以O(1)计算答案[crayon-67ae652390208196966982/] ...
02014年12月3日3,888三分法

WC2010重建计划
DescriptionInput第一行包含一个正整数N，表示X国的城市个数.第二行包含两个正整数L和U，表示政策要求的第一期重建方案中修建道路数的上下限接下来的N-1行描述重建小组的原有方案，每行三个正整数Ai,Bi,Vi分别表示道路(Ai,Bi),其价值为Vi其中城市由1..N进行标号Output输出最大平均估值，保留三位小数SampleInput423121132143SampleOutput2.500HINT20%的数据,N<=500030%的数据,N<=100000,原有方案恰...
22014年12月3日7,659二分法,点分治,单调队列
「BZOJ1145」[CTSC2008] 图腾totem
Description在完成了古越州圆盘密码的研究之后，考古学家小布来到了南美大陆的西部。相传很久以前在这片土地上生活着两个部落，一个部落崇拜闪电，另一个部落崇拜高山，他们分别用闪电和山峰的形状作为各自部落的图腾。小布的团队在山洞里发现了一幅巨大的壁画，壁画上被标记出了N个点，经测量发现这N个点的水平位置和竖直位置是两两不同的。小布认为这幅壁画所包含的信息仅与这N个点的相对位置有关，因此不妨设坐标分别为(1,y...
12014年12月2日6,303树状数组
「BZOJ2428」[HAOI2006] 均分数据
Description已知N个正整数：A1、A2、……、An。今要将它们分成M组，使得各组数据的数值和最平均，即各组的均方差最小。均方差公式如下：,其中σ为均方差，是各组数据和的平均值，xi为第i组数据的数值和。Input第一行是两个整数，表示N,M的值（N是整数个数，M是要分成的组数）第二行有N个整数，表示A1、A2、……、An。整数的范围是1--50。（同一行的整数间用空格分开）Output这一行只包含一个数，表示最小均方差的值...
42014年12月2日5,629其它
致NOIP2014
大概记录一下吧考前听说NOIP面向社会征题难度会比较高，做好了暴力的准备。。。day0看考场，福州高级中学好像发生了点不愉快的事情，比较压抑day1第一题，数据范围逗我么，好吧我好像初中玩过这个加强版锤子剪刀布，不过送分也不要这样吧卧槽表只有一半真是坑第二题这不是傻逼树形dp么。。。写完，暴力，对拍一下。。。（为什么我要对拍）第三题嗯好像100很有难度，让我来先写个70的写完->过样例，才过了一个半小时嗯我先来...
182014年12月2日9,311竞赛历程
「CF492E」Vanya and Field
Vanyadecidedtowalkinthefieldofsizen × ncells.Thefieldcontainsmappletrees,thei-thappletreeisatthecellwithcoordinates(xi, yi).Vanyamovestowardsvector(dx, dy).ThatmeansthatifVanyaisnowatthecell(x, y),theninasecondhewillbeatcell.Thefollowingconditionissatisfiedforthevector:,whereisthelargestintegerthatdividesbothaandb.Vanyaendshispathwhenhereachesthesquarehehasalreadyvisited.Vanyawonders...
02014年12月2日3,922其它
「CF492D」Vanya and Computer Game
VanyaandhisfriendVovaplayacomputergamewheretheyneedtodestroynmonsterstopassalevel.Vanya'scharacterperformsattackwithfrequencyxhitspersecondandVova'scharacterperformsattackwithfrequencyyhitspersecond.Eachcharacterspendsfixedtimetoraiseaweaponandthenhehits(thetimetoraisetheweaponis1 / xsecondsforthefirstcharacterand1 / ysecondsforthesecondone).Thei-thmonsterdiesafterhereceivesaihits.Vanya...
02014年12月2日3,371二分法
「CF492C」Vanya and Exams
Vanyawantstopassnexamsandgettheacademicscholarship.Hewillgetthescholarshipiftheaveragegrademarkforalltheexamsisatleastavg.Theexamgradecannotexceedr.Vanyahaspassedtheexamsandgotgradeaiforthei-thexam.Toincreasethegradeforthei-thexamby1point,Vanyamustwritebiessays.Hecanraisetheexamgrademultipletimes.WhatistheminimumnumberofessaysthatVanyaneedstowritetogetscholarship?InputThefirstlinecontai...
22014年12月2日3,460贪心
「CF492B」Vanya and Lanterns
Vanyawalkslateatnightalongastraightstreetoflengthl,litbynlanterns.Considerthecoordinatesystemwiththebeginningofthestreetcorrespondingtothepoint0,anditsendcorrespondingtothepointl.Thenthei-thlanternisatthepointai.Thelanternlightsallpointsofthestreetthatareatthedistanceofatmostdfromit,wheredissomepositivenumber,commonforalllanterns.Vanyawonders:whatistheminimumlightradiusdshouldthelanternshavet...
02014年12月2日2,132模拟
「CF492A」Vanya and Cubes
Vanyagotncubes.Hedecidedtobuildapyramidfromthem.Vanyawantstobuildthepyramidasfollows:thetoplevelofthepyramidmustconsistof1cube,thesecondlevelmustconsistof1 + 2 = 3cubes,thethirdlevelmusthave1 + 2 + 3 = 6cubes,andsoon.Thus,thei-thlevelofthepyramidmusthave1 + 2 + ... + (i - 1) + icubes.Vanyawantstoknowwhatisthemaximumheightofthepyramidthathecanmakeusingthegivencubes.InputT...
02014年12月2日2,521模拟
「BZOJ2300」[HAOI2011] 防线修建
Description近来A国和B国的矛盾激化，为了预防不测，A国准备修建一条长长的防线，当然修建防线的话，肯定要把需要保护的城市修在防线内部了。可是A国上层现在还犹豫不决，到底该把哪些城市作为保护对象呢？又由于A国的经费有限，所以希望你能帮忙完成如下的一个任务：给出你所有的A国城市坐标A国上层经过讨论，考虑到经济问题，决定取消对i城市的保护，也就是说i城市不需要在防线内了A国上层询问对于剩下要保护的城市，修...
42014年12月1日5,815凸包,离线处理
「BZOJ2298」[HAOI2011] problem a
Description一次考试共有n个人参加，第i个人说：“有ai个人分数比我高，bi个人分数比我低。”问最少有几个人没有说真话(可能有相同的分数)Input第一行一个整数n，接下来n行每行两个整数，第i+1行的两个整数分别代表ai、biOutput一个整数，表示最少有几个人说谎SampleInput3200222SampleOutput1题解100%的数据满足：1≤n≤100000 0≤ai、bi≤n求最多说真话的人数，答案即为n-ans设dp[i]表示在前i名中最多有多少人说真话dp...
32014年12月1日5,523递推与动规