POI Sum of one-sequence 连续串之和 解题报告

题目描述

我们定义连续串为一串整数,它的第一个元素为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

思路分析

本题采用构造法。时间复杂度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 工具来降本增效,辅助工作和生活?限时报名

当前页阅读量为: