Codeforces Round #143 (Div. 2) B. Magic, Wizardry and Wonders YY题目

题目"/>

Codeforces Round #143 (Div. 2) B. Magic, Wizardry and Wonders YY题目

题意：

给你一个长度为n的序列每个元素的取值为[1,l] 然后进行如下操作，每次将 a[n - 1] - a[n] 替换a[n - 1]使原序列个数减1,最后得到一个数字d。给你长度n，最后得到的数d，和l。找去满足条件的序列。

思路：
这题真心不好想啊，首先我们能够退出 x1 - (x2 - (x3 - (.....)))得到x1 - x2 + x3 - x4 + x5 -... = d; 所以有(x1 + x2 + x3 ....) - (x2 + x4 + x6 + x8....) = d;这个公式，我想到这就卡住了不知道该怎么往下想了。 其实我们这里只要 s1表示奇数和，s2表示偶数和 s1 - s2 = d 我们现假设s1,s2中小的那个都取值为1,然后大的那个就确定+d 。 然后将总和平均加到对应的奇偶序列里面就好了。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <string>#define CL(a,num) memset((a),(num),sizeof(a))
#define iabs(x)  ((x) > 0 ? (x) : -(x))
#define Min(a,b) (a) > (b)? (b):(a)
#define Max(a,b) (a) > (b)? (a):(b)#define ll long long
#define inf 0x7f7f7f7f
#define MOD 1073741824
#define lc l,m,rt<<1
#define rc m + 1,r,rt<<1|1
#define pi acos(-1.0)
#define test puts("<------------------->")
#define maxn 100007
#define M 150
#define N 107
using namespace std;
//freopen("data.in","r",stdin);int ans[N];
int main(){int i;int n,d,l;while (~scanf("%d%d%d",&n,&d,&l)){CL(ans,0);int num1 = (n + 1)>>1;int num2 = n>>1;int s1,s2,t;//记录左右两边的和if (d > 0){s2 = num2;s1 = s2 + d;}else{s1 = num1;s2 = s1 - d;}int n1 = s1/num1;int n2 = s2/num2;//注意这里用double处理如果得到l.01那么肯定不行，存在值加的大于l了。if (1.0*s1/num1 <= l && 1.0*s2/num2 <= l){for (i = 0; i < n; i += 2){ans[i] += n1;}t = s1%num1;for (i = 0; i < n && t; i += 2,--t){ans[i]++;}for (i = 1; i < n; i += 2){ans[i] += n2;}t = s2%num2;for (i = 1; i < n && t; i += 2,--t){ans[i]++;}for (i = 0; i < n - 1; ++i) printf("%d ",ans[i]);printf("%d\n",ans[i]);}else printf("-1\n");}return 0;
}

转载于:.html