Models(Pascal)

KMP

var
    p,t:string;
    f:Array[0..255] of longint;
    m,n,i,j:longint;

procedure getfail;
begin
    f[1]:=1;f[2]:=1;
    for i:=2 to m do 
    begin
        j:=f[i];
        while (j>1)and(t[i]<>t[j])do j:=f[j];
        if t[i]=t[j] then f[i+1]:=j+1 else f[i+1]:=1;
    end;
end;
    
begin
    readln(p);
    readln(t);
    n:=length(p);
    m:=length(t);
    getfail;//for str T[]
    
    j:=1;
    for i:=1 to n do
    begin
        while (j>1)and(p[i]<>t[j]) do j:=f[j];
        if p[i]=t[j] then
        begin
            if j=m then writeln(i-m+1);
            inc(j);
        end;
    end;
end.

View Code

LCA

type
    point=^rec;
    rec=record
        data:longint;
        next:point;
    end;

const maxn=30000+100;

var
    d:array[0..maxn] of longint;
    p:array[0..maxn,0..20] of longint;
    map:array[0..maxn] of point;
    i,n,m,x,y,last,log,ans:longint;
    k:point;

procedure swap(var a,b:longint);
var t:longint;
begin
    t:=a;a:=b;b:=t;
end;

procedure dfs(u,fa:longint);
var k:point;
begin
    d[u]:=d[fa]+1;
    p[u,0]:=fa;
    log:=trunc(ln(n)/ln(2));
    for i:=1 to log do p[u,i]:=p[p[u,i-1],i-1];
    k:=map[u];
    while k<>nil do 
    begin
        if k^.data<>fa then dfs(k^.data,u);
        k:=k^.next;
    end;
end;

function lca(a,b:longint):longint;
var del,i:longint;
begin
    if d[a]>d[b] then swap(a,b);
    if d[a]<d[b] then
    begin
        del:=d[b]-d[a];
        log:=trunc(ln(d[b])/ln(2));
        for i:=log downto 0 do
            if (d[b]-(1 shl i))>=d[a] then b:=p[b,i];
    end;
    if a<>b then 
    begin
        log:=trunc(ln(d[b])/ln(2));
        for i:=log downto 0 do
            if p[a,i]<>p[b,i] then 
                begin
                    a:=p[a,i];b:=p[b,i];
                end;
        a:=p[a,0];b:=p[b,0];
    end;
    exit(a);
end;

begin
    readln(n);
    fillchar(d,sizeof(d),0);
    for i:=1 to n-1 do 
    begin
        readln(x,y);
        new(k);
        k^.data:=y;
        k^.next:=map[x];
        map[x]:=k;
        new(k);
        k^.data:=x;
        k^.next:=map[y];
        map[y]:=k;
    end;
    k:=map[1];
    while k<>nil do
    begin
        dfs(k^.data,1);
        k:=k^.next;
    end;
    readln(m);
    last:=1;
    for i:=1 to m do
    begin
        readln(x);
        inc(ans,d[x]+d[last]-2*d[lca(x,last)]);
        last:=x;
    end;
    writeln(ans);
end.

//codevs 2370

type
    point=^rec;
    rec=record
        data:longint;
        next:point;
    end;
    link=^reco;
    reco=record
        p,dis:longint;
        next:link;
    end;

const
    maxn=50000+10;

var
    d,dep:array[0..maxn]of longint;
    distance:array[0..maxn] of link;
    p:array[0..maxn,0..20]of longint;
    map:array[0..maxn] of point;
    n,m,i,x,y,ans,last,log,dis:longint;
    k:point;
    kk:link;

function get_dis(a,b:longint):longint;
var kk:link;
begin
    kk:=distance[a];
    while kk<>nil do 
    begin
        if kk^.p=b then exit(kk^.dis);
        kk:=kk^.next;
    end;
end;
    
procedure swap(var a,b:longint);
var t:longint;
begin
    t:=a;a:=b;b:=t;
end;

procedure dfs(u,fa:longint);
var k:point;
begin
    dep[u]:=get_dis(u,fa)+dep[fa];
    d[u]:=d[fa]+1;
    p[u,0]:=fa;
    log:=trunc(ln(n)/ln(2));
    for i:=1 to log do p[u,i]:=p[p[u,i-1],i-1];
    k:=map[u];
    while k<>nil do
    begin
        if k^.data<>fa then dfs(k^.data,u);
        k:=k^.next;
    end;
end;

