首页 > 代码库 > Day4：T1小技巧（类似于指针操作）T2搜索+小细节
Day4：T1小技巧（类似于指针操作）T2搜索+小细节
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.
Day4：T1小技巧（类似于指针操作）T2搜索+小细节