小豪的第一次div1。
Problem A
题意：一叠砖块每个砖块都有最大负载量，就是上面碟的砖块数不能超过负载。给你若干砖块，问你最少堆几堆？
思路：贪心题，先排序然后每次检查能不能堆在已有的砖块上，不行在新开一堆，最后输出答案即可。
代码如下：
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 }
Problem B
题意：让你构造一个图，要求结点数不超过1000，从1-2有k条最短路。输出他的结点数和邻接矩阵。
思路：首先看k最大为1E9先想拆成2进制，显然结点太多了。然后就拆成10进制，测试后发现最多不会超过600个结点。具体细节还是看代码吧。
代码如下：
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 }