首页 > 代码库 > Codeforces#373 Div2
Codeforces#373 Div2
Ranting重新回到浅蓝的一场比赛
Problem A
题意:月亮的大小是按照这样的顺序排列的0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
然后给定一串数，试判断最后一个是增加还是减少
分析：这题还被hack了，对于最后一个不是0，15，且是一个数的情况，直接输出－1，然后只有一个数是0或15，分别对应增加或减少，然后其他的
情况就分别讨论与前一个数的关系就行
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <string> 5 #include <vector> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <bitset>10 #include <cmath>11 #include <queue>12 #include <stack>13 using namespace std;14 const int maxn=100;15 int a[maxn];16 int n;17 int main()18 {19 while(cin>>n)20 {21 for(int i=1;i<=n;i++)22 cin>>a[i];23 if(a[n]==0){24 cout<<"UP"<<endl;25 continue;26 }27 if(a[n]==15){28 cout<<"DOWN"<<endl;29 continue;30 }31 if(n==1){32 cout<<"-1"<<endl;33 continue;34 }35 if(a[n-1]<a[n]){36 cout<<"UP"<<endl;37 }else{38 cout<<"DOWN"<<endl;39 }40 }41 return 0;42 }
Problem B
题意：全是由r和b组成的字符串，要改成交错的，问至少要操作多少次
分析：这题可以(1)分别统计如果奇数位全为r，偶数位全为b要修改的次数，取二者当中的最大；(2)统计如果奇数位全为b，偶数位全为r要修改的次数，取二者当中的最大；最后再来求(1)和(2)的最小
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <string> 5 #include <vector> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <bitset>10 #include <cmath>11 #include <queue>12 #include <stack>13 using namespace std;14 const int maxn=100010;15 int a[maxn];16 int n;17 int main()18 {19 while(cin>>n)20 {21 for(int i=1;i<=n;i++){22 char ch;23 cin>>ch;24 if(ch==‘b‘){25 a[i]=0;26 }else{27 a[i]=1;28 }29 }30 31 int cntb=0,cntr=0;32 int ans=1<<30;33 int tot=0;34 for(int i=1;i<=n;i++){35 if(i%2==1){36 if(!a[i]){37 cntb++;38 }39 }40 }41 for(int i=1;i<=n;i++){42 if(i%2==0){43 if(a[i]){44 cntr++;45 }46 }47 }48 while(cntr&&cntb) tot++,cntr--,cntb--;49 tot+=cntr+cntb;50 ans=min(ans,tot);51 52 int cntr1=0,cntb1=0;53 int tot1=0;54 for(int i=1;i<=n;i++){55 if(i%2==1){56 if(a[i])57 cntb1++;58 }59 }60 for(int i=1;i<=n;i++){61 if(i%2==0){62 if(!a[i])63 cntr1++;64 }65 }66 while(cntb1&&cntr1) tot1++,cntr1--,cntb1--;67 tot1+=cntr1+cntb1;68 ans=min(ans,tot1);69 cout<<ans<<endl;70 }71 return 0;72 }
Problem C
暂时没做
Problem E
题意：给定一个数组，1表示对区间[l,r]每个数加上x，2表示统计[l,r]中已元素为下标的斐波拉契的和
分析：矩阵快速幂＋线段树 ，这题是很好的模板题，get一份很好的模板
1 // 2 // main.cpp 3 // E 4 // 5 // Created by wanghan on 16/9/26. 6 // Copyright © 2016年 wanghan. All rights reserved. 7 // 8 9 #include<iostream> 10 #include<cstdio> 11 #include<cstring> 12 #include<string> 13 #include<cmath> 14 #include<vector> 15 #include<queue> 16 #include<stack> 17 #include<algorithm> 18 #include<cctype> 19 #include<map> 20 #include<set> 21 #include<deque> 22 using namespace std; 23 const int N=2; 24 const long long MOD=1e9+7; 25 const int maxn=1e5+10; 26 int n,m; 27 28 //矩阵快速幂 29 struct Matrix{ 30 int a[2][2]; 31 Matrix(){ 32 memset(a,0,sizeof(a)); 33 } 34 void init(){ 35 for(int i=0;i<N;i++) 36 for(int j=0;j<N;j++) 37 a[i][j]=(i==j); 38 } 39 Matrix operator + (const Matrix &B)const{ 40 Matrix C; 41 for(int i=0;i<N;i++) 42 for(int j=0;j<N;j++) 43 C.a[i][j]=(a[i][j]+B.a[i][j])%MOD; 44 return C; 45 } 46 Matrix operator * (const Matrix &B)const{ 47 Matrix C; 48 for(int i=0;i<N;i++) 49 for(int k=0;k<N;k++) 50 for(int j=0;j<N;j++) 51 C.a[i][j]=(C.a[i][j]+1LL*a[i][k]*B.a[k][j])%MOD; 52 return C; 53 } 54 Matrix operator ^ (const int &t)const{ 55 Matrix A=(*this),res; 56 res.init(); 57 int p=t; 58 while(p){ 59 if(p&1) res=res*A; 60 A=A*A; 61 p>>=1; 62 } 63 return res; 64 } 65 }One,Two; 66 67 68 //线段树部分 69 Matrix sum[maxn<<2],add[maxn<<2]; 70 void PushUp(int rt){ 71 sum[rt]=sum[rt<<1]+sum[rt<<1|1]; 72 } 73 void Build(int l,int r,int rt){ 74 add[rt].init(); 75 if(l==r){ 76 sum[rt]=One; 77 return; 78 } 79 int mid=(l+r)/2; 80 Build(l,mid,rt<<1); 81 Build(mid+1,r,rt<<1|1); 82 PushUp(rt); 83 } 84 85 void PushDown(int rt,int l,int r) 86 { 87 if(add[rt].a[0][0]!=0){ 88 int mid=(l+r)/2; 89 add[rt<<1]=add[rt<<1]*add[rt]; 90 sum[rt<<1]=(sum[rt<<1]*add[rt]); 91 add[rt<<1|1]=(add[rt<<1|1]*add[rt]); 92 sum[rt<<1|1]=(sum[rt<<1|1]*add[rt]); 93 add[rt].init(); 94 } 95 } 96 void Update(int L,int R,Matrix& v, int l,int r,int rt){ 97 if(l>R||r<L) 98 return; 99 if(L<=l&&r<=R){100 add[rt]=add[rt]*v;101 sum[rt]=sum[rt]*v;102 return;103 }104 PushDown(rt, l, r);105 int mid=(l+r)/2;106 Update(L, R, v, l, mid, rt<<1);107 Update(L, R, v, mid+1, r, rt<<1|1);108 PushUp(rt);109 }110 int Query(int L,int R,int l,int r,int rt){111 if(l>R||r<L)112 return 0;113 if(L<=l&&r<=R)114 return sum[rt].a[0][1];115 PushDown(rt, l, r);116 int mid=(l+r)/2;117 return (Query(L, R, l, mid, rt<<1)118 +Query(L, R, mid+1, r, rt<<1|1))%MOD;119 }120 121 //初始化斐波拉契数列122 void Init(){123 One.a[0][0]=1,One.a[0][1]=1;124 One.a[1][0]=0,One.a[1][1]=0;125 Two.a[0][0]=1,Two.a[0][1]=1;126 Two.a[1][0]=1,Two.a[1][1]=0;127 }128 129 int tt[maxn];130 int main()131 {132 Init();133 while(scanf("%d%d",&n,&m)!=EOF)134 {135 Build(1, n, 1);136 for(int i=1;i<=n;i++)137 scanf("%d",&tt[i]);138 Matrix tmp;139 for(int i=1;i<=n;i++){140 tmp=Two^(tt[i]-1);141 Update(i, i, tmp, 1, n, 1);142 }143 for(int i=1;i<=m;i++){144 int num,x,y,w;145 scanf("%d",&num);146 if(num==1){147 scanf("%d%d%d",&x,&y,&w);148 tmp=Two^(w);149 Update(x, y, tmp, 1, n, 1);150 }else{151 scanf("%d%d",&x,&y);152 cout<<Query(x, y, 1, n, 1)<<endl;153 }154 }155 }156 return 0;157 }
Codeforces#373 Div2
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。