长沙集训-2019-08-21

<center>长沙集训 $ Day 3 $ 2019-08-21 </center>

得分：$ 193/300 $

---

T1 $ Matrix $

基本思路

此题可以用枚举解决，分别枚举每一列作为矩形中间点统计答案，最后取最大值。每次统计答案时，分别算出每一列相邻的 $ 1 $ 的个数 $ sum $：

之后从该列向两边查找（其实只向一边也可以），如果当前枚举的列为 $ k $ ，查找到的列为 $ i $ ，则答案为 $ |i-j| \cdot sum[i] $ 。

直接暴力查找的时间复杂度时 $ O(n \cdot m^2) $ ，为了加快速度，可以预处理出以 $ i $ 为中心的每行连续 $ 1 $ 的左右端点，之后计算 $ sum $ 时用前缀和处理。使时间复杂度降低为 $ O(n \cdot m) $ 。

程序

program matrix;

type tp=record
  l,r:longint;
end;

var
   f:array[0..1005,0..1005]of tp;
   a:array[0..1005,0..1005]of integer;
   sum:array[0..1005]of longint;
   n,m:longint;

function max(a,b:longint):longint;
begin
  if a>b then exit(a)
    else exit(b);
end;

procedure re;
var i,j:longint;
    s:ansistring;
begin
  for i:=1 to n do begin
    readln(s);
    for j:=1 to m do
      if s[j]='0' then a[i,j]:=0
        else a[i,j]:=1;
  end;
end;

procedure first;
var i,j,loc:longint;
    t:boolean;
begin
  for i:=1 to n do begin
    loc:=1;
    t:=false;
    for j:=1 to m do
      if a[i,j]<>0 then begin
        if t=true then begin
          f[i,j].l:=f[i,j-1].l;
          f[i,j].r:=f[i,j-1].r;
        end
          else begin
            while a[i,loc]<>0 do inc(loc);
            t:=true;
            f[i,j].l:=j;
            f[i,j].r:=loc;
          end;
      end
        else begin
          t:=false;
          inc(loc);
        end;
  end;
end;

function ans(x:longint):longint;
var i,t:longint;
begin
  fillchar(sum,sizeof(sum),0);
  for i:=1 to n do
    if a[i,x]=1 then begin
      inc(sum[f[i,x].l]);
      dec(sum[f[i,x].r]);
    end;
  for i:=1 to n do
    sum[i]:=sum[i]+sum[i-1];
  ans:=0;
  t:=0;
  for i:=x+1 to n do
    if sum[i]=sum[i-1] then inc(t)
      else break;
  for i:=x downto 1 do begin
    inc(t);
    ans:=max(ans,sum[i]*t);
  end;
  t:=0;
  for i:=x-1 downto 1 do
    if sum[i]=sum[i+1] then inc(t)
      else break;
  for i:=x to n do begin
    inc(t);
    ans:=max(ans,sum[i]*t);
  end;
end;

procedure main;
var i,j,anss:longint;
begin
  anss:=0;
  for i:=1 to m do 
    anss:=max(anss,ans(i));
  writeln(anss);
end;

begin
  readln(n,m);
  re;
  first;
  main;
end.

T2 $ Present $

基本思路

刚看到题面，第一反应：“这不是背包板子吗！”。看到数据范围：“。。。”。

这三天的 $ T2 $ 都异常巧妙，昨天考了最小生成树，今天的 $ T2 $ 则是一个最短路径。从原题上完全看不出和图论的联系，但是却能根据题目的特点进行转化：

假设所有的物品中，价值最小为 $ p_{min} $ 。如果一个值 $ W = \sum_{i=1}^n p_i \cdot k_i $ 可以被组成，那么 $ W = \sum_{i=1}^n p_i \cdot (k_i + p_{min} \cdot s_i) $ 也一定能被组成。

可以借此降低背包的上界，将最大容量从 $ 4 \times 10^7 $ 降为 $ p_{min} \cdot \sum_{i=1}^n p_i $ ，时间复杂度为 $ O(n \cdot p_{min} \cdot \sum_{i=1}^n p_i ) $ 。可以通过 $ 60 $% 的数据。

