首页 > 代码库 > 【数论 Day2】基础归纳法 题解

【数论 Day2】基础归纳法 题解

2024-09-27 23:37:01   220人阅读

题目： http://www.cnblogs.com/ljc20020730/p/6919989.html

1.烧水问题SDOI2008（山东省队选拔）

对于本题，O(n2)的贪心算法很好找出，就是让前几杯水都加热到100℃后面进行热传递。

打印出前几项，会发现规律……可以优化到O(n)。 或者，也可以无耻地打表……

提醒：令第一杯水需要提高t度，找出第二杯、第三杯……需要提高温度的比例关系，找规律解决。

技术分享

 

推倒如下:

设沸腾温度为a

则第一杯温度为a,需要加热t1=a

第二杯可以中和的最高温度为a/2,需要加热t2=a/2

第三杯可以中和的最高温度为t3=(a/4+a)/2=5a/8,需要加热t3=3a/8

第四杯可以中和的最高温度为t4=((a/8+5a/8)/2+a)/2=11a/16,需要加热t4=5/16

则t3/t2=3/4=1-1/4,

t4/t3=5/6=1-1/6

…………………………

继续推导得t(n+1)/t(n)=1-1/2n

 

根据题目描述及物理常识，我们至多能往当前的杯子里分配(现在花费的总热量/i)的热量，而且一定有办法做到。

所以，实际上第i杯水要花费(上一次花费的热量*(2*i-i)/(2*i))单位热量。

 

var
  n,i:longint;
  cur,tot:double;
begin
assign(input,‘heat.in‘);
assign(output,‘heat.out‘);
reset(input);
rewrite(output);
  readln(n);
  cur:=420000.00/n;
  tot:=0;  
  for i:=1 to n-1 do begin
    tot:=tot+cur;
    cur:=cur*(2*double(i)-1)/(2*double(i))
  end;
  writeln(tot+cur:0:2);
  close(input);
  close(output);
end.

2.六边形(hexagons.pas/c/cpp)

首先讲一种暴力的方法orz

●暴力: 一圈一圈的加，加到i<a or j<b or k<c。

技术分享

 

ans:=7; //红色线为公共点。
i:=2;j:=2;k:=2;
while i<a do begin
  ans:=ans+j+k-1;
  i:=i+1;
end;
while j<b do begin
  ans:=ans+i+k-1;
  j:=j+1;
end;
while k<c do begin
  ans:=ans+i+j-1;
  k:=k+1;
end;
writeln(ans);

 

接下来讲一种O(1)的算法：

直接ans=a*c+a*b+b*c-c-b-a+1

看到下面看到分成3块的面积和为ac+bc+ab

重叠算一次的a+b+c

重叠算两次的1（交点）

所以ans=ac+bc+ab-(a+b+c)+1=a*c+a*b+b*c-c-b-a+1

 

技术分享

程序如下：

var a,b,c:longint;
begin
assign(input,‘Hexagons.in‘);
assign(output,‘Hexagons.out‘);
reset(input);
rewrite(output);
 readln(a,b,c);
 writeln(a*c+a*b+b*c-c-b-a+1);
close(input);
close(output);
end.

 

3.最大子序和

对于样例的解释图：

技术分享

输入数据，不需要保存序列，可马上序列前缀和为s[i]。q[i]队列维护选取范围的编号，l,r分别表示队列的首尾指针。

队列放起始点

初始化l=0 r=-1

首出队：i-q[l]>B

尾出队：s[q[r]]>=s[i-a]

入队：inc(r);q[r]:=i-a;

ans:=max(s[i]-s[q[l]],ans);

程序如下：

var l,r,a,b,n,i,t,max:longint;
    s,q:array[0..500000]of longint;
begin
assign(input,‘max.in‘);
assign(output,‘max.out‘);
reset(input);
rewrite(output);
 readln(n,a,b);
 s[0]:=0;
 for i:=1 to n do begin
  read(t);
  s[i]:=s[i-1]+t;
 end;//前缀和
 l:=0; r:=-1;
 max:=-maxlongint;
 for i:=a to n do begin
  if (l<=r)and(i-q[l]>b) then inc(l);//当l在r前面并且当前的长度超过B，出队
  while (l<=r)and(s[i-a]-s[q[r]]<=0) do dec(r);//当l在r的前面并且新加入队列的数为负数，那么得出的答案一定会小于某个数
  inc(r); q[r]:=i-a;//扩充队列
  if s[i]-s[q[l]]>max then max:=s[i]-s[q[l]];//s[i]-s[q[l]]表示 i 到 当前队列起始点这么多数的和
 end;
 writeln(max);//输出
 close(input);
 close(output);
end.

这样就可以使平均时间复杂度降为O(n2)以下，关键就是上面的当l在r的前面并且新加入队列的数为负数，那么得出的答案一定会小于某个数，判掉

4.哥德巴赫矩阵

 

运用筛法求质数的方法，建立一个布尔数组a[]。

技术分享＝s[x2]-s[x1-1])*(s[y2]-s[y1-1])

技术分享

观察上面的规律(除2以个的质数的增加)编程实现。

复杂度：预处理O(MAXN*√MAXN)，处理s[]为O(N)，查询O(1)。

程序如下：

 

const maxn=1000000;
var u:array[1..10000000]of boolean;
    s:array[0..10000000]of int64;
    i,m,x1,y1,x2,y2:longint;
    now:int64;
Procedure prime(n:longint);
  var i,j:longint;
begin
  for i:=2 to n do
    if not u[i] then begin
      j:=i+i;
      while j<=n do begin
        u[j]:=true;
        inc(j,i);
      end;
    end;
end;
begin
assign(input,‘pmatrix.in‘);
assign(output,‘pmatrix.out‘);
reset(input);
rewrite(output);
  prime(maxn);
  s[1]:=0; s[2]:=0;
  now:=0;
  for i:=3 to maxn do begin
   if u[i]=false then inc(now);
   s[i]:=now;
  end;
  readln(m);
  for i:=1 to m do begin
  readln(x1,y1,x2,y2);
  writeln((s[x2]-s[x1-1])*(s[y2]-s[y1-1])) ;
  end;
  close(input);
  close(output);
end.

 

【数论 Day2】基础归纳法 题解


联系
我们