永远鲜红的幼月

分类

CF(19) dp(6) gcd的应用(1) sort(4) spfa(1) 二分(12) 几何(1) 博弈(2) 固定算法(1) 图论(11) 套题(5) 字符串匹配(1) 并查集(4) 思维(2) 搜索(4) 数学题(2) 数据结构(10) 数论(4) 未归档(192) 树状数组(1) 状压DP(1) 科普(3) 线段树(2) 网络流(3) 计算几何(4) 计算几何学习(17) 贪心(1) 题解(1)

/ 注册

全部文章（共315篇）

1二分+线段树

一个板子题.不过看评论那么多O(n^2)的解法...反正我用O(n^2)试了试..没过... 其实二分套线段树还挺常见的. 不过因为长时间没写过题了..我线段树板子都快忘了,花了一个多小时才回忆起来... 下面是思路: 由于是将所有>=x的数减一.所以我们很容易想到线段...

2020-04-06

5 921

2019牛客假日团队赛7 A,B,C,D,E,G,H,I,K

又写了一天的水题，牛客多校第二场还没怎么补...我好咸鱼啊QAQ A-Oh Those Rollers（简单BFS）题目链接：https://ac.nowcoder.com/acm/contest/997/A 题目大意：n个齿轮，每个齿轮有它的原点，半径，原点在0,0处的是主动轮，问最后一个...

2019-07-23

0 721

牛客小白月赛16 A,B,C,D,E,F,G,H

这次比赛是在家里打的。比赛一半的时候才想起来，从1小时40分钟开始写的。写完5道题之后还剩半个多小时，觉得也写不出什么题了，就直接放弃了（其实是发现6道也进不了rank50）。 Contest：https://ac.nowcoder.com/acm/contest/949#question A-...

2019-07-19

0 579

2019牛客假日团队赛6 （A，B，C，D，E，F，H，J，K，L）

哎。。本来想写完之后在写博客的，但感觉剩下两道比较难啊，估计要等好久才能写出来了。。 A-Card Stacking 题目链接：https://ac.nowcoder.com/acm/contest/993/A 题目大意：n头牛坐在一圈，按顺序发牌。1,2,3,4,5.。。问自己最后都获得那些...

2019-07-19

0 692

2019牛客多校第一场 A，B，E，F，J

随缘补题中我好菜啊QAQ... A-Equivalent Prefixes 题目链接：https://ac.nowcoder.com/acm/contest/881/A 题目大意：给出两个数组，分别包含n个数字。定义RMQ(u,l,r)=RMQ(v,l,r)是数组u和v在同样的[l,r]区间，...

2019-07-19

0 539

POJ-3621-Sightseeing Cows（最优比率环）

题目链接：http://poj.org/problem?id=3621 题目大意：给出一个有向图，每个节点有一个权值val，每条边有一个长度len。奶牛要逛不少于两个点，并且最后要回到原点。求Ans= 所逛过的节点权值之和 / 经过的边的距离之和的最大Ans。思路：讨论区有个大佬证明了最终答...

2019-07-17

0 652

POJ-2728-Desert King（最优比率生成树）

题目链接：http://poj.org/problem?id=2728 题目大意：给出一个三维地图，每个村庄包含x，y，z三点坐标。要在村庄之间通上管子。每两个村庄之间的水平距离（x，y）是有效距离。两村庄之间的abs（高度差）是成本。让你找到一个生成树满足总成本/总有效距离最小。思路：最优...

2019-07-17

0 1104

51nod-1257-背包问题V3（0/1分数规划）

题目链接：http://www.51nod.com/Challenge/Problem.html#problemId=1257 题目大意：中文题。思路：0/1分数规划的入门。由于答案用分数表示。因此我们需要另开一个数组记录二分到Ans时的分子和分母，然后化简即可。 ACCode： #in...

2019-07-17

0 664

POJ-2976-Dropping tests（0/1分数规划）

题目链接：http://poj.org/problem?id=2976 题目大意：给出n次考试，每次考试都有解决问题数Ai 和问题总数两种Bi 属性。我们从中选择n-k场考试，使得最大。输出最大的答案（Ans）。思路：0/1分数规划入门题：二分Ans，前n-k项之和==0....

2019-07-17

0 961

POJ-3622-Gourmet Grazers（贪心，Splay优化）

题目链接：http://poj.org/problem?id=3622 题目大意：给出n头牛，每头牛有两个属性：金钱，美味。m个产品，每个产品有两个属性：金钱，美味。只有一个产品的两个属性都大于等于牛的时候，这头牛才会去吃这个产品。问使n头牛都能吃上产品，最少花费多少。如果不能满足，输出-1； ...

2019-07-16

0 597