算法 - Page 77 - hzwer.com

「BZOJ1643」[Usaco2007 Oct] Bessie’s Secret Pasture 贝茜的秘密草坪
Description农夫约翰已经从他的牧场中取得了数不清块数的正方形草皮，草皮的边长总是整数（有时农夫约翰割草皮的刀法不合适，甚至切出了边长为0的正方形草皮），他已经把草皮放在了一个奶牛贝茜已经知道的地方。贝茜总是希望把美味的草皮放到她的秘密庄园里，她决定从这些草皮中取出恰好4块搬到她的秘密庄园中，然后把它们分成1×1的小块，组成一个面积为N(1<=N<=10,000)个单位面积的部分。贝茜对选出这样四块草皮的方法数...
02014年7月24日2,689递推与动规

「BZOJ3693」「FJ2014集训」圆桌会议
问题描述有n组人要一起开一个圆桌会议（编号为0~n-1），会议的圆桌上有m个位置（编号为0~m-1）。每个组有ai个人，他们需要被安排在（li，(li+1)%m，(li+2)%m，…，ri）的座位范围内。每个座位只能安排一个人就坐，并且每个人都需要被安排一个座位。现在你需要判断是否存在满足条件的座位安排。输入格式输入包含不超过10组数据。第一行有一个数字T，表示数据组数。接下来有T组数据，每组数据第一行包含两个数n，m，表示有多少组的...
02014年7月23日5,713线段树
「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,870贪心,二分法
「BZOJ1628」[Usaco2007 Demo] City skyline
DescriptionThebestpartofthedayforFarmerJohn'scowsiswhenthesunsets.Theycanseetheskylineofthedistantcity.Bessiewondershowmanybuildingsthecityhas.Writeaprogramthatassiststhecowsincalculatingtheminimumnumberofbuildingsinthecity,givenaprofileofitsskyline.Thecityinprofileisquitedullarchitecturally,featuringonlybox-shapedbuildings.Theskylineofacityonthehorizonissomewherebetween1andWunitswide(1&...
02014年7月23日3,591单调栈
「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,586广度搜索
「BZOJ1637」[Usaco2007 Mar] Balanced Lineup
DescriptionFarmerJohn决定给他的奶牛们照一张合影，他让N(1≤N≤50,000)头奶牛站成一条直线，每头牛都有它的坐标(范围:0..1,000,000,000)和种族(0或1)。一直以来FarmerJohn总是喜欢做一些非凡的事，当然这次照相也不例外。他只给一部分牛照相，并且这一组牛的阵容必须是“平衡的”。平衡的阵容，指的是在一组牛中，种族0和种族1的牛的数量相等。请算出最广阔的区间，使这个区间内的牛阵容平衡。区间的大小为区间内最右边的...
12014年7月23日3,008模拟
「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,917状压动规
「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,485kruskal
「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,976splay
「BZOJ1251」序列终结者
Description网上有许多题，就是给定一个序列，要你支持几种操作：A、B、C、D。一看另一道题，又是一个序列要支持几种操作：D、C、B、A。尤其是我们这里的某人，出模拟试题，居然还出了一道这样的，真是没技术含量……这样我也出一道题，我出这一道的目的是为了让大家以后做这种题目有一个“库”可以依靠，没有什么其他的意思。这道题目就叫序列终结者吧。「问题描述」给定一个长度为N的序列，每个序列的元素是一个整数（...
172014年7月21日8,787splay
「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,732深度搜索
「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,505线段树,树链剖分