題目描述

方格紙與草稿紙一樣，都是算法競賽中不可或缺的重要工具。身經百戰的小Q自然也會隨身帶著方格紙。小Q的方格紙有n行m列，一共n*m個方格，從上到下依次標記為第1,2,...,n行，從左到右依次標記為第1,2,...,m列，方便起見，小Q稱第i行第j列的方格為(i,j)。小Q在方格紙中填滿了數字，每個格子中都恰好有一個整數a_{i,j}。小Q不喜歡手算，因此每當他不想計算時，他就會讓你幫忙計算。小Q一共會給出q個詢問，每次給定一個方格(x,y)和一個整數k(1<=k<=min(x,y))，你需要回答由(x,y),(x-k+1,y),(x,y-k+1)三個格子構成的三角形邊上以及內部的所有格子的a的和。

輸入

第一行包含6個正整數n,m,q,A,B,C(1<=n,m<=3000,1<=q<=3000000,1<=A,B,C<=1000000) 其中n,m表示方格紙的尺寸，q表示詢問個數。 為了防止輸入數據過大，a和詢問將由以下代碼生成： unsigned int A,B,C; inline unsigned int rng61(){ A ^= A << 16; A ^= A >> 5; A ^= A << 1; unsigned int t = A; A = B; B = C; C ^= t ^ A; return C; } int main(){ scanf("%d%d%d%u%u%u", &n, &m, &q, &A, &B, &C); for(i = 1; i <= n; i++) for(j = 1; j <= m; j++) a[i][j] = rng61(); for(i = 1; i <= q; i++){ x = rng61() % n + 1; y = rng61() % m + 1; k = rng61() % min(x, y) + 1; } }

輸出

為了防止輸出數據過大，設f_i表示第i個詢問的答案，則你需要輸出一行一個整數，即：

$(\sum\limits_{i=1}^q 233^{q-i}*f_i)\ mod\ 2^{32}$

樣例輸入

3 4 5 2 3 7

樣例輸出

3350931807

---

題解

前綴和

考慮答案怎么組成：

(0,0)

顯然答案（紅色區域）等于黑色邊框（矩形）面積 - 藍色邊框（大三角形）面積 + 綠色邊框（小三角形）面積。

于是維護兩種前綴和：第一種維護一般的矩形區域二維前綴和，第二種維護直角邊邊長為x，左下角橫坐標為y，縱坐標為1的等腰直角三角形的數之和。

然后亂搞就過了。為了防止n和m弄混，可以令n'=m'=max(n,m)。

#include <cstdio> #include <cstring> #include <algorithm> #define N 3010 using namespace std; unsigned A , B , C , a[N][N] , sum[N][N] , ste[N][N]; inline unsigned rng61() {A ^= A << 16;A ^= A >> 5;A ^= A << 1;unsigned t = A;A = B;B = C;C ^= t ^ A;return C; } int main() {int n , m , q , i , j , x , y , k;unsigned ret , ans = 0;scanf("%d%d%d%u%u%u" , &n , &m , &q , &A , &B , &C);for(i = 1 ; i <= n ; i ++ )for(j = 1 ; j <= m ; j ++ )a[i][j] = rng61();for(i = 1 ; i <= max(n , m) ; i ++ )for(j = 1 ; j <= max(n , m) ; j ++ )sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];for(i = 1 ; i <= max(n , m) ; i ++ )for(j = max(n , m) ; j >= 1 ; j -- )ste[i][j] = ste[i - 1][j + 1] + sum[j][i] - sum[j - 1][i];while(q -- ){x = rng61() % n + 1;y = rng61() % m + 1;k = rng61() % min(x , y) + 1;ret = (sum[x][y] - sum[x - k][y]) - (ste[y - 1][x - k + 1] - ste[y > k ? y - k - 1 : 0][x + 1]);ans = ans * 233 + ret;}printf("%u\n" , ans);return 0; }

?

轉載于:https://www.cnblogs.com/GXZlegend/p/7413438.html

總結

以上是生活随笔為你收集整理的【bzoj4972】小Q的方格纸 前缀和的全部內容，希望文章能夠幫你解決所遇到的問題。

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