2019.2.14

长沙集训 $ Day 4 $

今天的题目异常困难，至少这是我最接近爆零的一次

---

T1 高斯消元

虽然题目名字是高斯消元，实际上和高斯消元法没半点关系！

这题的核心解法是栈，在读入时将数字压入栈中，如果栈顶有连续k个相同数字就将他们全部弹出。之后再从数列的首尾模拟将数字删去。

程序

var
  f:array[0..100005,1..2]of int64;
  n,m,k:int64;

procedure re;
var i:longint;
    x,t:int64;
begin
  t:=0;
  f[t,1]:=-1;
  for i:=1 to n do begin
    read(x);
    if x=f[t,1] then inc(f[t,2])
      else begin
        inc(t);
        f[t,1]:=x;
        f[t,2]:=1;
      end;
    if f[t,2]=k then begin
      f[t,2]:=0;
      dec(t);
    end;
  end;
  n:=t;
end;

procedure main;
var i,l,r:longint;
    sum,del:int64;
begin
  r:=n;
  sum:=0;
  del:=0;
  for i:=1 to n do inc(sum,f[i,2]);
  for i:=1 to n do begin
    if (i>=r) or (f[i,1]<>f[r,1]) then begin
      l:=i;
      break;
    end;
    if f[i,2]+f[r,2]=k then begin
      if l+1=r then begin
        f[i,2]:=0;
        f[r,2]:=0;
        l:=i;
        break;
      end else dec(r);
    end
      else if f[i,2]+f[r,2]>k then begin
        dec(f[r,2],k-f[i,2]);
        f[i,2]:=0;
      end else begin
        l:=i;
        break;
      end;
  end;
  if (l=r) and (l=1) then begin
    writeln(f[l,2]*m mod k);
    exit;
  end;
  if l=r then begin
    writeln(sum-1+f[l,2]*m mod k);
    exit;
  end;
  for i:=l to r do inc(del,f[i,2]);
  writeln(sum*m-(sum-del)*(m-1));
end;

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