专栏文章

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

HHZEason_Ai
P12006题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miprahgb
此快照首次捕获于
2025/12/03 16:39
3 个月前
此快照最后确认于
2025/12/03 16:39
3 个月前
查看原文

题目大意

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

分析

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

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
因为我们只知道两两相邻数的和，所以我们便假设 a2a_2 也出现了 958958 次，则这样 a2a_2 会多算 325325 次，那么就再假设 a3a_3 有 −325-325 个，那么 a3a_3 就少算 325325 次，以此类推得到如下代码：
CPP
//fre[]表示出现次数，sum[]表示两两的和
	for(int i=1;i<n;i++)
	{
		ans+=fre[i]*sum[i];
		fre[i+1]-=fre[i],fre[i]=0;
	}
算到最后我们欣喜地发现 ana_n 的次数消成了零，则代表没有漏下的，否则无解。

AC Code

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

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...