题目"/>
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
更多推荐
Codeforces Round #143 (Div. 2) B. Magic, Wizardry and Wonders YY题目
发布评论