Daily Archives: 14 11 月, 2012

POJ 1961(KMP前缀最长重复子串）

Posted on by
Language:
Period
Time Limit: 3000MS   Memory Limit: 30000K
Total Submissions: 10179   Accepted: 4662

Description

求一个字符串中，所有循环节大于2的子串。

Input

有若干组数据，
每组数据第一行为字符串长度，第二行为字符串
以0结束。

Output

对于每组数据，输出'Test case #i",i从0开始，之后每行输出两个数，分别表示前缀长度和循环节数（>1).
每组数据后输出一个空行。

Sample Input

3
aaa
12
aabaabaabaab
0

Sample Output

Test case #1
2 2
3 3

Test case #2
2 2
6 2
9 3
12 4

Source

Southeastern Europe 2004

这题就是KMP问题。

还是Next，

先做不判重复优化的处理

观察发现若前面有循环节，则有i->i-p->i-2p...->i-kp=1

则i-next[i]表示循环结长度p，显然有p|（i-1),(i-1) div p>1.

如下:



Program Poj1961;
const
   maxn=10000000;
var
   i,j,tt,n,duan_luo:longint;
   next:array[1..maxn] of longint;
   a:ansistring;
begin
   tt:=1;
   while (true) do
   begin
      readln(n);
      if n=0 then break;
      readln(a);  inc(n); a:=a+'.';
      i:=1;j:=0;next[1]:=0;
      while (i<=n-1) do
      begin
         if (j=0) or (a[i]=a[j]) then
         begin
             inc(i);inc(j);
           //  if (a[i]<>a[j]) then next[i]:=j else next[i]:=next[j];
             next[i]:=j;
         end
         else j:=next[j];
      end;

      writeln('Test case #',tt);

      for i:=2 to n do
      begin
         duan_luo:=i-next[i];
         if (duan_luo>0) and ((i-1) mod duan_luo=0) and ((i-1) div duan_luo>1) then
            writeln(i-1,' ',(i-1) div duan_luo);



      end;

//    readln;
      writeln;
      inc(tt);
   end;

end.


