题解：P12006 【MX-X10-T2】[LSOT-4] 网易云

前言

解题思路

• 设第 $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}$。

代码实现

#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;
}