集训划水记录

牛客多校 2021-4

I

推理题 + 逆序对搜索

全题复杂度要求$nlogn$；推理过程无代表性，不做赘述，复杂度为$n$；记录查找逆序对$nlogn$的写法。

计算一个已确定序列中逆序对的总数：

把序列分成前半段和后半段，均分别排序；例如1,3,6,7，2,3,4,5 这两段数，因为2小于3，故产生的逆序对是(3,2)(6,2)(7,2)，该数量可以直接计算出来，即(4 - 2 + 1)。通过这种方式递归前半段和后半段，注意到每次操作的过程，其实也是排序的部分过程，该复杂度等于归并排序，即$nlog_2n$。

代码：

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
43
44
int a[1000];
//solve函数l是操作序列的左端点，l为右端点(包含左端点不包含右端点)；序列长度为x时(即从a[0]到a[x-1])，调用函数solve(0, x);
void solve(int l, int r)
{
    int mid = (l + r) / 2;
    if (r - l > 1)
    {
        solve(l, mid);
        solve(mid, r);
    }
    int i = 0, j = 0, k = 0, b[mmax];
    while (i + l < mid && j + mid < r)
    {
        if (a[i+l] <= a[j+mid])
        {
            b[k] = a[i+l];
            i++;
            k++;
        }
        else 
        {
            b[k] = a[j+mid];
            j++;
            k++;
            ans += mid - l - i;
        }
    }
    while (i + l < mid)
    {
        b[k] = a[i+l];
        i++;
        k++;
    }
    while (j + mid < r)
    {
        b[k] = a[j+mid];
        j++;
        k++;
    }
    for (int tem = 0; tem < k; tem++)
    {
        a[tem + l] = b[tem];
    }
}

J

推理 + 从一个序列中找出长度不小于m的连续子序列，使得该序列平均值最大（该问题无限等价于POJ-2018）

该题推理部分很简单，现提供第二个问题的思路：

很显然平均值是在序列中最大数值和最小数值之间的，因此可以确定上界和下界。

给定一个数，判断序列中是否有长度不小于m的子序列，使得子序列平均值不小于该给出的数，我们来分析一下该操作的复杂度：

  • 将序列中所有的数均减去给定的数值，问题变成了“是否存在长度不小于m的子序列，使得子序列之和不小于零”，复杂度$On$
  • 求出前缀和，即通过递推操作求出数组：$s[i] = a[0]+a[1]+…+a[i]$，复杂度为$On$(前缀和非常好用，请熟练掌握)
  • 用min_s记录当前最小前缀和的值，用max_ans记录当前最大“长度不小于m的子序列”的和；min_s初始值为0，max_ans初始值为s[m-1]；i 从0开始累加，每一次进行操作：min_s = min(min_s, s[i]);，max_ans = max(max_ans, s[i+m] - min_s)，直到数组末尾。该操作可以保证每次判断的子序列长度不小于m，且对“和一定不是最大值”的子序列进行了有效剪枝；复杂度为$On$
  • 如果最终max_ans不小于零，则结果为“存在”，否则为不存在

综上分析，该操作复杂度为$On$。因此我们可以在区间内，用二分查找的办法来进行搜寻，如果中间值判断结果为“存在”，则二分搜索上半区间，否则搜索下半区间。通过确定推出搜索时上下界的差值，来保证最终结果的精确度。

实例代码：（这段代码貌似可以直接在类似题里面混用）

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
43
44
45
46
47
48
49
//check判断序列中是否有长度不小于x的子序列，使得子序列平均值不小于该给出的数
//a为原数组，n为数组长度，x为子序列最小长度，val为给定的值
bool check(int *a, int n, int x, double val)
{
    double b[mmax];
    double sum[mmax];
    sum[0] = 0;
    int value = (int)val;
    for (int i = 1; i <= n; i++)
    {
        b[i] = double(a[i]) - val;
        sum[i] = sum[i-1] + b[i];
    }
    double min_val = 1e8, max_ans = -1e8;
    for (int i = x; i <= n; i++)
    {
        min_val = min(min_val, sum[i-x]);
        max_ans = max(max_ans, sum[i] - min_val);
    }
    if (max_ans >= 0) return 1;
    else return 0;
}
//solve函数返回值是最大平均数，a, n, x解释同上
double solve(int *a, int n, int x)
{
    double max_v = -1e8, min_v = 1e8;
    for (int i = 1; i <= n; i++)
    {
        max_v = max(max_v, double(a[i]));
        min_v = min(min_v, double(a[i]));
    }
    double mid = (max_v + min_v) / 2.0;
//下一行的1e-7即精度
    while (max_v - min_v > 1e-7)
    {
        bool c = check(a, n, x, mid);
        if (c)
        {
            min_v = mid;
            mid = (max_v + min_v) / 2.0;
        }
        else
        {
            max_v = mid;
            mid = (max_v + min_v) / 2.0;
        }
    }
    return mid;
}

补充常用的“尺取法”

（先摸一会儿鱼）