这是一个竞赛问题:
有 N 个数字 a[0],a[1]..a[N - 1]。最初都是 0。你必须执行两种类型的操作:
- 将索引 A 和 B 之间的数字增加 1。这由命令“0 A B”表示
- 回答索引 A 和 B 之间有多少个数字可以被 3 整除。这由命令“1 A B”表示。
输入:第一行包含两个整数,N和Q。
接下来的 Q 行中的每一行都是上述形式的“0 A B”或“1 A B”。
输出:为“1 A B”形式的每个查询输出 1 行,其中包含相应查询所需的答案。
示例输入:
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 保存第 ith 个元素之前的 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;
}
在这种方法中,我在 k*1000 和 (k+1)*1000 之间保存了 3 的倍数,对于 k*100 和 (k+1)*100 以及 10 也是如此。这对我有帮助查询更快。但这让我超过了时间限制。
最佳答案
提示 #1:
想想如何使用 MODULUS 运算符来帮助您。最初,您有 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。
此优化消除了除初始步骤之外的任何除法的需要。除法是一项非常昂贵的操作,这就是我们希望尽可能消除它的原因。
所以在从 0 递增到 5 之后,数组看起来像这样:
a[0] = 1
a[1] = 2
a[2] = 0
a[3] = 1
a[4] = 2
a[5] = 0
A 和 B 之间可被 3 整除的数字的数量就是具有 0 的元素的数量(在本例中为 2)。
现在您必须考虑如何有效地查询范围 A 到 B 以找到可被 3 整除的数字的数量。
提示#2:
要找出区间 [A,B] 内有多少数字可以被 3 整除,您可以考虑使用一种算法/数据结构,即线段树。了解一下 here .这给您带来的好处是,现在您可以非常快速地计算任何此类区间 [A,B] 中可被 3 整除的数字的数量,而不是遍历数组并计算它们。
关于c - 如何求 3 的倍数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3620141/