首页 > ACM题库 > 九度OJ > 九度-1333-考研海报[模拟]
2014
01-27

九度-1333-考研海报[模拟]

题目描述:
sun是万千考研学子中的一员,他每天过着三点一线的生活。
学校里有一个公告栏,他每天都看到上面张贴着各种考研海报。
sun提出了一个问题:公告栏上还剩多少空白区域是没被考研海报张贴过的?
于是sun果断上王道贴上了这道题目。
输入:
公告栏左上角是坐标原点(0,0),公告栏长宽相等。
数据有多组,每组输入公告栏长度n(0<n<=100)。
海报张数m(0<m<=100),以及每张海报的左上角坐标(x1,y1)和右下角坐标(x2,y2)。
注意:其中坐标有可能小于0,大于n,但在int范围内。
输出:
对每一组输入输出公告栏还剩多少空白区域,输出带回车。
样例输入:
3
2
0 0 1 2
0 0 2 1
10
2
0 0 1 1
0 0 3 3
样例输出:
6
91

 

比较水的一题。数据量不大,直接模拟。由于面积不好直接计算,直接用标志位,用最原始的方法相加,没有覆盖过的则加1。

// Copyright   : www.acmerblog.com
#include <stdio.h>
#include <string.h>
bool a[100][100];
int n,m;
int x1,y1,x2,y2;
int count;
int main(){
    //freopen("input.txt","r",stdin);
    while(scanf("%d%d",&n,&m) != EOF){
        count = 0;//记录被覆盖的面积
        memset(a,false,10000);
        for(int i=0;i<m;i++){
            scanf("%d%d%d%d",&x1, &y1, &x2, &y2);
            //处理边界
            if(x1<0) x1=0;
            if(x1>n) x1=n;
            if(y1<0) y1=0;
            if(y1>n) y1=n;
            if(x2<0) x2=0;
            if(x2>n) x2=n;
            if(y2<0) y2=0;
            if(y2>n) y2=n;
            for(int j=x1;j<x2;j++){
                for(int k=y1;k<y2;k++){
                    if(!a[j][k]){
                        //该处如果没有被覆盖过
                        count++;
                        a[j][k] = true;
                    }
                }
            }
        }
        printf("%d\n", n*n-count);
    }
    return 0;
}

/**************************************************************
    Problem: 1333
    User: 从此醉
    Language: C++
    Result: Accepted
    Time:30 ms
    Memory:1032 kb
****************************************************************/

 


  1. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

  2. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法