【题目链接】http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3324
【题目大意】
给定一个串，让你求里面的最长连续重复子串的长度。
这个连续重复子串是这么定义的：
设S为原串Str里的一个子串，如果在Str里，S后面紧接着一个和S一模一样的串，那么S被称为连续重复子串。
【算法分析】
枚举答案ans，对原串的n/ans个字符进行标记，每个字符之间间隔ans-1个字符。
那么假如答案ans成立，那么对应长度为ans的连续重复子串必然包含且仅包含一个被标记的字符。
然后他紧接着和他一模一样的字符串必然会包含且仅包含下一个被标记的字符。
于是令现在其中一个标记为i，我们只需要求(i,i+ans)之间的最长公共前缀和最长公共后缀就可以了。
最长公共前缀和最长公共后缀可以通过建立一个正向字符串的后缀数组和一个逆向字符串的后缀数组来实现。
【时间复杂度】O(n lg n) 【n/1+n/2+n/3+…+n/n <= n lg n】
【空间复杂度】O(n lg n)
转载自：http://blog.csdn.net/hilyoo/archive/2009/08/20/4466028.aspx
最近发现自己太依赖Google了，一遇到什么问题，Google一下。
诚然，搜索是除直接请教别人外的最快捷的方法。但是，这样不利于自己思考，不利于知识体系的形成，不利于基本功的学习。
一般情况下，查到的知识是很狭窄的一部分。如果目的仅仅是应一时之急，当然很好。但是，在不是很紧紧的时候，驱使自己查阅相关的较权威的书籍，可能收获更多。
毕竟知识是有体系的，知其一不知其二对于基本功的掌握是无益的，这无异于引鸠止渴。
著名的《提问的智慧》是这么建议的：
1、看手册
2、看FAQs
3、搜索（Google）
4、问人
现在我却养成了第一Google的习惯，网络资源着实丰富，一般能找到大部分所需的。但是，越来越感觉到知识的不成体系，基础的不扎实。
看来以后，还是得踏实学习了。
问人显然是最快、交互性最好的，但可能知道你问的问题的不多，当然如有知道更好；不论老师、同学或其他的人，主动点，知者为师。
对于需要掌握的基本的知识，多翻越书籍、手册。
对于不重要的临时性的问题，不必浪费时间学习，Google之。
、
、
、
、
、
恩，看来我一直以来通过看论文学习的习惯还是很好的，继续保持。
高一、高二NOIP的失利给我的打击已经足够大了。
我还不是一步一步走到了NOI，还拿了夏令营银牌。
然后，顶着巨大压力拿了NOIP一等。
现在，虽前路茫茫，又有何惧？
不管怎样，路还是要走的。
我自这一路走来，经历的挫折还少吗？
它们早已把我的心锻炼得坚强无比。
我相信，再大的风浪，也能镇定自若。
无论结果如何，我的目标始终不会改变。
就这么样吧。
Someone with strong heart never gives up.
人生不如意者十有八九。
最坏情况也不过如此嘛~
OI退役文暂时没兴趣写了。。。
ACM的事先搁一搁，努力搞好文化课，争取上一个台阶。
大学，起码拿个区域赛金，不能丢师父的脸啊
Final，就像当初的NOI对我一样。
我想，还是有希望的。
然后工作什么的，到时再看看吧。
End.
基本规则
TopCoder的比赛类型很多，最常见的是周赛SRM（Single Round Match），另外还有TCHS SRM（TopCoder High School SRM，题目和SRM一样，仅限中学生参加，参赛者水平较低，据说涨rating很容易），马拉松（Marathon Matchs），还有TCOpen（每年两次的大比赛）之类的比赛。因为大多数人都在做SRM，所以本文介绍的TC比赛即为SRM。
SRM的规则总结起来就是一句话：75分钟做完3道难度递增的题。
TC的每个用户（handle）都有自己的积分（rating），从0-3000+不等。成绩越好，分数越高。
积分与颜色的对应为：白色——未参赛（unrated）；灰色——0~899；绿色——900~1199；蓝色——1200~1499；黄色——1500~2199；红色——2200+。另外排名最高的几个人在TC客户端中会变成红色靶子图标。
比赛分为两个Division，Div I和Div II。白色灰色和绿色的参加Div II，蓝色黄色和红色的参加Div I。Div I的题要比Div II难许多，一般DivII的最后一题和Div I的第一或第二题是一样的。无论是Div I或Div II。三道题目的Score一般为250, 500和1000。
TC的计分规则很诡异，可以见http://www.topcoder.com/wiki/display/tc/Algorithm+Competition+Rating+System，但基本是没人看的懂。不过，TC积分规则的基本思想很简单。
首先是SRM每道题的计分规则。题目从打开开始计时，随着时间的流逝，你这道题目可能得到的分数也越来越少。不过分数减少的速率会逐渐变慢（有人说是先快后慢再快再慢，我不清楚到底哪个是对的，不过总体趋势是越来越慢），一般1000分的题目在降低到300分的时候就基本不会再下降太多了。每道题点击Submit才算正式提交，如果Submit之后发现错误，还可以再次点击Submit修改提交，不过这样会扣除这道题一定的分数。
其次是TC的计分规则。复杂的数学公式很难看懂，但大概的计分思想是：根据此次比赛的得分算出一个这次比赛的rank，然后和以前的rank做比较，求出一个期望的rank，再根据这个期望的rank调整rating。而有时也会出现考得很砸但依然涨rating的情况，不过总体来说TC的计分公式是十分稳定的。
运行环境
TC的客户端是一个Java程序，所以需要JRE（Java Runtime Environment）或者JDK（Java Development Kit）来运行。如果平时不写Java程序的话，装JRE就可以了。毕竟JDK比JRE大一个数量级，下载慢。安装照着提示完成就行了。推荐使用1.4.1以后的版本，因为带了java web start，可以快速登陆。具体方法下一部分讲。
JRE下载地址（中文）：http://www.java.com/zh_CN/download/index.jsp
注册
原文在注册的地方没有详细说明，但很多人似乎对注册都有疑问。所以这里我来注册一个小号，并通过整个过程讲解如何注册。
首先打开http://www.topcoder.com/tc（本文后面TopCoder的主页都指这个网址），然后点击右上角的Register Now（没看到？你可能看到了一个Login，目光向下挪一点，那个红底白字的“Register Now”就在下面）。接下来会弹出http://www.topcoder.com/reg这个页面，因为我们要参加SRM，所以选择第一个，Competition Registration。如果要参加TCHS可以选择第二个High School (Secondary School) Registration。这些以后都可以更改（这里没有选的如果以后要选上，只需要更新个人设置并挑勾；如果选上的要撤销选择则需要点一个“Unregister”的链接）。这里选择项目的多少和后面的页面需要填写内容的多少相关，本文以只选择第一项为例。
需要填写的项目和对应的中文翻译如下：
* Given Name: 名
* Surname: 姓
* Address1: 地址1
Address2: 地址2
Address3: 地址3（如果一行写不开，就在三行中分别写）
* City: 城市
State (US Only): 地区（不在美国就不用选）
Postal Code: 邮编
Province: 省
* Country: 国家
* Country to represent: 代表国家（不知道啥意思，中国人两个都填China就行）
* Timezone: 时区（选Asia/Chongqing）
Phone Number: 电话号码
* Email Address: 电子邮件
* Confirm Email Address: 确认电子邮件地址（就是把电子邮件地址重新打一遍）
Email Notifications: 邮件提醒（就是它给你发邮件提醒什么东西）
– Algorithm Competitions 算法比赛，就是SRM和TCOpen
– Software Development Opportunities 貌似就是有软件开发的项目就告诉你
– Employment Opportunities 工作机会
– TopCoder News & Events 新闻
* Enable Member Contact: 允许成员联系（似乎就是说是不是让别人在TC上能找到你）
* Show / hide earnings: 显示/隐藏收入（大概是说别人是不是能看到你赚了多少钱，TC的比赛可是有钱赚的）
* User Name: 用户名（下面的话提醒你一定不要填错，因为注册多个用户是不符合规定的。据说有人因为别人在TC客户端和他打招呼说“怎么你拿小号上了”，那个人的号就被封了）
* Password: 密码
* Confirm Password: 确认密码
* Secret Question: 密码找回问题（找回密码时需要回答这个问题，注意至少要8个字符长，而一个中文字似乎算一个字符，所以最后可能要打几个问号补齐长度）
* Secret Question Response: 密码找回问题答案
Quote: 座右铭，就是个签名档之类的东西
* Student/Professional: 学生/职业程序员
* = required 带*的项目必填
填写之后点Term of Use下面的I Agree，再点Submit，完成提交。除了用户名别的以后似乎都可以改。
接下来进入Demographics页面，这个大概相当于一个注册用户情况调查。
* Age : 年龄
* Gender : 性别（Male男，Female女）
* Ethnic Background : 民族背景（似乎选Asian or Pacific Islander就行吧……）
* Primary Interest in TopCoder : 在TC的主要兴趣，看不懂的就选第一个吧，那个是说你的兴趣在奖金……
* Shirt Size : T-Shirt大小（有的比赛会给排名前N的选手发T-Shirt，这里你需要选择适合自己的大小，如果选最后一个说明你不想要T-Shirt，人家也不发你了。TC的T-Shirt还是挺好看的，比AStar的好）
* College Major : 大学的专业
* College Major Description : 这个不知道啥意思，随便填点东西就行……
* Degree Program : 学位（从上到下分别为：准学士，学士，硕士，博士，中学生）
* Graduation Year : 毕业年份
* Graduation Month : 毕业月份
* Clubs / Organizations : 组织（一般选None，可以按住Ctrl点鼠标多选）
Other Clubs / Organizations : 其它组织
* School: 学校（点Choose School选择学校，可以搜索，不过为啥shanghaijiaotong university才2个人注册？！）
* Show / hide my school: 显示/隐藏我的学校
GPA: 不懂的自己百度去……
GPA Scale: 同上
Resume: 简历
* How did you hear about TopCoder?: 你怎么知道的TC，如果选了“Member Referral”的话，需要填写那个人在TC的用户名（欢迎填写sqybi~）
* = required
点Submit，进入Confirm页面，确认信息。如果有误可以点Edit修改，否则点最下面的Confirm提交。
接下来进入Success，提示你已经发送一封邮件到你的邮箱中，你必须去点击里面的链接激活用户。激活之后就可以使用这个用户了。
登录
登录的方法一般都是使用Java Web Start。
在TopCoder主页（http://www.topcoder.com/tc）最下方有一段话，第一句是“Load the Arena as an Applet or as a Java Web Start Application”。点“Java Web Start Application”，就会自动下载登陆需要的文件（一个jnlp格式的文件，本机装了JRE/JDK才能打开）。经测试在IE7下这个链接似乎不管用，在Firefox 3下正常。
然后运行下载下来的jnlp文件，就打开了TC客户端。第一次运行和有更新的时候会自动下载安装程序，等待即可，很快。
在我这里有时会提示“语法错误”，但没有任何影响，点“确定”就可以。启动可能会慢一些，耐心等待。
然后输入用户名密码，在Connection的地方选合适的登录方式（一般Direct就行，如果不行的话可以试试别的或者用AUTODETECT自动检测），在PROXY处设置代理，点GO登陆。这时可能还会提示语法错误，再确定就行，这个也没有什么影响。
界面
下面的图们来自原文，很经典，不打算改动了。请使用等宽字体浏览。
主界面：
———————————————————————–
| Advertisements…………. |
———————————————————————–
| Main | Lobbies | Options | Practice Rooms | Active Contests | Help ||
———————————————————————–
| | Clock | |
———————————————————————–
| Rating Key | Who’s here | Chat Area |
| . | | |
| . | | |
| . | | |
| . | | |
| . | | |
|————| | |
| MESSAGES | | |
|————| | |
|LEADER BOARD| | |
|————| | |
| | | |
| | |——————————————-|
| | | >>_______________________________________ |
———————————————————————–
Advertisements 广告。
菜单项:
– Main里可以看在线名单和找人。
– Lobbies基本用不着，因为用户一般都在Chat Room 1。
– Options里是一些选项和颜色设置。
– Practice Rooms里有大量的练习，都是以前比赛的题目
– Active Contests只有有比赛的时候才有用，显示当前正在进行和将要进行的比赛以及比赛注册之类的东西。
– Help里是….不用说了吧。
Rating Key: handle的颜色是随着积分而改变的，这里显示了积分与颜色的关系。
MESSAGES: 比赛的时候这里有注册提示和clarification。
LEADER BOARD: 看每个room的最高分。
Who’s here: 当前room里的人。
Chat Area: 聊天。
练习
在Practice Rooms里随便选择一个room就可以进入practice了。
界面与主页面稍有变化，但基本相同，略去不画。主要的变化就是Who’s here分成了两块，多了一块Who’s assigned。这块显示的是谁被分到了这个room。因为是练习区，所以只要是在这里打开过题的都算是assigned。而在正式比赛中room是由TC分配的。这里显示的是被分配到这个room的人。界面上还有一个变化是Chat Area顶上多了三块。最左边的是一个下拉菜单。里面有三个分值，选择后就可以打开相应的题目。中间的summary可以看这个room里每个人的提交情况。
在practice room里只有coding phase。提交后要判的话需要自己选择Practice Options（多出来的菜单项）里的Run System Test。
比赛
每次比赛(除了1年两次的大赛)都需要在赛前3小时-5分钟之间登陆注册方可参加，注册需要在Active Contest菜单中，选择你要参加的那个比赛，再选择Register。注意比赛前5分钟注册停止，这时候如果没有注册就不能参赛了。而注册了没有打开题目也视为没有参赛，rating不变动。
然后TopCoder开始根据每个人的rating分配room，一般每个room都有高手和菜鸟，只不过如果你的rating高，和高手分在一起的概率高一些（当然也不一定是这样，比如我上次就和yuhch大牛分在了一起……）
分配完成后，Active Contest菜单中Register一项变成Enter。选择后可以直接进入你被分配到的room。Active Contest菜单最下面还有一项暗色背景的Room子菜单，可以进入各个room溜达。
进入自己room的时候一般离开始只有3分钟左右，静一下心就可以直接开始比赛了。coding phase的过程与practice基本相同。注意每题的得分是和用的时间相关（见前面的计分规则），而时间是从你打开该题开始算的。所以一题做完后可以不急着打开下一题，先放松一下。
75分钟的coding后是5分钟的intermission，这段时间是用来休息和聊天的。
然后就是最刺激的15分钟challenge phase，也就是通常说的cha人。打开summary，双击别人的各题Score可以打开那题的程序，如果觉得有错误就可以点左下的Challenge然后输入你认为他会错的输入数据，如果输入数据合法那么系统会用标程的输出和这个程序的输出对比，如果出现不同则cha人成功。成功的话你能得到50分，对方该题分数为0；而如果失败了，你会被减去25分。每个程序只能成功被cha一次，也就是说，如果有人cha掉了这个程序，你就不能再次cha。但是一个人可以cha某个程序很多次，直到这个程序被cha掉或者你放弃。
Challenge结束后就是System Test。这个过程一般比较慢，可以先走开做其他事，过20分钟再回来看结果。System Test中的测试数据有两种：一种是出题者准备的测试数据，一种是成功cha掉别人的数据。所以，TC中很少出现有bug的程序能通过System Test的情况。
结果出来后再过一段时间，就可以看到一系列message,比如rating更新了，新的practice room建好了以及可以通过主页查看这次比赛的数据了。这时比赛就宣告结束。
注意事项
1.在TC主页（http://www.topcoder.com/tc）上可以看到Next SRM，这是下次SRM的时间。注意我们的时间与他们刚好相差12小时，因此若时间是7月9日9:00 PM的话，这里是7月10日9:00 AM。还有要注意的是美国有夏令时，非夏令时的时候，还要再加1小时，就是7月10日10:00 AM。
2.Practice Rooms里写的程序只要点SAVE就可以保存，下次login的时候还可以看到，但是比赛时候的程序必须Submit才可以在coding phase结束后保存(coding phase结束前还是只要SAVE就可以的)。
3.若想cha别人的程序，自己必须是正分(0分也不行)，所以若没有一题有正确的程序但有很好的数据的话，随便交一道看上去正确的程序，然后在challenge的时候快下手，就可以赚到了。
4.客户端自带的编辑器只有基本的编辑功能和编译及测试功能，所以若觉得不方便的话可以使用parser和plugin，TC主页最下面有plugin的连接。每个plugin都有详细说明文档，这里不再赘述。
5.TC的FAQ：http://www.topcoder.com/?&t=support&c=index
6.最后一条，千万不要作弊，会有严重的后果。
SRM的输入输出
SRM是不用标准或文件输入和输出的，只要写一个类的一个成员函数。也就是说，你需要编写的并不是一个完整的程序，而是一个类。
输入是成员函数的参数，输出用return，所以经常需要STL中的vector和string。
因为TC的系统并不测试标准输出，所以标准输出可以当调试用。
编辑器
打开题目后，TC默认使用的编辑器为Standard，在右上角可以看到，choose your editor。我们可以通过使用插件的方式增加自己的编辑器。
随便进入一个Practise Rooms，可以看到增加了一栏为Tools，Tools下有个TopCoder Plugins，点击进入，或者通过这个链接：
http://www.topcoder.com/tc?module=Static&d1=applet&d2=plugins
常用的编辑器有KawigiEdit、PopsEdit和FileEdit，其中KawigiEdit编辑器已经将运行sample的功能添加了进来，会比较方便一些。
以安装KawigiEdit为例说明下插件的安装方法。
a.下载KawigiEdit，从上面的页面链接或者是
http://www.topcoder.com/contest/classes/KawigiEdit/KawigiEdit.jar
下载放到一个目录中，比如：
C:Documents and SettingsAdministrator桌面topcoder
b.进入Options->Editor，在这里添加新的编辑器。点击Add按钮，在Name一栏输入编辑器的名字，比如KawigiEdit；在EntryPoint一栏输入jar的运行方式，这里是：kawigi.KawigiEdit；ClassPath就是类所在的位置，这里通过Browse按钮将KawigiEdit.jar的地址添加进来，比如C:Documents and SettingsAdministrator桌面topcoderKawigiEdit.jar
c.将KawigiEdit设置为默认的编辑器，将Default复选框打勾
【算法分析】
以(x0,y0)为起点向x轴正方向作一水平射线，如果中间穿过奇数个多边形上的点，应该是在多边形内，否则应该是在多边形外。
但是有不少特殊情况。
WA了好多次，找了下资料，原来遵循下面几个原则即可：
1对于多边形的水平边不作考虑；
2对于多边形的顶点和L相交的情况，如果该顶点是其所属的边上纵坐标较大的顶点，则计数，否则忽略；
3对于P在多边形边上的情形，直接可判断P属于多边形
【CODE】http://xiudaima.appspot.com/code/detail/3434005