题解：P17678 [IO 2025 #4] 拆钞幻术

jcy2345 · 2026-10-22 18:42:10 · 题解

蒟蒻的第一篇题解

题目传送门

题意：

初始有一个数 S，每次可以把一个数 y 拆成 a+b，花费为 ab，拆分后总和不变。

每次询问要求板上必须出现区间 [l,r] 中的所有数，求最小花费；如果无法构造，输出 -1。

思路：

每次拆分 y=a+b 的花费是 ab，而总和始终等于初始的 S。

设最后板上留下的数是 t_1,t_2,\dots,t_k，可以推出总花费为：

所以要让花费最小，就要让 \sum t_i^2 尽可能大。

题目要求板上必须包含 [l,r] 中的所有数，记它们的和为 T，平方和为 \sum_{x=l}^{r}x^2。剩下的 S-T 如果继续拆，只会让平方和变小，因此最优做法是不再拆，直接保留一个数 S-T。

代入后得到答案：

如果 T>S，说明无法构造，输出 -1。

用前缀和与前缀平方和预处理，每次询问 O(1) 计算。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
long long sum[N], sq[N],S,T,res;
int n,q,a[N],l,r;
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
        sq[i]=sq[i-1]+1LL*a[i]*a[i];
    }
    while(q--){
        cin>>l>>r>>S;
        T=sum[r]-sum[l-1];
        if(T>S){
            cout<<"-1"<<endl;
            continue;
        }
        res=(2*S*T-T*T-sq[r]+sq[l-1])/2;
        cout<<res<<endl;
    }
    return 0;
}