下载文档原格式
NOIP2023普及组解题报告1. 题目背景NOIP（全国青少年信息学奥林匹克竞赛）是中国最重要的信息学竞赛之一，旨在选拔出优秀的信息学人才。
本文将解析NOIP2023普及组的题目并给出详细的解题思路。
2. 题目描述题目一：数找数给定一组数字，从中选择出两个数字，它们的和正好等于给定的目标数。
假设给定的数字集合中只有一组解。
请编写程序找出这两个数字并输出其下标。
输入： - 第一行为一个整数n，表示数字的个数。
- 第二行为n个以空格分隔的整数，表示一组数字。
- 第三行为一个整数target，表示目标数。
输出： - 输出两个整数i和j，表示所选数字的下标（从1开始计数，索引间以空格分隔）。
题目二：矩阵变换给定一个大小为n x m的矩阵，请编写程序将其顺时针旋转90度。
输入： - 第一行为两个正整数n和m，表示矩阵的行数和列数。
- 接下来的n行为矩阵的元素，每行包含m个以空格分隔的数字。
输出： - 输出顺时针旋转后的矩阵，每行包含n个以空格分隔的数字。
题目三：字符串缩写给定一个字符串，请编写程序将其缩写。
输入： - 输入为一行字符串，长度不超过100个字符。
- 字符串中只包含英文小写字母。
输出： - 输出为缩写后的字符串。
3. 解题思路题目一：数找数本题通过使用两个指针，一个指向数组开始，一个指向数组末尾，不断向内扩展判断两个指针对应的数字之和与目标数的大小关系，直到找到解为止。
具体步骤如下：1.定义两个指针left和right，初始时分别指向数组的第一个和最后一个元素。
2.循环执行以下步骤：–如果left和right对应的数字之和等于目标数，则输出left+1和right+1，结束循环。
–如果left和right对应的数字之和大于目标数，则将right 向左移动一位。
–如果left和right对应的数字之和小于目标数，则将left 向右移动一位。
题目二：矩阵变换本题的思路是将原矩阵逐个读入，并按照顺时针旋转的规律重新输出。
NOIP2009xx组复赛试题解题报告xx1、多项式输出本题只是一个基本知识点考核的一个题目，主要是看参赛选手的细心程度，无算法体现。
先定义一个系数的数组a[105]。
首先这一题解题的大的方向需要考虑两点，多项式系数a[i]大于零和小于零两种情况，因为系数为零时不输出该项，而大于零的要求输出含有“+”号，小于零的直接输出。
然后在分项进行处理：第一项要单独处理，在处理第一项时有3种情况如下：If (a[i]==1)Else if (a[i]==-1)Else if (a[i]!=0)接着对第二项到第n-1项进行处理这里在循环里面处理又有（a[i]>0 && a[i]!=1）（a[i]==1）（a[i]<0&& a[i]!=-1）（a[i]==-1）这四种情况分别讨论。
然后对a[n-1]项进行处理，同上面的循环里的处理方法只要注意幂指数为1的时候不需要输出就可以了，省略幂指数。
最后对常数项处理，分两种情况，a[n]>0和a[n]<0两种情况分别讨论最终即可解出本题。
参考程序如下：#include"stdio.h"main(){FILE *fin,*fout;int i,a[105],n;fin=fopen("poly.in","r");fout=fopen("poly.out","w");fscanf(fin,"%d",&n);for(i=0;i<=n;i++)fscanf(fin,"%d",&a[i]);if(a[0]==1)fprintf(fout,"x^%d",n);else if(a[0]==-1)fprintf(fout,"-x^%d",n);else if (a[0]!=0)fprintf(fout,"%dx^%d",a[0],n);for(i=1;i<n-1;i++){if(a[i]>0 && a[i]!=1) fprintf(fout,"+%dx^%d",a[i],n-i);if (a[i]==1)fprintf(fout,"+x^%d",n-i);if(a[i]<0 && a[i]!=-1)fprintf(fout,"%dx^%d",a[i],n-i);if (a[i]==-1)fprintf(fout,"-x^%d",n-i);}if(a[n-1]>0 && a[n-1]!=1)fprintf(fout,"+%dx",a[n-1]);if(a[n-1]==1)fprintf(fout,"+x");if(a[n-1]<0&&a[n-1]!=-1)fprintf(fout,"%dx",a[n-1]);if(a[n-1]==-1)fprintf(fout,"-x");if(a[n]>0)fprintf(fout,"+%d",a[n]);if(a[n]<0)fprintf(fout,"%d",a[n]);fclose(fin);fclose(fout);}2、分数线划定本题就是一个基本的简单排序题目，由于数据范围比较小，不需要用到快排或者其他排序，只要会一种基本的排序即可，比如用最熟悉的冒泡就可以完成该题的所有测试数据。
NOIP2008普及组复赛解题报告一、ISBN号码基础字符串处理题，心细一点的基本都能得满分。
参考程序：program isbn;constinp='isbn.in';oup='isbn.out';vari,j,k,ans:longint;s:string;ch:char;procedure flink;beginassign(input,inp);reset(input);assign(output,oup);rewrite(output);end;procedure fclose;beginclose(input);close(output);end;beginflink;readln(s);// 输入字符串j:=0;i:=1;ans:=0;while j<9 dobeginif s[i] in ['0'..'9'] then//如果是数字,那么累加到ans中,共9个数字begininc(j);inc(ans,(ord(s[i])-ord('0'))*j);end;inc(i);end;ans:=ans mod 11;计算识别码if ans=10 then ch:='X' else ch:=chr(ord('0')+ans);//把识别码转换成字符,方便输出if s[length(s)]=chthen write('Right')else write(copy(s,1,12)+ch);//输出正确的识别码fclose;end.二、排座椅用的是赛前集训时提到的贪心，当时说某些题目用贪心可以得部分分，但是本题贪心可以得满分的。
当然本题的贪心需要预处理下，开2个一维数组，row[i]录如果在第i行加通道,可以分割多少对调皮学生,col[i]记录如果在第j列加通道,可以分割多少对调皮学生,最后贪心法输出分割学生最多的前K行和前L列。
NOIP20XX普及组复赛试题与解题报告NOIP 20XX普及组解题报告一、ISBN号码【问题描述】每一本正式出版的图书都有一个ISBN号码与之对应，ISBN码包括9位数字、1位识别码和3位分隔符，其规定格式如“x-xxx-xxxxx-x”，其中符号“-”是分隔符，最后一位是识别码，例如0-670-82162-4就是一个标准的ISBN码。
ISBN码的首位数字表示书籍的出版语言，例如0代表英语；第一个分隔符“-”之后的三位数字代表出版社，例如670代表维京出版社；第二个分隔之后的五位数字代表该书在出版社的编号；最后一位为识别码。
识别码的计算方法如下：首位数字乘以1加上次位数字乘以2……以此类推，用所得的结果mod 11，所得的余数即为识别码，如果余数为10，则识别码为大写字母X。
例如ISBN号码0-670-82162-4中的识别码4是这样得到的：对067082162这9个数字，从左至右，分别乘以1，2，…，9，再求和，即0×1+6×2+……+2×9=158，然后取158 mod 11的结果4作为识别码。
你的任务是编写程序判断输入的ISBN号码中识别码是否正确，如果正确，则仅输出“Right”；如果错误，则输出你认为是正确的ISBN号码。
【输入】输入文件只有一行，是一个字符序列，表示一本书的ISBN号码。
【输出】输出文件共一行，假如输入的ISBN号码的识别码正确，那么输出“Right”，否则，按照规定的格式，输出正确的ISBN号码。
【输入输出样例1】 0-670-82162-4Right【输入输出样例2】0-670-82162-00-670-82162-4【试题分析】基础字符串处理题，心细一点的基本都能得满分。
【参考程序】 program isbn; constinp=''; oup=''; vari,j,k,ans:longint; s:string; ch:char; procedure flink; beginassign(input,inp);reset(input); assign(output,oup); rewrite(output); end;procedure fclose; beginclose(input); close(output); end; begin flink;readln(s);// 输入字符串 j:=0;i:=1; ans:=0; while jk do inc(i); while tmp[j]j;if m0 then begin inc(j);tmp[j]:=row[i]; end; end;qsort(1,j);//对tmp数组排序flag:=tmp[k];//flag为前K项的最小值 i:=1;j:=0;while (i=flag then //如果该行能分割的人数不少于flag,说明此处可以添加通道 begin write(i); inc(j);if jk then write(' '); end; inc(i); end; writeln;//下面是求列通道,思想同上j:=0;for i:= 1 to n do beginif col[i]>0 then begin inc(j);tmp[j]:=col[i]; end; end; qsort(1,j); flag:=tmp[L]; i:=1; j:=0;while (i=flag then begin write(i); inc(j);if jL then write(' '); end; inc(i); end;fclose; end.三、传球游戏【问题描述】上体育课的时候，小蛮的老师经常带着同学们一起做游戏。
信息学奥赛NOIP2012普及组解题报告（c++版本）第一题质因数分解, 题目已知正整数n是两个不同的质数的乘积, 试求出较大的那个质数, 没什么技术含量, 直接开个根号搜一遍就好了. 另外不开根号会TLE导致得60分.1 #include <stdio.h>2 #include <math.h>3int main()4 {5int n;6scanf("%d", &n);7for (int i = 2, k = sqrt(n) + 1; i < k; ++i)8if (n % i == 0)9{10printf("%d\n", n / i);11break;12}13return0;14 }第二题寻宝[题目]传说很遥远的藏宝楼顶层藏着诱人的宝藏。
小明历尽千辛万苦终于找到传说中的这个藏宝楼，藏宝楼的门口竖着一个木板，上面写有几个大字：寻宝说明书。
说明书的内容如下：藏宝楼共有N+1层，最上面一层是顶层，顶层有一个房间里面藏着宝藏。
除了顶层外，藏宝楼另有N层，每层M个房间，这M个房间围成一圈并按逆时针方向依次编号为0，…，M-1。
其中一些房间有通往上一层的楼梯，每层楼的楼梯设计可能不同。
每个房间里有一个指示牌，指示牌上有一个数字x，表示从这个房间开始按逆时针方向选择第x个有楼梯的房间（假定该房间的编号为k），从该房间上楼，上楼后到达上一层的k号房间。
比如当前房间的指示牌上写着2，则按逆时针方向开始尝试，找到第2个有楼梯的房间，从该房间上楼。
如果当前房间本身就有楼梯通向上层，该房间作为第一个有楼梯的房间。
寻宝说明书的最后用红色大号字体写着：“寻宝须知：帮助你找到每层上楼房间的指示牌上的数字（即每层第一个进入的房间内指示牌上的数字）总和为打开宝箱的密钥”。
请帮助小明算出这个打开宝箱的密钥。
这个题是个简单的模拟, 但是出乎意料的恶心, 当年做这个题的时候爆零, 钛蒻了, 总感觉这个比第三题难.1 #include <stdio.h>2int x[10003][103], fjx[103];3bool k[10003][103];4int main()5 {6int n, m, s, t, key = 0, turn;7scanf("%d %d", &n, &m);8for (int i = 0, j; i < n; ++i)9for (j = 0; j < m; ++j)10scanf("%d %d", &k[i][j], &x[i][j]);11scanf("%d", &s);12key = 0;13for (int i = 0, j = s, h = 0, fj = 0; i < n; ++i)14{15key = (key + x[i][s]) % 20123;16while (h < m)17{18if (k[i][j] == 1)19fjx[fj++] = j;20++h;21++j;22if (j == m)23j = 0;24}25t = (x[i][s] - 1) % fj;26s = fjx[t];27}28printf("%d\n", key);29return0;30 }第三题摆花[题目]小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共m盆。
N O I P 2 0 1 5 普及组解题报告南京师范大学附属中学树人学校CT1. 金币（coin.cpp/c/pas）【问题描述】国王将金币作为工资，发放给忠诚的骑士。
第一天，骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天（第七、八、九、十天），每天收到四枚金币；这种工资发放模式会一直这样延续下去：当连续N天每天收到N 枚金币后，骑士会在之后的连续N+1天里，每天收到N+1枚金币。
请计算在前K天里，骑士一共获得了多少金币。
【输入格式】输入文件名为coin.in 。
输入文件只有1行，包含一个正整数K,表示发放金币的天数。
【输出格式】输出文件名为coin.out 。
输出文件只有 1 行，包含一个正整数，即骑士收到的金币数。
【数据说明】对于100%的数据，1< K< 10,000。
【思路】模拟【时空复杂度】O(k) ，O(1)2 、扫雷游戏（mine.cpp/c/pas ）【问题描述】扫雷游戏是一款十分经典的单机小游戏。
在n行m列的雷区中有一些格子含有地雷（称之为地雷格），其他格子不含地雷（称之为非地雷格）。
玩家翻开一个非地雷格时，该格将会出现一个数字——提示周围格子中有多少个是地雷格。
游戏的目标是在不翻出任何地雷格的条件下，找出所有的非地雷格。
现在给出n行m列的雷区中的地雷分布，要求计算出每个非地雷格周围的地雷格数。
注：一个格子的周围格子包括其上、下、左、右、左上、右上、左下、右下八个方向上与之直接相邻的格子。
【输入格式】输入文件名为mine.in 。
输入文件第一行是用一个空格隔开的两个整数n和m分别表示雷区的行数和列数。
接下来n行，每行m个字符，描述了雷区中的地雷分布情况。
字符’* '表示相应格子是地雷格，字符''表示相应格子是非地雷格。
相邻字符之间无分隔符。
【输出格式】输出文件名为mine.out 。
noip2009复赛普及组解题报告多项式输出问题转述：给出一个一元多项式各项的次数和系数，按照规定的格式要求输出该多项式。
分析：普及组的水题。
多项式大家应该很熟悉，输出的时候注意一下几点即可：1. 最高次项为正的话开头无加号。
2. 系数为0不输出。
3. 一次项输出x，并非x^1。
4. 非常数项系数为1或-1时直接输出正负号，但是常数项需要输出该数字。
其中除第三项外其它均可在样例中检查出错误，但是若没想到第三点那么就只能得到50分了。
程序：var i,k,n:longint;beginassign(input,'poly.in');reset(input);assign(output,'poly.out');rewrite(output);readln(n);for i:=n downto 0 dobeginread(k);if k=0 then continue;if (k>0) and (i<>n) then write('+');if i=0 then write(k)else if (abs(k)<>1) then write(k) else if k=-1 then write('-');if i<>0 thenif i=1 then write('x')else write('x^',i);end;writeln;close(input);close(output);end.---------------------------------------------------------------------分数线划定问题转述：给出录取人数及所有面试者成绩，考号。
求出分数线和实际录取人数，并按成绩降序，若成绩相同则考号升序的规则输出录取人考号与成绩。
全国信息学奥林匹克联赛（NOIP2010）复赛_普及组_解题报告（pascal）全国信息学奥林匹克联赛（NOIP2010）复赛普及组解题报告1．数字统计(two.pas/c/cpp)【问题描述】请统计某个给定范围[L, R]的所有整数中，数字2 出现的次数。
比如给定范围[2, 22]，数字2 在数2 中出现了1 次，在数12 中出现1 次，在数20 中出现1 次，在数21 中出现1 次，在数22 中出现2 次，所以数字2 在该范围内一共出现了6次。
【算法思路】枚举法，依次将L至R转化为字符串，查找当中有多少个”2”.【程序代码】program two;varl,r:1..10000;i,j,h,c:longint;s:string;beginassign(input,'two.in');assign(output,'two.out');reset(input);rewrite(output);readln(l,r);c:=0;for i:=l to r dobeginstr(i,s);h:=length(s);for j:=1 to h doif s[j]='2'then c:=c+1;end;writeln(c);close(input);close(output);end.2．接水问题(water.pas/c/cpp)【问题描述】学校里有一个水房，水房里一共装有m 个龙头可供同学们打开水，每个龙头每秒钟的供水量相等，均为1。
现在有n 名同学准备接水，他们的初始接水顺序已经确定。
将这些同学按接水顺序从1到n 编号，i号同学的接水量为w i。
接水开始时，1 到m 号同学各占一个水龙头，并同时打开水龙头接水。
当其中某名同学j 完成其接水量要求w j 后，下一名排队等候接水的同学k马上接替j 同学的位置开始接水。
这个换人的过程是瞬间完成的，且没有任何水的浪费。
NOIP2009普及组复赛解题报告NFLS QMD第一题多项式输出1、摘要时间复杂度:O(n)空间复杂度:O(n)2、题目大意输入一个n次多项式各项的系数，按要求输出多项式3、算法分析先将不为0的系数和对应的次数存入a数组和b数组，然后依次输出。
要注意以下几点：①系数绝对值为1的情况②指数为1或0的情况③首项加号不必输出4、参考程序program poly;varn,i,g,xx:integer;a,b:array[0..200]of integer;function x(n:integer):string; //处理项的x^n部分varst1:string;beginif n=0 then x:='';if n=1 then x:='x';if n>1 thenbeginstr(n,st1);x:='x^'+st1;end;end;procedure flag(t:integer); //处理每项的符号beginif t>0 then write('+')else write('-');end;beginassign(input,'poly.in');reset(input);assign(output,'poly.out');rewrite(output);readln(n);g:=0;for i:=n downto 0 do //保存系数非零的项beginread(xx);if xx<>0 thenbeging:=g+1;a[g]:=xx;b[g]:=i;end;end;for i:=1 to g dobeginif i=1 then //处理首项的情况beginif abs(a[1])>1 then write(a[1]);if a[1]=-1 then write('-');endelsebeginflag(a[i]);if(b[i]=0)or(abs(a[i])<>1)then write(abs(a[i])); end;write(x(b[i]));end;writeln;close(input);close(output);end.第二题分数线划定1、摘要核心算法思想：排序时间复杂度：O(Nlog2N)空间复杂度：O(N)2、题目大意给出n个分数和编号(编号互不相同)，按分数从大到小取前[m*150%]个(可能有重分情况)，输出实际数目，最低分数以及按顺序排列的分数、编号。
N O I P2015普及组解题报告南京师范大学附属中学树人学校CT1.金币(coin.cpp/c/pas)【问题描述】国王将金币作为工资，发放给忠诚的骑士。
第一天，骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天（第七、八、九、十天），每天收到四枚金币……；这种工资发放模式会一直这样延续下去：当连续N天每天收到N枚金币后，骑士会在之后的连续N+1天里，每天收到N+1枚金币。
请计算在前K天里，骑士一共获得了多少金币。
【输入格式】输入文件名为coin.in。
输入文件只有1行，包含一个正整数K，表示发放金币的天数。
【输出格式】输出文件名为coin.out。
输出文件只有1行，包含一个正整数，即骑士收到的金币数。
【数据说明】对于100%的数据，1≤K≤10,000。
【思路】模拟【时空复杂度】O(k)，O(1)2、扫雷游戏（mine.cpp/c/pas）【问题描述】扫雷游戏是一款十分经典的单机小游戏。
在n行m列的雷区中有一些格子含有地雷（称之为地雷格），其他格子不含地雷（称之为非地雷格）。
玩家翻开一个非地雷格时，该格将会出现一个数字——提示周围格子中有多少个是地雷格。
游戏的目标是在不翻出任何地雷格的条件下，找出所有的非地雷格。
现在给出n行m列的雷区中的地雷分布，要求计算出每个非地雷格周围的地雷格数。
注：一个格子的周围格子包括其上、下、左、右、左上、右上、左下、右下八个方向上与之直接相邻的格子。
【输入格式】输入文件名为mine.in。
输入文件第一行是用一个空格隔开的两个整数n和m，分别表示雷区的行数和列数。
接下来n行，每行m个字符，描述了雷区中的地雷分布情况。
字符’*’表示相应格子是地雷格，字符’?’表示相应格子是非地雷格。
相邻字符之间无分隔符。
【输出格式】输出文件名为mine.out。
输出文件包含n行，每行m个字符，描述整个雷区。
用’*’表示地雷格，用周围的地雷个数表示非地雷格。
相邻字符之间无分隔符。
【数据说明】对于100%的数据，1≤n≤100，1≤m≤100。
【思路】模拟【技巧】可将数组多开一圈，省去边界条件的判断。
【时空复杂度】O(mn)，O(mn)3.求和(sum.cpp/c/pas)【问题描述】一条狭长的纸带被均匀划分出了n个格子，格子编号从1到n。
每个格子上都染了一种颜色color i（用[1，m]当中的一个整数表示），并且写了一个数字number i。
定义一种特殊的三元组：(x,y,z)，其中x，y，z都代表纸带上格子的编号，这里的三元组要求满足以下两个条件：1.x,y,z都是整数,x<y<z,y?x=z?y2.color x=color z满足上述条件的三元组的分数规定为(x+z)*(number x+number z)。
整个纸带的分数规定为所有满足条件的三元组的分数的和。
这个分数可能会很大，你只要输出整个纸带的分数除以10,007所得的余数即可。
【输入格式】输入文件名为sum.in。
第一行是用一个空格隔开的两个正整数n和m，n代表纸带上格子的个数，m代表纸带上颜色的种类数。
第二行有n个用空格隔开的正整数，第i个数字number i代表纸带上编号为i的格子上面写的数字。
第三行有m个用空格隔开的正整数，第i个数字color i代表纸带上编号为i的格子染的颜色。
【输出格式】输出文件名为sum.out。
共一行，一个整数，表示所求的纸带分数除以10,007所得的余数。
【数据说明】对于第1组至第2组数据，1≤n≤100,1≤m≤5；对于第3组至第4组数据，1≤n≤3000,1≤m≤100；对于第5组至第6组数据，1≤n≤100000,1≤m≤100000，且不存在出现次数超过20的颜色；对于全部10组数据，1≤n≤100000,1≤m≤100000,1≤color i≤m,1≤number i≤100000。
【思路】先分析一下，我们的任务是什么。
题目的要求是求分数和，我们就得把所有符合条件的三元组“找”出来。
至少需要枚举三元组(x,y,z)中的一个元素，这里枚举的是z（当然x 也可以，不过不要选y，因为y对分数没什么用）。
1、因为x<y<z，所以只需向前枚举x,y2、因为y-x=z-y，所以x+z=2y，x、z同奇偶，且分数与y无关，只需枚举z和x。
3、因为colour x=colour z，所以只需枚举z之前同奇偶且同色的x。
这样的话时间复杂度是O(n2)，能得40分。
如何快速枚举x呢？其实不是快速枚举x，是快速枚举分数和。
观察三元组分数：(x+z)·(number x+number z)显然我们不方便处理多项式乘法，那就把它拆开（事实上很多人到这步都放弃了，其实试一试立刻就明白了）=x·number x+x·number z+z·number x+z·number z那么对于z的所有合法决策x1,x2, (x)根据乘法分配率，分数=Σ(xi*number xi)+Σ(xi)*number z+Σ(number xi)*z+Σ(z*number z)(1<=i<=k)由于z是枚举的，所以只需快速得到Σ(x·number x)，Σx，Σnumber x 和k（注意最后一项被算了k次，要乘k）这样我们就可以开4个累加器，分别记录这四个量。
而对于不同奇偶性、不同颜色的z有不同的决策x，所以要开一个s[2][m][4]的累加器。
【时空复杂度】O(n)，O(n+m)【注意】题目数据较大，每次计算一定要模10007，否则很容易出错。
【样例程序】#include<cstdio>constintmaxn=100000;constintmaxm=100000;constintp=10007;intn,m,ans;intnumber[maxn+1],colour[maxn+1];ints[2][maxm+1][4];voidinit(){freopen("sum.in","r",stdin);freopen("sum.out","w",stdout);scanf("%d%d",&n,&m);for(inti=1;i<=n;i++)scanf("%d",&number[i]);for(inti=1;i<=n;i++)scanf("%d",&colour[i]);}voidsolve(){for(inti=1;i<=n;i++){intz=i%p,numz=number[i]%p,c=colour[i],t=i%2;intcount=s[t][c][0]%=p,x=s[t][c][1]%=p,numx=s[t][c][2]%=p,x_numx=s[t][c][3]%=p;ans=(ans+((count*z)%p*numz)%p)%p;ans=(ans+x_numx)%p;ans=(ans+x*numz)%p;ans=(ans+z*numx)%p;s[t][c][0]++;s[t][c][1]+=z;s[t][c][2]+=numz;s[t][c][3]+=z*numz;}}voidoutput(){printf("%d\n",ans);fclose(stdin);fclose(stdout);}intmain(){init();solve();output();return0;}4.推销员(salesman.cpp/c/pas)【问题描述】阿明是一名推销员，他奉命到螺丝街推销他们公司的产品。
螺丝街是一条死胡同，出口与入口是同一个，街道的一侧是围墙，另一侧是住户。
螺丝街一共有N家住户，第i家住户到入口的距离为S i米。
由于同一栋房子里可以有多家住户，所以可能有多家住户与入口的距离相等。
阿明会从入口进入，依次向螺丝街的X家住户推销产品，然后再原路走出去。
阿明每走1米就会积累1点疲劳值，向第i家住户推销产品会积累A i 点疲劳值。
阿明是工作狂，他想知道，对于不同的X，在不走多余的路的前提下，他最多可以积累多少点疲劳值。
【输入格式】输入文件名为salesman.in。
第一行有一个正整数N，表示螺丝街住户的数量。
接下来的一行有N个正整数，其中第i个整数S i表示第i家住户到入口的距离。
数据保证S1≤S2≤…≤S n<108。
接下来的一行有N个正整数，其中第i个整数A i表示向第i户住户推销产品会积累的疲劳值。
数据保证A i<103。
【输出格式】输出文件名为salesman.out。
输出N行，每行一个正整数，第i行整数表示当X=i时，阿明最多积累的疲劳值。
【数据说明】对于20%的数据，1≤N≤20；对于40%的数据，1≤N≤100；对于60%的数据，1≤N≤1000；对于100%的数据，1≤N≤100000。
【思路】题目要求每一个X的情况，显然不能每个X专门推一遍，要充分利用已知的X的情况，那么很可能会是DP。
定义f[i]为X=i时的最大疲劳值。
关键是怎么建立状态转移方程呢？考试时观察了两组样例数据，直觉告诉我f[i+1]的决策应该会包含f[i]的决策（此处的决策指住户下标）。
事实上也确实如此。
证明：设f[i]的决策为k1,k2,……,k i(k1<k2<……<k i)，f[i+1]的决策将f[i]决策中的k s换成j并增加了一个决策k i+1，f[i+1]的决策k中最大的为maxk。
f[i]=2*s[k i]+Σa[k t](1<=t<=i)f[i+1]=2*s[maxk]+Σa[k t](1<=t<=s-1)+Σa[k t](s+1<=t<=i)+a[j]+a[k i+1]∵2*s[maxk]+Σa[k t](1<=t<=s-1)+Σa[k t](s+1<=t<=i)+a[j]是X=i时的一种决策的疲劳值（即决策为k1,k2,……k s-1,k s+1,……k i,k j时）∴2*s[maxk]+Σa[k t](1<=t<=s-1)+Σa[k t](s+1<=t<=i)+a[j]<=f[i] ∴2*s[maxk]+Σa[k t](1<=t<=s-1)+Σa[k t](s+1<=t<=i)+a[j]+a[k i+1] <=f[i]+a[k i+1]（即决策为k1,k2,……,k s,……,k i,k i+1时的疲劳值）若小于，说明保留k s更优；若等于，对于两个目前疲劳值相等的决策序列k，max{k}越小越好（就是说目前走的路程越短越好），因为在max{k}左边的决策l只能增加a[l]的疲劳值，而对于max{k}右边的决策r则可以增加2*(s[r]-s[max{k}])+a[r]，对于左边，max{k}没有影响，而对于右边，max{k}越小，后面的f[]增加疲劳值的空间越大。