POJ 3080(最长公共子串）

Posted on by
Language:
Blue Jeans
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 8767   Accepted: 3688

Description

给出若干个基因串（由'A','T','S','C'构成），请找出最长公共子串。

Input

第一行为数据数。
对每组数据：第一行为字符串的个数m(2 <= m <= 10)
                        之后m行，每行一个基因串（有且仅有60个字母）

Output

对每组数据，找出最长公共子串，如果长度小于3，请输出 "no significant commonalities" ，否则输出最长的字符串，若有多个答案，输出字典序最小的。

Sample Input

3
2
GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
3
GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA
GATACTAGATACTAGATACTAGATACTAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA
GATACCAGATACCAGATACCAGATACCAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA
3
CATCATCATCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
ACATCATCATAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AACATCATCATTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

Sample Output

no significant commonalities
AGATAC
CATCATCAT

Source

South Central USA 2006

枚举字符串更新答案，用kmp算法进行匹配。


Program BlueJeans;
const
   maxn=60;
   maxm=10;
var
   tt,i,j,k,n,m:longint;
   a:array[1..maxm] of string;
   next:array[1..maxn] of longint;
   p,ans:string;
   flag:boolean;

function kmp(a,s:string):boolean;
var
   i,j,n:longint;
begin
   n:=length(a);

   j:=0; next[1]:=0; i:=1;
   while i<n do
   begin
      if (j=0) or (a[i]=a[j]) then
      begin
         inc(i); inc(j);
         if (a[i]<>a[j]) then next[i]:=j else next[i]:=next[j];
      end else j:=next[j];
   end;

   j:=0; i:=0;
   while (i<=maxn) and (j<=n) do
   begin
      if (j=0) or (a[j]=s[i]) then
      begin
         inc(i); inc(j);
  //       if (j=n) then exit(true);
      end else j:=next[j];
   end;

   if j>n then exit(true);
   exit(false);


end;
function compare(a,b:string):boolean;
var
   i,n,m:longint;
begin
   n:=length(a); m:=length(b);
   if (n<>m) then exit(n<m);
   for i:=1 to n do if (a[i]<>b[i]) then exit(ord(a[i])>ord(b[i]));
   exit(false);
end;
begin
   readln(tt);
   while (tt>0) do
   begin
      ans:='';
      readln(m);
      for i:=1 to m do readln(a[i]);

      for i:=1 to maxn do
         for j:=i to maxn do
         begin
            p:=copy(a[1],i,j-i+1);
            flag:=false;
            for k:=2 to m do
            begin
               if not(kmp(p,a[k])) then begin flag:=true; break; end;
            end;
            if not(flag) and (compare(ans,p)) then ans:=p;
         end;

      if length(ans)<3 then writeln('no significant commonalities')
      else writeln(ans);




      dec(tt);
   end;
end.

POJ 2752(不满足P[i]<>P[next[i]] 的next函数）

Posted on by
Language:
Seek the Name, Seek the Fame
Time Limit: 2000MS   Memory Limit: 65536K
Total Submissions: 8682   Accepted: 4112

Description

给定一个字符串P，求它所有的满足P[1..i]到P[n-i+1..n]的i.

Input

数据有若干行
每行为一组数据P,1 <= Length of P <= 400000. 

Output

每行一组数据，按数字升序输出所有的i. 

Sample Input

ababcababababcabab
aaaaa

Sample Output

2 4 9 18
1 2 3 4 5

Source

POJ Monthly--2006.01.22,Zeyuan Zhu


要考虑KMP中Next函数的性质-P[next[i]]<>P[i]

如果这个条件不满足呢？

先在字符串后插入一个'.'，表示'.'前的循环，这样就能规避这一点（因为‘.’不会与任何字母重合）

再把后面那个if从句删掉(它只能跳过一些-非全部的-P[next[i]]<>P[i]的情况，因为.后面可能出现两次'a'

这样就可以了，最后把答案（由于不考虑a[i],只考虑前面循环节的长度，故-1）


Program SeekName;
const
    maxn=400000;
var
   n,i,j,size:longint;
   a:ansistring;
   ans,next:array[1..maxn] of longint;

begin
   while not seekeof do
   begin
      readln(a); a:=a+'.';
      n:=length(a);
      j:=0;next[1]:=0;i:=1;
      while (i<n) do
      begin
         if (j=0) or (a[i]=a[j]) then
         begin
            inc(i);
            inc(j);
         //   if (a[i]<>a[j]) then next[i]:=j else next[i]:=next[j];
            next[i]:=j;
         end else j:=next[j];
      end;
      size:=0; j:=n;
      repeat
         inc(size);
         ans[size]:=j-1;
         j:=next[j];
      until j<=1;


      write(ans[size]);
      for i:=size-1 downto 1 do write(' ',ans[i]);
      writeln;



   end;

end.


POJ 3468(成段更新）

Posted on by
Language:
线段树的成段更新
Time Limit: 5000MS   Memory Limit: 131072K
Total Submissions: 38010   Accepted: 11017
Case Time Limit: 2000MS

Description

对于数列 A1, A2, ... , AN. 你要进行2个操作：将一个区间的数同加上某个数，输出一段区间的和。

Input

第一行2个整数表示数列长度和操作次数. 1 ≤ N,Q ≤ 100000.
第二行为数列 A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.
接下来的Q行操作：
"C a b c" 表示将 Aa, Aa+1, ... , Ab.加上c. -10000 ≤ c ≤ 10000.
"Q a b" 输出区间[a,b]的和。

Output

输出所有询问的答案，每行1个。

Sample Input

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

Sample Output

4
55
9
15

Hint

longint会爆的。

Source

POJ Monthly--2007.11.25, Yang Yi



显然这题是线段树。

但是我之前习惯的nowl和nowr似乎太费解了（以致于我自己都要想半天）

回去看看其它人咋写……


Program poj3468;
const
   maxn=100000;
   maxq=100000;
var
   n,m,i,j,k:longint;
   lazy,t:array[1..maxn*8] of int64;
   c:char;
Procedure pushup(root:longint);
begin
   t[root]:=t[root*2]+t[root*2+1];
end;
Procedure build(l,r,root:longint);
var
   m:longint;
begin
   if (l=r) then
   begin
      read(t[root]);
      exit;
   end;
   m:=(l+r) shr 1;
   build(l,m,root*2);
   build(m+1,r,root*2+1);
   pushup(root);
end;
Procedure Pushdown(l,r,root:longint);
var
   m:longint;
begin
   m:=(l+r) shr 1;
   if (lazy[root]=0) then exit;
   inc(lazy[root shl 1],lazy[root]);
   inc(lazy[root shl 1+1],lazy[root]);
   inc(t[root shl 1],lazy[root]*(m-l+1));
   inc(t[root shl 1+1],lazy[root]*(r-(m+1)+1));

   lazy[root]:=0;
end;
Procedure update(l,r,nowl,nowr,root,cost:longint);
var
   m:longint;
begin
   if (l<=nowl) and (nowr<=r) then
   begin
      inc(lazy[root],cost);
      inc(t[root],(nowr-nowl+1)*cost);
      exit;
   end;
   pushdown(nowl,nowr,root);
   m:=(nowl+nowr) shr 1;
   if (l<=m) then update(l,r,nowl,m,root*2,cost);
   if (m+1<=r) then update(l,r,m+1,nowr,root*2+1,cost);
   pushup(root);
end;
function query(l,r,nowl,nowr,root:longint):int64;
var
   m:longint;
   res:int64;
begin
   if (l<=nowl) and (nowr<=r) then
   begin
      exit(t[root]);
   end;
   pushdown(nowl,nowr,root);
   m:=(nowl+nowr) shr 1;
   res:=0;
   if (l<=m) then res:=res+query(l,r,nowl,m,root*2);
   if (m+1<=r) then res:=res+query(l,r,m+1,nowr,root*2+1);
   exit(res);
end;


begin
   readln(n,m);
   fillchar(lazy,sizeof(lazy),0);
   build(1,n,1);
   readln;
   while (m>0) do
   begin
      read(c);
      if c='Q' then
      begin
         readln(i,j);
         writeln(query(i,j,1,n,1));
      end
      else
      begin
         readln(i,j,k);
         update(i,j,1,n,1,k);
      end;



      dec(m);
   end;
end.

接下来再来说说zkw线段树的解法：

这涉及到原数组A，差分数组A‘，差分数组前缀前缀和A''：

首先，它们3者满足如下关系：
1.差分数组的前缀和SA[i]'为原数组A[i](定义)。
2.原数组的前缀和SA[I]为差分数组的前缀前缀和A''[i];


接下来我们分别建立A‘和(i*A')的{单点修改，区间求和}线段树
显然要想知道

A[i]+A[i+1]+....A[ j ]
     =SA[ j ]-SA[ i -1]
     =A''[ j  ] - A'' [ i-1 ]
     =(SA'[1] +SA'[2]+...SA''[ j ] )- (SA'[1] +SA'[2]+...SA''[ i-1 ] )
     ={ j *A'[1] +(j-1)'A'[2]+....A'[ j ]}-{ (i-1) *A'[1] +(i-2)'A'[2]+....A'[ i-1 ]  }
     ={  (j+1)*(A'[1]+A'[2]+...A'[ j ] )-(1*A'[1]+2*A'[2]+...j*A'[ j ]  }  -  {   i*(A'[1]+A'[2]+...A'[ i-1 ] )-(1*A'[1]+2*A'[2]+...(i-1)*A'[ i-1 ]  }

这个方程如果看起来乱的话就直接看上面的图A''(相当于原数组前缀和SA-请想办法表示成A‘的累加形式）

显然如果将一个区间[A,B]+V,对3个数组影响如下：


幸运的是，我们只要维护A‘和{i*A’}
A和A‘’都要折腾一段区间，只有A'只要修改头和(尾+1)（如果存在）

那么{i*A‘} 的 维护 也只要修改2个节点 （请注意每个A‘ 实际上是独立的），同上：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (100000+10)
#define MAXAi (1000000000)
#define MAXCi (10000)
__int64 a[MAXN];
int n,q;
char c[10];
class SegMentTree
{
public:
	int M;
	__int64 t[MAXN*10];
	void fillchar()
	{
		M=1;while (M-2<n) M<<=1;
		memset(t,0,sizeof(t));
	}
	__int64 h(__int64 x,__int64 y)
	{
		return x+y;
	}
	void update(int x,__int64 c)
	{
		for (x>>=1;x;x>>=1) t[x]=t[x]+c;
	}
	void insert(int x,__int64 c)
	{
		x+=M;
		t[x]+=c;
		update(x,c);
	}
	__int64 find(int l,int r)
	{
		l=l-1+M;r=r+1+M;
		__int64 ans=0;
		while (l^r^1)
		{
			if (~l&1) {ans+=t[l+1];/* cout<<l+1<<' ';*/}
			if (r&1)  {ans+=t[r-1];/* cout<<r-1<<' ';*/}
			l>>=1;r>>=1;
		}
//		cout<<ans<<' ';
		return ans;
	}
	/*
	void print()
	{
		for (int i=1;i<=M*2;i++) if (t[i]!=0) cout<<i<<':'<<t[i]<<' ';
		cout<<endl;
	}
	*/

}t_ai,t_iai;
int main()
{
//	freopen("Poj3468.in","r",stdin);
	scanf("%d%d",&n,&q);t_ai.fillchar();t_iai.fillchar();
	a[0]=0;for (int i=1;i<=n;i++) scanf("%I64d",&a[i]);
	for (int i=1;i<=n;i++)
	{
		t_ai.insert(i,a[i]-a[i-1]);
		t_iai.insert(i,i*(a[i]-a[i-1]));
	}
	for (int i=1;i<=q;i++)
	{
		scanf("%s",c);
		if (c[0]=='Q')
		{
			int p1,p2;
			scanf("%d%d",&p1,&p2);p1--;
			__int64 ans1=(p1>0)?(__int64)(t_ai.find(1,p1)*(__int64)((__int64)p1+1)-(__int64)t_iai.find(1,p1)):0;//cout<<ans1<<endl;
			__int64 ans2=(__int64)t_ai.find(1,p2)*(__int64)(p2+1)-(__int64)t_iai.find(1,p2);//cout<<ans2<<endl;
			cout<<(__int64)(ans2-ans1)<<endl;
		}
		else
		{
			int l,r;
			__int64 c;
			scanf("%d%d%I64d",&l,&r,&c);
			t_ai.insert(l,(__int64)c);
			t_iai.insert(l,(__int64)c*l);
			if (r<n)
			{
				t_ai.insert(r+1,-(__int64)c);
				t_iai.insert(r+1,-(__int64)c*(__int64)(r+1));
			}
		}
//		t_ai.print();
//		t_iai.print();
	}


	return 0;
}