function lca(a,b:longint):longint;
var del,i:longint;
begin
    if d[a]>d[b] then swap(a,b);
    if d[a]<d[b] then
    begin
        del:=d[b]-d[a];
        log:=trunc(ln(d[b])/ln(2));
        for i:=log downto 0 do 
            if (d[b]-(1 shl i))>=d[a] then b:=p[b,i];
    end;
    if a<>b then
        begin
        log:=trunc(ln(d[b])/ln(2));
        for i:=log downto 0 do
            if p[a,i]<>p[b,i] then
                begin
                    a:=p[a,i];b:=p[b,i];
                end;
                a:=p[a,0];b:=p[b,0];
    end;
    exit(a);
end;

begin
    fillchar(d,sizeof(d),0);
    readln(n);
    for i:=1 to n-1 do
    begin
        readln(x,y,dis);
        new(kk);
        kk^.p:=y;
        kk^.dis:=dis;
        kk^.next:=distance[x];
        distance[x]:=kk;
        new(kk);
        kk^.p:=x;
        kk^.dis:=dis;
        kk^.next:=distance[y];
        distance[y]:=kk;
        new(k);
        k^.data:=y;
        k^.next:=map[x];
        map[x]:=k;
        new(k);
        k^.data:=x;
        k^.next:=map[y];
        map[y]:=k;
    end;
    k:=map[1];
    while k<>nil do
    begin
        dfs(k^.data,1);
        k:=k^.next;
    end;
    readln(m);
    last:=1;
    for i:=1 to m do
    begin
        readln(x,y);
        writeln(dep[x]+dep[y]-2*dep[lca(x,y)]);
    end;
end.

View Code

并查集

var
  father:array[1..5000] of longint;
  i,j,k,p,n,m:longint;
   
function getfather(v:longint):longint;//寻找根节点
begin
  if father[v]=v then
    exit(v);
  father[v]:=getfather(father[v]);
  exit(father[v]);
end;
 
procedure merge(x,y:longint);//合并两集合
var
  xx,yy:longint;
begin
  xx:=getfather(x);
  yy:=getfather(y);
  father[xx]:=yy;
end;
 
function judge(x,y:longint):boolean;//判断是否在一集合中
var
  xx,yy:longint;
begin
  xx:=getfather(x);
  yy:=getfather(y);
  exit(xx=yy);
end;
begin
  readln(n,m,p);
  for i:=1 to n do
    father[i]:=i;
  for i:=1 to m do
    begin
      readln(j,k);
      merge(j,k);
    end;
  for i:=1 to p do
    begin
      readln(j,k);
      if judge(j,k) then
        writeln('Yes')
      else
        writeln('No');
    end;
end.

View Code

二分快速幂

var
    t,a,b,ans:qword;

begin
    readln(a,b);
    t:=a;
    ans:=1;
    while b>0 do 
    begin
        if odd(b) then ans:=ans*t;
        t:=t*t;
        b:=b div 2;
    end;
    writeln(ans);
end.

View Code

线段树

type
    node=^rec;
    rec=record
        l,r,sum,delta:int64;
        lc,rc:node;
    end;

var
    root:node;
    l,r,add,i,n,m,tmp:longint;
    
procedure build(now:node;l,r:longint);
begin
    now^.l:=l;now^.r:=r;
    if l=r then
    begin
        read(now^.sum);
        now^.lc:=nil;
        now^.rc:=nil;
        exit;
    end;
    new(now^.lc);
    new(now^.rc);
    build(now^.lc,l,(l+r)div 2);
    build(now^.rc,(l+r)div 2+1,r);
    now^.sum:=now^.lc^.sum+now^.rc^.sum;
end;

procedure update(now:node;l,r,add:int64);
begin
    if (l<=now^.l)and(now^.r<=r) then
    begin
        inc(now^.delta,add);
        exit;
    end;
    if l<=(now^.l+now^.r)div 2 then update(now^.lc,l,r,add);
    if r>(now^.l+now^.r)div 2 then update(now^.rc,l,r,add);
    now^.sum:=now^.lc^.sum+now^.lc^.delta*(now^.lc^.r-now^.lc^.l+1);
    inc(now^.sum,now^.rc^.sum+now^.rc^.delta*(now^.rc^.r-now^.rc^.l+1));
end;

function query(now:node;l,r:longint):int64;
var
    ret:int64;
begin
    if (l<=now^.l)and(now^.r<=r) then exit(now^.sum+now^.delta*(now^.r-now^.l+1));
    inc(now^.lc^.delta,now^.delta);
    inc(now^.rc^.delta,now^.delta);
    inc(now^.sum,now^.delta*(now^.r-now^.l+1));
    now^.delta:=0;
    ret:=0;
    if l<=(now^.l+now^.r)div 2 then inc(ret,query(now^.lc,l,r));
    if r>(now^.l+now^.r)div 2 then inc(ret,query(now^.rc,l,r));
    exit(ret);
