题意:
给你棵树,询问有多少点对,使得这条路径上的权值和小于K
题解:
就。。大约就是树的分治
代码:
https://github.com/HarryGuo2012/ACMCode/blob/worldLine/POJ/1741.cpp
Thanks ACM
给你棵树,询问有多少点对,使得这条路径上的权值和小于K
就。。大约就是树的分治
https://github.com/HarryGuo2012/ACMCode/blob/worldLine/POJ/1741.cpp
有很多牛,每头牛有两个吃草的要求,每个种草有这两种属性,并且每头牛吃的草都不能一样,问你价格最少是多少
先考虑没有第二维的限制,那么问题就转换成了一个很简单的贪心问题,每次二分既可。现在加入第二维的限制,如果要保持运算中不受影响,那么必须把第二维的限制排序后,像一维的那样维护一个multiset即可。
https://github.com/HarryGuo2012/ACMCode/blob/worldLine/POJ/3622.cpp
给你一个数对的序列,问你最长上升子序列是什么
这是典型的三维偏序,第一维就是编号。
做法是一维排序,二维分治,三维树状数组
https://github.com/HarryGuo2012/ACMCode/blob/worldLine/SPOJ/LIS2.cpp
给你一个全是黑色的序列,每次操作能够将一段序列变成黑色或者白色。最后问最长的白色的序列。
做法就是用个链表维护若干不相交的白色序列。最后就能得到答案了。使用链表的原因是链表的删除和插入是非常快的。
https://github.com/HarryGuo2012/ACMCode/blob/worldLine/HDU/1199.cpp
给你平面上若干直线,问你在$(L,R)$这个区间内,有多少直线会相交
想象一下怎样的直线能够相交,设直线$Line_1$,直线$Line_2$与$x=L$的交点分别是$L_1,L_2$,与$x=R$的交点分别是$R_1,R_2$,设$L_1>L_2$,那么如果这两根直线在这个区间相交,则必有$R_1<R_2$。
所以这个问题就转换成了求逆序对的个数,维护一个树状数组即可。
https://github.com/HarryGuo2012/ACMCode/blob/worldLine/ZOJ/3157.cpp
|
|
|
|
想必打开这篇博客的人已经知道什么是ACM了吧,如果不知道,请自行百度或者谷歌
这里不是让你设计一个搜索引擎,而是让你学会正确使用搜索引擎,当你有任何不解的时候(包括阅读下文),问问谷歌或者百度,这不只是ACM才需要的技能。
虽然现在编程语言总类繁多,有些OJ也支持多种语言,不过C++还是搞ACM不二的选择,另外最好也学会使用java,因为无论在什么地方,什么国家,什么网站的比赛,C++和java都是支持的。ACM是算法的比拼,所以并不需要将编程语言钻研过深,毕竟语言只是工具。
ACM是国际比赛,英文交流能力是无可厚非的。英文差,但是想搞怎么办?对于这样的问题,我的答案是:请自行学习英语,世上无难事,只怕有心人。
算法算法,无论怎样都脱离不了数学。我认为,几何学、线性代数、离散数学、初等数论和微积分是必须掌握的。太多了怎么办?这点请放心,你可以在不断的比赛中积累这些知识。
全球有非常多非常多的OJ,即Online Judge,在线评测平台,他们可以将你的代码进行在线评测,来判断正误。推荐的国内的OJ有CDOJ(电子科技大学),POJ(北京大学),HDUOJ(杭州电子科技大学),BNUOJ(北京师范大学)。
我不打算详细讲解,所以可以的话,请看每个OJ的F.A.Qs,英文怎么办?自己想办法。
国内的线上比赛有HDU的bestcoder,这个是有奖金的比赛,国外的推荐codeforces,会不定期的进行比赛,比赛的难度适合新手(英语较好),另外就是Topcoder,这个是相当有名的比赛,不过入手较为困难,你可以百度或者谷歌相关教程,这里就不详细解释了。这些比赛都有着积分的规则,简单说,你打得好,积分就会上涨,否则下跌。高排名总是被各大公司相中,如Google、阿里等,特别是Topcoder,在这里的高排名相当有价值。
英语我就不推荐了,自己想办法。下列书籍中的任何习题,都推荐去完成。
《C++大学基础教程》作者是Deitel,这个作者所著的编程书籍都是值得学习的。
《挑战程序设计》,《算法竞赛入门经典》作者刘汝佳。
《组合数学》,《算法导论》,《具体数学》
多看书,多想,细细琢磨,别人能懂,你也可以。问问老师同学,周围的大牛肯定有人知道。
碰到不会的题是很正常的事,此时你就需要搜索题解,怎么搜索?当然谷歌百度。
勤能补拙,每个大神的背后都有着辛勤的付出。凡事靠坚持,每个人都有着无限的潜能,也许你会看见比你更厉害的大神,但只要你努力,你就是下一个大神。
有得便有失,投入和专注是获得成绩的充要条件。
时间不会因为你的犹豫而止步,既然你决定了搞ACM,那么就应当立马开始行动,要知道有很多人已经在你的前面走了很远。
众所周知scanf比cin快的多,那么有没有比scanf更快的东西呢?答案就是输入挂,输入挂利用了告诉读取的函数getchar(),然后再人工处理成整数或浮点,比使用scanf快太多。
当输入规模达到1×10^6次方的时候,就需要输入挂,否则很有可能超时。
不是我写的