Codeforces Round #308 (Div. 2) 题解

题意：给你n个矩形，问你他们的面积和是多少，是这样的吧-w-

解：~

 1 /*
 2  * Problem:  
 3  * Author:  SHJWUDP
 4  * Created Time:  2015/7/3 星期五 12:19:42
 5  * File Name: 233.cpp
 6  * State: 
 7  * Memo: 
 8  */
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <algorithm>
13 
14 using namespace std;
15 
16 int n;
17 int main() {
18 #ifndef ONLINE_JUDGE
19     freopen("in", "r", stdin);
20     //freopen("out", "w", stdout);
21 #endif
22     while(~scanf("%d", &n)) {
23         int sum=0;
24         for(int i=0; i<n; i++) {
25             int a, b, c, d;
26             scanf("%d%d%d%d", &a, &b, &c, &d);
27             sum+=(c-a+1)*(d-b+1);
28         }
29         printf("%d
", sum);
30     }
31     return 0;
32 }

View Code

B、Vanya and Books

题意：给你一个n，问你1~n有多少位数，tips：1,7,5是一位数；21,33,99是两位数

解：~

 1 /*
 2  * Problem:  
 3  * Author:  SHJWUDP
 4  * Created Time:  2015/7/3 星期五 12:19:42
 5  * File Name: 233.cpp
 6  * State: 
 7  * Memo: 
 8  */
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <algorithm>
13 
14 using namespace std;
15 
16 typedef long long int64;
17 
18 const int MaxA=9+7;
19 
20 int n;
21 int64 table[MaxA];
22 int64 pow(int x, int n) {
23     int64 res=1;
24     while(n--) {
25         res*=x;
26     }
27     return res;
28 }
29 int main() {
30 #ifndef ONLINE_JUDGE
31     freopen("in", "r", stdin);
32     //freopen("out", "w", stdout);
33 #endif
34     table[0]=0;
35     for(int i=1; i<=9; i++) {
36         table[i]=table[i-1]+(pow(10, i)-pow(10, i-1))*i;
37     }
38     while(~scanf("%d", &n)) {
39         int x=0;
40         while(pow(10, x+1)<=n) x++;
41         printf("%I64d
", table[x]+(x+1)*(n-pow(10, x)+1));
42     }
43     return 0;
44 }

View Code

C、Vanya and Scales

题意：给你一个天平和一些砝码，砝码的质量为w的0~100次方（每种一个），问你能不能称出质量为m的物品

解：看到一个很棒的解法，将m化为w进制，从低位到高位考虑，如果该位为0或者1，直接跳过，如果为w-1，将m增加1个当前位的砝码，继续运算，这样就绕过了情况较复杂的减法

 1 /*
 2  * Problem:  
 3  * Author:  SHJWUDP
 4  * Created Time:  2015/7/13 星期一 14:10:32
 5  * File Name: 233.cpp
 6  * State: 
 7  * Memo: 
 8  */
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <algorithm>
13 
14 using namespace std;
15 
16 const int MaxA=64+7;
17 
18 int W, M;
19 int stk[MaxA], top;
20 int main() {
21 #ifndef ONLINE_JUDGE
22     freopen("in", "r", stdin);
23     //freopen("out", "w", stdout);
24 #endif
25     while(~scanf("%d%d", &W, &M)) {
26         if(W<=3) {
27             puts("YES");
28             continue;
29         }
30         top=0;
31         bool ok=1;
32         do {
33             int x=M%W;
34             if(x<=1) M/=W;
35             else if(x==W-1) M=M/W+1;
36             else {
37                 ok=0;
38                 break;
39             }
40         } while(M);
41         puts(ok?"YES":"NO");
42     }
43     return 0;
44 }

View Code

D、Vanya and Triangles

题意：给你欧式平面上的一些点，问你这些点做顶点能组成多少个三角形

解：~

 1 /*
 2  * Problem:  
 3  * Author:  SHJWUDP
 4  * Created Time:  2015/7/13 星期一 14:41:52
 5  * File Name: 233.cpp
 6  * State: 
 7  * Memo: 
 8  */
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <algorithm>
13 #include <map>
14 
15 using namespace std;
16 
17 const int MaxA=2000+7;
18 
19 struct Point {
20     int x, y;
21 } p[MaxA];
22 
23 int n;
24 int main() {
25 #ifndef ONLINE_JUDGE
26     freopen("in", "r", stdin);
27     //freopen("out", "w", stdout);
28 #endif
29     while(~scanf("%d", &n)) {
30         for(int i=0; i<n; i++) {
31             scanf("%d%d", &p[i].x, &p[i].y);
32         }
33         int ans=0;
34         for(int i=0; i<n; i++) {
35             int surplus=n-i-1;
36             map<pair<int, int>, int> M;
37             for(int j=i+1; j<n; j++) {
38                 int dx=p[j].x-p[i].x;
39                 int dy=p[j].y-p[i].y;
40                 if(dx<0) dx=-dx, dy=-dy;
41                 int d=__gcd(dx, dy);
42                 dx/=d; dy/=d;
43                 pair<int, int> x(dx, dy);
44                 M[x]++;
45             }
46             for(const auto& u : M) {
47                 surplus-=u.second;
48                 ans+=u.second*surplus;
49             }
50         }
51         printf("%d
", ans);
52     }
53     return 0;
54 }

View Code

E、Vanya and Brackets

题意：给你一个只有+和*还有数字1~9组成的算式，让你加入一对括号使得算式的值尽可能大

解：遇见这么深藏不露的模拟题也是醉了

 1 /*
 2  * Problem:  
 3  * Author:  SHJWUDP
 4  * Created Time:  2015/7/13 星期一 22:17:46
 5  * File Name: 233.cpp
 6  * State: 
 7  * Memo: 
 8  */
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <algorithm>
13 
14 using namespace std;
15 
16 typedef long long int64;
17 
18 const int MaxA=5e3+7;
19 
20 char str[MaxA];
21 int64 arr[MaxA], n;
22 char op[MaxA];  //0:'+' 1:'*'
23 int64 func(int l, int r) {
24     int64 res=0, x=arr[l];
25     for(int i=l; i<r; i++) {
26         if(op[i]=='+') {
27             res+=x;
28             x=arr[i+1];
29         } else {
30             x*=arr[i+1];
31         }
32     }
33     res+=x;
34     return res;
35 }
36 int main() {
37 #ifndef ONLINE_JUDGE
38     freopen("in", "r", stdin);
39     //freopen("out", "w", stdout);
40 #endif
41     while(~scanf("%s", str)) {
42         int len=strlen(str);
43         n=0;
44         vector<int> pos;
45         for(int i=0; i+1<len; i+=2) {
46             if(i==0 || str[i-1]!=str[i+1]) pos.push_back(n);
47             arr[n]=str[i]-'0';
48             op[n++]=str[i+1];
49         }
50         pos.push_back(n);
51         arr[n]=str[len-1]-'0';
52         int64 ans=func(0, n);
53         for(int i=0, lim=(int)pos.size(); i<lim; i++) {
54             int64 x=0;
55             int64 pm=1;
56             int p=pos[i]-1;
57             while(p>=0 && op[p]=='*') pm*=arr[p--];
58             if(0<=p) x=func(0, p);
59             for(int j=i+1; j<lim; j++) {
60                 int64 y=0;
61                 p=pos[j];
62                 int64 am=1;
63                 while(p<n && op[p]=='*') am*=arr[++p];
64                 if(p+1<=n) y=func(p+1, n);
65                 ans=max(ans, x+y+am*pm*func(pos[i], pos[j]));
66             }
67         }
68         printf("%I64d
", ans);
69     }
70     return 0;
71 }

View Code