看动漫用的python脚本

某神牛推荐我看《命运石之门》,我本想玩原作,但原作又没有汉化,自己日语不会,于是干脆直接看吧……

不知道其他人怎么找的动漫,我下动漫的步骤就是

  1. 在verycd上找到相应的资源
  2. 在115上找到相同的资源
  3. 用用优蛋下载

因为verycd上资源比较全,但下载速度实在不敢恭维。而115资源索引不太好,但是下载速度很给力,而且基本google都有收录。

但是一个一个找太麻烦,这种事情应该可以交给电脑吧……于是我就想到了看过却从没有用过的python。

于是就有了以下脚本……

?View Code PYTHON
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
from xml.dom import minidom
import urllib2,urllib
 
def search(word):
 url='https://www.google.com.hk/search?ix=seb&sourceid=chrome&ie=UTF-8&q=' + word
 req=urllib2.Request(url)
 req.add_header("User-Agent",'Mozilla/4.0 (compatible; MSIE 7.0; Windows NT 5.2; .NET CLR 1.1.4322)')
 opener=urllib2.build_opener()
 text=opener.open(req).read()
 return text
 
file = open('hello.txt','w');
response = urllib2.urlopen('http://www.verycd.com/topics/2888738/');
html = response.read();
file.write(html);
file.close();
 
file = open('output.txt','w');
 
i = 0;
for k in range(1, 23):
    if k < 10:
        s = '0' + str(k)
    else:
        s = str(k)
    s = '[' + s + ']'
    j = html.find('[SumiSora&CASO][Steins_Gate]'+ s +
                  '[GB_Big5][x264_aac][720p]', i)
    if j == -1:
        break
    ind = html[j+58: j+66]
    i = j + 1
    spage = search(ind)
    p = spage.find('http://115.com/file/')
    if spage[p+28] != '&':
        nowurl = spage[p: p+30]
    else:
        nowurl = spage[p: p+28]
    #print nowurl
    response = urllib2.urlopen(nowurl)
    nowurl = response.read()
    pos = nowurl.find('pick_code')
    print 'http://115.com/file/' + nowurl[pos+12:pos+20]

这个脚本会以次把每一集《命运石之门》的115下载地址输出。因为优蛋没试出接口,貌似也不支持批量下载,只能一个个手动添了……这点很遗憾……话说python的库确实很强大。
这个脚本粘了其他人的一点代码……声明下……有问题联系我……
从开始的C++到pascal又到C++,到最近的javascript、python,我觉得语言只不过是辅助我们创造、实现思想的工具。语言到底有什么精髓呢?我至今也没能理解。

RSA公钥加密系统

为了研究黑客技术,今天看了《算法导论》的RSA的部分,给大家简单介绍下。

RSA加密系统是加密两个人之间的通信的一种方法。

我们假设这个通信是一个数字,显然大多数通信都能转化成数字。而我们的通信是用户向网站发送密码。

主要工作是网站这边的:

  1. 随机找到两个大素数p和q(p不等于q)。令n=p*q,m=(p-1)*(q-1)。
  2. 找到一个与m互质的小奇数e。
  3. 求出一个值d使得ed≡1(mod m)。由数论可知因为e与m互质,所以d唯一。
  4. 我们把数对(d,n)自己留着,把数对(e,n)留个公布给用户。我们把前者叫私钥,后者叫密钥。

这样网站的工作就完成了!

用户传输密码p时就传输t=p^e mod n,而网站解密的时候只要计算t^d就可以得到p了。

