題目背景 此題約為NOIP提高組Day2T2難度。 題目描述 眾所周知，模數的hash會產生衝突。例如，如果模的數p=7，那麼4和11便衝突了。 B君對hash衝突很感興趣。他會給出一個正整數序列value[]。 自然，B君會把這些數據存進hash池。第value[k]會被存進(k%p)這個池。這樣 ...
題目背景
此題約為NOIP提高組Day2T2難度。
題目描述
眾所周知，模數的hash會產生衝突。例如，如果模的數p=7，那麼4和11便衝突了。
B君對hash衝突很感興趣。他會給出一個正整數序列value[]。
自然，B君會把這些數據存進hash池。第value[k]會被存進(k%p)這個池。這樣就能造成很多衝突。
B君會給定許多個p和x，詢問在模p時，x這個池內數的總和。
另外，B君會隨時更改value[k]。每次更改立即生效。
保證.
輸入輸出格式
輸入格式：
第一行，兩個正整數n,m，其中n代表序列長度，m代表B君的操作次數。
第一行，n個正整數，代表初始序列。
接下來m行，首先是一個字元cmd，然後是兩個整數x,y。
-
若
cmd='A'，則詢問在模x時，y池內數的總和。 - 若
cmd='C'，則將value[x]修改為y。
輸出格式：
對於每個詢問輸出一個正整數，進行回答。
輸入輸出樣例
輸入樣例#1：10 5 1 2 3 4 5 6 7 8 9 10 A 2 1 C 1 20 A 3 1 C 5 1 A 5 0輸出樣例#1：
25 41 11
說明
樣例解釋
A 2 1的答案是1+3+5+7+9=25.
A 3 1的答案是20+4+7+10=41.
A 5 0的答案是1+10=11.
數據規模
對於10%的數據，有n<=1000,m<=1000.
對於60%的數據，有n<=100000.m<=100000.
對於100%的數據，有n<=150000,m<=150000.
保證所有數據合法，且1<=value[i]<=1000.
題解：
數據太水，暴力模擬就能過。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int read() { int x=0,f=1; char ch; ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m; int a[150001]; int main() { n=read();m=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=m;i++) { char s[3]; scanf("%s",s); if(s[0]=='A') { int x,y,ans=0; x=read();y=read(); for(int j=y;j<=n;j+=x) ans+=a[j]; printf("%d\n",ans); } else if(s[0]=='C') { int x,y; x=read();y=read(); a[x]=y; } } return 0; }
