二分法 - Page 2

「CF611X」Good Bye 2015
智商基本已经放弃我了，身败名裂后的题解。因为太弱加上是个高三狗，所以就只有ABCD了QAQA.NewYearandDays求2016年有多少个星期n求2016年有多少个月有n号可以算好答案输出[crayon-68bb441b3b3aa341556809/]B.NewYearandOldProperty求L-R中有多少十进制数转为二进制只有1个0枚举0在哪一位，然后再枚举1的个数[crayon-68bb441b3b3b3362252778/]C.NewYearandDomino求一个子矩形有多少种放置1*2的方式二维前缀和...
102016年1月2日4,274递推与动规,模拟,二分法,哈希表

NOI2012骑行川藏
Description蛋蛋非常热衷于挑战自我，今年暑假他准备沿川藏线骑着自行车从成都前往拉萨。川藏线的沿途有着非常美丽的风景，但在这一路上也有着很多的艰难险阻，路况变化多端，而蛋蛋的体力十分有限，因此在每天的骑行前设定好目的地、同时合理分配好自己的体力是一件非常重要的事情。由于蛋蛋装备了一辆非常好的自行车，因此在骑行过程中可以认为他仅在克服风阻做功（不受自行车本身摩擦力以及自行车与地面的摩擦力影响）。某一天...
02015年6月30日3,821二分法
「CF360X」Codeforces Round #210 (Div. 1)
A.LevkoandArrayRecovery求出每个位置初始值的最大值，然后check一下[crayon-68bb441b3c298356955861/]B.LevkoandArray二分答案，f(i)表示前i个的最小修改次数，且i不修改，枚举上一个不修改的位置转移[crayon-68bb441b3c2a3423091669/]C.LevkoandStringsf(i,j)表示前i个字母，beauty值为j的合法方案，\(t_k=s_k\)(k>j)1.在第i位放一个比s[i]大的字母，枚举上一个位置i-k-1满足\(s_{i-k-1}!=t_{i-k-1}\)产生的新的bea...
12015年6月23日5,389递推与动规,spfa,贪心,二分法,最大公约数与最小公倍数
「CF551X」Codeforces Round #307 (Div. 2)
A.GukiZandContest排序[crayon-68bb441b3ca8e946945319/]B.ZgukistringZ统计每个串每个字母的使用次数，枚举串b出现次数，计算c最大出现次数，更新答案我不知道为什么写太挫还能T[crayon-68bb441b3ca97413977565/]C.GukiZhatesBoxes感受一下可以发现，比较远的箱子堆去的人越少越好所以二分答案后，从后往前贪心check即可[crayon-68bb441b3ca9e804060820/]D.GukiZandBinaryOperations按位考虑，给定K以后，每一位...
12015年6月17日5,643模拟,贪心,二分法,分块,快速幂,矩阵乘法
「CF325X」MemSQL start[c] up Round 1
A.SquareandRectangles模拟题[crayon-68bb441b3d27b749734363/]B.StadiumandGames\[(2^k-1)m+m(m-1)/2=n\]枚举k二分得出m[crayon-68bb441b3d284608169140/]C.MonstersandDiamonds此题比较恶心QAQ求最短用个类似dijkstra的东西，如果一种u->{v}的转移所有mn[v]都确定了，把这个转移放进堆或者是某个转移的代价被更新了求最长用记忆化搜索，走出环就是inf[crayon-68bb441b3d289755400593/]D.Reclamation把图扩展成r...
12015年6月16日4,262STL,深度搜索,并查集,二分法,记忆化搜索
「CF260X」Codeforces Round #158 (Div. 2)
A.AddingDigits模拟，每次可以根据当前模的结果，得出下一个添加的数字[crayon-68bb441b3daa3992226866/]B.AncientProphesy在串中枚举一段，用map统计出现次数[crayon-68bb441b3daac359940459/]C.BallsandBoxes可以发现，拿来分的那个盒子现在的数量一定是最少的，于是模拟大法[crayon-68bb441b3dab3874350920/]D.BlackandWhiteTree将两色的结点排序后，依次贪心构造构造方法很简单[crayon-68bb441b3dab7113068700/]E...
02015年6月9日5,062贪心,STL,线段树,二分法
「CF549X」Looksery Cup 2015
A.FaceDetection模拟[crayon-68bb441b3e06a837141743/]B.LookseryParty如果当前每个人还需要的信息数都非0，则已构造完否则，找出为0的那个人，让其发一次信息（这个人之后一定<0）[crayon-68bb441b3e074728404061/]C.TheGameOfParity如果奇数和偶数城市都足够多，那么最后一个操作的人一定能将局面变成他想要的否则就考虑某一方想将奇数或偶数的城市先取完还要特判一下n=K的情况[crayon-68bb441b3e079166703871/]D...
82015年6月8日4,662模拟,贪心,构造,二分法
PKUSC 2014 #2
A:QuadTiling对于某一层来说，状态只有6种，所以手推下转移方程，矩阵乘法加速即可[crayon-68bb441b3eb7d837067256/]B:Garden傻逼线段树[crayon-68bb441b3eb87067444789/]D:One-movecheckmate枚举一下皇后能一步到达的位置，然后判一下是否将死注意细节较多具体见discuss[crayon-68bb441b3eb8f640377674/]E:ATP二分答案后，从比赛最后阶段往前考虑当然是每场给每个人分配一个可以打败的最NB的人。。。贪心判解的可行性...
02015年6月1日3,981模拟,递推与动规,贪心,线段树,二分法,矩阵乘法
PKUSC 2014 #4
A:MagicalGCD枚举每个起点gcd变化不超过log次，二分+rmq求分界点[crayon-68bb441b5b137646299059/]B:DataPacking不知道是不是这样做QAQ[crayon-68bb441b5b143225017342/]C:RadarInstallation得出覆盖每个点的区间贪心即可[crayon-68bb441b5b148850962361/]E:EgyptianFraction确实不好撸。。精度炸飞最后写了个分数。。。[crayon-68bb441b5b151494650268/]...
02015年5月21日3,809贪心,ST表,迭代深搜,二分法
POJ训练记录2
3613.CowRelays求经过n条边的最短路，floyd+倍增QAQ[crayon-68bb441b5b6df160475905/]2728.DesertKing最优比率生成树分数规划[crayon-68bb441b5b6eb243271556/]1639.PicnicPlanning带度数限制的最小生成树http://wenku.baidu.com/link?url=UKcnK1pZvaVwypQOrIFRTOPzM4edIlBmqvnZjZipGf2o_6u-aB1F2tFsMGdUQbA1O-96menmbgyxNoSoWKWBeJnr-RJKuG2yM4b6Jf7IvR3[crayon-68bb441b5b6...
02015年5月17日7,268STL,贪心,prim,树形动规,并查集,floyd,二分法,2-SAT
CERC 2014 填坑计划(9 / 12)
又是一个深不见底的大坑9/12A.Parades树形dp，dp[x]=∑dp[son]可能还有从一个子树出发，到达另一个子树的路径在每个结点记录在这棵树最优解的情况下去掉覆盖的路径树根能到达的点，这个每次暴力合并每个结点用状压dp配对子树得出最优解[crayon-68bb441b5be1f155801270/]C.Sum我傻逼了。。。枚举答案后二分（其实可以直接算）不合法的情况似乎是2的幂[crayon-68bb441b5be2e346087067/]D.Wheels模拟[crayon-68bb441b5be3266636...
02015年5月16日5,320STL,贪心,区间动规,深度搜索,二分法,树形动规,状压动规
PKUSC 2013 #1
poj2245.Lotto裸搜索[crayon-68bb441b5c581498407928/]poj2601.Simplecalculations推公式麻烦。。直接二分[crayon-68bb441b5c58a811938801/]poj1635.Subwaytreesystems树的同构，哈希[crayon-68bb441b5c58f280072426/]poj2419.Forests暴力即可[crayon-68bb441b5c595629523030/]poj1717.Dominoesdp水题[crayon-68bb441b5c59a889851251/]poj2949.WordRings建图+分数规划[crayon-68bb441b5c5a0602135438/] ...
02015年5月14日4,395递推与动规,spfa,深度搜索,并查集,二分法,哈希表