洛谷9月月赛2
t1
题意：懒得说了
分析：模拟
代码：
program flag;
var
a:array[..,..]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:= to n do begin
for j:= to m do
read(a[i,j]); readln;
end;
k:=maxlongint;
for i:= to n- do
for j:=i+ to n do
begin
ans:=;
for x:= to i do
for y:= to m do
if a[x,y]<>'W' then inc(ans);
for x:=i+ to j- do
for y:= to m do
if a[x,y]<>'B' then inc(ans);
for x:=j to n do
for y:= to m do
if a[x,y]<>'R' then inc(ans);
if ans<k then k:=ans;
end;
writeln(k);
close(input); close(output);
end.
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[..]of point;
q:array[..]of longint;
dis,mk:array[..]of int64;
g:array[..]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:= to n do dis[i]:=maxlongint*;
for i:= to n do g[i]:=false;
h:=; t:=; q[]:=s; g[s]:=true; dis[s]:=;
while h<t do
begin
inc(h); x:=q[h]; new(p); p:=a[x]; g[x]:=false;
if h>= then h:=;
while p<>nil do
begin
y:=p^.x;
if not((s=)and(mk[y]=)) then
begin
if s= then cost:=;
if s= then
if mk[y]= then cost:=ppp else cost:=qqq;
if dis[x]+cost<dis[y] then
begin
dis[y]:=dis[x]+cost;
if g[y]=false then
begin
inc(t); q[t]:=y; g[y]:=true;
if t>= then t:=;
end;
end;
end;
p:=p^.next;
end;
end;
end;
begin
readln(n,m,k,maxs); readln(ppp,qqq);
for i:= to k do
begin
readln(x); mk[x]:=; add(,x);
end;
for i:= to m do
begin
readln(x,y); add(x,y); add(y,x);
end;
spfa();
for i:= to n do
if dis[i]<=maxs+ then begin
if mk[i]< then mk[i]:=;
end;
spfa();
if n= then writeln() else
if mk[n]= then writeln(int64(dis[n]-ppp)) else writeln(int64(dis[n]-qqq));
end.
t3
题意：给出一段行走命令，机器人连续执行k次，每走一次放一个标记，求四角被标记的正方形个数。
分析：有一个乱搞方法是走4次找出被标记的个数然后得到k次的，正解懒得写了。