当前位置:首页 >> 学科竞赛 >>

NOIp每日整理


最大子序列和
设 ans[i]表示前 i 个元素的最大和,a[i]表示元素数字 则 ans[i]:=max{ans[i-1]+a[i],a[i]} For i:=1 to n do Ans[i]:=max(ans[i-1]+a[i],a[i]); Writeln(max{ans[n]});

最大子矩阵
对于一个矩阵而言,如果我们将连续 k

行的元素纵向相加,并对相 加后所得的数列求连续最大和,则此连续最大和就是一个行数为 k 的最优子矩阵 在一序列中,sum[i]表示前 i 个元素的和 sum[i]:=sum[i-1]+a[i]; 从 i 至 j 的元素和为 sum[j]-sum[i] 则对于一矩阵(n*m) Sum[i][j]表示第 j 列前 i 个元素的和 求 sum[i][j] For i:=1 to n do For j:=1 to m do Sum[i][j]:=sum[i-1][j]+a[i][j]; 从 sum[i][j]中读取元素 for i:=n downto 1 do for j:=i-1 downto 0 do for k:=1 to m do

temp[k]:=sum[i,k]-sum[j,k];

不同的行组合 第一行 第二行 第三行 第一、二行 第二、三行 第一、二、三行

数据处理方法 sum[1,j] sum[2,j]-sum[1,j] sum[3,j]-sum[2,j] sum[2,j] sum[3,j]-sum[1,j] sum[3,j]

则 temp[k]表示每一小行每一小列的和(能全部记录) For i:=n downto 1 do //每一部分行[1,n] 更新 best Begin For j:=i-1 downto 0 do F or k:=1 to m do Temp[k]:=sum[i][k]-sum[j][k]; End; 只需从 temp[k]中求出最大子序列和 最终 best 即为所求

Var a,sum:array[0..1000,0..1000] of longint; n,m:longint; procedure init; var i,j,k:longint; begin assign(input,'in.in'); reset(input); readln(n,m); for i:=1 to n do for j:=1 to m do read(a[i][j]); for i:=1 to n do for j:=1 to m do sum[i][j]:=sum[i-1][j]+a[i][j]; //预处理记录第 j 列前 i 个元素和 close(input); end; function max(a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; procedure solve; var i,j,k,ans,tot:longint; temp,b:array[0..1000] of longint; begin tot:=0; for i:=n downto 1 do // 每一部分行 for j:=i-1 downto 0 do begin ans:=-maxlongint; fillchar(b,sizeof(b),0); for k:=1 to m do temp[k]:=sum[i][k]-sum[j][k]; for k:=1 to m do begin b[k]:=max(b[k-1]+temp[k],temp[k]); if ans<b[k] then ans:=b[k]; end; // 求最大子序列和 if ans>tot then tot:=ans; //更新最大者 end; writeln(tot); end;

begin init; solve; end.

["扫地"杯 III day1]诡异的数学题 From

liouzhou_101

背景 Background

“扫地”杯 III NOIP2012模拟赛 day1 第一题
描述 Description

liouzhou_101从 NOI 归来后文化课像坨屎,于是决定去补做一些 作业,结果翻开作业的第一题就傻眼了: 设 a、b、c 为实数,且满足 a+b+c=15,a^2+b^2+c^2=100,则 a 的最大值和最小值的积为____。 话说这题他都没有想出来怎么做,就开始自己 YY,把这题牛逼成了: 设 a1、a2、…、an 为实数,且 a1+a2+…+an=x, a1^2+a2^2+…+an^2=y,则 a1的最大值和最小值的积为____。 liouzhou_101这种傻× 自然不会做了,于是来向你请教…
输入格式 InputFormat

输入的第一行是一个正整数 T,表示测资组数。 接着对每组测资,输入只有一行,三个正整数 N、x 和 y,之间以一 个空格隔开。
输出格式 OutputFormat

对于每组测资,输出只有一行,假若不存在满足题目要求的,就输出 “WA RE CE TLE MLE OLE”(不含引号);否则输出一个精确到小数 点后6位的浮点数,即 a1的最大值和最小值的积。
样例输入 SampleInput [复制数据]

2 3 15 100 1 4 15

样例输出 SampleOutput [复制数据]

