永远鲜红的幼月

分类

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篇）

POJ-1066-Treasure Hunt（线段相交）

题目链接：http://poj.org/problem?id=1066 题目大意：一个100*100的房间，里面有n个墙，题目保证不会有三个墙交于一个点。问离开房间的最少穿墙次数（包括房间的墙壁）思路：n的范围很小，枚举所有顶点，然后找到最小的即可。 ACCode： //#pragma ...

2019-04-10

0 738

CF#510 (Div. 2) D（前缀和，逆序数）

CF#510 Div.2 D. Petya and Array（前缀和，逆序数）题目链接：http://codeforces.com/contest/1042/problem/D 题目大意：区间中选择一些连续的区间，满足，然后看有多少个这样的区间。思路：满足条件sum[r]-sum[l-...

2019-04-10

0 485

权值线段树学习（模板+例题）

之前写一道题的时候，看到了一个数据结构叫做权值线段树，跟普通的线段树不太一样，一直没有仔细看，上课无聊，随手推了推，画了几张图，感觉容易多了。权值线段树普通线段树基本上会点数据结构的人都知道了，维护区间的一些属性（最值，区间和什么的）。权值线段树虽然挂了一个权值的名字，其实本职工作仍然离不开...

2019-04-10

1 1673

河南省11届ACM省赛--练习向：A（模拟）B（思维）C（DP）D（读题）E（费用流）F（暴力读题）G（最短路）H（博弈）

又快要到省赛了，补一补去年的题的，话说当时还没补过... 断断续续，两天写了8道，剩下两道应该是防AK的，去年榜首也是8道*2.剩下两道随缘补吧。补题OJ：ZZULI A-计划日（模拟）题目链接：http://acm.zzuli.edu.cn/problem.php?id=2304 题...

2019-04-03

0 561

POJ-2653-Pick-up sticks（暴力，线段相交）

题目链接：http://poj.org/problem?id=2653 题目大意：按顺序给出n条线段，每条线断按输入顺序放置，求最后在最上面的下线段的编号（最上面的线段数量<=1000）。思路：n的范围1e5，m的范围1e3，想着O(n^2)的算法不行，那怕给了3000ms，开始就想...

2019-04-01

0 454

POJ-1556-The Doors（DP+线段相交）

题目链接：http://poj.org/problem?id=1556 题目大意：给出一个10*10的房间，从坐标(0,5)到(10,5)问最短的距离是多少，中间有n个墙，每个墙有两个门，人只能从门进出。思路：一开始想着暴力所有路线，发现似乎会TLE，想了会发现可以用DP（贪心？）的思路解决。...

2019-03-29

0 428

POJ-1269-Intersecting Lines（判断直线相交，测板子）

题目链接：http://poj.org/problem?id=1269 题目大意：给出两条直线上的四个点（每条直线两个点），判断这两条直线：1重合（输出LINE），2.平行（输出NONE），3.相交（输出交点）。思路：测试板子的一道题，把之前总结的板子写上就好了。 ACCode： //#...

2019-03-27

0 511

POJ-3304-Segments（转化成线段相交）

题目链接：http://poj.org/problem?id=3304 题目大意：给出n条线段，判断是否存在一条直线，可以使所有的线段的投影一个点上。思路：这道题乍一看没有什么思路，但是可以转化成求线段相交，即：过投影所在直线做一条垂线，那么这个垂线与所有线如果都有焦点，那么说明存在一个投影都...

2019-03-27

0 521

PTA-L3-2 水果忍者（30 分)（凸包+枚举）

题目链接：https://pintia.cn/problem-sets/994805046380707840/problems/994805049102811136 题目大意：中文体，很清楚。看网上这道题的题解很少，就写一份吧。思路：这道题开始拿到确实不好想。看题解说可以使用凸包。顿时茅塞顿开...

2019-03-26

0 1036

POJ-2398-Toy Storage（二分+线段相交）

题目链接：http://poj.org/problem?id=2398 题目大意：n条线段将一个盒子分成了n+1个区域。给出m个玩具的坐标，问含有i（i∈[1,m]）个玩具的格子都有多少个。给出的线段是乱序的（部分先后给出）。思路：类似POJ-2318，一样的分析。发现由于线段不想交，所以线段...

2019-03-25

0 357