首页 > 代码库 > Codeforces Round #373 (Div. 2)
Codeforces Round #373 (Div. 2)
岑寂了一个暑假之后终于涨分了，借助了A题的hack大法， c题没有理解好题意，wa就放弃了，后来再样例的帮助下。。终于AC
现在还没搞懂矩阵啊。烦。。抄来别人的代码
A. Vitya in the Countryside
当n = 1时候特判0，15
1 #include <iostream> 2 #include <cstdio> 3 4 using namespace std; 5 int main() { 6 int n, m; 7 int a[100]; 8 scanf("%d", &n); 9 for(int i = 0;i < n; i++){10 scanf("%d", &a[i]);11 }12 if(a[n-1] == 15) printf("DOWN\n");13 else if(a[n-1] == 0) printf("UP\n");14 else if(n == 1) printf("-1\n");15 else if(a[n-1] < a[n-2]){16 printf("DOWN\n");17 }else printf("UP\n");18 return 0;19 }
B. Anatoly and Cockroaches
分别计算奇偶位r、b的个数，求一下就好
1 #include <iostream> 2 #include <cstdio> 3 4 using namespace std; 5 int main() { 6 int n, m; 7 char s[100002]; 8 scanf("%d", &n); 9 scanf("%s", s);10 int first_r = 0, first_b = 0, second_r = 0, second_b = 0;11 for(int i = 0; i < n; i++){12 if(i%2 == 0) {13 if(s[i] == ‘r‘) first_r++;14 else first_b++;15 }else {16 if(s[i] == ‘b‘) second_b++;17 else second_r++;18 }19 }20 //printf("%d %d %d %d\n", first_r, first_b, second_r, second_b);21 int ans1 = first_b + second_r - min(first_b, second_r);22 int ans2 = first_r + second_b - min(first_r, second_b);23 printf("%d\n", min(ans1, ans2));24 return 0;25 }
C. Efim and Strange Grade
搞得我也很恶心了， 分类讨论各个情况
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 int main() { 6 int n, m; 7 scanf("%d%d", &n, &m); 8 char s[200005]; 9 scanf("%s", s);10 int flag = 0, flags = 1;11 int ans = -1;12 for(int i = 0; i < n; i++) {13 if(s[i] == ‘.‘) {14 flag = 1;15 continue;16 }17 if(s[i] - ‘0‘ >= 5 && flag == 1 && m > 0) {18 ans = i;19 m--;20 break;21 }22 }23 if(ans == -1) printf("%s\n", s);24 else {25 int snow = 1;26 if(s[ans-1] == ‘.‘) ans--, flags = 0;27 for(int i = ans-1; i >= 0; i--) {28 if(s[i] == ‘.‘) continue;29 int sum = s[i] - ‘0‘ + snow;30 s[i] = sum%10 + ‘0‘;31 snow = sum/10;32 }33 if(snow == 1) {34 printf("1");35 for(int i = 0; i < ans; i++) printf("%c", s[i]);36 printf("\n");37 } else {38 int last = ans, now = 0;39 for(int i = last-1; i >= 0; i--) {40 if(s[i] == ‘.‘) {41 flags = 0;42 ans = i-1;43 continue;44 }45 int sum = s[i] - ‘0‘ + now;46 // printf("%d %d %d %d\n", i, now, sum, flags);47 if((sum <= 4 || m <= 0) && flags) {48 now = 0;49 s[i] = sum + ‘0‘;50 ans = i;51 break;52 } else if(flags) {53 m--;54 now = 1;55 ans--;56 } else {57 s[i] = sum%10 + ‘0‘;58 now = sum /10;59 }60 }61 if(now == 1) {62 printf("1");63 for(int i = 0; i <= ans; i++) printf("%c", s[i]);64 printf("\n");65 }66 else {67 if(s[ans] < ‘0‘ || s[ans] > ‘9‘) ans--;68 for(int i = 0; i <= ans; i++) printf("%c", s[i]);69 printf("\n");70 }71 }72 }73 return 0;74 }
E. Sasha and Array（抄的代码）
1 #include<cstdio> 2 using namespace std; 3 typedef long long LL; 4 const int N = 100010; 5 const int P = 1000000007; 6 7 struct Matrix { 8 int n,m; 9 LL c[3][3]; 10 Matrix() { 11 for(int i=0; i<2; i++)for(int j=0; j<2; j++)c[i][j]=0; 12 n=m=0; 13 return; 14 } 15 Matrix operator * (const Matrix & a) const { 16 Matrix b; 17 b.n=n; 18 b.m=a.m; 19 for(int i=0; i<n; i++) 20 for(int j=0; j<b.m; j++) { 21 for(int k=0; k<m; k++) 22 b.c[i][j]=(b.c[i][j]+c[i][k]*a.c[k][j])%P; 23 } 24 return b; 25 } 26 Matrix operator + (const Matrix & a) const { 27 Matrix b; 28 b.n=n; 29 b.m=m; 30 for(int i=0; i<n; i++) 31 for(int j=0; j<m; j++) 32 b.c[i][j]=(a.c[i][j]+c[i][j])%P; 33 return b; 34 } 35 } o,ini,oo,T[N<<2],tag[N<<2]; 36 37 Matrix FP(Matrix a,int x) { 38 oo=o; 39 for(; x; x>>=1,oo=oo*oo) 40 if(x&1) a=a*oo; 41 return a; 42 } 43 44 int n,m,seq[N]; 45 46 void Build(int x,int l,int r) { 47 T[x].n=1,T[x].m=2; 48 if(l==r) { 49 tag[x].n=tag[x].m=0; 50 T[x]=ini; 51 T[x]=FP(T[x],seq[l]-1); 52 return; 53 } 54 int mid=(l+r)>>1; 55 Build(x<<1,l,mid); 56 Build(x<<1|1,mid+1,r); 57 T[x]=T[x<<1]+T[x<<1|1]; 58 return; 59 } 60 61 void Pushdown(int x) { 62 if(tag[x].n==0) return; 63 T[x<<1]=T[x<<1]*tag[x]; 64 if(tag[x<<1].n==0) tag[x<<1]=tag[x]; 65 else tag[x<<1]=tag[x<<1]*tag[x]; 66 T[x<<1|1]=T[x<<1|1]*tag[x]; 67 if(tag[x<<1|1].n==0) tag[x<<1|1]=tag[x]; 68 else tag[x<<1|1]=tag[x<<1|1]*tag[x]; 69 tag[x].n=tag[x].m=0; 70 return; 71 } 72 73 void Change(int x,int l,int r,int L,int R,Matrix d) { 74 if(L<=l&&r<=R) { 75 if(tag[x].n==0) tag[x]=d; 76 else tag[x]=tag[x]*d; 77 T[x]=T[x]*d; 78 return; 79 } 80 Pushdown(x); 81 int mid=(l+r)>>1; 82 if(L<=mid) Change(x<<1,l,mid,L,R,d); 83 if(R>mid) Change(x<<1|1,mid+1,r,L,R,d); 84 T[x]=T[x<<1]+T[x<<1|1]; 85 return; 86 } 87 88 LL Query(int x,int l,int r,int L,int R) { 89 if(L<=l&&r<=R) return T[x].c[0][1]; 90 Pushdown(x); 91 int mid=(l+r)>>1; 92 LL res=0; 93 if(L<=mid) res+=Query(x<<1,l,mid,L,R); 94 if(R>mid) res+=Query(x<<1|1,mid+1,r,L,R); 95 res%=P; 96 return res; 97 } 98 99 int main() {100 ini.n=1;101 ini.m=2;102 ini.c[0][1]=1ll;103 o.n=2,o.m=2;104 o.c[1][0]=1ll;105 o.c[0][1]=1ll;106 o.c[1][1]=1ll;107 108 scanf("%d%d",&n,&m);109 for(int i=1; i<=n; i++) scanf("%d",&seq[i]);110 Build(1,1,n);111 112 int typ,l,r,x;113 for(int i=1; i<=m; i++) {114 scanf("%d%d%d",&typ,&l,&r);115 if(typ==2) printf("%I64d\n",Query(1,1,n,l,r));116 else {117 scanf("%d",&x);118 Change(1,1,n,l,r,FP(o,x-1));119 }120 }121 return 0;122 }
Codeforces Round #373 (Div. 2)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。