2009年東莞市信息學特長生測試題 開發區規劃

Description

小王是D市主管經濟的副市長，由于經濟發展的需要，要在D市組建一個高新技術開發區，經過研究，規劃局在D市的東部劃出了一塊土地作為開發區選址。這塊土地是一塊矩形平原，小王準備在上面修建一些建筑。為了規劃方便，他將矩形劃分成N*M格。棘手的是，這塊土地有些歷史文化遺址散布在某些格子內，這些歷史文化遺址是萬萬不能拆除的，否則將激起民憤，小王深知這一點，因此，他的新建筑在選址時要避開這些格子。
　　假設新的建筑物有P種規格，每種建筑物都是正方形的，占地為Ti*Ti格 (1<=i<=P)。小王想知道對于每種規格的建筑，有多少種不同的合適選址方案（一種合適的選址方案指的是在該建筑所占的正方形區域內不存在有歷史文化遺址的格子）。現在請你來當小王的秘書 幫他完成這個光榮而艱巨的任務。

Input

　　從文件d.in讀入數據，輸入文件第一行包含三個數，分別代表N,M,P (1<=N,M<=2000,1<=P<=1000)。隨后的n行，每行有m個0或1（1表示該格為空地，0表示該格有歷史文化遺址）。接下來的P行每行有一個整數Ti (1

Output

　　結果輸出到文件d.out中，共有P行，每行一個整數，第i行的數代表邊長為Ti的建筑物選址方案數。

Sample Input

4 4 2
1011
1111
1110
1110
2
3

Sample Output

5
1

Source

elba

題解：

???先看一下本題的范圍，輸入為2000*2000。看似很小，但如果直接枚舉的話就是2000^3=80e(把每種邊長的正方形都枚舉一遍)。這樣做就會超時(TLE)，所以我們要剪下枝~（づ￣3￣）づ
???我們以所有點作為右下角，求出最大能拓展的正方形的邊長，最后累加(如果這個位置能拓展邊長為5的正方形，它就一定能拓展邊長為4（1≤x≤5）的正方形)
???首先我們先處理第一行，因為第一行無法向左上拓展，所以方便我們初始化和記錄邊長為1的正方形
???然后就處理后面幾行就行了，不過要注意判斷！例如i點可以向上拓展3個點，但它只能向左拓展2個點，由于它只能拓展正方形，所以它最多只能拓展邊長為2的正方形！(否則頂多是矩形)

PS:

???x[i]為在第i個點時可以向x軸方向拓展x[i]個長度(靠前一個來更新)，y[i]也以此類推。z[i]存放當前這個點最大能拓展的正方形數(靠對角線來更新)，f[i]為以i為邊長的正方形有f[i]個

varx,y,z,f:array[0..2001]of longint;n,m,p,t,i,j:longint;s:ansistring; function min(a,b:longint):longint; beginif a<b then exit(a);exit(b); end; beginread(n,m,p);readln;read(s);for i:=1 to m doif s[i]='0' then begin x[i]:=0; y[i]:=0; endelsebeginx[i]:=x[i-1]+1;//拓展~inc(y[i]);z[i]:=1;inc(f[1]);//第一行只能拓展邊長為1的正方形end;for i:=2 to n dobeginreadln;read(s);for j:=1 to m doif s[j]='0' then begin x[j]:=0; y[j]:=0; endelse begin x[j]:=x[j-1]+1; inc(y[j]); end;for j:=m downto 1 doif s[j]='0' then z[j]:=0//判斷elsebeginz[j]:=z[j-1]+1;z[j]:=min(z[j],x[j]);//找合法的正方形z[j]:=min(z[j],y[j]);inc(f[z[j]]);end;end;for i:=min(n,m) downto 1 do inc(f[i],f[i+1]);//累加for i:=1 to p dobeginreadln(t);writeln(f[t]);end; end.

總結

以上是生活随笔為你收集整理的(ssl1960)2009年东莞市信息学特长生测试题 开发区规划的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。