NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2004高中組決賽
 NPSC 2004 高中組 決賽 A.地牛翻身 By 波卡Poka

作者 主題: NPSC 2004 高中組 決賽 A.地牛翻身 By 波卡Poka  (閱讀 1735 次)

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 217
    • 檢視個人資料
NPSC 2004 高中組 決賽 A.地牛翻身 By 波卡Poka
« 於: 十二月 08, 2009, 03:34:06 pm »

NPSC 2004 高中組 決賽 A.地牛翻身

提供者:波卡Poka

說明:輸入一個 N*M 的表格,然後輸入兩點的座標,求這兩點座標所形成的矩形每一個儲存格數字的總合。

解法:因為使用兩層的 for 迴圈去計算距形區域的總合,時間複雜度為 O(n^2),如此一來資料量一大時,會超過時間。因此要用更有效率的解法,如下:
1.把原本記錄一格一格的值,改成從(1,1)到那一格的總合,在一邊輸入時就同時計算總合。
2.查詢時用 a[t][r] - a[b-1][r] - a[t][l-1] + a[b-1][l-1] 的公式,即可算出 (b,l) 到 (t,r) 的總合。

參考程式:(By 波卡Poka)

代碼: [選擇]
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
  FILE *fo,*fw;
  long int **ma,q,sum,i,j,n,m,b,t,l,r,tmp;
  fo=fopen("pa.in","r");
  fw=fopen("pa.out","w");
  fscanf(fo,"%ld %ld",&n,&m);
  ma=(long int **)malloc((n+=1)*sizeof(long int *));
  ma[0]=(long int *)calloc((m+=1),sizeof(long int));
  for(i=1;i<n;i++){
      ma[i]=(long int *)malloc(m*sizeof(long int));
      ma[i][0]=0;
      for(j=1,sum=0;j<m;j++){
          fscanf(fo,"%ld",&tmp);
          ma[i][j]=(sum+=tmp)+ma[i-1][j];
          }
      }
  fscanf(fo,"%ld",&q);
  for(i=0;i<q;i++){
      fscanf(fo,"%ld %ld %ld %ld",&b,&t,&l,&r);
      fprintf(fw,"%d\n",ma[t][r]+ma[b-1][l-1]-ma[t][l-1]-ma[b-1][r]);
      }
  for(i=0;i<n;i++)
    free(ma[i]);
  free(ma);
  fclose(fo);
  fclose(fw);
  return 0;
}
« 上次編輯: 十二月 08, 2009, 04:15:07 pm 由 sagit »
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2004高中組決賽
 NPSC 2004 高中組 決賽 A.地牛翻身 By 波卡Poka