主页
Featured image of post ACM练习——P4863 JerryC Loves Driving……

ACM练习——P4863 JerryC Loves Driving……

一言加载中_(:з」∠)_……

文章字数:4041
预计阅读时长: 分钟

题目链接

题目分析

对于一层求和,其实就是一层for,那么两层求和就是两层for,也就是二维的。
而对于求和O(n)的优化计算方法,最基本的就是转换为等差数列O(1)计算

我们将两层求和的每一项列表观察(看是否有等差数列),得出下表:

求和表
求和表

图片来自于「Insouciant21」的题解

观察发现,对于每一列,是类似呈等差数列的形式的,
对于第\(i\)列,是由\(i\)\(0 \sim n\)的等差数列组成。

如第四列:为\(4\)\(0,1,2,\cdots,n\)的等差数列组成。

因此我们就可以O(1)计算出每一列的和,那么就只用按列循环依次求和,O(n)的时间内求出结果。


想到求解方法后,我们来确定求和计算范围。

以下以\(A=2, B=7\)来举例。

求和表范围1
求和表范围1

对于题上给出的两个界:上界\(A\)和下届\(B\)
按照题中所给公式,最初始的范围,则对应图中红色框选内容。
由于0部分不影响,所以也可以看成蓝色矩形部分。

但如果直接这样进行计算,会发现会有很多要考虑的地方,或说运用等差数列时有很多边界的处理。

如图中所给例子:
对于\(2\)这一列,则上方\(1\)并不完全属于\(n\)个等差数列中,要排除。
对于\(3\)这一列,则下方\(-2\)并不完全属于\(n\)个等差数列中,要排除。

于是我们可以想到对于求\(f(A \sim B)\)这一范围,可以转化为求\(f(B)-f(A-1)\)这两范围的差
如图所示:

求和表范围2
求和表范围2

则可以只用考虑下界的不符合。

这是一个很重要的方法
将两个不确定的界的函数(\(f(x \sim y)\)),转化为两个有一个确定的界的函数之差(\(f(C \sim x)-f(C \sim y)\))。(如定积分中经常运用)

解题方法

O(n)方法

对于每一列\(i\)
其和(的绝对值)为:\(i\)\(1,2,3,\cdots,n\)的等差数列的和,加上剩余非等差数列的部分。

每一列均为\(n - 0 + 1\)\(n + 1\)项。

等差数列部分:
首项——\(a_1 = 0\)
末项——\(a_n = (n + 1) / i - 1\);【原因是:首先项数有\(n+1\)项(包括0行),整除\(i\),则得到等差数列的项数,那么末项\(a_n = a_1 + (n-1)*d\),即为项数\(-1\)
项数——\(n = (a_n - a_1) / 1 + 1\)(公差为1),即为\(a_n + 1\)

非等差数列部分:
每一项均为\(a_n + 1\)
前面已经计算了\(cnt * i\)项,所以剩余部分的项数为\(n + 1 - (cnt * i)\)

O(√n)方法

首先根据上述的规律可以发现:

  1. 每一个数重复次数是按列递增的。

    \(1\)列是\(1,2,3,\cdots,n\),每个数出现\(1\)次;第\(2\)列是\(1,1,2,2,3,3,\cdots,n,n\),每个数出现\(2\)次。

  2. 奇数行和偶数行的符号是一样的。

基于以上两点,我们发现:
如果存在间隔的几列(使符号相同,能合并处理),满足他们有的数字为一样的(比如都只有\(1,2,3\),只是出现次数不同)。

如求\(f(33)\)

例一:
\(9\)列为\(0,0,\cdots,0;-1,-1,\cdots,-1;-2,-2,\cdots,-2;-3,-3,-3,-3,-3,-3,-3\)\(9\)\(0\)\(9\)\(-1\)\(9\)\(-2\)\(7\)\(-3\)
\(11\)列为\(0,0,\cdots,0;-1,-1,\cdots,-1;-2,-2,\cdots,-2;-3\)\(11\)\(0\)\(11\)\(-1\)\(11\)\(-2\)\(1\)\(-3\)
为下图中蓝色两列。