end;

begin
    new(root);
    readln(n);
    build(root,1,n);
    readln(m);
    for i:=1 to m do 
    begin
        read(tmp);
        if tmp=1 then
        begin
            readln(l,r,add);
            update(root,l,r,add);
        end;
        if tmp=2 then
        begin
            readln(l,r);
            writeln(query(root,l,r));
        end;
    end;
end.

View Code

SPFA

const
 maxp=1000;
var
 p,c,s,t,head,tail:longint;
 a,b:array[0..maxp,0..maxp] of longint;
 d:array[0..maxp] of integer;
 v:array[0..maxp] of boolean;
 dist:array[0..maxp] of longint;
procedure init;
var
 i,x,y,z:longint;
begin
 readln(p,c);
 for i:=1 to c do begin
  readln(x,y,z);
  inc(b[x,0]); b[x,b[x,0]] := y; a[x,y] :=z;
 end;
 readln(s,t);
end;

procedure spfa(s:longint);
var
 i,j,now,sum:longint;
begin
 fillchar(d,sizeof(d),0);
 fillchar(v,sizeof(v),false);
 for j:=1 to p do dist[j]:=maxlongint;
 dist[s]:=0;v[s]:=true;d[1]:=s;
 head:=1;tail:=1;
 while head<=tail do begin
  now:=d[head];
  for i:=1 to b[now,0] do
   if dist[b[now,i]]>dist[now]+a[now,b[now,i]] then
   begin
    dist[b[now,i]]:= dist[now]+a[now,b[now,i]];
    if not v[b[now,i]] then begin
     inc(tail);
     d[tail]:=b[now,i];
     v[b[now,i]]:=true;
    end;


   end;inc(head);  v[now]:=false;
  end;
end;

begin
 init;
 spfa(s);
 writeln(dist[t]);
end.









type
  point=^rec;
  rec=record
    sum:longint;
    data:integer;
    next:point;
  end;
var
  i,n,m:longint;
  dist:array[0..10000]of longint;
  h:array[1..20000]of integer;
  v:array[1..10000]of boolean;
  a:array[0..10000]of point;
procedure init;
var
  i,z:longint;
  x,y:integer;
  k:point;
begin
  read(n,m);
  for i:=1 to m do
  begin
    new(k);
    readln(x,y,z);
    k^.data:=y;
    k^.sum:=z;
    k^.next:=a[x];
    a[x]:=k;
  end;
end;

procedure spfa(x:longint);
var
  front,rear,now,j:longint;
  i:point;
begin
  for j:=1 to n do dist[j]:=maxlongint;
  dist[x]:=0;front:=0;rear:=1;h[1]:=x;v[x]:=true;
  while front<rear do
  begin
    inc(front);
    now:=h[front];
    i:=a[now];
    while i<>nil do
    begin
      if dist[i^.data]>dist[now]+i^.sum then
      begin
        dist[i^.data]:=dist[now]+i^.sum;
        if not v[i^.data] then
        begin
          inc(rear);
          h[rear]:=i^.data;
          v[i^.data]:=true;
        end;
      end;
      i:=i^.next;
    end;
    v[now]:=false;
  end;
end;

begin
  init;
  spfa(1);
  writeln(dist[n]);
end.

var
    i,p,c,s,t:longint;
    a,b:array[0..1000,0..1000]of longint;
    v:array[0..1000] of boolean;
    q,dist:array[0..1000] of longint;
    
procedure init;
var x,y,z:longint;
begin
    fillchar(b,sizeof(b),0);
    readln(p,c);
    readln(s,t);
    for i:=1 to c do 
    begin
        readln(x,y,z);
        inc(b[x,0]);b[x,b[x,0]]:=y;
        a[x,y]:=z;
    end;
end;

procedure spfa;
var head,tail,now:longint;
begin
    head:=1;
    tail:=1;
    fillchar(v,sizeof(v),false);
    for i:=1 to p do dist[i]:=maxlongint;
    q[1]:=p;v[p]:=true;dist[p]:=0;
    while head<=tail do 
    begin
        now:=q[head];
        for i:=1 to b[now,0] do 
        begin
            if dist[b[now,i]]>dist[now]+a[now,b[now,i]] then
            begin
                dist[b[now,i]]:=dist[now]+a[now,b[now,i]];
                if not v[b[now,i]] then
                begin
                    v[b[now,i]]:=true;
                    inc(tail);
                    q[tail]:=b[now,i];
                end;
            end;
        end;
        inc(head);v[now]:=false;
    end;
    
end;

begin
    init;
    spfa;
    writeln(dist[t]);
end.

View Code