集训队作业9803sum of one-sequence解题报告

1、解题题意描述本题要求的是简单数列的和的情况。而简单数列的变化没有一定的模式，很难找到一个相应的模型来研究。试着改变一下，将简单数列a1，a2，a3an改写为a2-a1，a3-a2an-an-1。这样形成的数列就是单纯的由 1 和-1 组成的了。记这个数列为b1，b2，b3bn-1，而这个数列的和就可以表示为（n-i）*bi（i1，n-1）。算法分析本题的关键就在于如何来找到和为S 的简单数列。首先，S过 b 数列全为 1 时的最大值（n-1）*n div 2，也不能小于 b 数列全为-1 时的最小值-（n-1）*n div 2。更进一步的，S 必须与（n-1）*n div 2 同奇偶。对此的证

2、明如下：b 数列全为 1 时的和为（n-1）*n div 2，对于 b 数列的任意一种放法，若 i 使得 bi=-1。这时，数列的和减少了 2*（n-i）是一个偶数。所以无论 b 数列如何变化，数列和的奇偶性是不变的。证一个等价题：b 数组中元素个为了证明满足以上条件的简单数列一定存在，数为 n-1 的数列的和可以为（n-1）*n div 2，-（n-1）*n div 2上所有与（n-1）*n div 2 同奇偶的数。用数学归纳法。n=2 时，命题显然成立。当 n=k 时命题成立，则 n=k+1 时b1 取 1 时，由归纳假设，数列的和可以为k+1+（k+1）*k div 2，k+1-（k+1

3、）*k div 2上所有与（k+1）*（k+2）div 2 同奇偶的数，即S（k+1）*（k+2）div 2，0 （k+1）*（k+2）div 2，（k+1）*（2-k）div 2。b1 取-1 时，由归纳假设，数列的和可以为-k-1+（k+1）*k div 2，-k-1-（k+1）*k div 2上所有与（k+1）*（k+2）div 2 同奇偶的数，即 S0，-（k+1）*（k+2）div 2（k-2）*（k+1）div 2，-（k+1）*（k+2）div 2。综上，bk+1 可取（k+1）*（k+2）div 2，-（k+1）*（k+2）div 2上的所有数。证毕。有了上面的性质，在选取 b

4、 数列的第 p 位时只要使得S-（n-i）*b（ii1，p）不超过（n-p-1）*（n-p）div 2 也不小于-（n-p-1）*（n-p）div 2 即可。算法效率时间复杂度：O（n）空间复杂度：O（1）算法效率：所有测试数据都能在瞬间出解。源程序constinf ouf=sum.in;=sum.out;varn,m,i,max,min,now:long;beginassign(input,inf); assign(output,ouf); reset(input); rewrite(output); readln(n); readln(m);if (odd(n*(n-1) div 2-m) or (mn*(n-1) div 2) or (m-n*(n-1) div 2) then wrin(NIE)else beginmax:=n*(n-1) div 2;min:=-n*(n-1) div 2; now:=0;wrin(now);for i:=n-1 downto 1 do beginif min+2*i=m then beginnow:=now+1;min:=min+2*i;endelse beginnow:=