算法 - Page 87 - hzwer.com

「BZOJ1005」[HNOI2008] 明明的烦恼
Description自从明明学了树的结构,就对奇怪的树产生了兴趣......给出标号为1到N的点,以及某些点最终的度数,允许在任意两点间连线,可产生多少棵度数满足要求的树?Input第一行为N(0<N<=1000),接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1Output一个整数,表示不同的满足要求的树的个数,无解输出0SampleInput31-1-1SampleOutput2HINT 两棵树分别为1-2-3;1-3-2 题解该题运用到了...
62014年5月30日12,096高精度,prufer编码,排列组合

「BZOJ1211」[HNOI2004] 树的计数
Description一个有n个结点的树，设它的结点分别为v1,v2,…,vn，已知第i个结点vi的度数为di，问满足这样的条件的不同的树有多少棵。给定n，d1,d2,…,dn，编程需要输出满足d(vi)=di的树的个数。Input第一行是一个正整数n，表示树有n个结点。第二行有n个数，第i个数表示di，即树的第i个结点的度数。其中1<=n<=150，输入数据保证满足条件的树不超过10^17个。Output输出满足条件的树有多少棵。SampleInput42121SampleOutpu...
02014年5月30日5,644prufer编码,排列组合
NOIP2013火柴排队
描述涵涵有两盒火柴，每盒装有n根火柴，每根火柴都有一个高度。现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相同，两列火柴之间的距离定义为：∑ i=1 n (a i −b i ) 2 ，其中a i 表示第一列火柴中第i个火柴的高度，b i 表示第二列火柴中第i个火柴的高度。每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数...
22014年5月30日7,064树状数组
「BZOJ1592」[Usaco2008 Feb] Making the Grade 路面修整
DescriptionFJ打算好好修一下农场中某条凹凸不平的土路。按奶牛们的要求，修好后的路面高度应当单调上升或单调下降，也就是说，高度上升与高度下降的路段不能同时出现在修好的路中。整条路被分成了N段，N个整数A_1,...,A_N(1<=N<=2,000)依次描述了每一段路的高度(0<=A_i<=1,000,000,000)。FJ希望找到一个恰好含N个元素的不上升或不下降序列B_1,...,B_N，作为修过的路中每个路段的高度。由于将每一段路...
72014年5月29日4,465递推与动规
「BZOJ2388」旅行规划
DescriptionOIVillage是一个风景秀美的乡村，为了更好的利用当地的旅游资源，吸引游客，推动经济发展，xkszltl决定修建了一条铁路将当地n个最著名的经典连接起来，让游客可以通过火车从铁路起点（1号景点）出发，依次游览每个景区。为了更好的评价这条铁路，xkszltl为每一个景区都哦赋予了一个美观度，而一条旅行路径的价值就是它所经过的景区的美观度之和。不过，随着天气与季节的变化，某些景点的美观度也会发生变化。xkszlt...
42014年5月29日6,140分块,二分法
「BZOJ3155」Preprefix sum
DescriptionInput第一行有两个整数N和M，分别表示序列长度和操作个数。接下来的一行有N个整数，即给定的序列a1,a2….an。接下来有M行，每行对应一个操作，格式见题目描述。Output对于每个询问操作，输出一行，表示所询问的SSi的值。SampleInput5312345Query5Modify32Query5SampleOutput3532HINT1<=N,M<=100000,且在任意时刻0<=Ai<=100000题解开俩个树状数组，第一个维护a[i]前缀和第二个维护(n...
22014年5月29日4,754树状数组
「BZOJ1452」[JSOI2009] Count
DescriptionInputOutputSampleInputSampleOutput12HINT题解发现第一次写二维树状数组妈蛋就是多了一层for。。。对于每种颜色开一个二维树状数组水过。。。[crayon-69edc81e1deb5890538707/] ...
22014年5月29日5,576树状数组
「BZOJ1537」[POI2005] Aut – The Bus
DescriptionByteCity的街道形成了一个标准的棋盘网络–他们要么是北南走向要么就是西东走向.北南走向的路口从1到n编号,西东走向的路从1到m编号.每个路口用两个数(i,j)表示(1<=i<=n,1<=j<=m).ByteCity里有一条公交线,在某一些路口设置了公交站点.公交车从(1,1)发车,在(n,m)结束.公交车只能往北或往东走.现在有一些乘客在某些站点等车.公交车司机希望在路线中能接到尽量多的乘客.帮他想想怎么才能接到最多的乘客.I...
02014年5月28日4,124递推与动规,树状数组
「BZOJ2506」calc
Description 给一个长度为n的非负整数序列A1,A2,…,An。现有m个询问，每次询问给出l,r,p,k，问满足l<=i<=r且Aimodp=k的值i的个数。Input 第一行两个正整数n和m。第二行n个数，表示A1,A2,…,An。以下m行，每行四个数分别表示l,r,p,k。满足1<=l<=r<=n。Output 对于每个询问，输出一行，表示可行值i的个数。SampleInput521...
12014年5月28日4,402离线处理
「BZOJ1651」[Usaco2006 Feb] Stall Reservations 专用牛棚
DescriptionOhthosepickyN(1<=N<=50,000)cows!TheyaresopickythateachonewillonlybemilkedoversomeprecisetimeintervalA..B(1<=A<=B<=1,000,000),whichincludesbothtimesAandB.Obviously,FJmustcreateareservationsystemtodeterminewhichstalleachcowcanbeassignedforhermilkingtime.Ofcourse,nocowwillsharesuchaprivatemomentwithothercows.HelpFJbydetermining:*Theminimumnumberofstallsreq...
02014年5月28日4,366线段树
「BZOJ1707」[Usaco2007 Nov] tanning分配防晒霜
Description奶牛们计划着去海滩上享受日光浴。为了避免皮肤被阳光灼伤，所有C(1<=C<=2500)头奶牛必须在出门之前在身上抹防晒霜。第i头奶牛适合的最小和最大的SPF值分别为minSPF_i和maxSPF_i(1<=minSPF_i<=1,000;minSPF_i<=maxSPF_i<=1,000)。如果某头奶牛涂的防晒霜的SPF值过小，那么阳光仍然能把她的皮肤灼伤；如果防晒霜的SPF值过大，则会使日光浴与躺在屋里睡觉变得几乎没有差别。...
02014年5月28日3,440贪心
「BZOJ1828」[Usaco2010 Mar] balloc 农场分配
DescriptionInput第1行：两个用空格隔开的整数：N和M*第2行到N+1行：第i+1行表示一个整数C_i*第N+2到N+M+1行：第i+N+1行表示2个整数A_i和B_iOutput*第一行：一个整数表示最多能够被满足的要求数SampleInput541321313252345SampleOutput3题解贪心，按照右端点排序以后冲突的舍弃[crayon-69edc81e1f64a729763299/] ...
02014年5月28日4,307贪心,线段树