这一把打得还算过得去。。。
最大问题在于A题细节被卡了好久。。。连续被hack两次。。。
B题是个规律题。。。C题也是一个细节题。。。D由于不明原因标程错了被删掉了。。。E是个线段树套矩阵。。。
考试的时候过了ABC三个。。。
Problem A：
这题纯细节，只要看最后两个数就可以了。（注意n＝1的情况以及最后一个数是0或者15的情况）
代码如下：
var n,i:longint;
a:array[..] of longint;
begin
readln(n);
fillchar(a,sizeof(a),);
for i:= to n do
read(a[i]);
readln;
if (a[n]=) then writeln('UP')
else if (a[n]=) then writeln('DOWN')else
if (n=) then writeln('-1')
else if (a[n]<a[n-]) or (a[n]=) then writeln('DOWN')
else writeln('UP');
end.
Problem B：
这题是个规律题。。。（或者说贪心）
先考虑010101的情况，并且假装（嗯，就是假装）不能进行染色，然后跑出最大值，
另一种情况一样处理，最后两个最大值较小的一个就是答案。
代码如下：
uses math;
var n,i,j,ans,ans1,ans2:longint;
a:array[..] of longint;
x:char;
begin
readln(n);
fillchar(a,sizeof(a),);
for i:= to n do
begin
read(x);
if (x='r') then a[i]:=;
end;
ans1:=;
ans2:=;
for i:= to n do
begin
if (i mod =) and (a[i]=) then inc(ans1);
if (i mod =) and (a[i]=) then inc(ans2);
end;
ans:=max(ans1,ans2);
ans1:=;
ans2:=;
for i:= to n do
begin
if (i mod =) and (a[i]=) then inc(ans1);
if (i mod =) and (a[i]=) then inc(ans2);
end;
ans:=min(ans,max(ans1,ans2));
writeln(ans);
end.
Problem C：
这题是一个细节题。。。
先把大于等于5的或者等于4且后面一个数字可能进位的全部分开处理出来，
然后跑贪心就可以了，注意细节。。。
（P.S.这题的pretest非常弱。。。然后比赛结束发现room一堆人过了。。。第二天看的时候只有我和另一个人过了hhh）
代码如下：
var n,k,i,j,t,tmp,now,noww,cnt:longint;
a:array[..] of char;
flag:array[..] of longint;
begin
readln(n,t);
for i:= to n do
begin
read(a[i]);
if (a[i]='.') then cnt:=i;
end;
readln;
fillchar(flag,sizeof(flag),);
if (ord(a[n])>=+) then flag[n]:=;
for i:=n- downto tmp+ do
if (ord(a[i])>=+) then flag[i]:= else if ((flag[i+]>) and (a[i]='')) then flag[i]:=;
now:=cnt+;
while (now<=n) and (flag[now]<>) do inc(now);
if (now=n+) then
begin
j:=n;
while (j>cnt) and (a[j]='') do dec(j);
if (j=cnt) then j:=cnt-;
for i:= to j do
write(a[i]);
writeln;
end
else
begin
noww:=;
while (noww<=t) do
begin
if (flag[now-]=) then flag[now-]:=;
now:=now-;
if (flag[now]<>) then break;
inc(noww);
end;
if (now=cnt) then
begin
j:=cnt-;
while (j>=) do
begin
if (a[j]='') then
begin
a[j]:='';
dec(j);
end
else
begin
a[j]:=chr(ord(a[j])+);
break;
end;
end;
if (j=) then write('');
for i:= to cnt- do
write(a[i]);
writeln;
end
else
begin
j:=now;
while (j>=) do
begin
if (a[j]='') then
begin
a[j]:='';
dec(j);
if (j=cnt) then j:=cnt-;
end
else
begin
a[j]:=chr(ord(a[j])+);
break;
end;
end;
if (j=) then write('');
for i:= to cnt- do
write(a[i]);
j:=now;
while (j>=cnt+) and (a[j]='') do dec(j);
if (j>=cnt+) then
begin
write('.');
for i:=cnt+ to j do
write(a[i]);
end;
writeln;
end;
end;
end.
Problem E：
这题是一个经典线段树，和模版题不同的是这题需要将原先的数字全部替换成矩阵。
中间用到一系列的快速幂，Fibonacci数列等运算。。。
然后卡卡常就能过了。。。
注意线段树调用的时候参数越少越好。。。（感谢cyand神犇QAQQQ）
代码如下：
type arr=array[..,..] of int64;
nodetype=record
sum,cover:arr;
flag:boolean;
lx,rx:longint;
end;
const modp=;
fff:arr=((,),(,));
one:arr=((,),(,));
onee:arr=((,),(,));
oneee:arr=((,),(,));
var t:array[..] of nodetype;
a:array[..] of longint;
i,j,n,m,op,x,y,z:longint;
xx:arr;
x1,y1:int64;
function plus(a,b:arr):arr;
var ans:arr;
i,j:longint;
begin
for i:= to do
begin
ans[i,]:=(a[i,]+b[i,]) mod modp;
ans[i,]:=(a[i,]+b[i,]) mod modp;
end;
exit(ans);
end;
function time(a,b:arr):arr;
var ans:arr;
i,j,k:longint;
begin
for i:= to do
for j:= to do
ans[i,j]:=(a[i,]*b[,j]+a[i,]*b[,j]) mod modp;
exit(ans);
end;
function try1(i:longint):arr;
var ans,now:arr;
left:longint;
begin
ans:=one;
now:=oneee;
left:=i;
while (left>) do
begin
if (left mod =) then ans:=time(ans,now);
left:=left div ;
now:=time(now,now);
end;
exit(ans);
end;
procedure build(node,lx,rx:longint);
var mid:longint;
begin
if (lx=rx) then
begin
t[node].sum:=time(fff,try1(a[lx]-));
t[node].cover:=one;
t[node].lx:=lx;
t[node].rx:=rx;
end
else
begin
mid:=(lx+rx) div ;
build(node*,lx,mid);
build(node*+,mid+,rx);
t[node].sum:=plus(t[node*].sum,t[node*+].sum);
t[node].cover:=one;
t[node].lx:=lx;
t[node].rx:=rx;
end;
end;
procedure pushdown(node:longint);
begin
if not(t[node].flag) then exit;
t[node*].cover:=time(t[node*].cover,t[node].cover);
t[node*+].cover:=time(t[node*+].cover,t[node].cover);
t[node*].sum:=time(t[node*].sum,t[node].cover);
t[node*+].sum:=time(t[node*+].sum,t[node].cover);
t[node*].flag:=true;
t[node*+].flag:=true;
t[node].cover:=one;
t[node].flag:=false;
end;
procedure updata(node:longint);
var mid:longint;
begin
if (t[node].lx>y) or (t[node].rx<x) then exit;
if (t[node].lx>=x) and (t[node].rx<=y) then
begin
t[node].cover:=time(t[node].cover,xx);
t[node].sum:=time(t[node].sum,xx);
t[node].flag:=true;
exit;
end;
pushdown(node);
mid:=(t[node].lx+t[node].rx) div ;
updata(node*);
updata(node*+);
t[node].sum:=plus(t[node*].sum,t[node*+].sum);
end;
function query(node:longint):arr;
var mid:longint;
begin
if (t[node].lx>y) or (t[node].rx<x) then exit(onee);
if (t[node].lx>=x) and (t[node].rx<=y) then exit(t[node].sum);
pushdown(node);
mid:=(t[node].lx+t[node].rx) div ;
exit(plus(query(node*),query(node*+)));
end;
begin
readln(n,m);
fillchar(t,sizeof(t),);
for i:= to n do
read(a[i]);
readln;
build(,,n);
for i:= to m do
begin
read(op);
if (op=) then
begin
readln(x,y,z);
xx:=try1(z);
updata();
end
else
begin
readln(x,y);
writeln(query()[,]);
end;
end;
end.
完结撒花！
