SD多校模拟赛Day1&Day2

      390分33名，淄博市3个参赛的我最弱。第一点还是注意细节，zzm神犇没有fill啊，我number O(k^2N)的贪心只有50分啊这些，但是会做的3道题都A了这个让我很高兴。第二学会骗分，zzm神犇ancestor写挂链hash就比裸的多20分，lock DFS-ID搞小数据，大数据输出了一个数。number在对拍的时候发现可以A的规律，这些都是很好的技巧。所以300分很容易，400分也不难。骗分认真搞搞，暴力能上500，囧。但是世上哪里有那么多如果呢。（引自萌原）。

A 枚举直径，弧长等于半径一半。

program rect;

var len,n,i,j,k,l,ans:longint;

    a,sum:array[0..30] of longint;

begin

readln(n);ans:=0;

for i:=1 to n do readln(A[i+1]);

for i:=1 to n do sum[i]:=sum[i-1]+A[i];

len:=sum[n]+A[n+1];

for i:=1 to n do

  begin

  j:=i+1;

  while(j<=n)and((sum[j]-sum[i])<<1<>len)do inc(j);

  if j>n then continue;

  for k:=i+1 to j-1 do

    begin

    l:=j+1;

    while(l<=n)and((sum[l]-sum[k])<<1<>len)do inc(l);

    if l>n then continue;

    inc(ans);//writeln(i:5,j:5,k:5,l:5);

    end;

  end;

writeln(ans);

end.




B 裸DFS+卡时。期望30分。正解是DP，难点在于处理处G[l][r][c](l从到r的一段能合并成字母c)，g[l][r][a[i]]:=true(存在g[l][k][b[i]] and g[k+1][r][c[i]]=true)，通过G可以去搞F，F[i]=min{F[j]}+1(存在c，G[j+1][i][c]=true)。
program ancestor;

uses math;

const FileName='ancestor';

var  a,b,c:array[0..50] of char;

     f:array[0..50] of integer;

     g:array[0..50,0..50,'a'..'z'] of boolean;

     m,n,i,j,k,l,r:longint;

     ch,ch1,ch2:char;

begin

fillword(f,sizeof(f)>>1,32767);f[0]:=0;

fillchar(g,sizeof(g),false);m:=0;

//input

read(ch);

while ch1 in['a'..'z'] do begin

  inc(m);g[m][m][ch]:=true;

  read(ch);end;

readln(n);

for i:=1 to n do

  readln(A[i],ch1,ch2,b[i],c[i]);

//--calc g--

for r:=1 to m do

  for l:=r-1 downto 1 do

     for i:=1 to n do

        for k:=l to r do begin

         g[l][r][a[i]]:=(g[l][k][b[i]] and g[k+1][r][c[i]])or g[l][r][a[i]];

         if g[l][r][a[i]] then break;

         end;

//--DP--

for i:=1 to m do

  for j:=0 to i-1 do

    for ch:='a' to 'z' do

      if g[j+1][i][ch]

        then f[i]:=min(f[j]+1,f[i]);

writeln(f[m]);

end.




C 二分答案+SPFA验证。遇到加油站dis[u]赋值为0，还有保证dis[i]<=limt


zzm神犇由于C题多组数据邻接表表头没有清空可能会坑。我没敢仔细看。很后悔没自己出数据。总是太相信样例。第一题可以出N个1啊，第二题算了，第三题可以出个环啊链啊的。
program f1;

const FileName='f1';

      maxn=100000+100;

      maxm=150000*2+100;

      inf=maxlongint div 2;

var tot,t:longint;

    ok,inq:array[0..maxn] of boolean;

    v,next:array[0..maxm+10] of longint;

    head,dis,Q:array[0..maxn] of longint;

procedure build(x,y:longint);

          begin

          inc(tot);

          v[tot]:=y;

          next[tot]:=head[x];

          head[x]:=tot;

          end;

function  SPFA(limt,s,e:longint):boolean;

          var h,t,i,u:longint;

          begin

          fillchar (InQ,sizeof(InQ),false);

          filldword(dis,sizeof(dis)>>2,inf);

          h:=0;t:=1;Q[1]:=s;dis[s]:=0;

          while h<>t do begin

            inc(h);if h>maxn then h:=0;

            u:=Q[h];i:=head[u];

            if ok[u] then dis[u]:=0;

            if dis[u]+1<=limt then

              begin

              while i<>0 do begin

                if dis[v[i]]>dis[u]+1

                  then begin

                       dis[v[i]]:=dis[u]+1;

                       if v[i]=e then exit(true);

                       if not InQ[v[i]]

                         then begin

                              inc(t);if t>maxn then t:=0;

                              Q[t]:=v[i];

                              end;

                       end;

                i:=next[i];end;

              end;end;

          if dis[e]<>inf then exit(true)

                         else exit(false);

          end;