例二: 第\(12\)列为\(0,0,\cdots,0;1,1,\cdots,1;2,2,\cdots,2\)\(12\)\(0\)\(12\)\(1\)\(10\)\(2\)
\(14\)列为\(0,0,\cdots,0;1,1,\cdots,1;2,2,2,2,2,2\)\(14\)\(0\)\(14\)\(1\)\(6\)\(2\)
\(16\)列为\(0,0,\cdots,0;1,1,\cdots,1;2,2\)\(16\)\(0\)\(16\)\(1\)\(2\)\(2\)
为下图中橙色三列。

举例求和表
举例求和表

那么这几列的等差数列,是可以合并为一个更大的等差数列一起求和的。

上例一中:
\(9\)列中的有\(9\)\(-1\)\(9\)\(-2\)
\(11\)列中的有\(11\)\(-1\)\(11\)\(-2\)
于是这两列便可合并为\(20\)\(-1\)\(20\)\(-2\)一起用高斯求和(等差数列求和)。

但对于最后的一项数(如上例一中的\(-3\)),因为出现次数不一致,不能很好的直接合并,需要单独处理计算,
所以我们只能合并倒数第二项用高斯求和,然后对剩下的最后一项单独处理

这样就可以在计算的过程中合并几列同时计算,达到减少操作降低复杂度的效果。
不过至于是否为O(\(\sqrt{n})\)的复杂度我就没证了_(:з」∠)_……


那么重点就是:

  1. 怎么分奇偶,找到哪几列出现数字相同。

    先算出这一列能出现的最大数,然后再用\(n\)除以这个数,得到只能出现到这个数的最大列

    比如求\(f(33)\),处理第\(9\)列时,
    \(9\)列能出现最大的数是\(33/9\)\(3\),但只能出现到\(3\)的最大列为\(33/3\)为第\(11\)列(可以配合上面给出的图来理解)。

  2. 怎么处理计算不能合并的最后一项。

    首先最后一项这个数我们知道是好多(为\(n/i\)),所以关键是求他有多少个
    由第一点发现可知,对于下一个间隔列,前面的项出现次数均多了\(2\)次,
    或者说最后一项出现次数依次减\(2\)
    所以其实对于最后一项的出现次数,也是个等差数列。
    找到等差数列的几个参数求和,得到有多少个。

    1. 首项:对应最后一列\(i\),总项数为\(n+1\)个,前面项每个数均出现了\(i\)次,一共有\(N\)个数(计算方法就是等差数列求项数)。
    2. 末项:对应第一列,计算方法同首项。
    3. 项数:就是合并了几项。

    比如求\(f(33)\),处理第\(12\)列时,最大列到\(16\)

    1. 首项——第\(16\)列中:前面的项(\(0\)\(1\))均出现了\(16\)次,所以这一列最后一项(\(2\))出现次数为\(2\)次。
    2. 末项——第\(12\)列中:前面的项均出现了\(12\)次,所以这一列最后一项出现次数为\(10\)次。
    3. 项数——合并了\(12\)\(14\)\(16\)列,项数为\(3\). 则可求得最后一项\(2\)一共出现了\((2+10)*3/2=18\)次。
  3. 怎么处理计算合并后的等差数列。

    方法就同\(O(n)\)方法中求等差数列了,
    只是在最后一项(an)和乘的次数(由乘i变成了乘cnt)变了一点。

    对于合并后的出现次数,也是个高斯求和。

    比如求\(f(33)\),处理第\(9\)列时,最大列到\(11\)
    \(9\)列每一项出现次数为\(9\)次,
    \(11\)列每一项出现次数为\(11\)次,
    所以一共出现\(9+11 = 20\)次,

个人代码

//P4863 [JerryC Loves Driving](https://www.luogu.com.cn/problem/P4863)
#include <bits/stdc++.h>
#define ALL(NAME_i, BEGIN, TO) \
    int NAME_i = BEGIN;        \
    NAME_i <= TO;              \
    NAME_i++
#define SGN (nega ? -1 : 1)
typedef long long LL;
using namespace std;
LL solve(int n)
{
    LL ans = 0;
    bool nega = 1;
    for (ALL(i, 1, n))
    {
        LL a1 = 0,                                      //首项
            an = (n + 1) / i - 1,                       //末项
            cntSeq = an + 1;                            //项数
        ans += i * ((a1 + an) * cntSeq / 2) * SGN;      //先求等差数列的和
        ans += (n + 1 - (cntSeq * i)) * (an + 1) * SGN; //再计算剩下的部分
        nega = !nega;                                   //变符号
    }
    return ans;
}

