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

ACM练习——P4863 JerryC Loves Driving……

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

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

题目链接

题目分析

对于一层求和,其实就是一层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));
}