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.