如何找到3的倍數

有N個數字a [0]，a [1] .. a [N - 1]。 Initally都是0。你必須執行操作的兩種類型：

增加1指數A和B之間的數字這是通過命令「0 AB」指數之間
回答多少個號碼代表A和B可以被3整除。這由命令「1 AB」表示。

輸入：第一行包含兩個整數，N和Q.

每個下一個Q線的要麼是形式爲「0 A B」或上述「1 A B」的。

輸出：輸出1行，用於包含相應查詢所需答案的「1A B」格式的每個查詢。

樣品輸入：

4 7 1 0 3 0 1 2 0 1 3 1 
0 0 0 0 3 1 3 3 1 0 3

樣本輸出：

4 1 0 2

約束：

1 <= N <= 100000 1 <= Q <= 100000 0 <= A <= B <= N - 1

我不知道如何解決這個問題。你能幫忙嗎？

時間限制爲1秒。我試圖蠻力，我也試圖保存每個我i元素前的3個除數。

，這裏是我的C代碼：

#include <stdio.h> 


int nums[100*1000+20]; 
int d[100*1000+20]; 
int e[100*1000+20]; 
int dah[100*1000+20]; 

int main() 
{ 
    int n,q; 
    scanf("%d%d",&n,&q); 
    int h; 
    for(h=0;h<n;h++) 
     {d[h/100]++; e[h/1000]++; dah[h/10]++;} 
    int test; 
    for(test=0;test<q;test++) 
    { 
     int op,start,end; 
     scanf("%d%d%d",&op,&start,&end); 
     if(0==op) 
     { 
      int x; 
      for(x=start;x<=end;x++) 
      { 
       nums[x]++; 
       nums[x]%=3; 
       if(nums[x]==0) 
       { 
        d[x/100]++; 
        e[x/1000]++; 
        dah[x/10]++; 
       } 
       else if(nums[x]==1) 
       { 
        d[x/100]--; 
        e[x/1000]--; 
        dah[x/10]--; 
       } 
      } 
     } 
     else if(1==op) 
     { 
      int f; 
      int ans=0; 
      for(f=start;f<=end;) 
      { 
       if(f%1000==0&&f+1000<end) 
       { 
        ans+=e[f/1000]; 
        f+=1000; 
       } 
       else if(f%100==0&&f+100<end) 
       { 
        ans+=d[f/100]; 
        f+=100; 
       } 
       else if(f%10==0&&f+10<end) 
       { 
        ans+=dah[f/10]; 
        f+=10; 
       } 
       else 
       { 
        ans+=(nums[f]==0); 
        f++; 
       } 
      } 
      printf("%d\n",ans); 
     } 
    } 
    return 0; 
}

在這種方法我保存的* 1000和（k + 1）* 1000，也對於k同樣的事情K的3倍數的數量* 100和（k +1）* 100，也爲10.這有助於我更快地查詢。但是這卻讓我超越了時間限制。

來源

2010-09-01 Ali

你可以重新格式化這個可讀性？ – Oded 2010-09-01 16:24:46

做你自己的家庭作業 – jer 2010-09-01 16:25:29

@jer - 作業題目在這裏是有效和合法的。我們通過提供提示來回答他們，而不是全面的答案。 – Oded 2010-09-01 16:26:13

數組的上限是多少？首先，明確指出。然後，計劃閱讀這兩種形式之一的輸入內容。格式爲0 A B的行很容易處理，你能至少編碼那麼多嗎？如果是這樣，張貼，然後擔心格式1A B.

來源

2010-09-01 16:33:35 Beth

提示＃1線：

想想如何使用模運算符來幫助你。最初，你有N個數字，假設N爲5

因此，我們可以存儲餘每個號碼（即商店0 MOD 3,1 MOD 3,2 MOD 3，依此類推）：

a[0] = 0 
a[1] = 1 
a[2] = 2 
a[3] = 0 
a[4] = 1 
a[5] = 2

每次增加A和B之間的數字範圍時，實際上只需要在數組中存儲0,1或2。例如，如果我們遞增2，那麼新的數字將是3.現在可以被3整除，所以我們在數組中存儲0。所以如果我們有0，我們增加，我們存儲1，如果我們有1，我們存儲2，如果我們有2，我們存儲0。

此優化消除了除初始步驟之外的任何分工的需要。分部是一個非常昂貴的操作，這就是爲什麼我們想在可能的地方消除它。

所以通過5遞增0之後，該陣列是這樣的：

a[0] = 1 
a[1] = 2 
a[2] = 0 
a[3] = 1 
a[4] = 2 
a[5] = 0

A和B由3整除之間的數字的量在剛剛具有0元件（2號這個案例）。

現在你必須思考如何通過對B查詢範圍內的有效通過3

提示＃2找到整除的數字量：

要通過找出多少號區間[A，B]可以被3整除，您可以考慮使用的算法/數據結構是分段樹。閱讀關於它here。這個買你的是，現在你可以很快地計算任何這樣的間隔[A，B]可以被3整除的數字的數量，而不是在數組上循環並且必須對它們進行計數。

來源

2010-09-01 16:34:03 dcp

我做了同樣的事情 – Ali 2010-09-01 16:37:20

感謝您的幫助。但我的問題其實是在查詢 – Ali 2010-09-01 16:39:39

@Ali - 請參閱提示＃2。 – dcp 2010-09-01 16:43:57

如果如您的標題所暗示的那樣，您不確定如何判斷一個數字是否可以被三整除，那麼我建議您查看modulus operation，使用我最熟悉的語言一個%。

來源

2010-09-01 16:34:32 torak

該評論是多餘的，它不回答這個問題，我敢肯定作者知道模數運算。 – Leonid 2010-09-01 22:32:04

提示＃3：

通過dcp很好的建議。雖然它不揭示如何解決問題。 沒有必要將所有數字MOD 3存儲在數組中。如果在陣列中每次更新數字，則複雜度爲O(Q * N)，對於給定的N,Q和1秒，顯然太多了。在最壞的情況下。這是對dcp建議的評論中的Ali這一點。

MOD%0,MOD%1,MOD%2的整數個數可以存儲在段樹的每個節點中。因此，更新可以在O(log N)中完成，僅在更新時產生O(Q log N)。對於每個查詢，應用相同的複雜度O(log N)。由於您知道每個殘基的整數MOD％3，所以沒有必要遍歷全部葉（每個葉子樹中的離開對應於數組元素）來計算有多少數字可以被3整除。一旦您瞭解段樹的工作原理應該是明顯的，爲什麼有必要在段樹的每個節點中存儲殘差。該算法的總體複雜度爲O(Q log N)，它將很好地適用於1 sec. time limit。

當沿着分段樹向下移動時，請確保爲沿着樹的方式訪問的每個分段累積每個殘基的整數數量。

來源

2010-09-01 22:43:32 Leonid

如果我的答案中有任何不清楚的地方，請讓我知道。希望你能弄清楚這裏有什麼意義。 – Leonid 2010-09-01 22:50:43

如何找到3的倍數

回答

相關問題