CSP 2021 12月

一 序列查询

针对这一题的思路很简单,直接使用一个pair数组记录所在的位置和大小进行排序.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <algorithm>
#define N 1010
using namespace std;
pair<int, int> a[N];
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i].first);
        a[i].second = i;
    }
    sort(a, a+n+1);
    int j = 0 ,ans = 0;
    for (int i = 0; i <= m - 1; i++) {
        while (a[j+1].first <= i&& j <= n) j++;
        if (j == n+1) j--;
        ans += a[j].second;
      //  printf("%d ",a[j].second);
    }
    printf("%d\n", ans);
}

二 序列查询新

这一题使用了一个估计的函数,求这个估计函数的结果和正确的结果之间的差距,我们可以使用的思路有两种,一种是二分+分块,一种是裸分块.

1. 分块

这种的思路其实很简单, 简单来说就是双指针的思想.
我们的数组A中的数据是 0 1 2 3… n- 1
B中的数据是 0 2 4 … (if r == 2)
B中的值同时也可以表示这个点的起始位置, a中的值也可以表示这个点对应的位置.
使用双指针的思想用i表示在a中的位置,j表示在b中的位置.

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
#include <iostream>
#include <algorithm>
using namespace std;
#define N 200100
#define ll long long
ll a[N], b[N], n, m, R;
int main() {
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    a[n+1] = m;
    R = m/(n+1);
    ll ans = 0, cnt = 0;
    for (cnt = 1; cnt*R < m;cnt++) b[cnt] = cnt*R;
    b[cnt++] = m;
    int i = 0, j = 0;
    while (i < n + 1 || j < cnt - 1) {
        if (a[i] == b[j]) {
            ans += (min(a[i+1], b[j+1]) - a[i])* abs(i - j);
            i++; j++;
        }
        else if (a[i] < b[j]) {
            ans += (min(a[i+1] ,b[j]) - a[i])* abs(j - 1 - i);
            i++;
        }
        else {
            ans += (min(a[i], b[j+1]) - b[j])* abs(i - j - 1);
            j++;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

2. 分块 + 二分

进行二分保证每次的分块的大小关系都是确定的

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
#include <bits/stdc++.h>
using namespace std;

long long h(long long i, long long r) { //求g(i)的前缀和h(i)
    if (i < 0) return 0;
    else return r * ((i + 1) / r - 1) * ((i + 1) / r) / 2 + (i + 1) % r * (i / r);
}

long long cal(long long fi, long long lft, long long rgt, long long r) { //给定一个f(i),计算区间里的|g(i)-f(i)|之和,前提是g(i)全部小于等于或者全部大于等于f(i)
    return abs(h(rgt, r) - h(lft - 1, r) - fi * (rgt - lft + 1));
}

int main()
{
	long long n, N, t;
	cin >> n >> N;
	vector<long long> a = {0};
	for (int i = 0; i < n; ++i) {
		cin >> t;
		a.push_back(t);
	}
	a.push_back(N);
	long long r = N / (n + 1), ans = 0;
	for (long long fi = 0; fi <= n; ++fi) { //遍历每个f(i)
		long long lft = a[fi], rgt = a[fi + 1] - 1;
		if (lft / r >= fi || rgt / r <= fi) ans += cal(fi, lft, rgt, r); //如果区间内g(i)全部小于等于或者全部大于等于f(i),直接使用cal函数
		else ans += cal(fi, lft, r * fi, r) + cal(fi, r * fi + 1, rgt, r); //否则将区间分成两半，分别使用cal函数
	}
	cout << ans << endl;
	return 0;
}