部分和

常用的预处理方法


作者:老陈

引言——统计成绩

Sample Input
5
2 3 5 9 7
5
1 2
2 3
4 5
1 5
3 5

Sample Output
2.500
4.000
8.000
5.200
7.000

分析

我们考虑一下这种解法的时间复杂度:首先,我们需要构造psum[]数组,这需要O(N)的时间。然后对于每一个查询,我们可以得知需要O(1)的时间。所以总时间复杂度为O(N),这符合题目时限要求。

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
int grade[1000010];
ll psum[1000010];

double result(int l, int r)
{
return (double)(psum[r] - psum[l - 1]) / (r - l + 1);
}

int main()
{
int n, m;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", grade + i);
psum[i] = psum[i - 1] + grade[i]; //
}
scanf("%d", &m);
for (int i = 1; i <= m; i++)
{
int l, r;
scanf("%d%d", &l, &r);
printf("%.3lf\n", result(l, r));
}
return 0;
}

内存能否再优化???是否注意到这里的grade[]数组在后面的询问中根本就没起到作用?此处可以不使用grade[]数组。

1
2
3
4
5
for (int i = 1; i <= n; i++)
{
scanf("%d", &grade);
psum[i] = psum[i - 1] + grade; //
}

再探索——统计成绩II


Sample Input
5
2 3 5 9 7
5
1 2
2 3
4 5
1 5
3 5

Sample Output
0.25000
1.00000
1.00000
6.56000
2.66667

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
int grade;
ll psum[1000010], sqsum[1000010];
double result(int l, int r)
{
double ave = (double)(psum[r] - psum[l - 1]) / (r - l + 1);
double res = sqsum[r] - sqsum[l - 1] - 2 * ave*(psum[r] - psum[l - 1]) + (r - l + 1)*ave*ave;
return res / (r - l + 1);
}
int main()
{
int n, m;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &grade);
psum[i] = psum[i - 1] + grade;
sqsum[i] = sqsum[i - 1] + grade * grade;
}
scanf("%d", &m);
for (int i = 1; i <= m; i++)
{
int l, r;
scanf("%d%d", &l, &r);
printf("%.5lf\n", result(l, r));
}
return 0;
}

在二维数组中的应用——统计成绩III

Sample Input
5
1 2 3 5 6
9 8 7 6 5
1 2 7 9 5
2 5 0 8 7
3 6 9 4 5
3
1 2 3 4
3 4 1 3
1 5 1 5

Sample Output
10
37
125

Devu, the Dumb Guy——Codeforces 439B

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

int num[100010];

int main()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++)
{
cin >> num[i];
}
sort(num, num + n);
ll res = 0;
for (int i = 0; i < n; i++)
{
res += (ll)num[i] * m;
m = (m == 1 ? 1 : m - 1);
}
cout << res;
return 0;
}

Alphabetic Removals——Codeforces 999C

时间限制:2s 内存限制:256MB

题目描述

给定一个由n个小写字母组成的字符串s。Polycarp想从s中删除k个字母。 ( k≤n)Polycarp使用下面的算法k次:

  • 如果存在至少一个’a’,则删除最左的一个结束算法

  • 如果存在至少一个’b’,则删除最左的一个结束算法

  • 如果存在至少一个’z’,则删除最左的一个结束算法

这个算法删除了字符串s中的一个字母,Polycarp执行这个算法正好k次,也就删除了k个字母。帮助Polycarp得到结果字符串。

Sample Input
15 3
cccaabababaccbc
1

Sample Output
cccbbabaccbc


Sample Input
4 15 9
cccaabababaccbc
2
5 1 2 1

Sample Output
cccccc


Sample Input
1 1
u

Sample Output


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
35
36
37
38
39
40
41
42
int t[26];

int main()
{
int n, m, z = 0;
cin >> n >> m;
string s;
cin >> s;
for (int i = 0; i < n; i++)
{
t[s[i] - 'a']++;
}
int sum = m, x = 0;
for (int i = 0; i < 26; i++)
{
if (sum - t[i] >= 0)
{
x++;
sum -= t[i];
}
else
break;
}

for (int i = 0; i < n; i++)
{
if (s[i] - 'a' < x)
continue;
else if (s[i] - 'a' == x)
{
if (z < sum)
{
z++;
}
else
cout << s[i];
}
else
cout << s[i];
}
return 0;
}