自动搬运

查看原文

来自洛谷，原作者为

	2011hym 暴力占据大脑，打表代替思考 | 寒鸦栖枯地，拿分靠暴力 | 空山不见人，爆0就红温

搬运于2025-08-24 23:12:03，当前版本为作者最后更新于2025-03-30 18:43:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

题目背景还是太超标了，跟我的年度曲风一模一样。

被做局了。

解题思路

• 设第 $i$ 首歌的好听值为 $x_i$，则题目给出的条件是 $x_i + x_{i+1} = S_i$。
• 通过这些方程，我们可以用 $x_1$ 表示所有的 $x$。例如：
  • $x_2=S_1-x_1$
  • $x_3=S_2-x_2=S_2-S_1+x_1$
  • $x_4=S_3-x_3=S_3-S_2+S_1-x_1$
  • 以此类推，可以发现 $x_i$ 可以表示为 $(-1)^{i+1}x_1+c_i$，其中 $c_i$ 是由 $S$ 数组决定的常数。

过程分析

• 总的好听值可以表示为 $x_1$ 的线性函数：$A\cdot x_1 + B$，其中 $A$ 和 $B$ 是由听歌操作和 $S$ 数组决定的常数。
• 如果 $A=0$，那么总和与 $x_1$ 无关，可以直接计算 $B$。
• 如果 $A\neq 0$，则无法确定总和，输出 Impossible。

最终计算

• 对于每次听歌操作 $a_i,b_i$，对应的 $x_{a_i}$ 的系数会增加 $b_i$。
• 将 $x_{a_i}$ 表示为 $(-1)^{a_i+1}x_1+c_{a_i}$，则总和中 $x_1$ 的系数 $A$ 就为 $\sum_{i=1}^m (-1)^{a_i+1} b_i$。
• 如果 $A=0$，则总和为 $B=\sum_{i=1}^m b_i\cdot c_{a_i}$。

是不是觉得很难？

其实主要代码只有 $7$ 行，已经很简便了。

代码实现

前面讲的思路很详细，就不加注释了。

#include <bits/stdc++.h>
using namespace std;
#define int long long
int s[100010],sum[100010],n,m,a,b,A,B;
signed main(){
    cin>>n>>m;
    for(int i=1;i<n;i++){
        cin>>s[i];
        sum[i]=sum[i-1]+((i%2==1)?s[i]:-s[i]);
    }
    for(int i=0;i<m;i++){
        cin>>a>>b;
        A+=((a%2==1)?1:-1)*b;
        if(a>1){
            B+=b*((a%2==1)?sum[a-1]:-sum[a-1]);
        }
    }
    if(A!=0){
        cout<<"Impossible";
    }else{
        cout<<-B;
    }
    return 0;
}

~一下秒了。~

update：2025.8.3 发现格式不太好看，改了亿点。