0%

3.9创新班总结

这天创新班的内容,主要的就是两道测试题。尽管这两道测试看上去并不难,实际上,这需要动动脑筋才想得到呢?

第一题:

这一道题主要就是讲,有n个数排成一个圈,求从第x个到第y个的和。(如果是x<=y表示从x到y,如果是x>y,则表示从x到n再从1到y)。

很多人一看题目,就知道这道题只需简单模拟一下即可。但是,我们一看到n高达100000,并且有高达100000次计算,最坏情况下,O(n*m),10^10次方,早就超时,那么我们该怎么办呢?我们发现,主要超时地方就是我们要一个数一个数加。

这是,我们要引入前缀和。前缀和,顾名思义,就是一个数前面的所有数字的和。那么,我们用f数组储存一个数的前缀和,即f[i]=f[i-1]+a[i]。那么我们现在有两种情况,一是x≤y;一是x>y。

  1. x≤y。f[x]表示a[1]到a[x]的和,f[y]表示a[1]到a[y]的和,a[x]到a[y]不就是f[y]-f[x]吗?

  2. x>y。(如果是x<=y表示从x到y,如果是x>y,则表示从x到n再从1到y)[原文],结果不就是f[n]-f[x]+f[y]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <fstream>
using namespace std;

ifstream fin("a.in");
ofstream fout("a.out");

int a[110000],b[110000]={0},n,m,sum;
int dodo(int l,int r);

int main()
{
int max=-11000000;
fin>>n>>m;
for (int i=1; i<=n; ++i) fin>>a[i];

b[1]=a[1];
for (int i=1; i<=n; ++i) b[i]=b[i-1]+a[i];
for (int i=1 ;i<=m ;++i)
{
int x,y,ans=0;
fin>>x>>y;
if (x<=y) ans=dodo(x,y); //①
else ans=dodo(x,n)+dodo(1,y); //②
if (ans>max) max=ans;
}

fout<<max<<'\n';
return 0;
}

int dodo(int l,int r)
{
return(b[r]-b[l-1]);
}

第二题:

这一道题,说难不难,说简单也不简单。这一道题主要就是说:有n个数,排成一排(与上一题不同),问有多少段数是11的倍数。

这一道题还是用前缀和来解决。还是老样子,用f数组储存。然后,我们还要开一个数组c,c[i]=f[i]%11,为什么呢?我们需要前缀的余数,就是为了,接下来的计算。例如数据[3,-2,4,6,9,2],前缀和就是[3,-1,5,11,20,22],那么前缀和的余数就是[3,1,5,0,9,0],这时我们发现,有两个不相邻的0,我们此时知道,第一个到第四个的和是11p1+q(q不一定是0),第一个到第六个的和是11p2+q,那么第五个到第六个的和不就是11(p2-p1)。换句话说,任意不相邻的两个余数是相等的话,结果就加一。

值得注意的是,我们要默认开头多一个0,即要考虑c[0]=0,因为,我们要考虑从第一个到第x个的情况。

那么,我们可以统计每个余数的出现次数记录在x数组上,根据排列组合,ans+=(x[i]+x[i-1])/2(x[0]要加上开头的0)。

PS:我们可以在输入数据时加上一个较大的11倍数的正整数,如110000,这样可以避免负数有不影响结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <fstream>
using namespace std;

ifstream fin("b.in");
ofstream fout("b.out");

typedef int arr[100005];
arr a,b={0};
int c[15]={0};
int n,sum=0;

int main()
{
fin>>n;
for (int i=1; i<=n; i++) { fin>>a[i]; a[i]+=110000; }

for (int i=1; i<=n; i++) b[i]=(b[i-1]+a[i])%11;
for (int i=0; i<=n; i++) c[b[i]]++;
for (int i=0; i!=11; i++) sum+=(c[i]*(c[i]-1)/2);

/*for (int i=1; i<=n; i++)

if (b[i]==b[i-1]) sum--;*/{Question:究竟是否需要判重呢?如何判重呢?}

fout<<sum<<'\n';
return 0;
}
Thank you so much.