Day4：其中有很多小技巧get
T1
一直沒有聽到過像這樣的小技巧的略專業(yè)名詞，有點類似于指針操作，之前有碰到過很多這樣的題目
每次都是以不同的形式出現(xiàn)，但是感覺思想還是有點接近的吧（就比如某天有一題happy，貌似也是這類型的）
?
這類題目第一眼總是看起來特別的不能寫，其實想到了這些技巧之后很簡單
感覺這也沒有什么規(guī)律性或是模板可言
大概的，就是指針?biāo)枷?平時積累吧
?
說說這一題吧
在分析正解之前，我們先說一說比較容易想到的騙分方法
設(shè)男女人數(shù)相同時ans=0,如果下一個是男->ans++,else ans--;
找到ans=0時，記錄下此時的位置，把這個位置和上個位置相減
之后再掃一遍答案，把連續(xù)的相加即可
這種方法很簡單也比較容易想到，但是這只是O(N2)的算法，只能過50%的數(shù)據(jù)
?
那正解是什么樣的呢？
其實也就是以上騙分方法的改進(jìn)而已；
想想其實我們并不需要找ans=0的情況，只需要前面的ans和后面再次出現(xiàn)相同的ans值，即可知男女人數(shù)相同(換句話說就是，男生比女生多多少或少多少相同）
用一個數(shù)組pos[i ]記錄“1”的個數(shù)比“0”的個數(shù)多i個時第一次出現(xiàn)的位置（i可以為負(fù)數(shù)，表示“1”的個數(shù)比“0”少）。
當(dāng)掃描到某個位置w時發(fā)現(xiàn)pos[x]已經(jīng)有值了，我們就得到了從第pos[x]+1個數(shù)到第w個數(shù)的子序列滿足條件，于是用w-pos[x]去更新滿足條件的子序列長度的最大值。為了方便處理x為0的情況，我們規(guī)定，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;
?很棒的思路，主要是懂得理解和運(yùn)用a數(shù)組，當(dāng)a[duo]！=0的時候就記錄位置
然而這種方法也巧妙的避開了騙分方法中找連續(xù)區(qū)間的必要，因為它一開始就是記錄duo第一次出現(xiàn)的位置！！
MARK
?//對了，由于c++里面數(shù)組是沒有負(fù)數(shù)位置的，所以duo最好賦為100000
T2：搜索
是一個很棒的題目
很明顯的看出這是一個很典型的搜索題，但是怎么搜，怎么思考其實才是問題的關(guān)鍵
首先思維不能只是局限人如何走，走了之后，如何判斷是否能射到？
如果這樣想的話，寫出來的程序一定會很復(fù)雜
有沒有更簡單的思路呢？
答案是肯定的。
換一種思路去想，假定人不動，預(yù)處理出一次人能夠一次射到的位置；
然后移動目標(biāo)點，搜目標(biāo)點移動到人可射的位置不就解決問題了嘛！
QAQ...一切都是智商的錯啊！！
?
想清楚了之后，只要仔細(xì)的預(yù)處理出八個方位能射到的點
然后在bfs一下即可：
附上代碼：
const
dx:array[1..4] of -1..1=(0,0,-1,1);//起點往四個方向擴(kuò)展。
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//從起點向四面八方擴(kuò)展
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//對四面八方進(jìn)行預(yù)處理 以下片段可以縮成一個過程
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//如果直接可以達(dá)到那么就直接判0
if not bfs(x1,y1) then writeln('Impossible!');
readln(x2,y2,x1,y1);
end;
close(input);
close(output);
end.
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