接下来，解决方法就非常巧妙了。由上可知，对于每一个询问 $ Q = C + p_{min} \cdot k $ ，只要判断 $ Q \mod p_{min} $ 能否被组成即可。所以我们只要知道能够被组成的数 $ K(K \mod p_{min} = C) $ ，的最小值是否小于 $ Q $ 即可。而解决这个问题，可以将 $ [0,p_{min}-1] $ 的每个数当成一个点，对于点 $ f $ ，将其向 $ (f + p_i) \mod p_{min} $ 的点连一条权值为 $ p_i $ 的无向边，最后算出从 $ 0 $ 到 $ i $ 的最短路便是 $ K(K \mod p_{min} = i) $ 的最小值。

程序

program present;
var
   dis:array[0..10005]of longint;
   a:array[0..505]of longint;
   n,m,w:longint;

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

procedure re;
var i:longint;
begin
  w:=maxint;
  for i:=1 to n do begin
    read(a[i]);
    w:=min(w,a[i]);
  end;
end;

procedure spfa;
var i,head,tail,f,v:longint;
    p:array[0..10005]of longint;
    tf:array[0..10005]of boolean;
begin
  fillchar(dis,sizeof(dis),$3f);
  fillchar(tf,sizeof(tf),0);
  dis[0]:=0;
  head:=0;
  tail:=1;
  p[tail]:=0;
  tf[0]:=true;
  while head<tail do begin
    inc(head);
    head:=head mod 10000;
    f:=p[head];
    for i:=1 to n do begin
      v:=(f+a[i]) mod w;
      if (a[i]<>w) and (dis[f]+a[i]<dis[v]) then begin
        dis[v]:=dis[f]+a[i];
        if tf[v]=false then begin
          inc(tail);
          tail:=tail mod 10000;
          p[tail]:=v;
          tf[v]:=true;
        end;
      end;
    end;
    tf[f]:=false;
  end;
end;

procedure main;
var i,ans,x:longint;
begin
  spfa;
  ans:=0;
  for i:=1 to m do begin
    read(x);
    if dis[x mod w]<=x then inc(ans);
  end;
  writeln(ans);
end;

begin
  read(n,m);
  re;
  main;
end.

T3 $ Mahjong $

基本思路

这是三天中最水的 $ T3 $ ，没有任何算法，就是按照题意模拟和枚举。主意好细节就可以，注意要先确定雀头，再查找顺子和刻子。对特殊牌型先行处理。

这题说明了看题是多重要，我没看到“字牌不能成顺子”，结果 $ 100 \to 63 $ 。

程序

program mahjong;

type arr=array[1..15]of longint;

type tp=record
  a:longint;
  b:char;
end;

var
   m,s,p,c:arr;
   ans:array[0..105]of tp;
   t:longint;


procedure re;
var ss:string;
    i,t:longint;
begin
  readln(ss);
  i:=1;
  while i<=length(ss) do begin
    val(ss[i],t);
    case ss[i+1] of
      'm':inc(m[t]);
      's':inc(s[t]);
      'p':inc(p[t]);
      'c':inc(c[t]);
    end;
    inc(i,3);
  end;
end;

function sc(m,s,p,c:arr):boolean;
var i,sum:longint;
begin

  //找刻子和顺子
  sum:=0;
  for i:=1 to 9 do
    if m[i]>0 then begin
      if m[i]<3 then while (m[i]>0) and (m[i+1]>0) and (m[i+2]>0) do begin
        inc(sum);
        dec(m[i]);
        dec(m[i+1]);
        dec(m[i+2]);
      end;
      if m[i]>=3 then begin
        inc(sum);
        dec(m[i],3);
      end;
      while (m[i]>0) and (m[i+1]>0) and (m[i+2]>0) do begin
        inc(sum);
        dec(m[i]);
        dec(m[i+1]);
        dec(m[i+2]);
      end;
    end;
  for i:=1 to 9 do
    if s[i]>0 then begin
      if s[i]<3 then while (s[i]>0) and (s[i+1]>0) and (s[i+2]>0) do begin
        inc(sum);
        dec(s[i]);
        dec(s[i+1]);
        dec(s[i+2]);
      end;
      if s[i]>=3 then begin
        inc(sum);
        dec(s[i],3);
      end;
      while (s[i]>0) and (s[i+1]>0) and (s[i+2]>0) do begin
        inc(sum);
        dec(s[i]);
        dec(s[i+1]);
        dec(s[i+2]);
      end;
    end;
  for i:=1 to 9 do
    if p[i]>0 then begin
      if p[i]<3 then while (p[i]>0) and (p[i+1]>0) and (p[i+2]>0) do begin
        inc(sum);
        dec(p[i]);
        dec(p[i+1]);
        dec(p[i+2]);
      end;
      if p[i]>=3 then begin
        inc(sum);
        dec(p[i],3);
      end;
      while (p[i]>0) and (p[i+1]>0) and (p[i+2]>0) do begin
        inc(sum);
        dec(p[i]);
        dec(p[i+1]);
        dec(p[i+2]);
      end;
    end;
  for i:=1 to 9 do
    if c[i]>=3 then begin
      inc(sum);
      dec(c[i],3);
    end;
  if sum<4 then exit(false)
    else exit(true);
  //

