2016-08-25
poj2528:线段树+离散化

http://poj.org/problem?id=2528 题意: 给出几条线段,求按顺序覆盖之后能看到得线段数目。 解法: 线段树+离散化: 但是离散化有几个问题要注意: 我建的是段树,也就是: |____|____|____| 1 2 3 这样子的。 2,3,4那组数据中比较有争议的一组是: 3 5 6 4 5 6 8 如果不离散化直接算覆盖的话,是这样的:(暂且忽略前面的1-4..) ... |____|__ …

阅读更多 →
代码 学习
2016-07-14
poj1204:AC自动机

最近在做AC自动机的题..这题做了三天...看题. Word Puzzles Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 10848 Accepted: 4098 Special Judge Description Word puzzles are usually simple and very entertaining for all ages. They are so entertaining that Pizza-Hut company started using table covers with word puzzles printed …

阅读更多 →
代码
2016-07-09
poj1118:多点共线几何问题

不知道怎么刷着就到这题了。 Lining Up Time Limit: 2000MS Memory Limit: 32768K Total Submissions: 24677 Accepted: 7736 Description "How am I ever going to solve this problem?" said the pilot. Indeed, the pilot was not facing an easy task. She had to drop packages at specific points scattered in a dangerous area. Furthermore, the …

阅读更多 →
代码
2016-07-08
poj1014:母函数

期末完了,做POJ,很水的题就不说了,来说一道比较水的题。 Dividing Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 67526 Accepted: 17570 Description Marsha and Bill own a collection of marbles. They want to split the collection among themselves so that both receive an equal share of the marbles. This would be easy if al …

阅读更多 →
代码
2016-06-17
poj2752:KMP的简单应用

Seek the Name, Seek the Fame Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 16388 Accepted: 8330 Description The little cat is so famous, that many couples tramp over hill and dale to Byteland, and asked the little cat to give names to their newly-born babies. They seek the name, and at the same time seek the fame. In …

阅读更多 →
代码
2016-05-31
poj2774:对后缀数组的复仇,O(nlog n)做法

话说上次发了一篇文章..A掉了2774这道水题,但是!用的是O(nlog^2 n)做法,有些不服.. 于是本人又研究了一次后缀数组的O(nlog n)做法,终于在昨晚领悟了!特A一题..终于可以教会师弟师妹们这一种数据结构了..哭 直接上代码吧..

阅读更多 →
代码
2016-05-27
poj2774:后缀数组之殇

不知道用这样的标题合不合适..总而言之,在我被后缀数组折磨了十余天后,我终于掌握了一种非主流的做法:O(nlog^2 n)构造法..在此我对在《高级数据结构》中介绍的后缀数组构造代码有很深的疑问..因为我发现我对着模板打出来的程序根本无法算出正确的后缀数组..晕 于是我使用的是《挑战程序设计竞赛》中的O(nlog^2 n)模板,真的很好理解,打算在暑假介绍给我亲爱的师弟 …

阅读更多 →
代码 学习
2016-05-18
poj3259:负环判定,SPFA

几天没有AC了..实在手痒啊,上题。 Wormholes Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 41416 Accepted: 15226 Description While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a time …

阅读更多 →
代码 学习
2016-05-10
poj3682:数学期望,O(1)做法附推导过程

这几天一直在磨蹭这题..第一个答案很容易,但在第二个答案我无法算出来了,于是只好求助于Zayin.Zayin又求助于我们年级里面的一个研究生数学老师..而现在终于算出来了,我看了看,自己也推出来几次了,先看题:) King Arthur's Birthday Celebration Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 2921 Accepted: 926 Description King Ar …

阅读更多 →
代码 学习
2016-05-07
hiho1299&hihocoder挑战赛20-t1:打折机票 - 我是思博

话说昨天我在hihocoder找数学期望练习题时,无意中发现了hihocoder有挑战赛!发现的时候,已经开赛了有十多分钟了,我匆忙地参加了比赛。 首先,我打开了第一题: #1299 : 打折机票 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 因为思念新宿的"小姐姐"们,岛娘计划6月份再去一趟东京,不过这次看来她需要自掏腰包。经过了几天的夜战,岛娘终于在 …

阅读更多 →
代码 参赛 学习
2016-05-07
poj1111:不是光棍节也要AC

Image Perimeters Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 8639 Accepted: 5172 Description Technicians in a pathology lab analyze digitized images of slides. Objects on a slide are selected for analysis by a mouse click on the object. The perimeter of the boundary of an object is one useful measure. Your task …

阅读更多 →
代码 学习
2016-04-27
poj2352:Stars(单点更新,树状数组做法)

学了线段树继续学树状数组..突然发现树状数组真的很精辟..找了一题练练手,看题: Stars Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 40264 Accepted: 17491 Description Astronomers often examine star maps where stars are represented by points on a plane and each star has Cartesian coordinates. Let the level of a star be …

阅读更多 →
代码 学习
2016-04-25
poj3468:线段树初学:区间更新(求和)模板题

A Simple Problem with Integers Time Limit: 5000MS Memory Limit: 131072K Total Submissions: 88419 Accepted: 27480 Case Time Limit: 2000MS Description You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to as …

阅读更多 →
代码 学习
2016-04-20
poj1511:链式前向星+SPFA做法

做了两天..终于AC了.. Invitation Cards Description In the age of television, not many people attend theater performances. Antique Comedians of Malidinesia are aware of this fact. They want to propagate theater and, most of all, Antique Comedies. They have printed invitation cards with all the necessary information and with the programme. A …

阅读更多 →
学习
2016-02-05
当大家都在抢红包的时候,程序员正在研究红包算法

[fire]微信红包在新年的火爆程度显而易见,广告主投入5亿现金红包,与央视羊年春晚独家协作起到了无穷的推动效果。这就像一剂大补丸,在短期内给微信带来了极大的关注度与流量。下面通过本篇文章学习下抢红包算法是如何的,小伙伴们快来一同学习吧[/fire] 除夕全天微信用户红包总发送量达到10.1亿次,摇一摇互动量达到110亿次,红包峰值发送量为8.1亿次/分钟。 抛开微 …

阅读更多 →
趣味阅