hzwer.com - Page 78

「BZOJ1650」[Usaco2006 Dec] River Hopscotch 跳石子
DescriptionEveryyearthecowsholdaneventfeaturingapeculiarversionofhopscotchthatinvolvescarefullyjumpingfromrocktorockinariver.Theexcitementtakesplaceonalong,straightriverwitharockatthestartandanotherrockattheend,Lunitsawayfromthestart(1<=L<=1,000,000,000).Alongtheriverbetweenthestartingandendingrocks,N(0<=N<=50,000)morerocksappear,eachatanintegraldistanceDifromthestart(0<Di...
22014年7月23日3,680贪心,二分法

「BZOJ1628」[Usaco2007 Demo] City skyline
DescriptionThebestpartofthedayforFarmerJohn'scowsiswhenthesunsets.Theycanseetheskylineofthedistantcity.Bessiewondershowmanybuildingsthecityhas.Writeaprogramthatassiststhecowsincalculatingtheminimumnumberofbuildingsinthecity,givenaprofileofitsskyline.Thecityinprofileisquitedullarchitecturally,featuringonlybox-shapedbuildings.Theskylineofacityonthehorizonissomewherebetween1andWunitswide(1&...
02014年7月23日3,352单调栈
「BZOJ1615」[Usaco2008 Mar] The Loathesome Hay Baler麻烦的干草打包机
DescriptionFarmerJohn新买的干草打包机的内部结构大概算世界上最混乱的了，它不象普通的机器一样有明确的内部传动装置，而是，N(2<=N<=1050)个齿轮互相作用，每个齿轮都可能驱动着多个齿轮。FJ记录了对于每个齿轮i，记录了它的3个参数：X_i，Y_i表示齿轮中心的位置坐标(-5000<=X_i<=5000;-5000<=Y_i<=5000)；R_i表示该齿轮的半径(3<=R_i<=800)。驱动齿轮的位置为0,0，并且FJ也知道最终的工...
02014年7月23日4,319广度搜索
「BZOJ1637」[Usaco2007 Mar] Balanced Lineup
DescriptionFarmerJohn决定给他的奶牛们照一张合影，他让N(1≤N≤50,000)头奶牛站成一条直线，每头牛都有它的坐标(范围:0..1,000,000,000)和种族(0或1)。一直以来FarmerJohn总是喜欢做一些非凡的事，当然这次照相也不例外。他只给一部分牛照相，并且这一组牛的阵容必须是“平衡的”。平衡的阵容，指的是在一组牛中，种族0和种族1的牛的数量相等。请算出最广阔的区间，使这个区间内的牛阵容平衡。区间的大小为区间内最右边的...
12014年7月23日2,815模拟
「BZOJ1688」[Usaco2005 Open] Disease Manangement 疾病管理
DescriptionAlas!AsetofD(1<=D<=15)diseases(numbered1..D)isrunningthroughthefarm.FarmerJohnwouldliketomilkasmanyofhisN(1<=N<=1,000)cowsaspossible.IfthemilkedcowscarrymorethanK(1<=K<=D)differentdiseasesamongthem,thenthemilkwillbetoocontaminatedandwillhavetobediscardedinitsentirety.PleasehelpdeterminethelargestnumberofcowsFJcanmilkwithouthavingtodiscardthemilk.Input...
12014年7月23日3,622状压动规
「BZOJ1682」Out of Hay 干草危机
DescriptionThecowshaverunoutofhay,ahorribleeventthatmustberemediedimmediately.Bessieintendstovisittheotherfarmstosurveytheirhaysituation.ThereareN(2<=N<=2,000)farms(numbered1..N);BessiestartsatFarm1.She'lltraversesomeoralloftheM(1<=M<=10,000)two-wayroadswhoselengthdoesnotexceed1,000,000,000thatconnectthefarms.Somefarmsmaybemultiplyconnectedwithdifferentlengthroads.Allfarm...
02014年7月23日4,084kruskal
「BZOJ3223」JoyOI 1729 文艺平衡树
Description您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1Input第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2……n-1,n) m表示翻转操作次数接下来m行每行两个数[l,r] 数据保证 1<=l<=r<=nOutput输出一行n个数字，表示原始序列经过m次变换后的结果SampleInput53131314...
262014年7月22日17,620splay
「BZOJ1251」序列终结者
Description网上有许多题，就是给定一个序列，要你支持几种操作：A、B、C、D。一看另一道题，又是一个序列要支持几种操作：D、C、B、A。尤其是我们这里的某人，出模拟试题，居然还出了一道这样的，真是没技术含量……这样我也出一道题，我出这一道的目的是为了让大家以后做这种题目有一个“库”可以依靠，没有什么其他的意思。这道题目就叫序列终结者吧。「问题描述」给定一个长度为N的序列，每个序列的元素是一个整数（...
172014年7月21日8,492splay
「FJ2014集训」愚蠢的算法
问题描述对于一个1~n的排列{p1,p2,…,pn}，将pi和pj交换，需要的代价为2*|i-j|-1，记f(p)表示通过交换将排列p变成从小到大的排列，即{1,2,3…,n}的最小代价。一个愚蠢的算法是用g(p)=Σmax(0,i-pi)来估算f(p)。给出1~n的排列的前m个元素，求有多少个排列p满足条件f(p)=g(p)。输入格式输入n和m，表示1~n的排列，以及确定了前m个数。接下来一行包含m个数，表示排列中确定的前m个数。输出格式输出一行，表示有多少个排列满足条件，输出...
02014年7月20日2,524深度搜索
「BZOJ3694」「FJ2014集训」最短路
题目描述给出一个n个点m条边的无向图，n个点的编号从1~n，定义源点为1。定义最短路树如下：从源点1经过边集T到任意一点i有且仅有一条路径，且这条路径是整个图1到i的最短路径，边集T构成最短路树。给出最短路树，求对于除了源点1外的每个点i，求最短路，要求不经过给出的最短路树上的1到i的路径的最后一条边。输入格式第一行包含两个数n和m，表示图中有n个点和m条边。接下来m行，每行有四个数ai，bi，li，ti，表示图中第i条边连接...
02014年7月20日5,281线段树,树链剖分
「BZOJ3698」「FJ2014集训」XWW的难题
「问题描述」XWW是个影响力很大的人，他有很多的追随者。这些追随者都想要加入XWW教成为XWW的教徒。但是这并不容易，需要通过XWW的考核。XWW给你出了这么一个难题：XWW给你一个N*N的正实数矩阵A，满足XWW性。称一个N*N的矩阵满足XWW性当且仅当：（1）A[N][N]=0；（2）矩阵中每行的最后一个元素等于该行前N-1个数的和；（3）矩阵中每列的最后一个元素等于该列前N-1个数的和。现在你要给A中的数进...
12014年7月20日4,970有上下界网络流
「FJ2014集训」信心题
「题目描述」在二维平面上有若干个多边形，每个多边形都覆盖了一定的区域，它们之间有可能重叠，请求出这些多边形遮住了多大的平面区域。即，求多边形的面积并。「输入格式」本题为提交答案题，共有10个输入，分别是cover1.in∼cover10.in。每个文件第一行，一个整数，表示这个输入文件的序号(1∼10)。接下来一行，一个整数n，表示这组数据中有n个多边形。接下来n行，每行第一个整数Pi，表示这个多边形有Pi个点，接下来有Pi组整...
02014年7月20日3,629线段树,几何