end;

function check(m,s,p,c:arr):boolean;
var i,sum:longint;
    tf:boolean;
begin

  //七对子
  sum:=0;
  for i:=1 to 9 do
    if m[i]>=2 then inc(sum);
  for i:=1 to 9 do
    if s[i]>=2 then inc(sum);
  for i:=1 to 9 do
    if p[i]>=2 then inc(sum);
  for i:=1 to 9 do
    if c[i]>=2 then inc(sum);
  if sum=7 then exit(true);
  if sum=0 then exit(false);
  //

  //国士无双
  tf:=true;
  for i:=2 to 8 do
    if m[i]<>0 then tf:=false;
  for i:=2 to 8 do
    if s[i]<>0 then tf:=false;
  for i:=2 to 8 do
    if p[i]<>0 then tf:=false;
  for i:=1 to 7 do
    if c[i]=0 then tf:=false;
  if (tf=true) and (m[1]>0) and (m[9]>0) and (s[1]>0) and (s[9]>0) and (p[1]>0) and (p[9]>0) then exit(true);
  //

  //找对子
  for i:=1 to 9 do
    if m[i]>=2 then begin
      dec(m[i],2);
      if sc(m,s,p,c)=true then exit(true);
      inc(m[i],2);
    end;
  for i:=1 to 9 do
    if s[i]>=2 then begin
      dec(s[i],2);
      if sc(m,s,p,c)=true then exit(true);
      inc(s[i],2);
    end;
  for i:=1 to 9 do
    if p[i]>=2 then begin
      dec(p[i],2);
      if sc(m,s,p,c)=true then exit(true);
      inc(p[i],2);
    end;
  for i:=1 to 7 do
    if c[i]>=2 then begin
      dec(c[i],2);
      if sc(m,s,p,c)=true then exit(true);
      inc(c[i],2);
    end;
  //

  exit(false);

end;

procedure main;
var i,t:longint;
begin
  t:=0;
  for i:=1 to 9 do
    if m[i]+1<5 then begin
      inc(m[i]);
      if check(m,s,p,c)=true then begin
        inc(t);
        ans[t].a:=i;
        ans[t].b:='m';
      end;
      dec(m[i]);
    end;
  for i:=1 to 9 do
    if s[i]+1<5 then begin
      inc(s[i]);
      if check(m,s,p,c)=true then begin
        inc(t);
        ans[t].a:=i;
        ans[t].b:='s';
      end;
      dec(s[i]);
    end;
  for i:=1 to 9 do
    if p[i]+1<5 then begin
      inc(p[i]);
      if check(m,s,p,c)=true then begin
        inc(t);
        ans[t].a:=i;
        ans[t].b:='p';
      end;
      dec(p[i]);
    end;
  for i:=1 to 7 do
    if c[i]+1<5 then begin
      inc(c[i]);
      if check(m,s,p,c)=true then begin
        inc(t);
        ans[t].a:=i;
        ans[t].b:='c';
      end;
      dec(c[i]);
    end;
  if t=0 then writeln('Nooten')
    else begin
      write(t,' ');
      for i:=1 to t do
        write(ans[i].a,ans[i].b,' ');
      writeln;
    end;
end;

begin
  readln(t);
  while t>0 do begin
    fillchar(m,sizeof(m),0);
    fillchar(s,sizeof(s),0);
    fillchar(p,sizeof(p),0);
    fillchar(c,sizeof(c),0);
    dec(t);
    re;
    main;
  end;
end.