【2019暑假】6-28

By shy

——回归NOIP

提高新生涯的第一天


1. 【NOIP2011 day1 T1】铺地毯

题意:用n个矩形覆盖平面直角坐标系,后放的矩形覆盖前面放好的矩形上,给出每个矩形的左下角的坐标(a,b)以及矩形在 x轴和 y 轴方向的长度,求覆盖地面某点(x,y)的最上面的那个矩形的编号。

Solution

水题。很早就做过

由题意可知对于一个点来说后放的矩形一定在先放的上面,所以该题是求覆盖在店上(x,y)的最后一个矩形。

于是先将所有矩形输入,按照输入顺序反向枚举每一个矩形,如果发现一个矩形包括了这个点,直接将编号输出并退出循环。


2. 【NOIP2011 day1 T2】选择客栈

题意:有 n 家客栈, 从 1 到 n 编号。 每家客栈都有某一种色调(总共 k 种,用整数 0 ~ k-1 表示)。每家客栈都设有一家咖啡店,每家咖啡店均有各自的最低消费。两位游客决定分别住在色调相同的两家客栈中,并要求有一家咖啡店位于两人住的两家客栈之间(包括他们住的客栈) ,且咖啡店的最低消费不超过 p。求可选的住宿方案的总数。

60%:O(N²)

用三重循环枚举两两客栈和它们中间的咖啡店时O(N³),此处不再赘述。

可以先用O(N²)枚举两两客栈之间的最低消费,再O(N²)枚举所有店的组合,总复杂度O(N²)。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int n,k,p,a[200001],b[200001];
int c[1001][1001];//客栈i和j之间咖啡店的最低消费
int main(){
    scanf("%d%d%d",&n,&k,&p);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i],&b[i]);//读入i号客栈的装饰色调和i号客栈的咖啡店的最低消费。
    }
//n^2:预处理所有店之间的最低消费,再枚举所有店的组合
    for(int i=1;i<=n;i++)
        c[i][i]=b[i];
        for(int j=i+1;j<=n;j++)
            c[i][j]=min(c[i][j-1],b[j]);//更新最低消费
    int ans=0;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            if(a[i]==a[j]&&c[i][j]<=p)
                ans++;//统计答案
    printf("%d\n",ans);
}

100%:O(N)

解题要点:在一个合法咖啡店的前面所有同色客栈都可以与当前客栈匹配

我们开三个数组,s[]表示第i个客栈之前以a为颜色的可匹配的客栈数 ,cnt[]百世第i个客栈之前以a为颜色的客栈总数 ,last[]表示第i个客栈之前最后一个以a为颜色的客栈的位置 。

我们可以只枚举第二个客栈,每当枚举到客栈i时,若我们发现了这个客栈的咖啡店是合法的,那这个咖啡店一定是最靠后的。

那么每枚举到一个客栈时,我们比较当前最靠后的咖啡店与第i个客栈之前最后一个同色客栈的位置,若当最后一个咖啡店的位置在最后一个同色的客栈的位置左边时 ,说明第i个客栈之前所有同色客栈都在咖啡店左边,此时将可匹配的客栈数更新为第i个客栈之前的总客栈数。最后每次将ans加上可匹配的客栈数即可。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int s[50];//第i个客栈之前以a为颜色的可匹配的客栈数
int cnt[50];//第i个客栈之前以a为颜色的客栈总数          
int last[50];//第i个客栈之前最后一个以a为颜色的客栈的位置
int main(){
    int n,k,p,ans=0,maxs;
    scanf("%d%d%d",&n,&k,&p);
    for(int i=1;i<=n;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        if(b<=p) maxs=i;//当遇到一个新的合法咖啡店时,更新最后一个咖啡店的位置
        if(last[a]<=maxs){//当最后一个咖啡店的位置在最后一个以a为颜色的客栈的位置后面时
            s[a]=cnt[a];//将可匹配的客栈数更新为以a为颜色的客栈总数
        }
        ans+=s[a];
        ++cnt[a];
        last[a]=i;
    }
    printf("%d\n",ans);
    return 0;
}

3. Mayan游戏

题面

Mayan puzzle 是最近流行起来的一个游戏。游戏界面是一个 7 行 5 列的棋盘,上面堆放着一些方块,方块不能悬空堆放,即方块必须放在最下面一行,或者放在其他方块之上。游戏通关是指在规定的步数内消除所有的方块。
游戏通关是指在规定的步数内消除所有的方块,消除方块的规则如下:
1、 每步移动可以且仅可以沿横向(即向左或向右)拖动某一方块一格:当拖动这一方块时, 如果拖动后到达的位置 (以下称目标位置) 也有方块, 那么这两个方块将交换位置 (参见输入输出样例说明中的图 6 到图 7) ;如果目标位置上没有方块,那么被拖动的方块将从原来的竖列中抽出,并从目标位置上掉落(直到不悬空,参见下面图 1 和图 2) ;

输入

