Codeforces Round #228 (Div. 1) 解题报告

小豪的第一次div1。

Problem A 

题意:一叠砖块每个砖块都有最大负载量,就是上面碟的砖块数不能超过负载。给你若干砖块,问你最少堆几堆?

思路:贪心题,先排序然后每次检查能不能堆在已有的砖块上,不行在新开一堆,最后输出答案即可。

代码如下:

Codeforces Round #228 (Div. 1) 解题报告
 1 //2014-02-03-23.33
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstdlib>
 5 #include <cmath>
 6 #include <cstring>
 7 #include <algorithm>
 8 #include <queue>
 9 #include <stack>
10 #include <vector>
11 #include <set>
12 #include <map>
13 #define MP(a, b) make_pair(a, b)
14 #define PB(a) push_back(a)
15 
16 using namespace std;
17 
18 typedef long long ll;
19 typedef pair<int ,int> pii;
20 typedef pair<unsigned int, unsigned int> puu;
21 typedef pair<int ,double> pid;
22 typedef pair<ll, int> pli;
23 typedef pair<int, ll> pil;
24 
25 const int INF = 0x3f3f3f3f;
26 const double eps = 1e-6;
27 const int LEN = 1010;
28 int n, bn[LEN], f[LEN], b;
29 
30 int main()
31 {
32 //    freopen("in.txt", "r", stdin);
33 
34     while(scanf("%d", &n)!=EOF){
35         int ans = 1;
36         memset(bn, 0, sizeof bn);
37         memset(f, 0, sizeof f);
38         for(int i=0; i < n; i++){
39             scanf("%d", &bn[i]);
40         }
41         sort(bn, bn+n);
42         for(int i=0; i<n; i++){
43             int su = 0;
44             for(int j=0; j<ans; j++){
45                 if(f[j] <= bn[i]) {f[j]++;su=1;break;}
46             }
47             if(!su)f[ans++] = 1;
48         }
49         printf("%d\n", ans);
50     }
51     return 0;
52 }
View Code

Problem B

题意:让你构造一个图,要求结点数不超过1000,从1-2有k条最短路。输出他的结点数和邻接矩阵。

思路:首先看k最大为1E9先想拆成2进制,显然结点太多了。然后就拆成10进制,测试后发现最多不会超过600个结点。具体细节还是看代码吧。

代码如下:

Codeforces Round #228 (Div. 1) 解题报告
 1 //2014-02-03-23.33
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstdlib>
 5 #include <cmath>
 6 #include <cstring>
 7 #include <algorithm>
 8 #include <queue>
 9 #include <stack>
10 #include <vector>
11 #include <set>
12 #include <map>
13 #define MP(a, b) make_pair(a, b)
14 #define PB(a) push_back(a)
15 
16 using namespace std;
17 
18 typedef long long ll;
19 typedef pair<int ,int> pii;
20 typedef pair<unsigned int, unsigned int> puu;
21 typedef pair<int ,double> pid;
22 typedef pair<ll, int> pli;
23 typedef pair<int, ll> pil;
24 
25 const int INF = 0x3f3f3f3f;
26 const double eps = 1e-6;
27 const int LEN = 1010;
28 int Map[LEN][LEN], n;
29 
30 int getnew(){return n++;}
31 
32 int ck(int tk){
33     int ret = 0;
34     while(tk){ret++; tk/=10;}
35     return ret;
36 }
37 
38 void medge(int a, int b){
39     int temp = getnew();
40     Map[a][temp] = Map[temp][a] = 1;
41     Map[temp][b] = Map[b][temp] = 1;
42 }
43 
44 int getkn(int num, int w){
45     while(w--){
46         num/=10;
47     }
48     return num%10;
49 }
50 
51 int main()
52 {
53 //    freopen("in.txt", "r", stdin);
54 
55     int k, s = 0, e = 1, cnt, wei[LEN];
56     while(scanf("%d", &k)!=EOF){
57         memset(Map, 0, sizeof Map);
58         n = 2;
59         cnt = ck(k);
60 //        cout << cnt;
61         int ted, tst, temp;
62         for(int i=0; i<cnt; i++){
63             wei[i] = getnew();
64             tst = wei[i];
65             for(int j=0; j<i; j++){
66                 ted = getnew();
67                 for(int k=0; k<10; k++) medge(tst, ted);
68                 tst = ted;
69             }
70             for(int j=i; j<cnt-1; j++){
71                 ted = getnew();
72                 medge(tst, ted);
73                 tst = ted;
74             }
75             int tt = getkn(k, i);
76             for(int j=0; j<tt; j++) medge(tst, e);
77         }
78         for(int i=0; i<cnt; i++) Map[s][wei[i]] = Map[wei[i]][s] = 1;
79         printf("%d\n", n);
80         for(int i=0; i<n; i++){
81             for(int j=0; j<n; j++){
82                 if(Map[i][j]) putchar(Y);
83                 else putchar(N);
84             }
85             puts("");
86         }
87     }
88     return 0;
89 }
View Code

Codeforces Round #228 (Div. 1) 解题报告

上一篇:OpenCL简介-----OpenCL学习(一)


下一篇:SqlServer 挂载本地盘符到服务器端,方面备份还原