Day4：其中有很多小技巧get
T1
一直没有听到过像这样的小技巧的略专业名词，有点类似于指针操作，之前有碰到过很多这样的题目
每次都是以不同的形式出现，但是感觉思想还是有点接近的吧（就比如某天有一题happy，貌似也是这类型的）
这类题目第一眼总是看起来特别的不能写，其实想到了这些技巧之后很简单
感觉这也没有什么规律性或是模板可言
大概的，就是指针思想+平时积累吧
说说这一题吧
在分析正解之前，我们先说一说比较容易想到的骗分方法
设男女人数相同时ans=0,如果下一个是男->ans++,else ans--;
找到ans=0时，记录下此时的位置，把这个位置和上个位置相减
之后再扫一遍答案，把连续的相加即可
这种方法很简单也比较容易想到，但是这只是O(N2)的算法，只能过50%的数据
那正解是什么样的呢？
其实也就是以上骗分方法的改进而已；
想想其实我们并不需要找ans=0的情况，只需要前面的ans和后面再次出现相同的ans值，即可知男女人数相同(换句话说就是，男生比女生多多少或少多少相同）
用一个数组pos[i ]记录“1”的个数比“0”的个数多i个时第一次出现的位置（i可以为负数，表示“1”的个数比“0”少）。
当扫描到某个位置w时发现pos[x]已经有值了，我们就得到了从第pos[x]+1个数到第w个数的子序列满足条件，于是用w-pos[x]去更新满足条件的子序列长度的最大值。为了方便处理x为0的情况，我们规定，pos[0]=0。
for i:=1 to n do
begin
read(x);
if x=1 then inc(duo) else dec(duo);
if (a[duo]=0) and (duo<>0) then a[duo]:=i
else if i-a[duo]>ans then ans:=i-a[duo];
end;
很棒的思路，主要是懂得理解和运用a数组，当a[duo]！=0的时候就记录位置
然而这种方法也巧妙的避开了骗分方法中找连续区间的必要，因为它一开始就是记录duo第一次出现的位置！！
MARK
//对了，由于c++里面数组是没有负数位置的，所以duo最好赋为100000
T2：搜索
是一个很棒的题目
很明显的看出这是一个很典型的搜索题，但是怎么搜，怎么思考其实才是问题的关键
首先思维不能只是局限人如何走，走了之后，如何判断是否能射到？
如果这样想的话，写出来的程序一定会很复杂
有没有更简单的思路呢？
答案是肯定的。
换一种思路去想，假定人不动，预处理出一次人能够一次射到的位置；
然后移动目标点，搜目标点移动到人可射的位置不就解决问题了嘛！
QAQ...一切都是智商的错啊！！
想清楚了之后，只要仔细的预处理出八个方位能射到的点
然后在bfs一下即可：
附上代码：
const
dx:array[1..4] of -1..1=(0,0,-1,1);//起点往四个方向扩展。
dy:array[1..4] of -1..1=(-1,1,0,0);
var
n,m,i,j,x1,y1,x2,y2,cx,cy:longint;
map:array[-10..200,-10..200] of char;
hx,hy,hd:array[1..20000] of longint;//队列
bo:array[-10..200,-10..200] of boolean;
function bfs(x,y:longint):boolean;
var
chong:array[-10..200,-10..200] of boolean;//判重
head,tail,i,j,x3,y3,x4,y4,long:longint;
begin
fillchar(hx,sizeof(hx),0);
fillchar(hy,sizeof(hy),0);
fillchar(hd,sizeof(hd),0);
bfs:=false;
fillchar(chong,sizeof(chong),false);
head:=0;tail:=1;hx[1]:=x;hy[1]:=y;hd[1]:=0;
chong[x,y]:=true;
while head<tail do//从起点向四面八方扩展
begin
inc(head);
x3:=hx[head];y3:=hy[head];long:=hd[head];
for i:=1 to 4 do
begin
x4:=x3+dx[i];y4:=y3+dy[i];
if (x4>=1) and (x4<=n) and (y4>=1) and (y4<=m) and (map[x4,y4]='O') and (not chong[x4,y4]) then//要判重
begin
chong[x4,y4]:=true;
if bo[x4,y4] then begin writeln(long+1);exit(true);end;
inc(tail);
hx[tail]:=x4;
hy[tail]:=y4;
hd[tail]:=long+1;
end;
end;
end;
end;
begin
assign(input,'dragon.in');
reset(input);
assign(output,'dragon.out');
rewrite(output);
readln(n,m);
for i:=1 to n do
begin
for j:=1 to m do
read(map[i,j]);
readln;
end;
readln(x2,y2,x1,y1);
while (x1<>0) or (y1<>0) or (x2<>0) or (y2<>0) do//对四面八方进行预处理 以下片段可以缩成一个过程
begin
fillchar(bo,sizeof(bo),false);
bo[x2,y2]:=true;
for i:=y2 to m do
if map[x2,i]='O' then bo[x2,i]:=true else break;
for i:=y2-1 downto 1 do
if map[x2,i]='O' then bo[x2,i]:=true else break;//横向
for i:=x2 to n do
if map[i,y2]='O' then bo[i,y2]:=true else break;
for i:=x2-1 downto 1 do
if map[i,y2]='O' then bo[i,y2]:=true else break;//纵向
cx:=x2;cy:=y2;
while (cx>=1) and (cy<=m) and (map[cx,cy]='O') do//右上
begin
bo[cx,cy]:=true;
dec(cx);
inc(cy);
end;
cx:=x2;cy:=y2;
while (cx<=n) and (cy>=1) and (map[cx,cy]='O') do//左下
begin
bo[cx,cy]:=true;
inc(cx);
dec(cy);
end;
cx:=x2;cy:=y2;
while (cx>=1) and (cy>=1) and (map[cx,cy]='O') do//左上
begin
bo[cx,cy]:=true;
dec(cx);
dec(cy);
end;
cx:=x2;cy:=y2;
while (cx<=n) and (cy<=m) and (map[cx,cy]='O') do//右下
begin
bo[cx,cy]:=true;
inc(cx);
inc(cy);
end;//以上四个段落是对角线方向
if bo[x1,y1] then writeln(0) else//如果直接可以达到那么就直接判0
if not bfs(x1,y1) then writeln('Impossible!');
readln(x2,y2,x1,y1);
end;
close(input);
close(output);
end.
