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.
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
