2009年9月16日

http://acm.pku.edu.cn/JudgeOnline/problem?id=3740
这道题目要求:选出一些行使得这些行构成矩阵的每一列都有且只有一个1。
 1 #include<cstdio>
 2 #include<string.h>
 3 using namespace std;
 4 
 5 int m,n,map[16][300];
 6 bool used[300];
 7 bool find;
 8 
 9 bool match(){ //判断所选取的行构成的矩阵是否符合情况
10     for(int i = 0;i < n;++i){
11         if(!used[i])return false;
12     }
13     return true;
14 }
15 
16 bool check(int row){ 
17     for(int i = 0;i < n;++i){
18         if(used[i] && map[row][i])return false; //used[i]&&map[row][i]表示该列有选取的该列有不只一个1,返回false放弃这种情况。
19     }
20     for(int i = 0;i < n;++i){
21         if(map[row][i]){
22             used[i] = true;
23         }
24     }
25     return true;
26 }
27 
28 void dfs(int start){
29     if(start>|| find)return;
30     if(match()){
31         printf("Yes, I found it\n");
32         find = true;
33         return;
34     }
35     for(int i = start;i < m && !find;++i){
36         if(check(i)){
37             dfs(i+1);
38             for(int j = 0;j < n;++j){
39                 if(map[i][j])used[j] = false;
40             }
41         }
42     }
43 }       
44 
45 int main()
46 {
47     int i,j;
48     while(scanf("%d%d",&m,&n)!=EOF){
49         for(i = 0;i < m;++i){
50             for(j = 0;j < n;++j){
51                 scanf("%d",&map[i][j]);
52             }
53         }
54         memset(used,false,sizeof(used));
55         find = false;
56         dfs(0);
57         if(!find)printf("It is impossible\n");
58     }
59     return 0;
60 }
61 
posted @ 2009-09-16 17:40 Johnnx 阅读(749) | 评论 (0)编辑 收藏
http://acm.pku.edu.cn/JudgeOnline/problem?id=2528
这是一道经典的线段树题目,另外加上离散化的方法。
    离散化:由于题目中wall有10000000bytes long,直接线段树无疑会MLE。所以要对其离散化,基本做法是:先对所有端点坐标进行排序,用相应序号代替端点坐标构造线段树进行计算。这样最大的序号也只是2*n。
   在构造线段树的节点结构体时,添加变量c。c=0时表示c线段没有贴海报,或者贴了不止一张海报;c>0时表示贴了一张海报,并且c的值表示贴的是第几张海报。
    线段树更新的基本原理就是,当我们贴海报i时,如果遇到某一线段区间能够被当前海报完全覆盖,那么我们更新到此区间即可,即让它的变量c更新为海报i,记录下i的值。如果不能被海报完全覆盖,则只是这一线段区间的部分区间需要修改,则更改这一区间的子区间即可。
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<string.h>
  5 #define MAX 20001
  6 
  7 using namespace std;
  8 
  9 int c,n,ls[MAX];
 10 struct node{
 11     int l,r;
 12     int c;
 13 }tree[MAX*4];
 14 struct ln{
 15     int li,num;//num表示第几张海报
 16 }line[MAX];
 17 int set[MAX][2];
 18 bool visit[MAX];
 19 int ans;
 20 
 21 bool cmp(struct ln a,struct ln b){
 22     return a.li<b.li;
 23 }
 24 
 25 void Inittree(int pos,int ll,int rr){
 26     tree[pos].l = ll;
 27     tree[pos].r = rr;
 28     tree[pos].c = 0;
 29     if(ll!=rr){
 30         int mid = (ll+rr)>>1;
 31         Inittree(pos*2,ll,mid);
 32         Inittree(pos*2+1,mid+1,rr);
 33     }
 34 }
 35 
 36 void Insert(int pos,int ll,int rr,int color){
 37     if(tree[pos].l == ll && tree[pos].r == rr){
 38         tree[pos].c = color;
 39         return;
 40     }
 41     if(tree[pos].c > 0 && tree[pos].c != color){
 42         tree[pos*2].c = tree[pos].c;
 43         tree[pos*2+1].c = tree[pos].c;
 44         tree[pos].c = 0;
 45     }
 46     int mid = (tree[pos].l + tree[pos].r)>>1;
 47     if(rr<=mid){
 48         Insert(pos*2,ll,rr,color);
 49     }
 50     else if(ll>mid){
 51         Insert(pos*2+1,ll,rr,color);
 52     }
 53     else{
 54         Insert(pos*2,ll,mid,color);
 55         Insert(pos*2+1,mid+1,rr,color);
 56     }
 57 }
 58 
 59 void Search(int pos){
 60     if(tree[pos].c!=0){
 61         if(!visit[tree[pos].c]){//tree[pos].c
 62             visit[tree[pos].c] = true;
 63             ans++;
 64         }
 65         return ;
 66     }
 67     Search(2*pos);
 68     Search(2*pos+1);
 69 }
 70 
 71 int main()
 72 {
 73     int i;
 74     while(scanf("%d",&c)!=EOF){
 75         while(c--){
 76             scanf("%d",&n);
 77             for(i = 0;i < n;++i){//离散化
 78                 scanf("%d%d",&set[i][0],&set[i][1]);
 79                 line[2*i].li = set[i][0];
 80                 line[2*i].num = -(i+1);//用负数表示 线段起点
 81                 line[2*i+1].li = set[i][1];
 82                 line[2*i+1].num = i+1;
 83             }
 84             sort(line,line+2*n,cmp);
 85             int temp = line[0].li,tp = 1;
 86             for(i = 0;i < 2*n;++i){
 87                 if(line[i].li != temp){
 88                     tp++;
 89                     temp = line[i].li;
 90                 }
 91