在poi的列表上是easy。。。。
我倒。。这也easy。。。。。。
这道题多亏了javaman。。呵呵。。这一次。。他讲的挺清楚的。。。谢谢他一下
题目大意：
根据输入，序列的长度，序列和，求这样一串序列
序列满足以下情况：
- for any k, such that 1 <= k < n : |ak - ak+1| = 1 and
- a1 = 0
如果没有如此序列则输出"No"
我们假设n-->序列长度，S-->序列和；
S=sigma a[i](1<=i<=n)
令bi=a[i+1]-a[i] (1<=i<n)
S=sigama b[i]+sigama a[i] (1<=i<n) ----> S= sgama (n-i)b[i]; (1<=i<n)//迭代加一下就能推出来
b[i]-->-1 or 1
S=sigama (n-i)(b[i]+1)-sigama(n-i)
=2*sigama ((n-i)(b[i]+1)/2) - n*(n-1)/2
d[i]=(b[i]+1)/2-->0 or 1
根据上式得：
no-->
1: S+n*(n-1)/2 为奇数
2: abs(S)>n*(n-1)/2 //
important ....我就是这里一直错...绝对值...没考虑....
#include<iostream>
#include<math.h>
int N,S;
int main()
{
int std,i,d,pre;
int T;
scanf("%d",&T);
for(int j=1;j<=T;j++)
{
scanf("%d%d",&N,&S);
std=(N*(N-1))/2;
if((S+std)%2||abs(S)>std)
{
printf("No\n");
if(j!=T)printf("\n");
continue;
}
printf("0\n");
for(pre=0,std+=S,std/=2,i=1;i<N;i++)
{
if(std>=N-i)
{
d=1;
std-=N-i;
}
else d=0;
printf("%d\n",pre=2*d-1+pre);
}
if(j!=T)printf("\n");
}
return 0;
}posted on 2008-07-12 12:08
zoyi 阅读(520)
评论(1) 编辑 收藏 引用 所属分类:
acm 、
数学