简单证明下:

  1. 设p不等于0(等于则显然成立)
  2. (p^e)^d≡p^(ed)≡p^(1+k*m)≡p*p^(k*m)≡p*((p^(p-1))^(k*(q-1)) (mod m)
  3. 由费马小定理知道p^(p-1)≡1 (mod m)
  4. p*((p^(p-1))^(k*(q-1))≡p (mod m)
  5. 即最后我们又得到了未加密的数p

这还可以应用到数字签名。也就是说你能知道“网站”传达给你的东西是不是真的是它传达的。

具体就是网站在它传达的信息后面附上它的名字,设这个串是p,然后给用户t=p^d mod n。用户只要看t^e mod n末尾有没有签名即可。这样可以防止中间人冒充你的网站。

注意到如果中间人在网站向用户传递公钥的时候只要修改成自己的公钥然后再用自己的密钥解密就可以盗窃用户的密码,所以网站再传递(e,n)的时候也要进行加密。这就似乎递归了。实际中我们用一个值得信赖的证书颁发机构,它有一个大家都知道的公钥,只要证书机构给我们的网站发个证明“兹证明dxmtb的公钥是(e,n)”然后用它的密钥加密下就行了。把这个加密的密钥传给用户用户就可以用颁发机构的公钥解密了。这样既不怕颁发机构给我们发证书的时候被修改(因为你可以解密看公钥是不是你的公钥),也不怕在传达给用户的时候被中间人修改(要想修改要知道颁发机构的密钥)。当然了,如果颁发机构不值得信赖而你的电脑却相信了它……

那么如何攻破RSA系统呢?当然,只有知道密钥额 我们才能解密或者冒充签名。因为作为用户的话我们只能知道公钥(e,n)。要求d的话我们只要知道m就好办了:这样就可以在log(m)的时间用扩展欧几里得算法求出d了。要想知道m只要能把n因式分解就行了。但看似n只有两个因数,其实是难以分解的。就用平时所知道的根号N的算法对于现在RSA的2048位(二进制)甚至1024位加密是完全不可行的。事实上,更好的算法如果不是针对的话跑起来也是相当困难。

最后再说一下随机两个大素数的问题。根据素数定理我们可以知道在1~N中随机选一个数是素数的概率大概是1/ln(n),所以我们在n只有2的几百到几千次方的时候也只不过用随机几百个几千个数而已。验证这些数是否是素数也有一个很好的算法:之前介绍过的蒙特卡洛算法:Miller-Rabbin算法,大概是O(klogn)级别的。对于将要使用很长时间的密钥、公钥来说,生成他们只需要很短的时间,最多也就几分钟而已。这样的算法显然是可以接受的。

我的学习方法介绍

首先必须明确几点:

  1. 一个人的学习方法不一定适合另一个人,
  2. 不同的学习方法可能达到相同的效果,所以一种方法好不能说明另一种不好,
  3. 学习目的的不同必然会影响学习方法,比如为了学习更多的知识和为了考高分就不一定采用相同的方法,
  4. 一些看似很好的方法也许是很糟糕的方法,不能把问题理想化,必须考虑时间等因素。

所以,我介绍自己的学习方法也是仅供参考的,也许不适合你,也许你的方法更好,也许你不光为了考高分。好了,下面进入正题。

最重要的一点,绝对不可缺少的一点,就是努力。什么是努力呢?就是充分利用你的时间,提高效率,如果你真的想要做什么,甚至可以牺牲其他很多时间来做这件事。努力还代表着专心做你正在做的事情。当然,努力还有一个量的问题,在这里就是学更多的习。我认为努力的时候不应该有轻松感,这说明你的效率还不够高。这说明如果将时间排得更紧一些,将计划增加一些,只不过会把轻松变成稍稍的紧张,却依然是可行的。许多人找所谓学习方法或诀窍,只不过是想偷个懒而已。然而再好的方法不去实施也不会有效的。你也许可以轻轻松松的超过他人,但不能懈怠。原因是成绩的高低不光与自己的水平高低有关,也在很大程度上会受试题难度与考查内容的影响。真的就比其他人强吗?自己总是会有不足的吧。如果更高更强是你所追求的话,那就不断努力吧。

但是努力并不一定是一件令人痛苦的事情。享受学习是必须的。但是既然说了这一点,那么就一定程度上说明学习并不一定是那么令人享受的。难题解出来了当然很高兴,做不出来又有谁会享受呢?不过获取新的知识是一种享受的过程。我们要在学习的过程中发掘快乐。享受学习这件事我也没怎么做到过,所以就不多说了。不过享受学习应该是一种良好的学习状态,但我想只有享受的理想学习状态应该是不存在的吧,参见上一段吧,只有享受是不是就说明还有努力的空间呢?

虽然口头上说努力,但也必须有实际的动力才行。往大的说可以牵扯到人生目标以及意义的问题。每个人的人生目标及意义可以完全不同,我不能说什么,想不想也是每个人的自由。不过我可以说一下我学习的动力。我是略带有被动的学习。因为我的学习成绩一直不错,所以就会承受来自各方面的期待与压力。并且由于之前的基础,往往不用费太大的劲就可以取得看得过去的成绩。这样对我来说努力学习从当今和未来的收益都是很大的。自身方面,确实对良好的大学环境比较期待,而且从小去清华上大学这种事情就好像顺理成章一样。另一方面,我认为学生除了学习就没多少其他可做的事了,把学习这一件事做得淋漓尽致不是一件很自然的事情吗?

有了目标就要时刻朝向目标。学习一个小的目的就是考高分或者学更多的知识。如果是考高分的话,自然是只做对分数有提高的事。课外知识就仅供闲暇时了解了。学知识就不同了。由于高年级的负担往往很重,所以这个我是忽略的。

下面谈一下做题。做题的目的一方面是查漏补缺,另一方面是熟练相关知识的掌握。那么一个显然的优化就是已经掌握且熟练的题目可以不做。在发现漏洞时,如果不能及时解决的话,就要随时记录下来,等到有机会了问老师或者和同学讨论。这里要注意一下,有些题不会蒙了一个选项也要记录下来,防止蒙对了就不小心漏掉了。对于一些比较难的题,一定要坚持独立思考,除非思路完全消失,否则不要放弃。做题并不是为了数量,做题从某种角度来说就是为了做这种不会的有难度的题,不要本末倒置。而熟练掌握的知识就很无聊了。有些题做错可能不是因为不熟练,而只不过是粗心罢了。如果一道题没做对还不如不做呢,所以要尽可能的减少失误。也不要因为自己一时粗心就盲目做题去弥补,一定要看清失败的原因。

另外,学每门课都会有些比较本质的东西。这种东西是通过深入的学习体会出来的。掌握本质可以在很大程度上帮助你。所谓本质,就是看似不同的东西中所蕴涵的相同点。

方法是学不来的,要的是向着自己的目标,一切都以自己的目标为判断标准,竭尽自己的全力去努力,千万不要迷失方向。自己总会体会到自己的方法,并不断改进使得它更加适合自己。

从2011到2012—高三上学期成果杂列

保送以后,很多人告诉我:要好好努力,继续学习。我只是觉得,花费无数睡觉与娱乐的时间换来的成果,不是用来折磨自己的。把初三到高二到变成高三,还要和其他人一样再一次走过高三,这是我无法接受的。从前我不明白自己为什么而活,但高二时我明白了:我所做的一切,都是为了幸福。当然,每个人的人生意义和追求不必完全相同。不过,那些继续努力的人也许是认为这样会在未来过得更加幸福吧。

所以呢,我下面陈列了我这么长时间玩的游戏和简评。请各位学习帝绕行吧。这就是我的颓废史,想鄙视就鄙视吧。

8月12日回到家中,我就迫不及待的在网上订购了《仙剑奇侠传五》,这大概是我第一次买正版游戏吧,挺惭愧的。之后,我又继续noi前玩完了《英雄传说:空之轨迹》的三部。

对于仙剑系列,我最开始接触的事《仙二》。是在初中的时候借同学的盗版光盘玩的。虽然只用了3天就通关了,但对我造成了极大的感动。《仙剑》那深情又委婉的风格给我留下了强烈的印象。不久我又陆续把每一部都玩完了。后来看评论,才发现《仙二》竟然被其它人认为是最烂的一部,而恰恰是这“最烂的”一部把我领进了RPG的大门。《仙剑奇侠传四》中主角门对于人和妖的关系的看法让我引起了深思,而玄霄不顾一切的想要飞升,云天河在所谓天道和人情中所做的抉择,也对我产生了不小的震撼。而在所有仙剑中,我最喜欢的是《仙剑奇侠传三外传问情篇》,比起所谓天道、人妖这些大道理,人与人之间的情更加贴近内心。矢志不渝是每对有情人的不懈追求。但可惜的是,制作历代仙剑系列的上海软星在发售了《仙四》后不久即倒闭,无论根本原因,毋庸置疑盗版罪不可赦。而这是热爱仙剑的玩家所不想看到的,于是我就下定决心《仙五》一定要买正版。说服父母有不小的难度。可悲的人们都不认为游戏需要用钱。甚至有个别人认为游戏祸害玩家,应该倒贴钱。唉!

而《空之轨迹》也是有精彩而不逊色于仙剑的剧情。这主要得益于谜一样的噬身之蛇。艾斯蒂尔与约修亚纯真的爱情也是令人感动。而且大规模的战斗和绝境中逆转也很振奋人心。而战争所到之处永远撒满了悲剧。剑帝莱恩的哲学并非一般人所能理解吧(至少我是没看懂)。

大概9月中旬,我接触了galgame《CLANNAD》,是从verycd的评分排行上看到的。

说到galgame我还是noi前省队的一位同学推荐我玩的。最开始我玩的是《秋之回忆7》,因为《秋之回忆》比较有名嘛。当时我还从他那拷了《Fate/Stay Night》。《秋之回忆7》的悬疑风格和高质量的画面、根据剧情代入感强烈的音乐极大地吸引了我。我还记得那时熬夜玩《秋之回忆》到达结局的激动。从此我正式进入了ACG界的大门。

咳咳,接着说《CLANNAD》。我只想说神作不解释。它甚至超越了我心中仙剑的地位。我甚至体会到了什么是信仰。我懂得了幸福是多么可贵,多么值得你去珍惜。我懂得了生活的力量不在于钱,而在于爱。爱的责任,爱的无私,爱的奇迹。而那时由于过于自由而不再充实、潦倒度日的我终于又找到了生活的目标。至于催泪,确实。我无法忘记每天晚上听着BGM眼泪直流的感动。但是,CLANNAD告诉我们的绝不是哭泣。眼泪不应该轻易地流,如果你仅仅是想要流泪,或者想要别人知道你流泪。后来又看了动漫版,权当回忆。只是动漫版的时间限制,游戏的内容根本无法表现完全。而游戏中第一人称视角所带来的体验是动漫绝对无法带来的。看动漫,你同情的是别人。而玩游戏,他们都是你身边的人,你为自己和身边的人而努力,为自己和身边的人而悲叹,光守护的坂道就是你的生活。而对于鄙视gal的人,请你们不要喷了,不要再亵渎神作了!尽管我们的队伍很小,尽管我们无视不渴望同伴,但我们不会把一块朽木拿来充数的。

之后,随随便便我就下了个《天下贰》,因为我很久没有玩网游,想稍微体验下。结果就一发不可收拾。最开始确实是新奇的体验,因为从当初玩《梦幻西游》开始,网游又有了许多新的元素。后来便陷入了每日无聊的任务与日常中,只为了升级,拿装备,游戏变得几乎毫无快乐。那时突然就变成《天下三》了。许多新玩家涌了进来,而网易又推出了大量高经验的日常。突然有一天,我发现我每天上线就像单机一样把日常做啊又做,想单机一样做任务,几乎没有朋友,而师父又很忙,势力主有好久才上线,其他大号都不愿意带小号打本。终于,我决定AFK几天换换心情。有一天,我终于想回到大荒,而一上线,发现师父已经把我删好友了。是啊,我也早已出师了……我寂寞灰心地关闭《天下三》。几天后天下三已经从我的硬盘中消失。我现在还记得一个boss说的话:“大荒还是那个大荒,只是你们的心变了。”我想,我永远大约都是63级了吧。

在压抑、深刻的《Fate》中我来到了11月。对于《Fate》我不想多说什么,也许是带入感太强了,太深刻了,我始终不能完全理解。只是Saber结局的sorrow和分别的那一段描写令人回味。英雄的背后总有不为人知的故事。每个人的道路都充满心酸。让我们向那些为人类光辉历史添彩的英雄致敬!也许你所做的事不为大家所认同,但请坚信你的道路:因为你是为自己而活!(稍微吐槽下:前几天手贱用wine打开了一下Fate,很高兴能打开,今天发现系统档清空了……)

为了寻求治愈,我想到了《CLANNAD 光见守る坂道で》,但由于没有psp玩不了。在我的苦苦哀求下,父母为我买了psp。结果玩了一点这部作品,大失所望:整个就在闲话家常、 卖萌。也许这就是主角们的幸福生活吧,而这样的幸福真是太假了。而在这部作品玩完前,我就转投了其他优秀作品。

首先是知名的《最终幻想》系列。我玩了《最终幻想7核心危机》。虽然感觉结尾有点仓促,我还不太明白发生了什么。但是最后配着那首《自由の代償》,我体会到了一种与仙剑不同的感动。走进绝境,我亦无悔,为了保护他人,纵使神罗士兵再多,我也不会轻易言败。无穷的军队,如一群蝼蚁,握着剑倒下,鲜血染红了雨水,这才是英雄!而扎克斯,只是为了保护克劳德。纯真的笑,单纯的梦。他像一个孩子,他渴望天使的翅膀。

然后是《零之轨迹》。作为《空之轨迹》的续作,玩了几章我觉得毫无意思,老套的剧情,老套的团战,于是就暂且搁置不玩。

大概在某个晚上我玩了《eden*》。作为一个只有一条线的游戏,搞的是意境。战争的残酷有讲。对爱的执着有讲。就像《秒速五厘米》一样,没什么波澜。世界也许会在平静中毁灭,而我在天堂等你吧,大概。还有某晚上的《星之梦》。也是平静性的。战争,不光杀人,活下来的人,心也会受伤啊。纯洁的爱情是gal中很主要的主题。这两部游戏主要实在是太短了……

之后便是《秋之回忆2》和《秋之回忆1》。2代被称为经典,1代评价也不错。但就像《仙一》一样,不是那么现代的画面让人无法投入。而短时间接触过多gal的对有些东西确实也免疫了。惭愧。对于白河萤我其实是很喜欢的,但再三地甩让我无法忍受。而一代彩花总是阴魂不散的样子,感觉这个问题解决得是那么生涩。这两作就像标准的gal里,在校园中普普通通的恋情。生活也许还是这样平平淡淡的好。谁愿意像《CLANNAD》或者仙剑那样折腾呢?

不久便到了12月国家集训队培训,那是机房的同学为我介绍的osu!这个音乐游戏。我很是喜欢,于是一个一个晚上在我喜欢的游戏、动漫歌曲中度过了。

之后虽然有乱搞《きっと、澄みわたる朝色よりも》、《怪物猎人P3》,但主要还是在看《钢之炼金术师FA》。这个比较长,很早以前都下了50多集,但是看了几集后觉得炼金术太扯,故事太阴暗,不想看。玩了《秋之回忆1、2》后觉得应该尊重每一部作品。作品总有缺点,但不能光看到缺点。应该认真地去评判每部作品,看几集就觉得不行是绝对的亵渎。之后,便渐渐不能自拔。艾尔利克兄弟的纠结让我也很纠结,战争就是执政者的政治阴谋,自大导致失败,团结对抗力量,不原谅他人但抛掉仇恨。当社会坠入黑暗时,需要我们每个人的努力把它拉出来。而民族的仇恨,可能也只不过被某些人利用和戏耍了。

到了1月初,我充了《魔兽世界》点卡,正式开始了艾泽拉斯的历险。我最初的人类法师也忘记了是哪一天没事在机房建的号,那是还是WLK时期呢。我本来不准备玩,但有位同学宁可他帮我充点。我被他的心所打动,就加入了WoW的行列。而后来,我的人类法师到了55,我又转战了死亡骑士,到今天63级了。在这期间,我其他的娱乐就是《きっと、澄みわたる朝色よりも》,不过也没有搞完。

 

与此同时,我还玩了《ever17》。悬疑的风格的确很吸引人。也批判了现代科学的发展和违背人性矛盾……嘛,不过不用那么认真。大家都好好活下来了就好。

半年来我看的其他动漫还有《魔法少女小圆》,还试图看小说《诛仙》,轻小说《魔法禁书目录》,不过前者由于套路不断重复让我丧失了兴趣,后者由于实在太休闲我就没有看下去。

这就是我半年来的浮躁史,供大家借鉴,另外欢迎大家进入gal的阵营。要说学习当然也有学,但在此忽略就好。既然得到了暂时的自由,那就好好享受这一切,做自己真正想做的事就好。学习什么时候都可以。我想我是永远不会后悔的,而这段时间会是终生难忘的吧。

祝大家新年快乐哦!

极限情况下strstr对比KMP

什么情况下strstr会达到最坏情况呢?考虑以下情况:

str1: 字母a重复N次 + 字母b

str2:字母a重复M次 + 字母b

粗略估计复杂度

strstr: O(N+N-1+N-2+…+N-M) = O((N-M)*M)

kmp:O(N+M)

我们就取M=N/2,N=100000。

实验结果就是KMP不到1秒,strstr没跑出来呢……

下附程序:

strstr:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <cstring>
#include <cstdio>
#include <ctime>
 
const int MAXN=1000005;
 
char str1[MAXN],str2[MAXN];
 
int main()
{
	freopen("data.in","r",stdin);
	freopen("data.out","w",stdout);
	scanf("%s",str1);
	scanf("%s",str2);
	int T=time(0);
	char *p=str1;
	while(true)
	{
		p=strstr(p,str2);
		if (p==NULL)
			break;
		printf("%d\n",p-str1);
		p++;
	}
	printf("%d\n",time(0)-T);
	return 0;
}

KMP:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <cstring>
#include <cstdio>
#include <ctime>
 
const int MAXN=1000005;
 
void kmp(char *str1,char *str2)
{
	static int next[MAXN];
	int N=strlen(str1),M=strlen(str2);
	next[0]=-1;
	for(int i=1,j=-1;i<M;i++)
	{
		while(j>=0 && str2[i]!=str2[j+1])
			j=next[j];
		if (str2[i]==str2[j+1])
			j++;
		next[i]=j;
	}
	for(int i=0,j=-1;i<N;i++)
	{
		while(j>=0 && str1[i]!=str2[j+1])
			j=next[j];
		if (str1[i]==str2[j+1])
			j++;
		if (j==M-1)
		{
			printf("%d\n",i-M+1);
			j=next[j];
		}
	}
}
 
char str1[MAXN],str2[MAXN];
 
int main()
{
	freopen("data.in","r",stdin);
	freopen("data.out","w",stdout);
	scanf("%s",str1);
	scanf("%s",str2);
	int T=time(0);
	kmp(str1,str2);
	printf("%d\n",time(0)-T);
	return 0;
}

maker:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <cstdio>
 
const int N=1000000;
 
int main()
{
	freopen("data.in","w",stdout);
	for(int i=0;i<N;i++)
		printf("a");
	printf("b\n");
	for(int i=0;i<N/2;i++)
		printf("a");
	printf("b\n");
	return 0;
}

BCM4313网卡驱动在Ubuntu/Fedora安装驱动的注意事项

装驱动大家都会装,但是装完以后发现可能还是不能用。

我的笔记本是Lenovo B460,在很早一前装完ubuntu时和今天装了Fedora后都出现了这样的问题,使用的驱动都是broadcom-wl。

之后需要这样

sudo modprobe -r acer-wmi

然后就好了。

为了避免每次开机都得输这样一条命令,我们在

/etc/modprobe.d/blacklist.conf

中加入

blacklist acer_wmi

直接屏蔽这个驱动就行了。

SPOJ UNTITLE1

很久没有写题解了,为了攒点rp,写一篇吧……
题目大意:给你一个序列(N<=50000),给某个区间的数都加上一个值,询问尾部在x~y的最大前缀和。

那么我们先根号N分段,每一段维护一个凸包支持询问这一段的最大前缀和。

即Max P=sum[i]+add*i,i是这个区间的第i个位置,sum[i]表示这个区间前i项和,add表示这个区间整个增加的值。

那么设y=sum[i],x=i,y=-add*i+P,add在询问时是一个常量,我们可以想象有一个斜率为-add的直线从上往下降落,最先碰到的点就是最大化P的最优解。那么很显然要维护一个上凸包,询问时二分碰到的点就可以了。

总结一下:对于修改操作,中间的段直接修改标号,两边的直接修改sum数组求凸包。注意求凸包时按照x递增的顺序加点,使用graham维护可以不用排序。对于询问操作,两边直接暴力枚举,中间的就用前面的方法二分找出第一个斜率小于-add的直线,取左端点为当前候选答案就可以了。

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
 
typedef long long Int;
const Int MAXN=100005;
const Int MAXM=1000;//ceil(sqrt(MAXN));
const Int oo=~0ull>>1;
#define pb push_back
 
struct Point
{
	Int x,y;
	Point (Int _x=0,Int _y=0):x(_x),y(_y){}
	bool operator < (const Point &b) const
	{
		return x<b.x || (x==b.x && y<b.y);
	}
	Int operator * (const Point &b) const
	{
		return (Int)x*b.y-(Int)b.x*y;
	}
	Point operator - (const Point &b) const
	{
		return Point (x-b.x,y-b.y);
	}
}P[MAXM];
 
Point *hull[MAXM];
struct Block
{
	Int l,r,size,add,sum[MAXM],ind[MAXM];
	double slope[MAXM];
	Int top;
	void update()
	{
		for(Int i=0;i<size;i++)
			P[i].x=i+1,P[i].y=sum[i+1];
		gethull(size);
	}
	Int getsum(Int t=-1)
	{
		if (t==-1)
			return sum[size]+add*size;
		else
			return sum[t]+add*t;
	}
	void addval(Int x,Int y,Int k)
	{
		x=x-l+1,y=y-l+1;
		for(Int i=x,j=k;i<=y;i++,j+=k)
			sum[i]+=j;
		for(Int i=y+1,j=(y-x+1)*k;i<=size;i++)
			sum[i]+=j;
		if (add!=0)
		{
			for(Int i=1,j=add;i<=size;i++,j+=add)
				sum[i]+=j;
			add=0;
		}
		update();
	}
	Int getmax()
	{
		Int pos=lower_bound(slope,slope+top,add)-slope;
		return getsum(ind[pos]);
	}
	void gethull(Int size)
	{
		if (size>=2)
		{
			hull[0]=&P[0];
			hull[1]=&P[1];
			top=2;
			for(Int i=2;i<size;i++)
			{
				while(top>=2 && (*hull[top-1]-*hull[top-2])*(P[i]-*hull[top-1])>=0)
					top--;
				hull[top++]=&P[i];
			}
		}
		else
		{
			hull[0]=&P[0];
			top=1;
		}
		slope[0]=-oo;
		for(Int i=1;i<top;i++)
		{
			slope[i]=-(hull[i]->y-hull[i-1]->y)/double(hull[i]->x-hull[i-1]->x);
			ind[i]=hull[i-1]-P+1;
		}
		slope[top]=oo;
		ind[top]=hull[top-1]-P+1;
		top++;
	}
}block[MAXM];
 
int N;
int A[MAXN],belong[MAXN];
void init()
{
	scanf("%d",&N);
	Int size=sqrt(N);
	for(Int i=0;i<N;i++)
		scanf("%d",A+i);
	for(Int j=0,i=0;i<N;j++)
	{
		Block &now=block[j];
		now.size=min(size,N-i);
		now.l=i;
		now.sum[0]=0;
		for(Int k=1;k<=now.size;k++)
		{
			now.sum[k]=now.sum[k-1]+A[i];
			belong[i]=j;
			i++;
		}
		now.r=i-1;
		now.add=0;
		now.update();
	}
}
 
void add(Int x,Int y,Int k)
{
	Int l=belong[x],r=belong[y];
	for(Int i=l+1;i<r;i++)
		block[i].add+=k;
	if (l==r)
		block[l].addval(x,y,k);
	else
	{
		block[l].addval(x,block[l].r,k);
		block[r].addval(block[r].l,y,k);
	}
}
 
Int query(Int x,Int y)
{
	Int l=belong[x],r=belong[y];
	Int base=0,ret=-oo,now;
	for(Int i=0;i<l;i++)
		base+=block[i].getsum();
	if (l!=r)
	{
		for(Int i=x-block[l].l+1;i<=block[l].size;i++)
			if ((now=base+block[l].getsum(i))>ret)
				ret=now;
		base+=block[l].getsum();
		for(Int i=l+1;i<r;i++)
		{
			if ((now=base+block[i].getmax())>ret)
				ret=now;
			base+=block[i].getsum();
		}
		for(Int i=1;i<=y-block[r].l+1;i++)
			if ((now=base+block[r].getsum(i))>ret)
				ret=now;
	}
	else
	{
		for(Int i=x-block[l].l+1;i<=y-block[l].l+1;i++)
			if ((now=base+block[l].getsum(i))>ret)
				ret=now;
	}
	return ret;
}
 
int main()
{
	init();
	int M;
	scanf("%d",&M);
	for(Int i=0;i<M;i++)
	{
		int ind,x,y;
		scanf("%d%d%d",&ind,&x,&y);
		x--,y--;
		if (ind==0)
		{
			int k;
			scanf("%d",&k);
			add(x,y,k);
		}
		else
			printf("%lld\n",query(x,y));
	}
	return 0;
}

HNOI2008 神奇的国度

弦图,没看出来……可以参见陈丹琦的弦图幻灯片。

什么是弦图呢?就是对于图中的任意一个长度大于3的环,都有一条弦。那么什么是弦呢?就是连接环上两个不相邻的点的边。

这个题实际上是求每个点染一个色,任意两个有边相连的点颜色不同,最少的颜色数(这个数叫做图的色数)。

对于弦图有一个特殊的性质:色数等于团数。

那么什么是团数呢?先要说一下什么是团。一个团就是一个图的导出子图(选定一些顶点,这些顶点之间的边同时必须选到子图里),并且这个子图是一个完全图(任意两点有边相连)。那么可以知道一个图可能有多个团,其中顶点数最多的一个团的顶点数就是团数。

所以我们只要找到包含顶点数最多的的一个团(最大团)就可以了。

那么怎么求一个弦图的极大团?这就需要求一个“完美消除序列”,详见ppt。

我用的是MCS算法,时间复杂度O(N+M)。具体做法是建一个链表有序记录当前有效的label[i](即链表内是所有存在的label[i]),再有N个链表记录各个label具体对应那些节点。每次找到最大的很明显是O(1)了。更新只会使每个节点的label加1,设一个点未更新前标号为label,如果第一个链表里没有label+1这个节点,就直接把label+1插到label后边就行了。如果增加以后没有节点标号为label,在第一个链表里删除这个节点。第二组链表直接插入删除就行了。为了找到第一个链表label对应的位置,可以使每个label使用固定的节点(即提前开好,需要用时拿来用),这样O(1)就可以找到,而不用遍历链表。

看网上的程序都模拟了一下染色过程,其实没有必要,因为没有求方案。直接求出团数输出就可以了。

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
/*
 * Problem: [HNOI2008]神奇的国度
 * Time: 2011.05.04
 * Author: dxmtb
 * State: Solved
 * Memo: 弦图
*/
#include <cstdio>
 
const int MAXN=10005,MAXM=1000005;
 
struct Node
{
	int v;
	Node *next;
	Node (int _v,Node *_next):v(_v),next(_next){}
	Node (){}
	void *operator new (size_t,void *p){return p;}
}*adj[MAXN],pool[MAXM*2],*mem=pool;
 
inline void addedge(int u,int v)
{
	adj[u]=new (mem++)Node(v,adj[u]);
	adj[v]=new (mem++)Node(u,adj[v]);
}
 
struct List
{
	int v;
	List *next,*back;
	List(){}
	void *operator new (size_t,void *p){return p;}
}pool1[MAXN],pool2[MAXN];
 
List *L1;
List *L2[MAXN];
 
inline void connect(List *a,List *b)
{
	a->next=b;
	b->back=a;
}
 
inline void push_back(List *&L,List *mem)
{
	if (L==NULL)
	{
		L=mem;
		L->next=L->back=L;
	}
	else
	{
		List *p=L->back;
		connect(p,mem);
		connect(mem,L);
	}
}
 
inline void pop_back(List *&L)
{
	if (L->next==L)
		L=NULL;
	else
		connect(L->back->back,L);
}
 
int N;
int pos[MAXN];
 
void init()
{
	for(int i=0;i<=N;i++)
		pool1[i].v=pool2[i].v=i;
	L1=pool1;
	L1->next=L1->back=L1;
	for(int i=1;i<=N;i++)
		push_back(L2[0],pool2+i);
}
 
inline void up(int u)
{
	int x=pos[u];
	pos[u]++;
	//check L1
	//insert x+1 if not exist
	if (pool1[x].next!=&pool1[x+1])
	{
		connect(&pool1[x+1],pool1[x].next);
		connect(&pool1[x],&pool1[x+1]);
	}
	//remove u from x
	if (L2[x]->next!=L2[x])//after remove u ,x is not empty
	{
		connect(pool2[u].back,pool2[u].next);
		if (L2[x]==&pool2[u])
			L2[x]=pool2[u].next;
	}
	else
	{
		connect(pool1[x].back,pool1[x].next);
		if (L1==&pool1[x])
			L1=pool1[x].next;
		L2[x]=NULL;
	}
	//insert u to x+1
	push_back(L2[x+1],pool2+u);
}
 
int ind[MAXN];
int M;
 
int main()
{
	freopen("1006.in","r",stdin);
	scanf("%d%d",&N,&M);
	for(int i=0;i<M;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		addedge(u,v);
	}
	init();
	int re=1;
	for(int i=N;i;i--)
	{
		int j=L1->back->v;
		int u=L2[j]->back->v;
		ind[u]=i;
		pop_back(L2[j]);
		if (L2[j]==NULL)
			pop_back(L1);
		int ans=1;
		for(Node *p=adj[u];p;p=p->next)
			if (!ind[p->v])
				up(p->v);
			else
				ans++;
		if (ans>re)
			re=ans;
	}
	printf("%d\n",re);
	return 0;
}