时间: 1000ms / 空间: 131072KiB / Java类名: Main
背景
第二届『Citric杯』NOIP提高组模拟赛第一题
描述
Lemon认为在第一届『Citric』杯模拟赛中出的题目太简单了，于是他决定，这次要给参赛选手们一个下马威！ ^_^ Lemon手上有一个长度为n的数列，第i个数为xi。 他现在想知道，对于给定的a,b,c，他要找到一个i，使得a*(i+1)*xi^2+(b+1)*i*xi+(c+i)=0成立。 如果有多个i满足，Lemon想要最小的那个i。 Lemon有很多很多组询问需要你回答，多到他自己也不确定有多少组。所以在输入数据中a=b=c=0标志着Lemon的提问的结束。 更加糟糕的是，Lemon为了加大难度，决定对数据进行加密以防止离线算法的出现。 假设你在输入文件中读到的三个数为a0,b0,c0，那么Lemon真正要询问的a=a0+lastans,b=b0+lastans,c=c0+lastans. lastans的值是你对Lemon的前一个询问的回答。如果这是第一个询问，那么lastans=0 所有的询问都将会按上述方式进行加密，包括标志着询问的结束的那个询问也是这样。
输入格式
输入文件第一行包含一个正整数n，表示数列的长度。 输入文件第二行包含n个整数，第i个数表示xi的值。 接下来若干行，每行三个数，表示加密后的a,b,c值（也就是上文所述的a0,b0,c0）
输出格式
包含若干行，第i行的值是输入文件中第i个询问的答案。注意，你不需要对标志着询问结束的那个询问作答。 同时，标志着询问结束的询问一定是输入文件的最后一行。也就是，输入文件不会有多余的内容。
测试样例1
输入
5 -2 3 1 -5 2 -5 -4 145 -1 -6 -509 -9 -14 40 -3 -13 21 -3 -3 -3
输出
5 4 3 3
备注
第一个询问中，真实的a=-5+0=-5，b=-4+0=-4，c=145+0=145（第一个询问中lastans=0） 带入发现，i=5时，-5*(5+1)*2^2+(-4+1)*5*2+145+5=0，而其他的i均不符合条件。所以答案是5. 第二个询问中，真实的a=-1+5=4,b=-6+5=-1,c=-509+5=-504（lastans是上一个询问的答案的值，也就是5） 经带入发现，i=4时，4*(4+1)*(-5)^2+(-1+1)*4*(-5)+(-504)+4=0，满足条件，而其他的i均不满足条件，所以答案是4. 同理，第三个询问中真实的a=-5,b=-10,c=44.答案i=3 第四个询问中真实的a=0,b=-10,c=24，答案i=3 第五个询问中真实的a=0,b=0,c=0，此时我们发现这是一个标志着结束的询问，这个询问我们无需作出回答。
思路
FROM HZWER
我们考虑最后一行，因为其代表文件结束，所以解密后的a=b=c=0。那么我们可以知道倒数第二行的答案（LastAns=-a=-b=-c）。那么原始式子即转换成一个简单的三元一次式子（只和a,b,c有关），然后这解密后的值又可以由上一行的答案和输入的a0,b0,c0得到，于是就变成了一个只和LastAns有关系的一元一次式子，所以又可以得到了上一行的答案。所以这样一直算回去就好了。
出题人真是丧失
var i,j,l,m,n:longint; k1,k2:int64; x,a,b,c,ans:array[1..500000] of int64;function work1(i:longint):int64;begin exit( (i+1)*sqr(x[i]) );end;function work2(i:longint):int64;begin exit( x[i]*i );end;function work3(i:longint):int64;begin exit( i*x[i]+i );end;begin read(n); for i:=1 to n do read(x[i]); m:=0; while true do begin inc(m); read(a[m],b[m],c[m]); if (a[m]=b[m])and(b[m]=c[m]) then break; end; ans[1]:=0-a[m]; l:=1; for i:=m-1 downto 2 do begin j:=ans[l]; inc(l); k1:=a[i]*work1(j)+b[i]*work2(j)+c[i]+work3(j); k2:=work1(j)+work2(j)+1; ans[l]:=(-k1) div k2; end; for i:=m-1 downto 1 do writeln(ans[i]);end.