共 6 行。
第一行为一个正整数 n,表示要求游戏通关的步数。
接下来的 5 行,描述 7*5 的游戏界面。每行若干个整数,每两个整数之间用一个空格隔开,每行以一个 0 结束,自下向上表示每竖列方块的颜色编号(颜色不多于 10 种,从 1 开始顺序编号,相同数字表示相同颜色) 。
输入数据保证初始棋盘中没有可以消除的方块。

输出

        如果有解决方案,输出 n 行,每行包含 3 个整数 x,y,g,表示一次移动,每两个整数之间用一个空格隔开,其中(x,y)表示要移动的方块的坐标,g 表示移动的方向,1 表示向右移动,-1 表示向左移动。 注意:多组解时,按照 x  为第一关健字,y  为第二关健字,1优先于-1 ,给出一组字典序最小的解。游戏界面左下角的坐标为(0 ,0 ) 。如果没有解决方案,输出一行,包含一个整数-1。

Solution

显然是个又臭又长的搜索。

花了一下午看着std憋出来的。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
int n;
int map[10][10];
struct stack{
    int x,y,f;
}ans[6];
bool empty(){//判断是否全部消除完
    for(int i=0;i<5;i++){
        for(int j=0;j<7;j++){
            if(map[i][j]) return 0;
        }
    }
    return 1;
}
void drop(){//方块下移
    int n[10][10];
    memset(n,0,sizeof(n));
    for(int i=0;i<5;i++){//按照合法的情况重新排版
        int h=0;
        for(int j=0;j<7;j++){
            if(map[i][j]){
                n[i][h++]=map[i][j];
            }
        }
    }
    for(int i=0;i<5;i++)
        for(int j=0;j<7;j++)
            map[i][j]=n[i][j];
}
bool clear(){//清除合法的联通块,本题的难点
    bool f=0;
    for(int i=0;i<3;i++)//横向判断,因为至少3个相同的连在一起,因此x只用枚举到2
        for(int j=0;j<7;j++)
            if(map[i][j]){//有方块
                int x;for(x=i;x<4&&map[x+1][j]==map[i][j];x++);
                if(x-i>=2){//至少有3个连在一起
                    for(int t=i;t<=x;t++){//竖向判断是否有共用的情况
                        int up=j,down=j;
                        while(up<6&&map[t][up+1]==map[i][j]) ++up;
                        while(down>0&&map[t][down-1]==map[i][j]) --down;
                        if(up-down>=2){
                            for(int p=down;p<=up;p++){
                                map[t][p]=0;
                            }
                        }
                    }
                    for(int t=i;t<=x;t++){
                        map[t][j]=0;
                    }
                    f=1;
                }
            }
    for(int i=0;i<5;i++)//竖向判断同理
        for(int j=0;j<5;j++)
            if(map[i][j]){
                int y;for(y=j;y<6&&map[i][y+1]==map[i][j];y++);
                if(y-j>=2){
                    for(int t=j;t<=y;t++){
                        int l=i,r=i;
                        while(l>0&&map[l-1][t]==map[i][j]) --l;
                        while(r<4&&map[r+1][t]==map[i][j]) ++r;
                        if(r-l>=2){
                            for(int p=l;p<=r;p++){
                                map[p][t]=0;
                            }
                        }
                    }for(int t=j;t<=y;t++) map[i][t]=0;
                    f=1;
                }
            }
    if(f) return 1;
    return 0;
}
void dfs(int step){
    if(step>n){
        if(empty()){
            for(int i=1;i<=n;i++){
                if(ans[i].f){//f等于1是代表x右边那块往左移
                    printf("%d %d %d\n",ans[i].x+1,ans[i].y,-1);
                }else printf("%d %d %d\n",ans[i].x,ans[i].y,1);
            }exit(0);
        }return;
    }
    int sum[11]={0};
    for(int i=0;i<5;i++){//如果一个数它的个数已经小于3了,则不能被消除
        for(int j=0;j<7;j++){
            sum[map[i][j]]++;
        }
    }for(int i=1;i<=10;i++)
        if(sum[i]>0&&sum[i]<3) return;
    int t[10][10];
    memcpy(t,map,sizeof(t));
    for(int i=0;i<4;i++)
        for(int j=0;j<7;j++)
            if(map[i][j]!=map[i+1][j]){//颜色相同的就不用交换了
                ans[step].x=i;
                ans[step].y=j;
                ans[step].f=!(map[i][j]);//如果当前这一块是空的话,那么我们就把它右边那一块左移,避免了分情况讨论
                swap(map[i][j],map[i+1][j]);
                drop();
                while(clear()) drop();//下移之后还肯能产生新的合法联通块,因此写成循环的形式
                dfs(step+1);//迭代加深
                memcpy(map,t,sizeof(map));
            }
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<5;i++){
        for(int j=0;;j++){
            scanf("%d",&map[i][j]);
            if(!map[i][j]) break;
        }
    }
    dfs(1);
    printf("-1\n");
    return 0;
}

——本来想简单随便写写的,一不小心又写了很长。。。

发表评论

电子邮件地址不会被公开。 必填项已用*标注