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

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 每日整理 暂无评价 4页 1下载券 NOIp每日整理 暂无评价 8页 2下载券 noip...[NOIP2010]乌龟棋 From NOIP2010提高组复赛第二题 描述 Description 小明过生日...
Noip整理
Noip整理_学科竞赛_高中教育_教育专区。团伙 背景 Background From BearHsu 经典题目描述 Description 1920年的芝加哥,出现了一群强盗。如果两个强盗遇上了,那么他 ...
Noip整理
或者如何实现呢?这正是 Kosaraju 算法最为精妙的地 方,关键在于第二次 DFS 选取的顺序:在第一次 DFS 中,将顶点按 照后序编号存放,第二次 DFS 就按照这个...
NOIP算法整理_图文
NOIP算法整理_学科竞赛_高中教育_教育专区。2015NOIP算法总结PASCAL版 前言离 NOIP 还有一个星期,匆忙的把寒假整理的算法补充完善,看 着当时的整理觉得那时还年少。...
2016.10.1 学习整理
2016.10.1 学习整理_教育学_高等教育_教育专区。2016.10.1 期清北学堂整理 ...(NOIP 不过多涉及这方面的知识) 并查集(这才是 NOIP 真正用得到的) 并查集是...
NOIP常用程序段整理
NOIP常用程序段整理 程序程序隐藏>> Noip2009 衢州一中 目录关于时间复杂度 快速排序 归并排序 筛选法求素数 floyed 迪杰斯特拉 prim 拓扑排序 深搜 广搜 最长子序...
冲刺NOIP之整理
NOIP范围内的DP算法 6页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 冲刺NOIP整理 冲刺NOIP2012知识点整理、冲...
NOIP算法整理
NOIP算法整理_IT认证_资格考试/认证_教育专区 暂无评价|0人阅读|0次下载|举报文档NOIP算法整理_IT认证_资格考试/认证_教育专区。By skyRolly ...
NOIP算法整理
NOIP算法整理_韩语学习_外语学习_教育专区。NOIP算法整理 前言 离 NOIP 还有一个星期, 匆忙的把寒假整理的算法补充完善, 看着当时的整理觉得那时还年少。 第二页...
Noip图论整理
图论程序整理 Edmonds-Karp var ans,i,j,k,s,t,tot,m,n,a,b,c:longint; u,v,w,next,other:array[0..200] of longint; point,d,q,pre:array[0...
更多相关标签:
金山词霸每日一词整理 | 叶攻tag每日整理 | 每日厨房整理术 | noip动态域名注册 | noip 竞赛 | noip吧 | noip2016 | noip一等奖有什么用 |