【题目链接】http://www.codeforces.com/problemset/problem/3/B
【题目大意】
给定一个容量为v<=10^9的背包和n<=10^5个物品。
每个物品有一个体积(1<=ti<=2)和价值(1<=pi<=10^4)。
每个物品只能装一次，问最多能装多少价值的东西。
【算法分析】
一开始看的时候2了一下。。。还想到把体积为1的和成体积为2的然后根据奇偶性讨论一下。
然后后来重新一想发现实在太2了。
就是把体积为1和体积为2的放进两个数组里面，然后按价值从大到小排序。
然后用两个指针利用单调性维护可以很容易得出当取i个体积为1的物品时，答案最大能是多少。
于是就解决了。
【其它】
用桶排可以做到总复杂度O(n)
【CODE】
http://xiudaima.appspot.com/code/detail/4348006
【题目链接】http://acm.hdu.edu.cn/showproblem.php?pid=3664
【题目大意】
输入n和k。
输出n的所有排列里有多少个是Ai>i的数量等于k的。
【算法分析】
递推。
F[n,k]表示对应答案。
然后F[n,k]=F[n-1,k]*(k+1)+F[n-1,k-1]*((n-1) – (k-1))
本质是现在多一个数字n，也多了一个位置An。
从F[n-1,k]那里继承过来的是用n去填那些已经满足Ai>i的位置，因为现在n是最大的，所以填进去以后肯定也是满足Ai>i的，然后原本对应位置的数字就填到An上。因为可以填本身An这个位置，所以系数+1。
从F[n-1,k-1]那里继承过来的是用n去和前面那些满足Ai<=i的位置上的数交换，因为现在n是最大的，所以填了以后显然满足Ai>i。
【Hint】
必须打表才能过。
【CODE】
【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=2105
【题目大意】
给定一个串，你可以对它进行修改插入删除等操作。
然后有一种询问操作，LCP(i,j)表示求S[i..n]和S[j..n]的最长公共前缀。
总操作数<=10^5
但是各种修改字符串的操作总数<=5000
10^5-5000=95000，几乎全是询问操作。。。
【算法分析】
众所周知、判断字符串是否相等可以利用hash来达到很高的正确率。
然后经过询问某牛，无符号整数爆了相当于Mod。有符号之间爆好像是未定义什么的。于是一般都是用无符号整数。
然后既然是相当于Mod，所以利用* + -的hash函数对于一个相同的字符串，无论计算的次序如何都是会相等的。
于是简单地把hash值定为S[1]*p^n+S[2]*p^(n-1)+S[3]*p^(n-2)….
p就随便取个素数什么的。比如13、131~
然后对于求LCP，有一个二分答案然后判断是否相同的想法。
那么，我们需要快速知道某个区间的hash值。
区间问题、比较经典的有ST表和线段树这种。
1、ST表，因为每次修改都要重建，所以我把这个想法抹杀了，实际上本题是CQF《New Lcp》里面的原题。就是利用ST表的思想。而且确实每次修改以后都以O(n)的复杂度重建。。。当然他论文后面还有个利用平衡常数的常数优化。
2、由于本题长短会变，所以用平衡树取代线段树。然后现在相当于维护一个线性表。所以Splay是比较好的选择。另外区间的处理上Splay也比较方便。
【结果】
一看题目就想到第二种算法。敲出来以后干脆地TLE了。
每次修改的时间复杂度是O(lg n)
每次询问的时间复杂度是O(lg^2 n)
本题的特殊性在于询问很多，修改很少。
而ST表的时间复杂度
修改O(n)
询问O(lg n)
然后我这沙茶就悲剧了= =。
其实如果把修改弄多一点，我觉得我这个算法还是理论上不错的。就是常数比较大。
【CODE】
Splay+hash=TLE
经对拍，该代码无误。当然hash本身是有概率出错的。
【题目链接】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之。
、
、
、
、
、
恩，看来我一直以来通过看论文学习的习惯还是很好的，继续保持。