1.23
Problem A Luxurious Houses
题意：给 n 个数 a[i],问使得 a[i] 为 [i,n] 最大值的时候需要给 a[i] 增加多少
简析：可以倒着扫一遍，维护一个 Max[i] 表示 从[i,n] 的最大值，如果 a[i] > Max[i+1] ,就是0，否则就是 Max[i+1]+1-a[i]
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 7 const int maxn = 100000 + 10; 8 9 int a[maxn], maxh[maxn]; 10 11 int main() 12 { 13 int n; scanf("%d", &n); 14 for(int i = 1; i <= n; i++) scanf("%d", a + i); 15 for(int i = n; i > 0; i--) maxh[i] = max(a[i], maxh[i+1]); 16 17 for(int i = 1; i < n; i++) { 18 if(a[i] > maxh[i+1]) printf("0 "); 19 else printf("%d ", maxh[i+1] + 1 - a[i]); 20 } 21 printf("0\n"); 22 23 return 0; 24 }
还可以用一个更笨的办法，每次直接用线段树查询[i,n] 的最大值
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<vector> 6 using namespace std; 7 8 #define getmid(l,r) ((l) + ((r) - (l)) / 2) 9 10 const int maxn = 200005; 11 int w[maxn],h[maxn],res[maxn]; 12 int n; 13 int nmax; 14 15 struct node{ 16 int l,r,maxx; 17 }t[4*maxn]; 18 19 void Push_up(int p){ 20 t[p].maxx = max(t[p<<1].maxx,t[p<<1|1].maxx); 21 } 22 23 void Build_tree(int p,int l,int r){ 24 t[p].l = l; 25 t[p].r = r; 26 if(l == r){ 27 t[p].maxx = h[l]; 28 return; 29 } 30 int mid = getmid(l,r); 31 Build_tree(p<<1,l,mid); 32 Build_tree(p<<1|1,mid+1,r); 33 Push_up(p); 34 } 35 36 void update(int idx,int p,int w){ 37 if(t[p].l == t[p].r){ 38 t[p].maxx = w; 39 return; 40 } 41 int mid = getmid(t[p].l,t[p].r); 42 if(idx <= mid) update(idx,p<<1,w); 43 else update(idx,p<<1|1,w); 44 Push_up(p); 45 } 46 47 void Query(int p,int l,int r){ 48 if(t[p].maxx <= nmax) return; 49 if(t[p].l == l && t[p].r == r){ 50 nmax = max(nmax,t[p].maxx); 51 return; 52 } 53 int mid = getmid(t[p].l,t[p].r); 54 if(r <= mid) Query(p<<1,l,r); 55 else if(l > mid) Query(p<<1|1,l,r); 56 else{ 57 Query(p<<1,l,mid); 58 Query(p<<1|1,mid+1,r); 59 } 60 } 61 62 int main(){ 63 while(scanf("%d",&n) != EOF){ 64 memset(h,0,sizeof(h)); 65 for(int i = 1;i <= n;i++) scanf("%d",&h[i]); 66 Build_tree(1,1,n); 67 68 // for(int i = 1;i <= 2*n;i++) 69 // printf("t[%d].l = %d t[%d].r = %d t[%d].maxx = %d\n",i,t[i].l,i,t[i].r,i,t[i].maxx); 70 71 for(int i = 1;i <= n;i++){ 72 if(i == n) res[i] = 0; 73 else{ 74 nmax = -1; 75 Query(1,i+1,n); 76 int b = nmax;//printf("i = %d b = %d\n",i,b); 77 // printf("i = %d nmaxx = %d\n",i,nmax); 78 if(b < h[i]) res[i] = 0; 79 else res[i] = b+1-h[i]; 80 } 81 } 82 83 for(int i = 1;i <= n;i++) printf("%d ",res[i]); 84 printf("\n"); 85 } 86 return 0; 87 }
Problem B Developing Skills
题意：给出 n 个数 a[i],k次操作，每次操作可以将a[i] 增加1，每个数的收益是floor(a[i]/10)，问最大的收益
简析：可以贪心的想，离整十更近的数 需要的操作数更少，所以按照 a[i]%10排序后，扫一遍就可以了
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<vector> 6 using namespace std; 7 8 const int maxn = 1e5+5; 9 int n,k; 10 11 struct node{ 12 int x,y; 13 }p[maxn]; 14 15 int cmp(node n1,node n2){ 16 return n1.y < n2.y; 17 } 18 19 int cmp0(node n1,node n2){ 20 return n1.x < n2.x; 21 } 22 23 int a[105]; 24 25 void solve(){ 26 for(int i = 1;i <= n;i++){ 27 int pos = lower_bound(a+1,a+10,p[i].x) - a; 28 if(a[pos] == p[i].x) pos++; 29 p[i].y = a[pos] - p[i].x; 30 } 31 sort(p+1,p+n+1,cmp); 32 int ans = 0; 33 for(int i = 1;i <= n;i++){ 34 if(k >= p[i].y){ 35 ans += (p[i].x + p[i].y)/10; 36 k -= p[i].y; 37 p[i].x = p[i].x + p[i].y; 38 } 39 else { 40 ans += p[i].x/10; 41 } 42 } 43 if(k){ 44 for(int i = 1;i <= n;i++){ 45 int l = 10 - p[i].x/10; 46 int r = k/10; 47 if(r >= l){ 48 ans += l; 49 k = k-l*10; 50 } 51 else{ 52 ans += k/10; 53 k = k%10; 54 } 55 if(k < 10) break; 56 } 57 } 58 printf("%d\n",ans); 59 } 60 61 int main(){ 62 for(int i = 1;i <= 10;i++) a[i] = i*10; 63 a[11] = 100; 64 // freopen("in.txt","r",stdin); 65 // freopen("out.txt","w",stdout); 66 while(scanf("%d %d",&n,&k) != EOF){ 67 for(int i = 1;i <= n;i++){ 68 scanf("%d",&p[i].x); 69 } 70 solve(); 71 } 72 return 0; 73 }
Problem C Three Logos
题意：给出 3 个矩形，问能否拼成一个正方形，如果能的话，输出正方形的边长和正方形
简析：暴力。可以先扫出最大的一条矩形边，这条边肯定作为正方形的边长，再枚举剩下的两个矩形的组合方式
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<vector> 6 using namespace std; 7 8 char g[105]; 9 char res[105][105]; 10 11 struct node{ 12 int x,y; 13 }a[5]; 14 15 int x2,y2,x3,y3,x1,y1; 16 int flag; 17 18 void work(int x2,int y2,int x3,int y3,char c1,char c2){ 19 if((y3 == y2) && (y3 + x1) == y1 && (x2 + x3) == y1){ 20 flag = 1; 21 for(int i = 1;i <= x2;i++){ 22 for(int j = x1+1;j <= y1;j++) res[i][j] = c1; 23 } 24 for(int i = x2+1;i <= y1;i++){ 25 for(int j = x1+1;j <= y1;j++) res[i][j] = c2; 26 } 27 } 28 29 if((y2 == y3) && (y2 == y1) && (x1 + x2 + x3) == y1){ 30 flag = 1; 31 for(int i = 1;i <= y1;i++){ 32 for(int j = x1 +1;j <= x1+x2;j++) res[i][j] = c1; 33 } 34 for(int i = 1;i <= y1;i++){ 35 for(int j = x1+x2+1;j <= y1;j++) res[i][j] = c2; 36 } 37 } 38 } 39 40 void print(){ 41 printf("%d\n",y1); 42 for(int i = 1;i <= y1;i++){ 43 for(int j = 1;j <= y1;j++) printf("%c",res[i][j]); 44 printf("\n"); 45 } 46 printf("\n"); 47 } 48 49 void solve(){ 50 g[1] = ‘A‘; g[2] = ‘B‘; g[3] = ‘C‘; 51 int maxx = -1; 52 for(int i = 1;i <= 3;i++) { 53 maxx = max(maxx,a[i].x); 54 maxx = max(maxx,a[i].y); 55 } 56 57 int pos = 0; 58 for(int i = 1;i <= 3;i++){ 59 if(a[i].x == maxx || a[i].y == maxx){ 60 pos = i; 61 break; 62 } 63 } 64 if(a[pos].x > a[pos].y) swap(a[pos].x,a[pos].y); 65 66 x1 = a[pos].x; y1 = a[pos].y; 67 68 for(int i = 1;i <= y1;i++){ 69 for(int j = 1;j <= x1;j++) res[i][j] = g[pos]; 70 } 71 72 int ok = 0; 73 char c1,c2; 74 for(int i = 1;i <= 3;i++){ 75 if(i != pos && ok == 0) { 76 x2 = a[i].x; 77 y2 = a[i].y; 78 c1 = g[i]; 79 ok = 1; 80 } 81 if(i != pos && ok){ 82 x3 = a[i].x; 83 y3 = a[i].y; 84 c2 = g[i]; 85 } 86 } 87 flag = 0; 88 work(x2,y2,x3,y3,c1,c2); 89 if(flag) { 90 print(); 91 return; 92 } 93 work(x2,y2,y3,x3,c1,c2); 94 if(flag) { 95 print(); 96 return; 97 } 98 work(y2,x2,x3,y3,c1,c2); 99 if(flag) { 100 print(); 101 return; 102 } 103 work(y2,x2,y3,x3,c1,c2); 104 if(flag) { 105 print(); 106 return; 107 } 108 puts("-1"); 109 } 110 111 int main(){ 112 while(scanf("%d %d %d %d %d %d",&a[1].x,&a[1].y,&a[2].x,&a[2].y,&a[3].x,&a[3].y) != EOF){ 113 solve(); 114 } 115 return 0; 116 }
一神的简洁的代码
1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 int a[6][3] = { 0, 1, 2, 0, 2, 1, 1, 0, 2, 1, 2, 0, 2, 0, 1, 2, 1, 0 }; 5 int b[8][6] = { 6 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 7 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 8 }; 9 char c[3] = {‘A‘, ‘B‘, ‘C‘}; 10 inline void pl(int x, int y){for(int i = 0; i < x; i++) putchar(c[y]);} 11 int d[3][2]; 12 13 int main(void) 14 { 15 for(int i = 0; i < 3; i++) scanf("%d %d", &d[i][0], &d[i][1]); 16 for(int i = 0; i < 6; i++) 17 { 18 for(int j = 0; j < 8; j++) 19 { 20 int A = a[i][0], B = a[i][1], C = a[i][2]; 21 int xa = d[A][b[j][0]], ya = d[A][b[j][1]]; 22 int xb = d[B][b[j][2]], yb = d[B][b[j][3]]; 23 int xc = d[C][b[j][4]], yc = d[C][b[j][5]]; 24 if(ya == yb && xa + xb == xc && ya + yc == xc) 25 { 26 printf("%d\n", xc); 27 for(int p = 1; p <= ya; p++) pl(xa, A), pl(xb, B), puts(""); 28 for(int p = 1; p <= yc; p++) pl(xc, C), puts(""); 29 return 0; 30 } 31 if(ya == yb && yb == yc && xa + xb + xc == ya) 32 { 33 printf("%d\n", ya); 34 for(int p = 1; p <= ya; p++) pl(xa, A), pl(xb, B), pl(xc, C), puts(""); 35 return 0; 36 } 37 } 38 } 39 puts("-1"); 40 return 0; 41 }
原文：http://www.cnblogs.com/chdacm/p/6344984.html
