算法 - Page 24 - hzwer.com

「BZOJ1875」[SDOI2009] HH去散步
DescriptionHH有个一成不变的习惯，喜欢饭后百步走。所谓百步走，就是散步，就是在一定的时间内，走过一定的距离。但是同时HH又是个喜欢变化的人，所以他不会立刻沿着刚刚走来的路走回。又因为HH是个喜欢变化的人，所以他每天走过的路径都不完全一样，他想知道他究竟有多少种散步的方法。现在给你学校的地图（假设每条路的长度都是一样的都是1），问长度为t，从给定地点A走到给定地点B共有多少条符合条件的路径Input第一...
02015年3月28日4,657递推与动规,矩阵乘法

「BZOJ1962」模型王子
DescriptionInput输入数据共一行，两个整数N，K，用一个空格隔开，具体意义如题目中所述。Output输出数据共一行，为最少所需要的时间S。SampleInput53SampleOutput5HINT对于全部的数据，1<=K<=100，1<=N<=10^5题解http://wenku.baidu.com/link?url=o0CPVzuBDLJMt0_7Qph1T7TtdFOzu7O-apIpvaWbIYMz8ZWqBneGqI8LGtLdqpuK5fbQ_v-H01zHwPXDsPrioR5xjCDHjqJn_boYO...
02015年3月26日3,349递推与动规
「BZOJ3208」花神的秒题计划Ⅰ
Description背景「backboard」： Memphis等一群蒟蒻出题中，花神凑过来秒题……描述「discribe」：花花山峰峦起伏，峰顶常年被雪，Memphis打算帮花花山风景区的人员开发一个滑雪项目。我们可以把风景区看作一个n*n的地图，每个点有它的初始高度，滑雪只能从高处往低处滑「严格大于」。但是由于地势经常变动「比如雪崩、滑坡」，高度经常变化；同时，政府政策规定对于每个区域都要间歇地进行保护，防止环境破坏。现在，滑雪...
02015年3月25日4,224记忆化搜索
「BZOJ3894」文理分科
Description 文理分科是一件很纠结的事情！（虽然看到这个题目的人肯定都没有纠结过）小P所在的班级要进行文理分科。他的班级可以用一个n*m的矩阵进行描述，每个格子代表一个同学的座位。每位同学必须从文科和理科中选择一科。同学们在选择科目的时候会获得一个满意值。满意值按如下的方式得到：1．如果第i行第秒J的同学选择了文科，则他将获得art[i][j]的满意值，如果选择理科，将得到science[i][j]的满意值。2．如果第i行...
22015年3月25日7,772最小割
「BZOJ1283」序列
Description给出一个长度为的正整数序列Ci，求一个子序列，使得原序列中任意长度为的子串中被选出的元素不超过K(K,M<=100)个，并且选出的元素之和最大。Input第1行三个数N,m,k。接下来N行，每行一个字符串表示Ci。Output最大和。SampleInput10534446666644SampleOutput30HINT20%的数据:n<=10。100%的数据：N<=1000，k,m<=100。Ci<=20000。题解线性规划裸题复习模板ing题解请看：http://hzwer.c...
02015年3月25日4,930费用流
「BZOJ3850」ZCC Loves Codefires
DescriptionThoughZCChasmanyFans,ZCChimselfisacrazyFanofacoder,called"Memset137".ItwasonCodefires(CF),anonlinecompetitiveprogrammingsite,thatZCCknewMemset137,andimmediatelybecamehisfan.Butwhy?BecauseMemset137cansolveallprobleminrounds,withoutunsuccessfulsubmissions;hisestimationoftimetosolvecertainproblemissoaccurate,thathecansurelygetanAcceptedthesecondhehaspredicted.Hesoon...
02015年3月23日3,021贪心
「CF529B」Group Photo 2(online mirror version)
Manyyearshavepassed,andnfriendsmetatapartyagain.Technologieshaveleapedforwardsincethelastmeeting,cameraswithtimerappearedandnowitisnotobligatoryforoneofthefriendstostandwithacamera,and,thus,beingabsentonthephoto.Simplyspeaking,theprocessofphotographingcanbedescribedasfollows.Eachfriendoccupiesarectangleofpixelsonthephoto:thei-thoftheminastandingstateoccupiesawipixelswideandahipixelshighrectang...
02015年3月23日2,674STL,贪心
「CF529E」The Art of Dealing with ATM
ATMsofawell-knownbankofasmallcountryarearrangedsothattheycannotgiveanyamountofmoneyrequestedbytheuser.Duetothelimitedsizeofthebilldispenser(thedevicethatisdirectlygivingmoneyfromanATM)andsomepeculiaritiesoftheATMstructure,youcangetatmostkbillsfromit,andthebillsmaybeofatmosttwodistinctdenominations.Forexample,ifacountryusesbillswithdenominations10,50,100,500,1000and5000burles,thenatk = ...
02015年3月23日3,235模拟
[JSOI2010] 旅行
给定一张无向图,可以k次交换两条边边权，求1到n的最短路交换执行于求最短路之前，边权1<=c<=1000点数<=50边数<=150k<=20此题找不到题解求神犇留言做法我的想法。。。先求从1-n，无视i条边边权的最短路，然后在路径外找i条最短的加回去。。最后只对了5个点。。。[crayon-6781c40247e22948517610/] ...
22015年3月23日3,950spfa,STL
「BZOJ2086」[POI2010] Blocks
Description给出N个正整数a[1..N]，再给出一个正整数k，现在可以进行如下操作：每次选择一个大于k的正整数a[i]，将a[i]减去1，选择a[i-1]或a[i+1]中的一个加上1。经过一定次数的操作后，问最大能够选出多长的一个连续子序列，使得这个子序列的每个数都不小于k。总共给出M次询问，每次询问给出的k不同，你需要分别回答。Input第一行两个正整数N(N<=1,000,000)和M(M<=50)。第二行N个正整数，第i个正整数表示a[i](a[i...
02015年3月23日3,826单调栈
「BZOJ2590」[Usaco2012 Feb] Cow Coupons
DescriptionFarmerJohnneedsnewcows!ThereareNcowsforsale(1<=N<=50,000),andFJhastospendnomorethanhisbudgetofMunitsofmoney(1<=M<=10^14).CowicostsP_imoney(1<=P_i<=10^9),butFJhasKcoupons(1<=K<=N),andwhenheusesacoupononcowi,thecowcostsC_iinstead(1<=C_i<=P_i).FJcanonlyuseonecouponpercow,ofcourse.WhatisthemaximumnumberofcowsFJcanafford?PROBLEMN...
12015年3月23日5,018STL,贪心
「BZOJ3907」网格
Description某城市的街道呈网格状，左下角坐标为A(0,0)，右上角坐标为B(n,m)，其中n>=m。现在从A(0,0)点出发，只能沿着街道向正右方或者正上方行走，且不能经过图示中直线左上方的点，即任何途径的点(x,y)都要满足x>=y，请问在这些前提下，到达B(n,m)有多少种走法。Input输入文件中仅有一行，包含两个整数n和m，表示城市街区的规模。Output输出文件中仅有一个整数和一个换行/回车符，表示不同的方案总数。SampleInp...
02015年3月23日5,279卡特兰数,排列组合