数据结构 - Page 9

「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日4,033单调栈

「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,199STL,贪心
「CF528A」Glass Carving
Leonidwantstobecomeaglasscarver(thepersonwhocreatesbeautifulartworksbycuttingtheglass).Healreadyhasarectangularwmm × hmmsheetofglass,adiamondglasscutterandlotsofenthusiasm.Whathelacksisunderstandingofwhattocarveandhow.Inordernottowastetime,hedecidedtopracticethetechniqueofcarving.Todothis,hemakesverticalandhorizontalcutsthroughtheentiresheet.Thisprocessresultsinmakingsmallerrectangularfra...
12015年3月18日907STL,离线处理
「codechef」March Challenge 2015
只做了前6题弃疗了感觉codechef写题解也没啥人看……「codechefCNOTE」ChefandNotebooks纯模拟[crayon-6908d8cea641c458230227/]「codechefSIGNWAVE」SignWave听说此题打表可以找规律。。引用zld神犇的话吧。。。就是若干个余弦函数的零点均不同。。然后sin函数的分布就十分奇怪了。。比如s=3的时候就是312131213，忽略两端的情况。。就变成非常规则的1213121然后我们再考虑余弦函数当c=2的时候分布就是011101110...
02015年3月17日3,627模拟,并查集,二分法,离线处理
「CF521X」Codeforces Round #295 (Div. 1)
A.DNAAlignment发现每俩个字母都会算一次所以只要求出现最多的字母的个数x快速幂求pow(x,n)[crayon-6908d8cea6b18488669252/]B.Cubes贪心，依次选择合法的编号最大/最小的，用set，map维护一下一个格子能删当且仅当它上方的格子可以找到其它的支撑[crayon-6908d8cea6b26189702750/]C.Pluseseverywhere每一位根据下一个加号位置算贡献，用排列组合算方案或者是后面没有加号延伸到末尾预处理阶乘O1算排列对排列再记录前缀和...
02015年3月14日1,885STL,贪心,快速幂,排列组合
「BZOJ2796」[POI2012] Fibonacci Representation
DescriptionFib数列0,1,1,2,3,5,8,13,21。给出一个数字，用FIB数列各项加加减减来得到。例如10=5+519=21-217=13+5-11070=987+89-5-1InputInthefirstlineofthestandardinputasinglepositiveintegerisgiven（1<=P<=10）thatdenotesthenumberofqueries.ThefollowinglinesholdasinglepositiveintegerKeach1<=K<=10^17.OutputForeachqueryyourprogramshouldprintonthestandardoutputtheminimumnumberofFibona...
12015年3月12日3,848STL,记忆化搜索
「BZOJ3728」PA2014Final Zarowki
Description有n个房间和n盏灯，你需要在每个房间里放入一盏灯。每盏灯都有一定功率，每间房间都需要不少于一定功率的灯泡才可以完全照亮。你可以去附近的商店换新灯泡，商店里所有正整数功率的灯泡都有售。但由于背包空间有限，你至多只能换k个灯泡。你需要找到一个合理的方案使得每个房间都被完全照亮，并在这个前提下使得总功率尽可能小。Input第一行两个整数n,k(1<=k<=n<=500000)。第二行n个整数p[i](1<=p[i]<...
02015年3月2日3,674STL,贪心
「codechef」January Lunchtime 2015
Pieceofcake 统计每个字母出现次数，取最大值，判断其是否等于l/2[crayon-6908d8cea823f404106544/]Justmultiply 乘法快速乘即可，但乘方由于M过大。。使用欧拉函数降幂比较麻烦。。发现a^(10b+c)=(a^b)^10*a^c然后就能On算出表达式了^10可以看做常数[crayon-6908d8cea824d266291888/]Candidatewalk状压一下，转移显然[crayon-6908d8cea8256773157700/]Manybananas这一题比较有意思将宗族大小分为<=300和>300用数组统...
02015年3月1日4,316模拟,状压动规,树状数组,快速幂
「CF519X」Codeforces Round #294 (Div. 2)
「cf519A」AandBandChess模拟[crayon-6908d8cea8a2c483147276/]「cf519B」AandBandCompilationErrors排序，双指针对比用个hash/map统计下元素出现次数[crayon-6908d8cea8a4d971095966/]「cf519C」AandBandTeamTraining实际上答案是min(n,m,(m+n)/3)我分类讨论了TAT还是很好yy的[crayon-6908d8cea8a57176548542/]「cf519D」AandBandInterestingSubstringsa[i][j]表示前缀和为i，字母j为末尾的前缀数量每次查询...
12015年2月28日4,522模拟,STL,树形动规,树上倍增,最近公共祖先
「BZOJ3544」[ONTAK2010] Creative Accounting
Description给定一个长度为N的数组a和M，求一个区间[l,r]，使得(\sum_{i=l}^{r}{a_i})modM的值最大，求出这个值，注意这里的mod是数学上的modInput第一行两个整数N，M。第二行N个整数a_i。Output输出一行，表示答案。SampleInput5131095-57SampleOutput11HINT「数据范围」N<=200000，M,a_i<=10^18题解水水更健康维护前缀和，对于每个前缀和，用set找第一个其大的数，找不到就取set中最小的数，然后将当前...
22015年2月28日4,034STL
最短周期
TAT不知道题目怎么贴不上来zld：傻逼题枚举答案哈希TAT[crayon-6908d8cea9b89471830195/]
12015年2月14日3,201哈希表
「fjWC2015」当小威遇上经济危机
格式问题比较大题面就不贴了tex搞的pdf太酷炫大意给定一棵树，支持修改点权，询问某个点子树内最大值是否超过根[crayon-6908d8ceaa43e524942356/]
52015年2月4日4,546dfs序,线段树