洛谷9月月赛2

t1

题意：懒得说了

分析：模拟

代码：

program flag;var  a:array[0..51,0..51]of char;  n,i,m,j,x,y,ans,k:longint;begin  assign(input,'flag.in');reset(input);assign(output,'flag.out');rewrite(output);  readln(n,m);  for i:=1 to n do begin   for j:=1 to m do     read(a[i,j]);  readln;  end;  k:=maxlongint;  for i:=1 to n-2 do   for j:=i+2 to n do    begin      ans:=0;      for x:=1 to i do       for y:=1 to m do        if a[x,y]<>'W' then inc(ans);      for x:=i+1 to j-1 do       for y:=1 to m do        if a[x,y]<>'B' then inc(ans);      for x:=j to n do       for y:=1 to m do        if a[x,y]<>'R' then inc(ans);      if ans

 t2

题意：无向无权图中，有k个点是禁止点，不可经过，与禁止点距离不超过s的点是危险点，可以经过，通过普通点花费为p，通过危险点花费为q，求1到n最小花费。

分析：；将0对所有禁止点，以0为起点建边跑最短路，凡是距离<=s+1的且不是禁止点的点标记为危险点，然后以1为起点跑最短路，花费为各点权值，注意最后一个点不交费，要在输出时减去在该点的花费（有两种情况，终点为危险点或普通点），记得用int64，另外dis初值要设很大。

program run;type  point=^node;   node=record     x:longint; next:point;   end;var  a:array[0..100000]of point;  q:array[0..300000]of longint;  dis,mk:array[0..100000]of int64;  g:array[0..100000]of boolean;  n,m,k,maxs,ppp,qqq,x,y:int64;  i:longint;procedure add(x,y:longint);var p:point;begin  new(p); p^.x:=y; p^.next:=a[x]; a[x]:=p;end;procedure spfa(s:longint);var h,t,x,y,cost:int64; i:longint; p:point;begin  for i:=0 to n do dis[i]:=maxlongint*10000;  for i:=0 to n do g[i]:=false;  h:=0; t:=1; q[1]:=s; g[s]:=true; dis[s]:=0;  while h
      
       =300000 then h:=0;     while p<>nil do      begin        y:=p^.x;        if not((s=1)and(mk[y]=2)) then        begin         if s=0 then cost:=1;         if s=1 then          if mk[y]=0 then cost:=ppp else cost:=qqq;         if dis[x]+cost
       
        =300000 then t:=0;             end;          end;        end;        p:=p^.next;      end;   end;end;begin  readln(n,m,k,maxs); readln(ppp,qqq);  for i:=1 to k do   begin     readln(x); mk[x]:=2; add(0,x);   end;  for i:=1 to m do   begin     readln(x,y); add(x,y); add(y,x);   end;  spfa(0);  for i:=0 to n do   if dis[i]<=maxs+1 then begin    if mk[i]<2 then mk[i]:=1;   end;  spfa(1);  if n=1 then writeln(0) else  if mk[n]=0 then writeln(int64(dis[n]-ppp)) else writeln(int64(dis[n]-qqq));end.
       
      

 t3

题意：给出一段行走命令，机器人连续执行k次，每走一次放一个标记，求四角被标记的正方形个数。

分析：有一个乱搞方法是走4次找出被标记的个数然后得到k次的，正解懒得写了。