注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【憧憬熊】【普及】【愚蠢的军官】  

2013-10-26 22:50:35|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    做法就是先暴力将1~n得到的函数值求出来,并用类似计数排序的方法记录每个数被映射的次数,用a[]下标表示每个数,其值为次数,复杂度为O(N),然后我们要做的就是从两个A[]数组中选出两个数相乘,输出前M个乘积最大的,这个用堆做,复杂度为O(MAXLOGMAX),MAX为9的7次方,然后就无压力了。突然出题人友情提示范围是(0,0)到(n,n),竟然不是(0,0)到(n-1,n-1),也就是说只要M一大咱的程序就会忽略东西了...所以只拿了50分...吐槽,出题写清楚嘛= = 

  program foolish;

const max=4782969;
var n,m,maxx:longint;
    a,b:array[0..max+1] of int64;
    h,oo,o:array[1..max+10]of int64;

procedure qsort(l,r:longint);
var x,y,i,j:longint;
begin
  i:=l;j:=r;
  x:=a[random(r-l)+l];
  repeat
   while a[i]>x do inc(i);
   while a[j]<x do dec(j);
   if i<=j then begin
     y:=a[i];a[i]:=a[j];a[j]:=y;
     y:=b[i];b[i]:=b[j];b[j]:=y;
     inc(i);dec(j);
   end;
  until i>j;
  if i<r then qsort(i,r);
  if j>l then qsort(l,j);
end;

procedure init;
begin
  read(n);read(m);
end;

procedure divide(n:longint);
var s,p:longint;
begin
  s:=1;
  p:=n;
  while n>0 do
    begin
      s:=s*(n mod 10);
      n:=n div 10;
    end;
  inc(a[s]);
end;

procedure prepare;
var i:longint;
begin
  for i:=1 to n-1 do
   divide(i);
  for i:=0 to max do
   b[i]:=i;
end;

procedure down(p,q:longint);
var j,x,y,z:longint;
begin
  x:=h[q];
  y:=oo[q];
  z:=o[q];
  j:=q*2;
  while j<=p do
   begin
    if (j<p)and(h[j+1]>h[j]) then inc(j);
    if x>=h[j] then j:=p+1
           else begin
                h[q]:=h[j];
                oo[q]:=oo[j];
                o[q]:=o[j];
                q:=j;
                j:=j*2;
                end;
   end;
  h[q]:=x;
  oo[q]:=y;
  o[q]:=z;
end;

procedure swap(var x,y:int64);
var t:int64;
begin
  t:=x;x:=y;y:=t;
end;

procedure tiao;
var i:longint;
begin
  for i:=1 to max-1 do
   if a[i]=0 then maxx:=i-1;
end;

procedure main;
var i:longint;
    ans:int64;
begin
  for i:=1 to maxx do
   begin
    h[i]:=a[i]*a[1];
    oo[i]:=i;
    o[i]:=1;
   end;
  for i:=maxx div 2 downto 1 do
    down(maxx,i);
  ans:=0;
  for i:=1 to m do
    begin
      ans:=ans+h[1];
      inc(o[1]);
      h[1]:=a[o[1]]*a[oo[1]];
      down(maxx,1);
    end;
  write(ans);
end;


begin
  randomize;
  init;
  prepare;
  swap(a[n-1],a[max]);
  swap(b[n-1],b[max]);
  qsort(1,max-1);
  tiao;
  main;
end.

  评论这张
 
阅读(13)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018