[USACO]Shaping Regions

题意:给你一个矩形网格,他的初始网格颜色为1,现在用颜色来覆盖里面的小矩形。问你最后能看到什么颜色且这种颜色的面积有多大。

解题思路:每一次增加一个矩形进来都要判断它和以前的矩形有没有交集,如果有交集则把原先的矩形分为几块。

解题代码:

[USACO]Shaping Regions
 1 // File Name: kimbits.c
 2 // Author: darkdream
 3 // Created Time: 2014年02月28日 星期五 19时02分25秒
 4 /*
 5 ID: dream.y1
 6 PROG: kimbits
 7 LANG: C++
 8 */
 9 #include<stdio.h>
10 #include<string.h>
11 #include<stdlib.h>
12 #include<time.h>
13 #include<math.h>
14 int hs[40];
15 int map[33][33];
16 void init()
17 {
18     memset(map,0,sizeof(map));
19     map[0][0] =1 ; 
20     for(int i = 1;i <= 31 ;i ++)
21     {
22       map[i][0] = 1; 
23       map[i][i] = 1; 
24     }
25     for(int i = 2;i <= 31;i ++)
26         for(int j = 1;j < i ;j ++)
27         {
28           map[i][j] = map[i-1][j] + map[i-1][j-1];
29         }
30 }
31 void solve(long long n , long long m , long long k )
32 {
33     long long sum[40];
34     memset(sum,0,sizeof(sum));
35     for(int i = 0;i <= n;i ++)
36     {
37        sum[i] = 0; 
38        for(int  j = 0;j <= m;j ++)
39        {
40          sum[i] += map[i][j];
41        }
42        if(sum[i] >= k )
43        {
44 
45            hs[i] = 1;
46            if(i == 1)
47                return ;
48            solve(i-1,m-1,k-sum[i-1]);
49            break;
50        }
51     }
52 }
53 int main(){
54    freopen("kimbits.in","r",stdin);
55    freopen("kimbits.out","w",stdout);
56     long long n , m , k ; 
57    scanf("%lld %lld %lld",&n ,&m,&k);
58    init();
59    solve(n,m,k);
60    for(int i = n ;i >= 1;i --)
61        if(hs[i])
62            printf("1");
63        else printf("0");
64    printf("\n");
65    return 0 ;
66 }
View Code

[USACO]Shaping Regions,布布扣,bubuko.com

[USACO]Shaping Regions

上一篇:Windows phone重写返回键


下一篇:WinForm中当TextBox重新获得焦点时输入法失效问题