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

2011hym · 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 发现格式不太好看，改了亿点。