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

· · 题解

题目大意

给你每两个相邻数的和，再给你每一个数出现的次数，问你是否能求出和，不能则输出 Impossible。

分析

以样例三为例，我们整理一下便得到了每首歌出现的次数：


1 958
2 633
3 0
4 0
5 98
6 249
7 0
8 0
9 0
10 858
11 1020
12 489
13 0
14 2078
15 1166
16 0
17 0
18 845
19 1910
20 0

因为我们只知道两两相邻数的和，所以我们便假设 a_2 也出现了 958 次，则这样 a_2 会多算 325 次，那么就再假设 a_3 有 -325 个，那么 a_3 就少算 325 次，以此类推得到如下代码：

//fre[]表示出现次数，sum[]表示两两的和
    for(int i=1;i<n;i++)
    {
        ans+=fre[i]*sum[i];
        fre[i+1]-=fre[i],fre[i]=0;
    }

算到最后我们欣喜地发现 a_n 的次数消成了零，则代表没有漏下的，否则无解。

AC Code

#include<bits/stdc++.h>
#define int long long //不开long long见祖宗
#define endl "\n"
#define er puts("")
#define sc putchar(' ')
using namespace std;
const int N=2e5+5;
int sum[N],fre[N];
int read() //快读版子
{
    int x=0,a=1;char c=getchar();
    for(;c<'0'||c>'9';c=getchar())
        if(c=='-') a=-1;
    for(;c>='0'&&c<='9';c=getchar())
        x=x*10+c-'0';
    return x*a;
}
void write(int x) //快写版子
{
    if(x<0)x*=-1,putchar('-');
    if(x>9) write(x/10);
    putchar(x%10+'0');
    return;
}
signed main()
{
    int n=read(),m=read(),ans=0;
    if(m==1){puts("Impossible");return 0;} //m=1显然不成立
    for(int i=1;i<n;i++) sum[i]=read();
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read();
        fre[x]+=y;
    }
    for(int i=1;i<n;i++)
    {
        ans+=fre[i]*sum[i];
        fre[i+1]-=fre[i],fre[i]=0; //若fre[i]为正则代表少算了，否则为多算了
    }
    if(!fre[n]) write(ans);
    else puts("Impossible");
    return 0;
}