procedure solve;

          var n,m,k,i,x,y,s,t,l,r,mid:longint;

          begin

          fillchar(ok,sizeof(ok),false);

          fillchar(head,sizeof(head),0);

          readln(n,m,k);tot:=0;

          for i:=1 to k do

            begin

            read(t);

            ok[t]:=true;

            end;

          for i:=1 to m do

            begin

            readln(x,y);

            build(x,y);

            build(y,x);

            end;

          readln(s,t);

          if s=t then begin writeln(0);exit;end;

          if not SPFA(M,s,t)

            then writeln(-1)

            else begin

                 if SPFA(1,s,t) then

                   begin writeln(1);exit;end;

                 l:=1;r:=M;

                 while l<r-1 do begin

                   mid:=(l+r)>>1;

                   if SPFA(mid,s,t)

                     then r:=mid

                     else l:=mid;

                   end;

                 writeln(r);

                 end;

          end;

begin

readln(T);

while T>0 do

  begin

  solve;

  dec(T);

  end;

end.




D 暴力即可，我觉得字符串判断相等时O(N)的果断KMP了。结果人家枚举答案，然后生成所有字符串，两两比较的也A了。
program message;

type Tsrt=string[110];

const FileName='message';

var   t,s:Tsrt;

      fix,prefix:array[0..110] of longint;

      ans,n:longint;ch:char;

function  KMP(var s,t:Tsrt):boolean;

          var k,i,m,cnt:integer;

          begin

          k:=0;Prefix[1]:=0;

          m:=length(t);cnt:=0;

          for i:=2 to m do begin

            while(k>0)and(T[k+1]<>T[i])do k:=Prefix[k];

            if T[k+1]=T[i] then inc(k);

            Prefix[i]:=k;end;k:=0;

          for i:=1 to n do begin

            while(k>0)and(T[k+1]<>S[i])do k:=Prefix[k];

            if T[k+1]=S[i] then inc(k);

            fix[i]:=k;

            if k=m then k:=prefix[m];

            end;

          for i:=1 to N do

            if fix[i]>=m then

              inc(cnt);

          if cnt>=2 then exit(true)

                    else exit(false);

          end;

function  check(len:longint):boolean;

          var j,i,m:longint;

          begin m:=n-len+1;

          for i:=1 to m do

            begin

            t:=copy(s,i,len);

            if KMP(s,t)

              then exit(false);

            end;

          exit(true);

          end;

begin

s:='';read(ch);

while ch in['a'..'z'] do

  begin

  s:=s+ch;

  read(ch);

  end;

n:=length(s);ans:=n;

while(ans>=1)and(check(ans))do dec(ans);

writeln(ans);

end.



E 乱贪了50分，还是应该多试一些例子，然后才能发现规律。
program number;

const FileName='number';maxn=200000;maxk=100;inf=maxlongint;

var   a,x,y,p:array[0..maxk] of int64;

      n:array[0..maxk] of longint;

      pos,j,count,i,minnum,pre,get,k,ans:longint;

begin

readln(k);

for i:=1 to k do

  begin

  readln(n[i],A[i],x[i],y[i],p[i]);

  inc(count,n[i]);

  end;

pos:=1;

for i:=2 to k do

  if A[i]<A[pos]

    then pos:=i;

dec(n[pos]);get:=1;pre:=A[pos];

if n[pos]>0 then 

  A[pos]:=(A[pos]*x[pos]+y[pos])mod p[pos];

while get<count do begin

  minnum:=inf;

  for i:=1 to k do

    if(n[i]>0)and

      (A[i]>pre)and

      (A[i]<minnum)

      then begin

           minnum:=A[i];

           pos:=i;

           end;

  if minnum<>inf

    then begin

         inc(get);

         pre:=A[pos];

         dec(n[pos]);

         if n[pos]>0 then 

           A[pos]:=(A[pos]*x[pos]+y[pos])mod p[pos];

         end

    else begin

         for i:=1 to k do

           if(n[i]>0)and

             (A[i]<minnum)

              then begin

              minnum:=A[i];

              pos:=i;

              end;

         inc(get);inc(ans);

         pre:=A[pos];

         dec(n[pos]);

         if n[pos]>0 then 

           A[pos]:=(A[pos]*x[pos]+y[pos])mod p[pos];

         end;

  end;

writeln(ans);

end.



E 为了理解标程花了好长好长时间。把每一段抽象成点处理，用这一段的最后一个点代表这一段，BFS预处理出把某个区间取反的代价，然后对新序列处理，新序列一定是关开关开……关开，然后记忆化搜索，每次找个区间搞。感觉很巧妙，还是有种不是十分理解的感觉。



        

	      

	    

	  

	  

	    
      
        【推广】
        免费学中医，健康全家人
      
	  

    

    

          原文地址：https://www.cnblogs.com/lijianlin1995/p/2756197.html