首页 > 代码库 > codeforces round373(div.2) 题解
codeforces round373(div.2) 题解
这一把打得还算过得去。。。
最大问题在于A题细节被卡了好久。。。连续被hack两次。。。
B题是个规律题。。。C题也是一个细节题。。。D由于不明原因标程错了被删掉了。。。E是个线段树套矩阵。。。
考试的时候过了ABC三个。。。
Problem A：
这题纯细节，只要看最后两个数就可以了。（注意n＝1的情况以及最后一个数是0或者15的情况）
代码如下：
1 var n,i:longint; 2 a:array[1..100] of longint; 3 begin 4 readln(n); 5 fillchar(a,sizeof(a),0); 6 for i:=1 to n do 7 read(a[i]); 8 readln; 9 if (a[n]=0) then writeln(‘UP‘)10 else if (a[n]=15) then writeln(‘DOWN‘)else11 if (n=1) then writeln(‘-1‘)12 else if (a[n]<a[n-1]) or (a[n]=15) then writeln(‘DOWN‘) 13 else writeln(‘UP‘);14 end.15
Problem B：
这题是个规律题。。。（或者说贪心）
先考虑010101的情况，并且假装（嗯，就是假装）不能进行染色，然后跑出最大值，
另一种情况一样处理，最后两个最大值较小的一个就是答案。
代码如下：
1 uses math; 2 var n,i,j,ans,ans1,ans2:longint; 3 a:array[0..100000] of longint; 4 x:char; 5 begin 6 readln(n); 7 fillchar(a,sizeof(a),0); 8 for i:=1 to n do 9 begin10 read(x);11 if (x=‘r‘) then a[i]:=1;12 end;13 ans1:=0;14 ans2:=0;15 for i:=1 to n do16 begin17 if (i mod 2=1) and (a[i]=0) then inc(ans1);18 if (i mod 2=0) and (a[i]=1) then inc(ans2);19 end;20 ans:=max(ans1,ans2);21 ans1:=0;22 ans2:=0;23 for i:=1 to n do24 begin25 if (i mod 2=0) and (a[i]=0) then inc(ans1);26 if (i mod 2=1) and (a[i]=1) then inc(ans2);27 end;28 ans:=min(ans,max(ans1,ans2));29 writeln(ans);30 end.31
Problem C：
这题是一个细节题。。。
先把大于等于5的或者等于4且后面一个数字可能进位的全部分开处理出来，
然后跑贪心就可以了，注意细节。。。
（P.S.这题的pretest非常弱。。。然后比赛结束发现room一堆人过了。。。第二天看的时候只有我和另一个人过了hhh）
代码如下：
1 var n,k,i,j,t,tmp,now,noww,cnt:longint; 2 a:array[1..200050] of char; 3 flag:array[1..200050] of longint; 4 begin 5 readln(n,t); 6 for i:=1 to n do 7 begin 8 read(a[i]); 9 if (a[i]=‘.‘) then cnt:=i;10 end;11 readln;12 fillchar(flag,sizeof(flag),0);13 if (ord(a[n])>=48+5) then flag[n]:=1;14 for i:=n-1 downto tmp+1 do15 if (ord(a[i])>=48+5) then flag[i]:=1 else if ((flag[i+1]>0) and (a[i]=‘4‘)) then flag[i]:=2;16 now:=cnt+1;17 while (now<=n) and (flag[now]<>1) do inc(now);18 if (now=n+1) then19 begin20 j:=n;21 while (j>cnt) and (a[j]=‘0‘) do dec(j);22 if (j=cnt) then j:=cnt-1;23 for i:=1 to j do24 write(a[i]);25 writeln;26 end27 else28 begin29 noww:=1;30 while (noww<=t) do31 begin32 if (flag[now-1]=2) then flag[now-1]:=1;33 now:=now-1;34 if (flag[now]<>1) then break;35 inc(noww);36 end;37 if (now=cnt) then38 begin39 j:=cnt-1;40 while (j>=1) do41 begin42 if (a[j]=‘9‘) then43 begin44 a[j]:=‘0‘;45 dec(j);46 end47 else48 begin49 a[j]:=chr(ord(a[j])+1);50 break;51 end;52 end;53 if (j=0) then write(‘1‘);54 for i:=1 to cnt-1 do55 write(a[i]);56 writeln;57 end58 else59 begin60 j:=now;61 while (j>=1) do62 begin63 if (a[j]=‘9‘) then64 begin65 a[j]:=‘0‘;66 dec(j);67 if (j=cnt) then j:=cnt-1;68 end69 else70 begin71 a[j]:=chr(ord(a[j])+1);72 break;73 end;74 end;75 if (j=0) then write(‘1‘);76 for i:=1 to cnt-1 do77 write(a[i]);78 j:=now;79 while (j>=cnt+1) and (a[j]=‘0‘) do dec(j);80 if (j>=cnt+1) then81 begin82 write(‘.‘);83 for i:=cnt+1 to j do84 write(a[i]);85 end;86 writeln;87 end;88 end;89 end.
Problem E：
这题是一个经典线段树，和模版题不同的是这题需要将原先的数字全部替换成矩阵。
中间用到一系列的快速幂，Fibonacci数列等运算。。。
然后卡卡常就能过了。。。
注意线段树调用的时候参数越少越好。。。（感谢cyand神犇QAQQQ）
代码如下：
1 type arr=array[1..2,1..2] of int64; 2 nodetype=record 3 sum,cover:arr; 4 flag:boolean; 5 lx,rx:longint; 6 end; 7 const modp=1000000007; 8 fff:arr=((1,0),(0,0)); 9 one:arr=((1,0),(0,1)); 10 onee:arr=((0,0),(0,0)); 11 oneee:arr=((1,1),(1,0)); 12 var t:array[0..400050] of nodetype; 13 a:array[0..100050] of longint; 14 i,j,n,m,op,x,y,z:longint; 15 xx:arr; 16 x1,y1:int64; 17 function plus(a,b:arr):arr; 18 var ans:arr; 19 i,j:longint; 20 begin 21 for i:=1 to 2 do 22 begin 23 ans[i,1]:=(a[i,1]+b[i,1]) mod modp; 24 ans[i,2]:=(a[i,2]+b[i,2]) mod modp; 25 end; 26 exit(ans); 27 end; 28 function time(a,b:arr):arr; 29 var ans:arr; 30 i,j,k:longint; 31 begin 32 for i:=1 to 2 do 33 for j:=1 to 2 do 34 ans[i,j]:=(a[i,1]*b[1,j]+a[i,2]*b[2,j]) mod modp; 35 exit(ans); 36 end; 37 function try1(i:longint):arr; 38 var ans,now:arr; 39 left:longint; 40 begin 41 ans:=one; 42 now:=oneee; 43 left:=i; 44 while (left>0) do 45 begin 46 if (left mod 2=1) then ans:=time(ans,now); 47 left:=left div 2; 48 now:=time(now,now); 49 end; 50 exit(ans); 51 end; 52 procedure build(node,lx,rx:longint); 53 var mid:longint; 54 begin 55 if (lx=rx) then 56 begin 57 t[node].sum:=time(fff,try1(a[lx]-1)); 58 t[node].cover:=one; 59 t[node].lx:=lx; 60 t[node].rx:=rx; 61 end 62 else 63 begin 64 mid:=(lx+rx) div 2; 65 build(node*2,lx,mid); 66 build(node*2+1,mid+1,rx); 67 t[node].sum:=plus(t[node*2].sum,t[node*2+1].sum); 68 t[node].cover:=one; 69 t[node].lx:=lx; 70 t[node].rx:=rx; 71 end; 72 end; 73 procedure pushdown(node:longint); 74 begin 75 if not(t[node].flag) then exit; 76 t[node*2].cover:=time(t[node*2].cover,t[node].cover); 77 t[node*2+1].cover:=time(t[node*2+1].cover,t[node].cover); 78 t[node*2].sum:=time(t[node*2].sum,t[node].cover); 79 t[node*2+1].sum:=time(t[node*2+1].sum,t[node].cover); 80 t[node*2].flag:=true; 81 t[node*2+1].flag:=true; 82 t[node].cover:=one; 83 t[node].flag:=false; 84 end; 85 procedure updata(node:longint); 86 var mid:longint; 87 begin 88 if (t[node].lx>y) or (t[node].rx<x) then exit; 89 if (t[node].lx>=x) and (t[node].rx<=y) then 90 begin 91 t[node].cover:=time(t[node].cover,xx); 92 t[node].sum:=time(t[node].sum,xx); 93 t[node].flag:=true; 94 exit; 95 end; 96 pushdown(node); 97 mid:=(t[node].lx+t[node].rx) div 2; 98 updata(node*2); 99 updata(node*2+1);100 t[node].sum:=plus(t[node*2].sum,t[node*2+1].sum);101 end;102 function query(node:longint):arr;103 var mid:longint;104 begin105 if (t[node].lx>y) or (t[node].rx<x) then exit(onee);106 if (t[node].lx>=x) and (t[node].rx<=y) then exit(t[node].sum);107 pushdown(node);108 mid:=(t[node].lx+t[node].rx) div 2;109 exit(plus(query(node*2),query(node*2+1)));110 end;111 begin112 readln(n,m);113 fillchar(t,sizeof(t),0);114 for i:=1 to n do115 read(a[i]);116 readln;117 build(1,1,n);118 for i:=1 to m do119 begin120 read(op);121 if (op=1) then122 begin123 readln(x,y,z);124 xx:=try1(z);125 updata(1);126 end127 else128 begin129 readln(x,y);130 writeln(query(1)[1,1]);131 end;132 end;133 end.
完结撒花！
codeforces round373(div.2) 题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。