2019.2.17

长沙集训 $ Day 7 $

T1 X国的军队

此题和国王游戏类似，看似毒瘤 $ DP $ ，其实是贪心+排序。

先看简单的情况：

据点	火力$ a $	人数$ b $
$ A $	$ a_1 $	$ b_1 $
$ B $	$ a_2 $	$ b_2 $

先打 $ A $ 再打 $ B $ ，需要总人数 $ sum_A=b_2-(b_1-a_1)+b_1 $

先打 $ B $ 再打 $ A $ ，需要总人数 $ sum_B=b_1-(b_2-a_2)+b_2 $

用两数相减比较大小：

$ sum_A-sum_B=(b_2-a_2)-(b_1-a_1) $

$ sum_A $ 小，先打 $ A $ 更优，此时 $ (b_2-a_2) < (b_1-a_1) $
$ sum_B $ 小，先打 $ B $ 更优，此时 $ (b_2-a_2) > (b_1-a_1) $

由此可知，不论何时， $ b-a $ 最大的据点一定是优先攻击的目标，只有这样我们才能以最小的人数攻击所有据点。

只需将数据以 $ b-a $ 从大到小排序后计算答案即可。

程序

program army;
type tp=record
  a,b,c:longint;
end;
var
   f:array[0..100005]of tp;
   t,n:int64;

procedure re;
var i:longint;
begin
  for i:=1 to n do begin
    read(f[i].a,f[i].b);
    f[i].c:=f[i].b-f[i].a;
  end;
end;

procedure qsort(l,r:longint);
var i,j:longint;
    t,mid:tp;
begin
  i:=l;
  j:=r;
  mid.a:=f[(l+r) shr 1].a;
  mid.c:=f[(l+r) shr 1].c;
  repeat
    while (f[i].c>mid.c) or ((f[i].c=mid.c) and (f[i].a<mid.a)) do inc(i);
    while (f[j].c<mid.c) or ((f[j].c=mid.c) and (f[j].a>mid.a)) do dec(j);
    if i<=j then begin
      t:=f[i];
      f[i]:=f[j];
      f[j]:=t;
      inc(i);
      dec(j);
    end;
  until i>j;
  if i<r then qsort(i,r);
  if l<j then qsort(l,j);
end;

procedure main;
var i:longint;
    ans,num:int64;
begin
  while t>0 do begin
    read(n);
    re;
    qsort(1,n);
    num:=0;
    ans:=0;
    for i:=1 to n do begin
      if f[i].b-num>0 then begin
        inc(ans,f[i].b-num);
        num:=f[i].b;
      end;
      num:=num-f[i].a;
    end;
    writeln(ans);
    dec(t);
  end;
end;

begin
  read(t);
  main;
end.

T2 排列组合

题目要我们对于每个给定 $ n $ 求这个式子的值：

$ C_{n}^{1} \cdot C_{n}^{1} + C_{n}^{2} \cdot C_{n}^{2} + C_{n}^{3} \cdot C_{n}^{3} + \ … \ + C_{n}^{n} \cdot C_{n}^{n} $

组合数公式：

$ C_{n}^{m}=\frac{n!}{m! \cdot (n-m)!}$

最简单的做法就是利用公式，对于每一个 $ n $ 求值，这样一次求值的时间复杂度是 $ O(n) $ ,有 $ T $ 次询问，总时间复杂度是 $ O(n \cdot T) $ ，保证 $ TLE $

所以我们要 $ O(n) $ 求出所有式子的值，然后 $ O(1) $ 处理询问。

这里要用到组合数平方和公式：

$ C_{n}^{1} \cdot C_{n}^{1} + C_{n}^{2} \cdot C_{n}^{2} + C_{n}^{3} \cdot C_{n}^{3} + \ … \ + C_{n}^{n} \cdot C_{n}^{n}=C_{2n}{n} $

对于此题，我们只要求出 $ C_{2n}^{n} \ \ \ , n \in [1,1000000] $ 的值即可。

程序

program pc;
const p=1000000007;

var
   f,ans:array[0..1000005]of int64;
   t,i:longint;

procedure up;
var i:longint;
    l,r,ans_c:int64;
begin
  l:=2;
  r:=2;
  ans_c:=2;
  ans[1]:=2;
  for i:=2 to 1000005 do begin
    inc(r);  
    ans_c:=(((ans_c*r) mod p)*f[i]) mod p;
    inc(r);
    ans_c:=(((ans_c*r) mod p)*f[l]) mod p;
    inc(l);
    ans[i]:=ans_c;
  end;
end;

procedure main;
var i,x:longint;
begin
  for i:=1 to t do begin
    read(x);
    writeln(ans[x]);
  end;
end;

begin
  read(t);
  f[0]:=0;
  f[1]:=1;
  for i:=2 to 1000005 do
    f[i]:=p-(p div i)*f[p mod i]mod p;
  up;
  main;
end.

T3 回文

看到求回文串，本来以为是要对 $ manacher $ 进行优化，最后发现正解和 $ manacher $ 一点关系都没有，而是毒瘤 $ DP $ ！

设 $ tf[i,j] $ 记录区间 $ [i,j] $ 是否为回文串：

$ tf[i,j]=tf[i+1,j-1] \ \ and \ \ (s[i]=s[j]) $

$ tf[i,j]=0 $ 表示区间未处理

$ tf[i,j]=1 $ 表示区间是回文串

$ tf[i,j]=2 $ 表示区间不是回文串

设 $ dp[i,j] $ 表示区间 $ [i,j] $ 的回文串个数：

当 $ tf[i,j]=2 $ 时：$ dp[i,j]=dp[i+1,j]+dp[i,j-1]-dp[i+1,j-1] $

当 $ tf[i,j]=1 $ 时：$ dp[i,j]=dp[i+1,j]+dp[i,j-1]-dp[i+1,j-1]+1 $

程序

program pal;
var
   tf:array[0..5005,0..5005]of integer;
   dp:array[0..5005,0..5005]of int64;
   s:array[0..5005]of char;
   len:longint;

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

procedure dp_up;
var i:longint;
begin
  for i:=1 to len do begin
    tf[i,i]:=1;   
    dp[i,i]:=1;
    dp[i,i+1]:=2;
    if s[i]=s[i+1] then begin
      tf[i,i+1]:=1;
      inc(dp[i,i+1]);
    end;
  end;
end;

function dfs(l,r:longint):boolean;
begin
  if l>r then exit(false);
  dfs:=false;  
  if tf[l,r]=2 then exit(false);
  if tf[l,r]=1 then exit(true)
    else begin
      if (dfs(l+1,r-1)=true) and (s[l]=s[r]) then tf[l,r]:=1
        else tf[l,r]:=2;
      if tf[l,r]=1 then exit(true)
        else exit(false);
    end;
end;

procedure dp_;
var i,j,l:longint;
begin        
  for i:=1 to len do begin
    l:=0;
    for j:=i to len do begin
      inc(l);
      dp[l,j]:=dp[l+1,j]+dp[l,j-1]-dp[l+1,j-1];
      if dfs(l,j)=true then inc(dp[l,j]);  
    end;
  end;
end;

procedure main;
var i,t,x,y:longint;
begin
  read(t);
  for i:=1 to t do begin
    read(x,y);
    writeln(dp[x,y]);
  end;
end;

begin
  re;  
  dp_up;
  dp_;
  main;
end.