2019.2.13
长沙集训 $ Day 3 $
今天的题突然变得简单了，感觉比 $ Day 1 $ 还简单，但一看标题…
$ NOIP $ 模拟赛！！！
T1 A
没错，今天的题目名称就是这么敷衍，甚至于题目描述也十分模糊…
第一题是一道模拟水题，只要按照横坐标从左到右枚举一遍，取最大答案即可。
评测结果我只有 $ 40 $ 分，但是用数据自测答案却是正确的，在本地用 $ lemon $ 测就 $ AC $ 了！？此问题有待解决…
程序
program a;
var
m,b,n:int64;
ans:int64;
procedure main;
var i:longint;
t,sum,max:int64;
begin
if (m<0) and (b>0) then begin
writeln((1+b)*b div 2);
exit;
end;
if (m<0) and (b<0) then begin
writeln((1+n)*n div 2);
exit;
end;
if (m>0) and (b<0) then begin
writeln('0');
exit;
end; //特判，防止m<0或b<0
t:=b+1;
ans:=(1+b)*b div 2;
sum:=ans;
max:=ans;
for i:=1 to n do begin
while t-1>-(i/m)+b do begin
dec(t);
dec(sum,t+i-1);
dec(max,i*t+(i*(i-1) div 2));
end;
inc(sum,t);
inc(max,sum);
if max>ans then ans:=max;
end;
writeln(ans);
end;
begin
ans:=0;
read(m,b);
n:=abs(m*b);
main;
end.T2 B
此题虽是 $ T2 $ ，但难度却远超 $ T3 $ ，思路并不复杂，但代码就…
一看到将区间覆盖成 $ 1 $ 或 $ 0 $ ，立刻就想到线段树，但如何维护？好在我做染色和软件包管理器时的处理方式给了我启发！
对于 $ tree[t] $ :
$ tree[t].l $ 维护 $ t $ 区间最左边连续 $ 0 $ 的个数
$ tree[t].r $ 维护 $ t $ 区间最有边连续 $ 0 $ 的个数
$ tree[t].p $ 维护 $ t $ 区间最多连续 $ 0 $ 的个数
有了储存方式，接下来就是修改了：
像如上这些区间的修改是一大难点
修改 $ tree[t].p $ :
$ tree[t].p = max(tree[t \ \ shl \ \ 1].r+tree[t \ \ shl \ \ 1 + 1].l,tree[t \ \ shl \ \ 1].p,tree[t \ \ shl \ \ 1 + 1].p) $
修改 $ tree[t].l $ 和 $ tree[t].r $ :
$ tree[t].l=tree[t \ \ shl \ \ 1].p+tree[t \ \ shl \ \ 1 + 1].l \ \ \ \ \ \ \ \ tree[t \ \ shl \ \ 1] $ 的区间全是 $ 0 $
$ tree[t].l=tree[t \ \ shl \ \ 1].l $
$ tree[t].r=tree[t \ \ shl \ \ 1].r+tree[t \ \ shl \ \ 1 + 1].p \ \ \ \ \ \ \ \ tree[t \ \ shl \ \ 1 + 1] $ 的区间全是 $ 0 $
$ tree[t].r=tree[t \ \ shl \ \ 1 + 1].r $
查找答案：
- $ tree[t].l>=len $ 处理答案
- $ tree[t \ \ shl \ \ 1].p>=len $ 扩展到$ t \ \ shl \ \ 1 $ 节点
- $ tree[t \ \ shl \ \ 1].r+tree[t \ \ shl \ \ 1 + 1].l>=len $ 处理答案
- $ tree[t \ \ shl \ \ 1 + 1].p>=len $ 扩展到 $ t \ \ shl \ \ 1 + 1 $ 节点
- $ tree[t].r>=len $ 处理答案
按照从 $ 1 $ 到 $ 5 $ 的步骤处理，随时下放懒标记
程序
program b;
type tp=record
l,r,p:longint;
end;
var
tree,tree_simple:array[0..200005]of tp;
p:array[0..200005]of integer;
n,m:longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
procedure up(t:longint);
begin
tree[t].p:=max(tree[t shl 1].r+tree[t shl 1 + 1].l,max(tree[t shl 1].p,tree[t shl 1 + 1].p));
if tree[t shl 1].p=tree_simple[t shl 1].p then tree[t].l:=tree[t shl 1].p+tree[t shl 1 + 1].l
else tree[t].l:=tree[t shl 1].l;
if tree[t shl 1 + 1].p=tree_simple[t shl 1 + 1].p then tree[t].r:=tree[t shl 1].r+tree[t shl 1 + 1].p
else tree[t].r:=tree[t shl 1 + 1].r;
end;
procedure build_simple(l,r,t:longint);
var mid:longint;
begin
if l=r then begin
tree_simple[t].p:=1;
tree_simple[t].l:=1;
tree_simple[t].r:=1;
exit;
end;
mid:=(l+r) shr 1;
build_simple(l,mid,t shl 1);
build_simple(mid+1,r,t shl 1 + 1);
tree_simple[t].p:=tree_simple[t shl 1].p+tree_simple[t shl 1 + 1].p;
tree_simple[t].l:=tree_simple[t shl 1].l+tree_simple[t shl 1 + 1].l;
tree_simple[t].r:=tree_simple[t shl 1].r+tree_simple[t shl 1 + 1].r;
end;
procedure down(t:longint); //下放懒标记
begin
if p[t]=0 then exit;
if p[t]=1 then begin
p[t shl 1]:=p[t];
p[t shl 1 + 1]:=p[t];
tree[t shl 1].p:=0;
tree[t shl 1].l:=0;
tree[t shl 1].r:=0;
tree[t shl 1 + 1].p:=0;
tree[t shl 1 + 1].l:=0;
tree[t shl 1 + 1].r:=0;
p[t]:=0;
end;
if p[t]=2 then begin
p[t shl 1]:=p[t];
p[t shl 1 + 1]:=p[t];
tree[t shl 1]:=tree_simple[t shl 1];
tree[t shl 1 + 1]:=tree_simple[t shl 1 + 1];
p[t]:=0;
end;
end;
procedure change(l,r,t,x,y,k:longint);
var mid:longint;
begin
if (x<=l) and (y>=r) then begin
if k=1 then begin
tree[t].p:=0;
tree[t].l:=0;
tree[t].r:=0;
end
else tree[t]:=tree_simple[t];
p[t]:=k;
exit;
end;
mid:=(l+r) shr 1;
down(t);
if x<=mid then change(l,mid,t shl 1,x,y,k);
if y>=mid+1 then change(mid+1,r,t shl 1 + 1,x,y,k);
up(t);
end;
function dfs(l,r,t,k,len:longint):boolean;
var mid:longint;
begin
dfs:=false;
mid:=(l+r) shr 1;
down(t);
if tree[t].l>=len then begin
writeln(l);
change(1,n,1,l,l+len-1,k);
exit(true);
end;
if tree[t shl 1].p>=len then dfs:=dfs(l,mid,t shl 1,k,len);
if dfs=true then exit(true);
if tree[t shl 1].r+tree[t shl 1 + 1].l>=len then begin
writeln(mid-tree[t shl 1].r+1);
change(1,n,1,mid-tree[t shl 1].r+1,mid-tree[t shl 1].r+len,k);
exit(true);
end;
if tree[t shl 1 + 1].p>=len then dfs:=dfs(mid+1,r,t shl 1 + 1,k,len);
if dfs=true then exit(true);
if tree[t].r>=len then begin
writeln(r-tree[t].r+1);
change(1,n,1,r-tree[t].r+1,r-tree[t].r+len,k);
exit(true);
end;
exit(false);
end;
procedure main;
var i,x,y,z:longint;
begin
for i:=1 to m do begin
read(x);
if x=1 then begin
read(y);
if dfs(1,n,1,1,y)=false then writeln('0');
end
else begin
read(y,z);
change(1,n,1,y,y+z-1,2);
end;
end;
end;
begin
read(n,m);
build_simple(1,n,1);
tree:=tree_simple;
main;
end.T3 C
此题其实并不复杂，一看到字符串的循环，立刻就想到 $ KMP $ ，但是…
我却敲不出 $ KMP $ 的代码，我好弱啊…
判断循环节方法：
到第 $ i $ 位时，若 $ i \ \ mod \ \ (i-next[i])=0 $ 且 $ i \ \ div \ \ (i-next[i])>1 $ ,则构成循环节。
程序
program c;
var
s:array[0..1000005]of char;
next:array[0..1000005]of longint;
n:longint;
procedure re;
var i:longint;
p:ansistring;
begin
readln(p);
for i:=1 to n do s[i]:=p[i];
end;
procedure first;
var i,k:longint;
begin
i:=0;
k:=-1;
next[0]:=-1;
while i<n do
if (k=-1) or (s[i+1]=s[k+1]) then begin
inc(k);
inc(i);
next[i]:=k;
if (i mod (i-next[i])=0) and (i div (i-next[i])<>1) then writeln(i,' ',i div (i-next[i]));
end else k:=next[k];
end;
begin
readln(n);
re;
first;
end.