在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 閱讀(542)
評論(1) 編輯 收藏 引用 所屬分類:
acm 、
數學