P〇〇н

恶心恶心太恶心了

做不下去了

晕

将近300行，回头理理再来调，现在睡觉去，2:40am

type hi=array[0..1000] of integer;

var ori:string;
    long:integer;
    a,b,ans,best:hi;

procedure init;
begin
  best[0]:=maxint;
  readln(ori);
  long:=length(ori);
end;

procedure incc(var a:string);
var i:integer;
begin
  a[length(a)]:=chr(ord(a[length(a)])+1);
  for i:=length(a) downto 1 do
    if a[i]<='9' then exit
    else
      begin
        a[i]:='0';
        if i=1 then
          begin
            insert('1',a,1);
            exit;
          end
        else a[i-1]:=chr(ord(a[i-1])+1);
      end;
end;

procedure decc(var a:string);
var i:integer;
begin
  a[length(a)]:=chr(ord(a[length(a)])-1);
  for i:=length(a) downto 1 do
    if a[i]>='0' then break
    else
      begin
        a[i]:='9';
        a[i-1]:=chr(ord(a[i-1])-1);
      end;
  while (a[1]='0') and (length(a)>1) do delete(a,1,1);
end;

function com(pos:integer; now:string):boolean;
var i,temp:integer;
    num:string;
begin
  num:=now;
  temp:=pos-length(now);
  decc(num);
  for i:=1 to temp-1 do
    if length(num)-i+1<=0 then break
    else
      if num[length(num)-i+1]<>ori[temp-i] then exit(false);
  while pos<=long do
    begin
      incc(now);
      for i:=1 to length(now) do
        if pos+i-1>long then exit(true)
        else
          if now[i]<>ori[pos+i-1] then exit(false);
      pos:=pos+length(now);
    end;
  exit(true);
end;

function special(len:integer; a,b:string; var return:string):boolean;
var i:integer;
begin
  return:=b;
  for i:=1 to length(a) do
    if len-(length(a)-i)>length(return) then return:=return+a[i]
    else
      if return[len-(length(a)-i)]<>a[i] then exit(false);
end;

function jian(a,b:hi):hi;
var l,i:integer;
begin
  fillchar(jian,sizeof(jian),0);
  if a[0]<b[0] then l:=b[0] else l:=a[0];
  for i:=1 to l do
    begin
      jian[i]:=a[i]-b[i]+jian[i];
      if jian[i]<0 then
        begin
          jian[i]:=10+jian[i];
          dec(jian[i+1]);
        end;
    end;
  while (jian[l]=0) and (l>1) do dec(l);
  jian[0]:=l;
end;

function jia(a,b:hi):hi;
var l,i:integer;
begin
  fillchar(jia,sizeof(jia),0);
  if a[0]>b[0] then l:=a[0] else l:=b[0];
  for i:=1 to l do
    begin
      jia[i]:=jia[i]+a[i]+b[i];
      jia[i+1]:=jia[i] div 10;
      jia[i]:=jia[i] mod 10;
    end;
  if jia[l+1]<>0 then inc(l);
  jia[0]:=l;
end;

function cheng(a:hi; b:integer):hi;
var l,i:integer;
begin
  fillchar(cheng,sizeof(cheng),0);
  for i:=1 to a[0] do
    begin
      cheng[i]:=cheng[i]+a[i]*b;
      cheng[i+1]:=cheng[i] div 10;
      cheng[i]:=cheng[i] mod 10;
    end;
  l:=a[0];
  while cheng[l+1]<>0 do
    begin
      inc(l);
      cheng[l+1]:=cheng[l] div 10;
      cheng[l]:=cheng[l] mod 10;
    end;
  cheng[0]:=l;
end;

function bigger(a,b:hi):boolean;
var i:integer;
begin
  if a[0]>b[0] then exit(true);
  if a[0]<b[0] then exit(false);
  for i:=a[0] downto 1 do
    begin
      if a[i]>b[i] then exit(true);
      if a[i]<b[i] then exit(false);
    end;
  exit(false);
end;

procedure print1(k:integer; num:string);
var len,i:integer;
begin
  len:=length(num);
  fillchar(a,sizeof(a),0);
  for i:=1 to len do
    a[i]:=ord(num[len-i+1])-48;
  a[0]:=len;
  fillchar(b,sizeof(b),0);
  b[len]:=1;
  b[0]:=len;
  ans:=cheng(jian(a,b),len);
  b[len]:=0;
  for i:=len-1 downto 1 do
    begin
      b[i]:=9;
      b[0]:=i;
      b:=cheng(b,i);
      ans:=jia(ans,b);
      b[i]:=0;
    end;
  b[0]:=0;
  str(k-1,num);
  for i:=1 to length(num) do
    b[i]:=ord(num[length(num)-i+1])-48;
  b[0]:=length(num);
  fillchar(a,sizeof(a),0);
  a[0]:=1;
  a[1]:=1;
  ans:=jia(jian(ans,b),a);
  if bigger(best,ans) then best:=ans;
