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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【小模拟2】【快速求和】  

2013-11-05 12:38:18|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   直接搜索,由于要求最短步骤,使用BFS,然后就是无穷无尽的BFS,我们直接枚举断点,然后截下断点旁的,将剩余的压入队列。下剪枝策略有二,一.就是截下来的数加上之前截的不能超过N,如果超过N则剪,二就是如果是0的话就跳过,我们显然在之前就已经枚举过了,咱还是没过两个点,表示弱爆了...
=================================================================

program quicksumm;
const maxn=500001;
var s:string;
    n,l1,l2,ans:longint;
   step,now:array[0..maxn-1]of longint;
   que:array[0..maxn-1]of string;

function delete(s:string;p:longint):string;
var i,j:longint;
begin
  delete:='';
  j:=length(s);
  p:=p+1;
  while (s[p]='0')and(p<=j) do inc(p);
  for i:=p to j do
   delete:=delete+s[i];
  exit(delete);
end;

function copy(s:string;p:longint):longint;
var i,j,k:longint;
begin
  j:=0;
  k:=1;
  while s[k]='0' do
  begin
   s:=delete(s,1);
   dec(p);
  end;
  for i:=1 to p do
   begin
     j:=j*10;
     j:=j+ord(s[i])-ord('0');
   end;
  exit(j);
end;

function val(s:string):longint;
var i,j,k:longint;
begin
  k:=length(s);
  if k>5 then exit(-100000);
  j:=0;
  for i:=1 to k do
   begin
     j:=j*10;
     j:=j+ord(s[i])-ord('0');
   end;
  exit(j);
end;

function min(a,b:longint):longint;
begin
  if a<b then exit(a);
  exit(b);
end;

function bfs:boolean;
var l,r,v,w,i,j:longint;
    u:string;
begin
  fillchar(que,sizeof(que),0);
  fillchar(step,sizeof(step),0);
  fillchar(now,sizeof(now),0);
  l:=0;r:=1;
  que[0]:=s;
  step[0]:=0;
  now[0]:=0;
  while l<>r do
   begin
     u:=que[l];
     j:=length(u);
     for i:=1 to min(l1,j-1) do
      if u[i]<>'0' then
        begin
          w:=now[l]+copy(u,i);
          if w>n then break;
          que[r]:=delete(u,i);
          step[r]:=step[l]+1;
          now[r]:=w;
          w:=val(que[r]);
          if now[r]+w=n then
          begin
            ans:=step[r];
            exit(true);
          end;
          r:=(r+1)mod maxn;
        end;
     l:=(l+1)mod maxn;
   end;
  exit(false);
end;

procedure init;
var i,j,k:longint;
    ch:char;
begin
  assign(input,'quicksum3.in');
  reset(input);
  assign(output,'quicksum.out');
  rewrite(output);
  s:=''; l1:=0;
  read(ch);
  while (ord(ch)>=ord('0'))and(ord(ch)<=ord('9'))do
    begin
      s:=s+ch;
      read(ch);
      inc(l1);
    end;
  k:=1;
  while s[k]='0' do
   delete(s,1);
  read(n);
  k:=n;l2:=0;
  while k<>0 do
   begin
     inc(l2);
     k:=k div 10;
   end;
end;

procedure main;
begin
  if l1<l2 then begin write(-1);exit;end;
  ans:=0;
  if bfs then write(ans)
         else write(-1);
end;

begin
  init;
  main;
 end.

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

历史上的今天

评论

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

页脚

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