P8902 [USACO22DEC] Range Reconstruction S题目描述Bessie 有一个数组a1,⋯ ,aNa_1, \cdots, a_Na1,⋯,aN其中1≤N≤3001 \le N \le 3001≤N≤300并对于所有iii有0≤ai≤1090 \le a_i \le 10^90≤ai≤109。她不会告诉你数组aaa本身但她会告诉你aaa的每个子数组的全距。也就是说对于每对索引i≤ji \le ji≤jBessie 告诉你ri,jmaxa[i⋯j]−mina[i⋯j]r_{i,j} \max a[i \cdots j]− \min a[i \cdots j]ri,jmaxa[i⋯j]−mina[i⋯j]。给定这些rrr的值构造一个可以作为 Bessie 的原始数组的数组。你的数组中的数值应在[−109,109][−10^9,10^9][−109,109]范围内。输入格式输入的第一行包含NNN。以下NNN行第iii行包含整数ri,i,ri,i1,⋯ ,ri,Nr_{i,i},r_{i,i1}, \cdots ,r_{i,N}ri,i,ri,i1,⋯,ri,N。输入保证存在某个数组aaa其中的数值在[0,109][0,10^9][0,109]范围内满足对于所有的i≤ji \le ji≤j有ri,jmaxa[i⋯j]−mina[i⋯j]r_{i,j} \max a[i \cdots j]−\min a[i\cdots j]ri,jmaxa[i⋯j]−mina[i⋯j]。输出格式输出一行包含NNN个整数b1,b2,⋯ ,bNb_1,b_2, \cdots ,b_Nb1,b2,⋯,bN在[−109,109][−10^9,10^9][−109,109]范围内表示你的数组。这些数需要满足对于所有的i≤ji \le ji≤j有ri,jmaxa[i⋯j]−mina[i⋯j]r_{i,j} \max a[i \cdots j]−\min a[i\cdots j]ri,jmaxa[i⋯j]−mina[i⋯j]。输入输出样例 #1输入 #13 0 2 2 0 1 0输出 #11 3 2输入输出样例 #2输入 #23 0 1 1 0 0 0输出 #20 1 1输入输出样例 #3输入 #34 0 1 2 2 0 1 1 0 1 0输出 #31 2 3 2输入输出样例 #4输入 #44 0 1 1 2 0 0 2 0 2 0输出 #41 2 2 0说明/提示样例 1 解释例如r1,3maxa[1⋯3]−mina[1⋯3]3−12r_{1,3}\max a[1 \cdots 3]−\min a[1\cdots 3]3−12r1,3maxa[1⋯3]−mina[1⋯3]3−12。样例 2 解释这个样例满足子任务111的限制。样例 3 解释这个样例满足子任务 2 的限制。测试点性质测试点555满足r1,N≤1r_{1,N} \le 1r1,N≤1。测试点6−86-86−8满足对于所有1≤iN1 \le iN1≤iN均有ri,i11r_{i,i1}1ri,i11。测试点9−149-149−14没有额外限制。C实现#includeiostreamusingnamespacestd;constintN305;intn;intr[N][N];//输入inta[N];//构造数组intmaxn[N],minx[N];//前缀和intmain(){inti,j;cinn;for(i1;in;i)for(ji;jn;j)cinr[i][j];for(i1;in;i)//初始化前缀和maxn[j]代表从j到i的最大值minx则相反maxn[i]-1e9,minx[i]1e9;a[1]0;maxn[1]0;//注意a[1]的初始化minx[1]0;for(i2;in;i){a[i]a[i-1]r[i-1][i];//先试正for(j1;ji;j){if(max(a[i],maxn[j])-min(a[i],minx[j])!r[j][i])break;//不符合}if(j!i)a[i]a[i-1]-r[i-1][i];//换成负for(j1;ji;j){maxn[j]max(maxn[j],a[i]);//更新前缀和数组minx[j]min(minx[j],a[i]);}}for(i1;in;i)couta[i] ;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