LL solve_Odev(const int &n, bool odd)
{
    LL ans = 0;
    int maxColumn;
    bool nega = odd ? 1 : 0;
    for (int i = odd ? 1 : 2; i <= n; i = maxColumn + 2) //注意赋值语句为maxColumn + 2,也就是合并处理完几列后,直接跳到处理完的列后面。
    {
        //1. 怎么分奇偶,找到哪几列出现数字相同。
        LL maxNum = n / i;           //当前列能出现的最大数(或最后一项)
        maxColumn = n / maxNum;      //只能出现到这个数的最大列
        if (odd && !(maxColumn & 1)) //本来处理奇数列,但算出来最大列为偶数情况
            maxColumn--;
        if (!odd && (maxColumn & 1)) //本来处理偶数列,但算出来最大列为奇数情况
            maxColumn--;
        /* 对应于上图中,当n = 33, i = 12时:
        maxNum    = 2
        maxColumn = 16	【对应为 合并12~16列。
        */

        //2. 怎么处理计算不能合并的最后一项。
        int minCnt = (n + 1) - maxColumn * maxNum,  //首项——这几列中,最后一项出现最少的次数(为最后一列,用maxColumn)
            maxCnt = (n + 1) - i * maxNum,          //末项——这几列中,最后一项出现最多的次数(最当前列,用i)
            cntColumn = ((maxColumn - i) >> 1) + 1; //项数——合并了几列
        /* 注意的点:
        1. 总项数为n+1个,因为0也算!
        2. 不为maxNum - 1,因为0也算!【前面项的项数为((maxNum-1) - 0) / 1 + 1,即maxNum
        */
        int cntNum = ((maxCnt + minCnt) * cntColumn) >> 1; //求得关键——最后一项有多少个(高斯求和)
        ans += maxNum * cntNum * SGN;
        /* 对应于上图中,当n = 33, i = 12, maxColumn = 16时:
        minCnt    = 2		【对应为 最后一列有2项
        maxCnt    = 10		【对应为 第一列有10项
        cntColumn = 3		【对应为 合并了3列
        cntNum    = 18		【对应为 最后一项由18个
        */

        //3. 怎么处理计算合并后的等差数列。
        LL a1 = 0,           //首项
            an = maxNum - 1, //末项
            cntSeq = an + 1; //项数
        /* 以上跟O(n)方法的几乎一样。
        区别在于当这一列完全为等差数列时(不存在不为等差数列的部分):
        O(n)方法计算等差数列和,会包括最后一项;
        O(sqrt(n))方法计算等差数列和,不会包括最后一项。
        */
        int cnt = ((i + maxColumn) * cntColumn) >> 1;   //合并后出现次数(高斯求和)
        ans += cnt * (((a1 + an) * cntSeq) >> 1) * SGN; //(高斯求和)
    }
    return ans;
}
LL solve_block(const int &n)
{
    LL ans = 0;
    ans += solve_Odev(n, 0) + solve_Odev(n, 1);
    return ans;
}

/*
LL slove_original(int A, int B)
//最原始的做法,但考虑的会更复杂所以未完成为错误的
//错误点为为考虑开始部分为非等差数列
{
    LL ans = 0;
    bool nega = 1;
    for (ALL(i, 1, B))
    {
        int seqBgeinIndex = A + max(i - A, 0), cnt = (B - seqBgeinIndex + 1) / i, seqEndIndex = seqBgeinIndex + cnt * i - 1;
        LL a1 = max(A / i, 1), an = a1 + cnt - 1;
        ans += i * ((a1 + an) * cnt / 2) * SGN;
        ans += (B - seqEndIndex) * (an + 1) * SGN;
        nega = !nega;
    }
    return ans;
}
*/
int main()
{
    int A, B;
    scanf("%d%d", &A, &B);
    //printf("%lld\n", solve(B) - solve(A - 1));
    printf("%lld", solve_block(B) - solve_block(A - 1));
}