P8590 『JROI-8』这是新历的朝阳，也是旧历的残阳题解

wdgm4 · 2022-10-23 17:01:58 · 题解

~~考试时没考虑到会爆 long long ，痛失 30 分，发题解留个纪念。~~

暴力的思路

我首先思考如何暴力（首先提醒，暴力会超时，但可以从暴力出发引出正解,~~反正我考试时先打的暴力，再去探索 AC 思路~~，如果想直接看 AC 思路可以跳过），题目中说如果将 a 分成 m 段（可以有空段），并从前往后第 i 段内的每个数都加上 i。我考试时读到这，一个~~邪恶的~~贪心思路浮出我的脑海。例如题目样例，我们可以像下面这样：

[-3][][]....[][1,2,2]

利用贪心，我们让负数都放在最左面的一段里，让正数放在最右面的一段里，这样既能保证负数在加 i 后还为负数时平方最大，正数平方最大。但有可能负数加上 i 变为正数且它的平方比原来的平方大，所以我们只需要加一个判断即可。

超时代码

#include<bits/stdc++.h>
#define XD 114514

using namespace std;
int n,k;
const int mod=998244353;
long long a[1000010],ans;
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    } 
    for(int i=1;i<=k;i++){
        for(int j=1;j<=n;j++){
            if(abs(a[j]+1)>abs(a[j]+i)){//判断放最左面还是最右面
                ans+=(a[j]+1)*(a[j]+1);
                ans%=mod;
            }else{
                ans+=(a[j]+i)*(a[j]+i);
                ans%=mod;
            }
        }
    }
    cout<<ans;
    return 0;
}

时间复杂度：O(nk)。

当然，由于是暴力，我们只能得 30 分，其他全部 TLE。看来需要优化一下了。

AC思路

让我们返回到题目界面（传送门），题目中要算的公式整理为 \sum\limits_{i=1}^k {\sum\limits_{j=1}^na_j^2}（其中 a_j 的值随 i 的变化而变化），我们简单转换一下，变成 \sum\limits_{i=1}^n{\sum\limits_{j=1}^ka_i^2}（其中 a_i 的值随 j 的值变化而变化），而在新算式中，\sum\limits_{j+1}^ka_i^2 能够用 O(1) 的复杂度算出来。

我们可以先用一个前缀和 b，b_i 表示前 i 个数的平方的和。计算时分两种情况：

如果 a_i 大于等于 0，在分段中放在最右面一定最优，所以用前缀和计算即可。
如果 a_i 小于 0，在分段时最优的分段位置不同，需要特殊判断（具体内容请看代码）。

思路就先差不多，下面放下代码。

code

#include<bits/stdc++.h>
#define XD 114514

using namespace std;
long long n,k;
long long m,f;
const long long mod=998244353;
const int MAXN=20000000;
long long a[1000010];
long long ans,num;
int b[20000010];//前缀和
int main(){
    cin>>n>>k;
    for(long long i=1;i<=MAXN;i++){
        b[i]=(b[i-1]+i*i%mod)%mod;//计算前缀和
    }
    for(register int i=1;i<=n;i++){
        num=0;
        scanf("%lld",&a[i]);
        if(a[i]<0){//分情况讨论
            m=(a[i]+1)*(-2)+1;
            f=-(a[i]+1);
            num+=min(m,k)*1ll*f%mod*f;//注意这里一定要取模一次，不然会爆long long
            num%=mod;
            if(k>m){
                num+=(b[k-m+f]*1ll-b[f]+mod)%mod;
                num%=mod;
            }
        }else{
            num+=(b[a[i]+k]*1ll-b[a[i]]+mod)%mod;
            num%=mod;
        }
        ans+=num;
        ans%=mod;
    } 
    cout<<ans%mod;
    return 0;
}

时间复杂度：O(n)（还要加一个计算前缀和的大常数）

注意事项

注意取模问题，算减法取模时要先加上 mod 再取模。
在几个数连乘时，要记得在中间取模，不然会爆 long long，~~然后痛失 30 分~~。
前缀和数组千万不要开 long long，不然你会MLE。

P8590 『JROI-8』这是新历的朝阳，也是旧历的残阳 题解