3106: [cqoi2013]棋盘游戏
3144: [Hnoi2013]切糕

3119: Book

高橋直樹 posted @ 2013年4月18日 08:24 in BZOJ with tags bzoj , 1202 阅读

http://www.lydsy.com/JudgeOnline/problem.php?id=3119

RunID User Problem Result Memory Time Language Code_Length Submit_Time
393153 Liu_Ts 3119 Accepted 904 kb 328 ms C++ 504 B 2013-04-18 07:59:10

 

题意

要求构造一个序列,

满足,长度为N,和为M,第一个数是X,

从第二项开始一定比前一项大A或比前一项小B;

保证有解。

题解

如果在第i个位置上+A,他会对所有i以后(N-i+1)个数造成影响,

即对和造成的影响是+(N-i+1)*A

那么设+A操作总共对x个数造成影响,-B操作总共对y个数造成影响。

列得:

     xA-yB=M-N*X;

     x+y=n*(n-1)/2;

可以把x、y解出来。

问题就变成了用1..n-1之间的数去凑x或者y。

就从n-1开始,不断减小x就可以了。

 

#include<cstdio>
#include<cstring>
using namespace std;
long long N,M,n,m,x,y,X,A,B;
bool f[100011];
int main()
{
	scanf("%lld%lld%lld%lld%lld",&N,&X,&A,&B,&M);
	m=M-N*X;n=N*(N-1)/2;
	x=(m+B*n)/(A+B);y=n-x;
	int now=N-1;
	while(x)
	{
		if (x-now>=0)
			f[now]=1,x-=now;
		now--;
	}
	printf("%lld",X);
	for(int i=N-1;i>=1;i--)
	{
		if(f[i]) X+=A;else X-=B;
		printf(" %lld",X);
	}
	puts("");
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter