codeforces round373(div.2) 题解

这一把打得还算过得去。。。

最大问题在于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.

完结撒花！

巴特西

codeforces round373(div.2) 题解

最新文章

热门文章