end;

procedure print2(k:integer; num:string);
var len,i:integer;
begin
  len:=length(num);
  fillchar(a,sizeof(a),0);
  for i:=1 to len do
    a[i]:=ord(num[len-i+1])-48;
  a[0]:=len;
  fillchar(b,sizeof(b),0);
  b[len]:=1;
  b[0]:=len;
  ans:=cheng(jian(a,b),len);
  b[len]:=0;
  for i:=len-1 downto 1 do
    begin
      b[i]:=9;
      b[0]:=i;
      b:=cheng(b,i);
      ans:=jia(ans,b);
      b[i]:=0;
    end;
  b[0]:=0;
  str(k,num);
  for i:=1 to length(num) do
    b[i]:=ord(num[length(num)-i+1])-48;
  b[0]:=length(num);
  fillchar(a,sizeof(a),0);
  a[0]:=1;
  a[1]:=1;
  ans:=jian(ans,b);
  ans:=jia(ans,a);
  if bigger(best,ans) then best:=ans;
end;

function judge(len:integer):boolean;
var i:integer;
    return:string;
begin
  judge:=false;
  for i:=1 to len do
   if ori[i]<>'0' then
    if i+len-1<=long then
      begin
        if com(i+len,copy(ori,i,len)) then
          begin
            print1(i,copy(ori,i,len));
            judge:=true;
          end;
      end
    else
      if special(len,copy(ori,1,i-1),copy(ori,i,255),return) then
        begin
          incc(return);
          print2(i-1,return);
          judge:=true;
        end;
end;

procedure doit;
var len:integer;
begin
  len:=0;
  repeat
    inc(len);
  until judge(len);
end;

procedure outit;
var i:integer;
begin
  for i:=best[0] downto 1 do write(best[i]);
  writeln;
end;

begin
  assign(output,'out.txt');
  rewrite(output);
  init;
  doit;
  outit;
  close(output);
end.

嗯，好久都没有来写过解题报告了。前段时间比较消沉，几乎没干什么。现在开始，系统地学东西了，从枚举贪心开始（其实就是跟着黑书走），抓紧时间咯。

至于斜率优化的PPT，家里电脑有点问题，PPT里无法输入中午，只有到学校去做了。

加油，嘿哦嘿！

社交网络

    首先这道题涉及最短路，其次看数据范围O(n^3)可以过。接下来考虑怎样记录从s经过v到达t的最短路方案数，g[i,j]记录i到j的最短路方案数，dis[i,j]记录i到j的最短路长度。如果存在dis[i,j]=dis[i,k]+dis[k,j]则g[i,j]=g[i,j]+g[i,k]*g[k,j]（所谓乘法原理，美其名曰：分步记数原理）。现在就可以考虑选一种算最短路算法，顺便记录g[i,j]。我用的Dijkstra，比较好理解，我就不细说了。

 

货币兑换

    本人很笨，那个O(nlogn)的算法没研究过，等研究了多……所以就用了个O(n^2)的算法，能拿60分不错了。这个算法还是还是比较好想，f[i]记录第i天兑换成钱后的最大价值。f[i]=max{k[j]*rate[i]*a[i]+k[j]*b[i] | k[j]=f[j]/(rate[j]*a[j]+b[j]), 1<=j<i}

Making the Grade

想到这种DP算法，我没这个级别，只有别人说了才做得来。算是立了个标志作为一种思路吧。

经证明，或者凭感觉，不论怎么调整，调整目标都是已知高度。所以把所有高度a[i]排序成b[i]。

f[i,j]表示a[i]变成b[j]的最小代价，f[i,j]=min{f[i-1,k] | 1<=k<=j}+|a[i]-b[j]|

写到这里，一定要形成一种优化的想法：用g[i,j]记录f[i,1]~f[i,j]的最小值，然后决策时就可以直接调用了f[i,j]=g[i-1,k]+|a[i]-b[j]|, g[i,j]=min{g[i,j-1],f[i,j]}。 边界g[i,0]=maxlongint。

由于这是抠门的USACO，只给了2Mb的内存，所以不得不改成了滚动数组再交