【题目大意】
给定两个串，让你求满足A[i..i+k]=B[j..j+k]且k>=K的(i,j)的数目。
【算法分析】
先把两个串连在一起，中间加一个特殊字符。
然后建立后缀数组和height数组。
最后对height进行线性分组，同组的height都>=K
然后注意到我们需要统计的是每一个点对(i,j)其中i为A串的后缀，j为B串的后缀，他们的lcp(i,j)-limit+1，然后加起来。但是我们注意到越向后延伸，对于同一个点的lcp只会单调递减，然后用一个栈合并lcp已经被并为同一个数字的区间，最后输出就可以。
【其它】3WA，s1和s2忘记搞成long long了。。。
表示紧紧跟随lcc的脚步。。。
【CODE】
#include 【题目】 http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1010 【算法分析】 好不容易终于看懂了，我还是链接一下算了。。。 http://www.byvoid.com/blog/noi-2009-poet/ 模仿他的解法三即可。。。 【CODE】 #include void init(){ double xl(int i,int j){ void work(){ int main(){ 【题目大意】 求所有对于同一字符串的前缀和后缀相等的位置。 【算法分析】 KMP，然后一直从n一直next回去，路上的都是。 为什么呢？ 首先从在n的第一次next是找最长的S[1,K]=S[n-K+1,n] 这个容易理解。 然后接下来的next是求最长的S[1,K]=S[J-K+1,J] 注意了，这个S[J-K+1,J]必然与S[n-K+1,n]相等。（可以用数学归纳法证明一下） 于是对应下一个前缀等于后缀的位置。 所以，这样一直下去就会找到所有的前缀等于后缀的位置。 【其它】1A http://hi.baidu.com/aekdycoin/blog/item/fbe5a03233bd1648ad4b5f1c.html 紧紧跟随师傅的脚步。 【CODE】 #include int next[500000],n,ans[500000],ansl; int main(){ 这次月赛终于不是一个人单挑了。 CWJ&&FHN&&CZM组成了一队。 然后说说比赛经历： 一开始12点开始，FHN和CZM都没在。。。于是我开了第一题。 写了一会儿，好像很繁琐，然后FHN和CZM陆续回来了。 然后FHN一下就把最后一题秒了，YM。。。 然后我碌碌无为，第一题没搞定，跳过。 看第2题，一看出题人，AekdyCoin，是师傅那题防AK的题目，于是再次跳过。 第三题，看着是个最大独立集问题。但是好像是任意图的。百度一下，发现MS是NP问题？跳过。。 然后CZM大概浏览了题目，告诉我第四题是字符串，让我去做。于是我一看，KMP，1A。 然后CZM和FHN看后面的题目，发现都挺神，于是他们把目光聚焦在那题比较多人AC的题目上，然后CZM一个犀利的背包把它搞定了。 然后FHN出去买电脑 剩下我和CZM，然后我表示第一题突然有了想法，线段树，因为long long WA了两次，终于AC。期间肥闽各种看题目，不过MS没什么结果。 然后我回看第三题，推了一些性质，然后交了个贪心，WA。。。CZM犀利地给了我一个反例。。。 最后我推出一个重要性质： ∵出题人戴牛 ∴必然可以网络流 于是尝试了各种二分图构图，终于WA了2次以后AC。 然后FHN回来了，和CZM一起在那里猜数字。。。 我去搞1009，发现应该是在AC自动机上的DP。但是空间好像卡着卡着。。。 纠结到剩下半小时，放弃，和他们一起猜数字。。。 然后得到的结论： 1、没有billion，million….and so on… 2、字符串长度14 然后我说：直接枚举吧，大不了(26+10+1)*14。。。 然后CZM就先去搞那个字符集，为我们枚举作为前提，后来很可惜，没有搞完，结束了。 一共就出了5题。。。。 其实和第一名的差距就是1009——AC自动机上的DP 以及 1005——猜数字。 猜数字其实想通了不难，但是一开始没有意识到是单case。。。 RANK：18 围观地址：http://acm.hdu.edu.cn/vip/contest_ranklist.php?cid=237&page=1 这次的猜数字，绝对NB，赞一个，不过在OI的话没法出。 这次GDKOI总的来说比较遗憾，但是也不算太差。。。 给AekdyCoin师傅丢脸了。。。 首先说下题目类型（后面的是题目分值）： Day1 1：Floyed——30分 2：基于连通性的状态压缩动态规划——40分 3：找循环节，然后比较繁琐的处理——40分 4：IMBA的压轴题，构造简单割处理，转化比较牛B，很可惜居然这题是上一年winter camp上的原题，而且当时的出题人也在参加比赛。。。无语——40分 Day2 1：直接积分 or 利用导数求出单调性，发现是单峰函数，可以二分 or 直接推导出答案O(1)，总的来说是数学题——30分 2：简单的DP——40分 3：双向BFS——40分 4：平衡树连边再处理。主要是这题我推不出那个边数必然为O（N）规模的这一结论。 我的情况： Day1： 1：AC 2：暴力DFS拿了90%的分数。。。 3：悲剧，怎么拍都有BUG，于是只拿30%分数。 4：被秒杀。。。55555555，被虐了，用了个状态压缩DP，拿了30%分数。 Day2： 1：AC 2：居然10分钟敲的DP写错了。。。我无语，直接丢32分。。。。 3：双向BFS写出来了，不过操作步数为0的情况没有特判，WA1个点。拿到36分。 4：居然暴力都写错，12分就这样没了。 假设是当前水平下，最好状态： Day1第3题过掉。+28分 Day2第2题DP写对。+32分 Day2第3题那个点拿掉。+4分 Day2第4题写对。+12分。 总共可以+76分，但是毕竟比赛不能说都能做出来，也算是这样了。。 最后并列第10，前面有两个是高三拿了NOI金牌回来FUN的。。。 总的来说比较遗憾，下次要减少这些SB失误唉。。。[HYBZ 1010]斜率优化的动态规划
using namespace std;
const int N=60000;
int n,L,head,tail,a[N],qp[N];
long long qf[N],f[N],sum[N];
scanf("%d%d",&n,&L);
for (int i=1;i<=n;i++){
scanf("%d",&a[i]);
a[i]++;
}
sum[0]=0;
for (int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
}
return (f[j]+sqr(sum[j])-f[i]-sqr(sum[i]))/(sum[j]-sum[i]);
}
f[0]=0;
int head=1, tail=1;
qf[1]=0; qp[1]=0;
for (int i=1;i<=n;i++){
while (head
f[i]=f[j]+sqr(sum[i]-sum[j]-1-L);
while (head
qp[tail]=i;
qf[tail]=f[i];
}
cout << f[n] << endl;
}
init();
work();
}[POJ 2752]KMP**
char s[500000];
int i,j;
while (scanf("%sn",&s[1])!=EOF){
n=strlen(s+1);
next[1]=0;
j=0;
for (i=2;i<=n;i++){
while (j && s[j+1]!=s[i]) j=next[j];
if (s[j+1]==s[i]) j++;
next[i]=j;
}
ansl=1; ans[1]=n;
j=n;
while (1){
if (next[j]==0) break;
j=next[j];
ans[++ansl]=j;
}
for (i=ansl;i>=1;i–){
printf("%d",ans[i]);
if (i!=1) printf(" ");
}
printf("n");
}
}HDU月赛——2010.3.6
GDKOI之旅