MYF

2016弱校连萌Round 1a Abstract Picture

Posted on | In | | Visitors

题目链接

Abstract Picture

方法： 搜索

题目分析

题目大意

给定一个n*n的画板，上面一个字符代表一个颜色。每一个格子会刷两次，一次横着刷，一次竖着刷，后刷的颜色会覆盖先刷的颜色，问号表示不关心这个位置的颜色，打印出一种方案，形成这样的画板。

解析

最后一次刷一定会形成一行或者一列，使这一行或一列一定是一个颜色，所以，以此作为突破口。初级想法是这样的，先找到最后一次刷的那一行或者那一列，然后把这一行或者这一列全部刷成?，然后再暴力横着扫n次，竖着扫n次，直到扫不出来为止，然而这个会T。中级想法是这样的，加入剪枝，如果这一行或这一列扫过，设置一个vis[]数组，如果再次循环扫到这个位置，直接continue跳过，然而这个也不可以，到35发会T。最终的想法是这样的，也是看了学长的代码学到的，敲了n遍，debug花了半天。建立两个set统计每一行的有哪些字符，每一列有哪些字符。建立两个cnt[maxn][26]表示每一行，每一列中每个字符出现的次数，先扫一遍，找到找到集合中只有一个字符或没有的那一行或者那一列，加入队列中。然后对队列中的每一个元素扫描。如果队首元素表示扫描这一行，则对这一行的每一个元素所在的每一列找到这个元素的统计，好吧说的很绕，其实就是cntH[i][mp[i][now]-'a']，如果这个元素递减之后等于零，则查看当前这一列的set，如果元素个数小于等于一，则把当前列标记访问，加入答案的数组里，然后加入队列。

收获

再也不用宏定义了

#define maxn 3000+50这个东西，当我定义了ans[2*maxn];表示的是ans[2*3000+5;也就是ans[6005]，但是ans[maxn*2];表示的却是ans[3000+5*2];也就是ans[3010];所以说，这一次又体会到了宏定义是一种不安全的定义方式，以后头文件里不用这个东西了。

移位标记方式

本来看到位运算就头晕，今天看到学长将入队的那个数进行一些操作，达到一种标记操作的目的。比如操作的值为x，我对x总共有7种操作方式，那么我可以使用7*x来表示第一种操作方式7*x+1表示第二种操作方式，然后等出队的时候，使用now%7即可知道应该对当前的这个元素进行那一个操作，使用now/7即可表示原值。

代码

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
117
118
119
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1)
#define rt(n)       (j == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#define eps 1e-8
#define INF 0x3f3f3f3f
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
using namespace std;
#define maxn 3000+50
#define mod 1000000007
int n,cnt=0;
int visV[maxn]={},visH[maxn]={};
int cntV[maxn][30]={},cntH[maxn][30]={};
char mp[maxn][maxn]={};
set<char> stV[maxn],stH[maxn];
queue<int>q;
struct node{
    char c,d;
    int p;
    node(){}
    node(char dir,int pos, char col):d(dir),p(pos),c(col){}
}ans[2*maxn];
int main(){
    scanf("%d",&n);
    for (int i=1; i<=n; i++) {
        scanf("%s",mp[i]+1);
    }
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            if (mp[i][j]!='?') {
                stH[i].insert(mp[i][j]);
                stV[j].insert(mp[i][j]);
                cntH[i][mp[i][j]-'a']++;
                cntV[j][mp[i][j]-'a']++;
            }
        }
    }
    for (int i=1; i<=n; i++) {
        if (stH[i].size()<=1) {
            visH[i]=1;
            q.push(i<<1|1);
            char ch='a';
            if (stH[i].size()) {
                ch=*stH[i].begin();
            }
            ans[cnt++]=node('h', i, ch);
        }
        if (stV[i].size()<=1) {
            visV[i]=1;
            q.push(i<<1);
            char ch='a';
            if (stV[i].size()) {
                ch=*stV[i].begin();
            }
            ans[cnt++]=node('v', i, ch);
        }
    }
    while (!q.empty()) {
        int now=q.front();q.pop();
        int dir=(now&1);
        now>>=1;		//移位标记的方式
        if (dir) {
        //横着扫
            for (int i=1; i<=n; i++) {
                if (!visV[i]&&mp[now][i]!='?') {
                    if (--cntV[i][mp[now][i]-'a']==0) {
                        stV[i].erase(mp[now][i]);
                        if (stV[i].size()<=1) {
                            q.push(i<<1);
                            char ch='a';
                            if (stV[i].size()) {
                                ch=*stV[i].begin();
                            }
                            visV[i]=1;
                            ans[cnt++]=node('v', i, ch);
                        }
                    }
                }
            }
        }
        else{
        //竖着扫
            for (int i=1; i<=n; i++) {
                if (!visH[i]&&mp[i][now]!='?') {
                    if (--cntH[i][mp[i][now]-'a']==0) {
                        stH[i].erase(mp[i][now]);
                        if (stH[i].size()<=1) {
                            q.push(i<<1|1);
                            visH[i]=1;
                            char ch='a';
                            if (stH[i].size()) {
                                ch=*stH[i].begin();
                            }
                            ans[cnt++]=node('h', i, ch);
                        }
                    }
                }
            }
        }
    }
    for (int i=cnt-1; i>=0; i--) {
        printf("%c %d %c\n",ans[i].d,ans[i].p,ans[i].c);
    }
    return 0;
}