8.333333 WA RE CE TLE MLE OLE
数据范围和注释 Hint 对于第一组测资,a1最大是9.082483,最小是0.917517,乘起来就是8.333333。 对于第二组测资,明显不可能存在 a1满足题意。 对于10%的数据,N=1; 对于20%的数据,N<=2; 对于40%的数据,N<=3; 对于70%的数据,N<=100; 对于100%的数据,1<=T<=10,1<=N<=10,000,-10,000<=x<=10,000,0<=y<=10,000。 来源 Source

liouzhou_101

解析
设 p:= ? a _ i
i?2 n

q:= i ?2

? (a _ i) ^ 2

n

则由均值不等式



p q n ? 1 大于等于 n ? 1

去掉根号得 q>=(p^2)/(n-1) 带入得 Y(n-1)-a1^2(n-1)>=x^2-2a1x+a1^2 即 x^2-2x*a1+n*a1^2+Y-Y*n <=0 开口向上 则最大值*最小值:=c/a 由韦达定理得 a1(1)*a1(2)=x^2-y*(n-1)/n 即为所求

var n,x,y,i,t:longint; temp:real; begin readln(t); for i:=1 to t do begin readln(n,x,y); if n=1 then begin if (x*x)<>y then Begin writeln('WA RE CE TLE MLE OLE'); continue; end; if (x*x)=y then begin writeln(x*x,'.000000'); continue; end; end; if (4*x*x-4*n*(x*x-y*n+y))<0 then writeln('WA RE CE TLE MLE OLE') else writeln((x*x-y*(n-1))/n:0:6); end; end.


相关文章:
NOIp每日整理
NOIp每日整理_学科竞赛_高中教育_教育专区。NOIp每日整理最大子序列和设 ans[i]表示前 i 个元素的最大和,a[i]表示元素数字 则 ans[i]:=max{ans[i-1]+a...
noip 每日整理
NOIp每日整理 暂无评价 8页 2下载券 冲刺NOIP之整理 15页 1下载券 Noip整理 暂无评价 16页 1下载券 Noip整理 暂无评价 5页 2下载券 Noip整理 暂无评价 8页...
Noip整理
noip 每日整理 暂无评价 4页 1下载券 NOIp每日整理 暂无评价 8页 2下载券 noip初赛基础知识整理(精... 8页 3下载券 基础代码汇总整理 for N... 30页 4下...
Noip整理
noip 每日整理 暂无评价 4页 1下载券 NOIp每日整理 暂无评价 8页 2下载券 noip...[NOIP2010]乌龟棋 From NOIP2010提高组复赛第二题 描述 Description 小明过生日...
Noip整理
Noip整理_学科竞赛_高中教育_教育专区。团伙 背景 Background From BearHsu 经典题目描述 Description 1920年的芝加哥,出现了一群强盗。如果两个强盗遇上了,那么他 ...
2016.10.1 学习整理
2016.10.1 学习整理_教育学_高等教育_教育专区。2016.10.1 期清北学堂整理 ...(NOIP 不过多涉及这方面的知识) 并查集(这才是 NOIP 真正用得到的) 并查集是...
Noip整理
或者如何实现呢?这正是 Kosaraju 算法最为精妙的地 方,关键在于第二次 DFS 选取的顺序:在第一次 DFS 中,将顶点按 照后序编号存放,第二次 DFS 就按照这个...
NOIP算法整理
NOIP算法整理_学科竞赛_高中教育_教育专区。2015NOIP算法总结PASCAL版 前言离 NOIP 还有一个星期,匆忙的把寒假整理的算法补充完善,看 着当时的整理觉得那时还年少。...
NOIP常用程序段整理
NOIP常用程序段整理 程序程序隐藏>> Noip2009 衢州一中 目录关于时间复杂度 快速排序 归并排序 筛选法求素数 floyed 迪杰斯特拉 prim 拓扑排序 深搜 广搜 最长子序...
冲刺NOIP之整理
NOIP范围内的DP算法 6页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 冲刺NOIP整理 冲刺NOIP2012知识点整理、冲...
更多相关标签:
金山词霸每日一词整理 | 蜀门75级每日任务整理 | noip2016 | noip2016提高组复赛 | noip2016普及组复赛 | noip吧 | noip2015提高组复赛 | 2016noip复赛成绩查询 |