POI Sum of one-sequence 连续串之和 解题报告
题目描述
我们定义连续串为一串整数，它的第一个元素为0，并且任两个相邻元素之差的绝对值为1。更精确的说，如果[a1, a2, …, an]为一个连续串，那么有： 对于任意的1<=ka1=0
任务： 写一个程序： 在文件SUM.IN中读入连续串的长度和连续串中所有元素的和； 找出一个给定长度的连续串，使其所有元素的和与给定的和相等，或者指出这样的连续串不存在。 将结果输出到文件SUM.OUT中。
输入格式： 在文本文件SUM.IN的第一行有一个整数n，满足1n10000，表示连续串中元素的个数。第二行为一个整数S，满足|S|<=50000000，表示连续串中所有元素之和。
输出格式： 如果能够找到满足条件的连续串，你应当在文本文件SUM.OUT的前n行输出n个整数（每行一个），表示连续串中的各个元素（第k个元素输出在第k行）。否则，文件应该只包含一个单词NIE（为波兰语的「否」）。
样例： 输入（SUM.IN）： 8 4
输出（SUM.OUT）： 0 1 2 1 0 -1 0 1
思路分析
本题采用构造法。时间复杂度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=10000;
Var
n,s,i,j,l:longint;
x:longint;
q:qword;
b:array[1..maxn]of boolean;
begin
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); exit; end;
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.
题外话：我帮你整理了包括 AI 写作、绘画、视频（自媒体制作）零门槛 AI 课程 + 国内可直接顺畅使用的软件。想让自己快速用上 AI 工具来降本增效，辅助工作和生活？限时报名。
© 转载需附带本文链接，依据 CC BY-NC-SA 4.0 发布。