2019.2.11

长沙集训 $ Day1 $

今天是长沙集训的第一天，今天的题目还是比较简单的。

~~其实是老师特别出了简单题，照顾我这个蒟蒻！！！~~

T1完美子串

这题是普通的模拟，从字符串首开始，将尾指针向后移动。每移动一位就将该位上的字符放入桶中计数。

如果 $ 26 $ 个字母均已出现，则开始移动头指针，并将头指针处的字符从桶中去除。在所有子串中选择长度最小的作为答案。

程序

program str;
var
   s:array[0..2000005]of char;
   sum:array['A'..'Z']of longint;
   len,ans:longint;

procedure re;
var st:ansistring;
    i:longint;
begin
  readln(st);
  len:=length(st);
  for i:=1 to len do s[i]:=st[i];
end;

function sc:boolean;
var i:char;
begin
  for i:='A' to 'Z' do
    if sum[i]=0 then exit(false);
  exit(true);
end;

procedure main;
var head,tail:longint;
begin
  ans:=100000000;
  head:=0;
  tail:=1;
  while tail<=len do begin
    inc(sum[s[tail]]);
    while sc=true do begin
      if tail-head<ans then ans:=tail-head;
      inc(head);
      dec(sum[s[head]]);
    end;
    inc(tail);
  end;
  if ans=100000000 then writeln('QwQ')
    else writeln(ans);
end;

begin
  re;
  main;
end.

T2游戏

此题是一道数学题，若不是有 $ CRN $ 巨佬的思路我估计就爆零了…

假设局游戏的分数是 $ k_{1} \ \ k_{2} \ \ k_{3} …$

因为每人的得分只能是 $ k^{2} $ 或 $ k $ ，所以设两人的得分相乘为 $ P $ ， $ P=(k_{1} \cdot k_{2} \cdot k_{3} \cdot … \cdot k_{n})^{3}$ ,所以 $ \sqrt[3]{P} $ 一定是一个整数。

设 $ Q= \sqrt[3]{P} $ ，两人的得分也一定能被 $ Q $ 整除。

所以：

$ Q $ 不为整数，输出 $ No $
两人得分不能被 $ Q $ 整除，输出 $ No $
$ Q $ 为整数，且两人得分都能被 $ Q $ 整除，输出 $ Yes $

$ Q $ 可以用二分快速求出，记得用 $ int64 $ !!!

程序

program game;
var
   t:longint;

function sc(q:int64):int64;
var l,r,mid,ans:int64;
begin
  ans:=-1;
  l:=0;
  r:=1000001;
  while l<=r do begin
    mid:=(l+r) shr 1;
    if mid*mid*mid=q then begin ans:=mid;break; end;
    if mid*mid*mid<q then l:=mid+1
      else r:=mid-1;
  end;
  exit(ans);
end;

procedure main;
var x,y,z:int64;
    i:longint;
begin
  for i:=1 to t do begin
    read(x,y);
    z:=sc(x*y);   
    if z=-1 then writeln('No')
      else if (x mod z=0) and (y mod z=0) then writeln('Yes')
        else writeln('No');
  end;
end;

begin
  read(t);
  main;
end.

T3泥泞的牧场

这题是二分图匹配的模板题。

二分图

如此，像这种可以分成两份，每一份中的点互不相交的图就是二分图。

二分图匹配

如此，连接像这样无公共顶点的两条边，就是一个二分图匹配。

最大匹配

最大匹配就是选择尽量多的边，使得选中的边中任意两条边均没有公共点。如果所有的点都是匹配点那就是一个完美匹配。

上图的最大匹配便是 $ 3 $ 。

求解二分图匹配的基本算法是匈牙利算法。

匈牙利算法

增广路

从一个未匹配的点开始，依次走过未匹配边，匹配边，未匹配边，匹配边… 如果最后的终点是一个未匹配点（即最后一条边是一条未匹配边），那么这条路就是一条增广路。而将增广路上的未匹配边和匹配边进行互换，就会使得匹配边多一条。

匈牙利算法便是利用增广路进行处理。

处理方法

1.对于一个节点，遍历与其相连的节点，如果可以直接连接，就立即进行连接。

2.继续下一个节点，发现直连节点已被占用。

3.搜索到增广路。

4.依靠增广路进行扩展。

5.非增广路，不进行扩展。

6.无增广路，左侧无空节点，处理结束。

本题转化

本题题面虽与二分图无关，但可以通过奇妙的变化，转为二分图匹配问题。

我们将连续行的 $ * $ 设为左侧图，连续列的 $ * $ 设为右侧图，行列的交点设为在两节点之间连了一条边。

之后我们要求出此图的最小顶点覆盖，因为我们在一行&一列放上木板，相当于选取了图中的一个点，覆盖的泥地相当于图中与此顶点相连的边。所以用最少的木板覆盖全部泥地相当于选最少的顶点覆盖全部的边。

根据二分图特点，最小顶点覆盖=最大匹配，求出该图的最大匹配就是答案。

程序

program cover;
var
   f:array[0..55,0..55]of char;
   x,y:array[0..55,0..55]of longint;
   p:array[0..505,0..505]of longint;
   next,next_f:array[0..505]of longint;
   tf:array[0..505,0..505]of boolean;
   t:array[0..505]of boolean;
   n,m,ans,totx,toty:longint;

procedure re;
var i,j:longint;
    s:string;
begin
  for i:=0 to 55 do
    for j:=0 to 55 do f[i,j]:='.';
  for i:=1 to n do begin
    readln(s);
    for j:=1 to m do f[i,j]:=s[j];
  end;
end;

procedure cover1(p,q:longint);
var i:longint;
begin
  for i:=q to m do
    if f[p,i]='*' then x[p,i]:=totx
      else if f[p,i]='.' then break;
end;

procedure cover2(p,q:longint);
var i:longint;
begin
  for i:=q to n do
    if f[i,p]='*' then y[i,p]:=toty
      else if f[i,p]='.' then break;
end;

procedure dfs_first;
var i,j:longint;
begin
  for i:=1 to n do
    for j:=1 to m do
      if f[i,j]='*' then begin
        if f[i,j-1]='.' then begin
          inc(totx);
          cover1(i,j);
        end;
        if f[i-1,j]='.' then begin
          inc(toty);
          cover2(j,i);
        end;
      end;
end;

procedure dfs_up;
var i,j:longint;
begin
  for i:=1 to n do
    for j:=1 to m do
      if tf[x[i,j],y[i,j]]=false then begin
        tf[x[i,j],y[i,j]]:=true;
        inc(p[x[i,j],0]);
        p[x[i,j],p[x[i,j],0]]:=y[i,j];
      end;
end;

function dfs(q:longint):boolean;
var i:longint;
begin
  dfs:=false;
  for i:=1 to p[q,0] do
    if next_f[q]<>p[q,i] then
      if next[p[q,i]]=0 then begin
        next[p[q,i]]:=q;
        next_f[q]:=p[q,i];
        exit(true);
      end;
  for i:=1 to p[q,0] do
    if (next_f[q]<>p[q,i]) and (t[p[q,i]]=false) then begin
      t[p[q,i]]:=true;
      if dfs(next[p[q,i]])=true then begin
        next[p[q,i]]:=q;
        next_f[q]:=p[q,i];
        exit(true);
      end;
    end;
end;

procedure main;
var i:longint;
begin
  ans:=0;
  for i:=1 to totx do begin
    if dfs(i)=true then inc(ans);
    fillchar(t,sizeof(t),false);
  end;
end;

begin
  readln(n,m);
  re;
  dfs_first;
  dfs_up;
  main;
  writeln(ans);
end.