本解题报告的版权归 Ceeji 所有,转载请注明出处并保留本注释。
题目描述
我们定义连续串为一串整数,它的第一个元素为0,并且任两个相邻元素之差的绝对值为1。更精确的说,如果[a1, a2, …, an]为一个连续串,那么有:
对于任意的1<=ka1=0
任务:
写一个程序:
在文件SUM.IN中读入连续串的长度和连续串中所有元素的和;
找出一个给定长度的连续串,使其所有元素的和与给定的和相等,或者指出这样的连续串不存在。
将结果输出到文件SUM.OUT中。
输入格式:
在文本文件SUM.IN的第一行有一个整数n,满足1n10000,表示连续串中元素的个数。第二行为一个整数S,满足|S|<=50000000,表示连续串中所有元素之和。
输出格式:
如果能够找到满足条件的连续串,你应当在文本文件SUM.OUT的前n行输出n个整数(每行一个),表示连续串中的各个元素(第k个元素输出在第k行)。否则,文件应该只包含一个单词NIE(为波兰语的“否”)。
样例:
输入(SUM.IN):
8
4
输出(SUM.OUT):
0
1
2
1
0
-1
0
1

思路分析
本解题报告的版权归 Ceeji 所有,转载请注明出处并保留本注释。
本题采用构造法。时间复杂度O(n),空间复杂度O(n)。先建立一个从0到n-1的数列,并求出要求的和与数列的和的差值。如果差值为奇数则无解,如 差值为偶数,则逐渐减小差值。比如将最后一位改为降序,则差值减小2,倒数第二位改为降序则差值减小4,以此类推。可以先从前面减,减到很小的时候(不能 再减)再从右面减。所谓减就是把这一位改为上一位减一,而保持后面的升序。

完整代码

 
//By Ceeji 
//Date: 2009-4-10 
//Type: Gouzao 
//HAOI test 1 - Problem 1 : sum (POI) 
//State : Accepted 
Program sum; 
Const 
   inf='sum.in'; 
   ouf='sum.out'; 
   maxn=10000Var 
   n,s,i,j,l:longint; 
   x:longint; 
   q:qword; 
   b:array[1..maxn]of booleanbegin 
   q:=1; 
   assign(input,inf);  reset(input); 
   assign(output,ouf); rewrite(output); 
   fillchar(b,sizeof(b),0); 
   readln(n,s); 
   close(input); 
   x:=((n-1)*n div 2-s); 
   if odd(x) then begin writeln('NIE'); close(output); exitend; 
   l:=2; 
   while x>=(n-l+1)<<1 do 
   begin 
       b[l]:=true; 
       dec(x,(n-l+1)<<1); 
       inc(l); 
   end; 
   l:=1; 
   b[n-(x>>1)+1]:=true; 
   j:=0; 
   writeln(j); 
   for i:=2 to n do 
   begin 
     if b[i] then dec(j) else inc(j); 
     inc(ans,j); 
     writeln(j); 
   end; 
   close(output); 
end