下一页 »Current position : 首页 >> 二分法
算法设计与分析上机作业
poj22991:Ultra-QuickSort2[crayon-5bc90f56cddce504822302/]2:最近点对问题[crayon-5bc90f56cddda655212138/]exercise2.123:集合求交[crayon-5bc90f56cdde0478390821/]
2017ACM萧山训练第5场(2016 Pacific Northwest – Division 1)
E.Enclosure做出大小两个凸包，即所有点的凸包和前k个点的凸包按动态凸包的思路，新加入的点会把小凸包上连续的一些点弹出，这些点是一个连续的区间相当于切掉凸包的一个角，加入一个三角形若在大凸包上顺时针枚举一个加入的点，这个区间左右端点也是顺时针转的，类似旋转卡壳切掉部分的面积顺便维护由于坐标范围较大，用double精度会炸[crayon-5bc90f56cf16d855257088/]G.MaximumIslandsL的上下左右直接贪心为W然后剩下的就...
2017ACM萧山训练第3场(World Final 2013)
A.Self-Assembly如果一个正方形有两条边a,b则a->op(b)b->op(a)，判图中是否有环，有环则说明我们能把一些正方形绕成环然后翻折旋转变得无限大[crayon-5bc90f56cfa3c042046228/]C.SurelyYouCongest只有最短路相同的会互相影响按最短路分组后跑c次最大流[crayon-5bc90f56cfa47410011106/]D.Factors爆搜前16个素数[crayon-5bc90f56cfa54984507192/]F.LowPower二分答案贪心检验[crayon-5bc90f56cfa5c301496165/]H:М...
2017 训练赛 1 by hzwer
「poj1054」TheTroublesomeFrog（恼人的青蛙）「poj1037」decorativefence「hdu2197」本原串「poj2112」OptimalMilkin「bzoj4010」[HNOI2015]菜肴制作「hdu2462」TheLuckiestnumber「bzoj3172」[Tjoi2013]单词「poj1054」TheTroublesomeFrog（恼人的青蛙）首先O(n^3)的算法是显然的，即枚举两个点，check一下这条路径上所有点，由于这道题时限放的比较宽，实际上图可以直接用二维的bool数组存下来网络上的题解大多...
2015 ACM / ICPC EC – Final
A. BoxesandBalls题意：有不超过n个球放在若干袋子里，每次操作拿一个新的袋子，从现有的所有袋子中各拿一个求放进新的袋子里，去掉空袋子问最多可以放多少个球，使得每次操作之后，所有袋子球数构成情况不变 容易发现，恒定不变的状态为1,12,123...[crayon-5bc90f56d0b64305356989/]B.BusinessCycle题意：给定一个n个结点的环，编号0~n-1，每个点有一定的权值，从点0出发沿编号走，到达某一个节点则把目前总权值加上这...
2016 CCPC Changchun Onsite
hdu5912.Fraction计算连分数的答案，直接模拟即可[crayon-5bc90f56d1c19932050004/]hdu5914.Triangle问长度1到n的线段，至少要去掉多少，使得剩下的线段无法构成三角形\(1\leqn\leq20\)斐波那契数列，手算完打表[crayon-5bc90f56d1c25206063963/]hdu5916.HarmonicValueDescription定义全排列的权值为相邻两个数的gcd，求1到n的所有全排列中第K小的排列\(1\leq2k\leqn\leq10000\)容易发现，第k大的全排列的权值为n-2+k构造方式...
2016 ACM / ICPC Asia Regional Qingdao Online
大部分都是队友写的代码QAQ我主要是填坑个题解1001ICountTwoThree定义『ICountTwoThreeNumber』为\(2^a3^b5^c7^d\)问超过n的最小的这种数字显然这样的数字数量是很少的，其质因数个数不会超过30个dfs出所有数字，二分查询1002Cure求\(\sum\limits_{k=1}^n\frac{1}{k^2}\)\(\lim_{n\rightarrow\infty}\)\(\sum\limits_{k=1}^n\frac{1}{k^2}=\frac{\pi^2}{6}\)n超过十几万之后就达到精度上限1003FamilyView把一个文本...
2016 ACM / ICPC Asia Regional Dalian Online
1002DifferentGCDSubarrayQuery问长为n的序列，m个询问，问区间[L,R]所有子段的不同gcd值个数考虑固定左端点，随着右端点的移动，gcd至多衰减log次（每次至少折半）从n开始添加询问的左端点，用树状数组维护每个gcd右端点的最小值[crayon-5bc90f56d29e1402664890/]1007FriendsandEnemiesn个人，每个人可以用m种颜色中的一部分染色自己的项链两个人是朋友当且仅当他们拥有相同的颜色敌人不拥有任何相同的颜色问对于任意一...
「CF613X」Codeforces Round #339 (Div. 1)
A.PeterandSnowBlower求多边形绕着一个形外一点p转一圈扫过的面积扫过的区域是个圆环注意由于可能是凹多边形，所以小圆半径是p到各条边的最近距离大圆半径就是p到顶点的最远距离[crayon-5bc90f56d2ea5745975373/]B.Skills将a数组排序以后，枚举最终值为A的元素个数为p，显然取最大的p个变为A，剩下的n-p个元素，两次二分+前缀和求能达到的最小值[crayon-5bc90f56d2eae419574492/] ...
「CF611X」Good Bye 2015
智商基本已经放弃我了，身败名裂后的题解。因为太弱加上是个高三狗，所以就只有ABCD了QAQA.NewYearandDays求2016年有多少个星期n求2016年有多少个月有n号可以算好答案输出[crayon-5bc90f56d3804344202964/]B.NewYearandOldProperty求L-R中有多少十进制数转为二进制只有1个0枚举0在哪一位，然后再枚举1的个数[crayon-5bc90f56d380d410800404/]C.NewYearandDomino求一个子矩形有多少种放置1*2的方式二维前缀和...
NOI2012骑行川藏
Description蛋蛋非常热衷于挑战自我，今年暑假他准备沿川藏线骑着自行车从成都前往拉萨。川藏线的沿途有着非常美丽的风景，但在这一路上也有着很多的艰难险阻，路况变化多端，而蛋蛋的体力十分有限，因此在每天的骑行前设定好目的地、同时合理分配好自己的体力是一件非常重要的事情。由于蛋蛋装备了一辆非常好的自行车，因此在骑行过程中可以认为他仅在克服风阻做功（不受自行车本身摩擦力以及自行车与地面的摩擦力影响）。某一天...
「CF360X」Codeforces Round #210 (Div. 1)
A.LevkoandArrayRecovery求出每个位置初始值的最大值，然后check一下[crayon-5bc90f56e27cf544276175/]B.LevkoandArray二分答案，f(i)表示前i个的最小修改次数，且i不修改，枚举上一个不修改的位置转移[crayon-5bc90f56e27da675661268/]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...
近期评论