2014ICPC-Anshan

Posted on | In | Views:

H. NAND

题意

给一个真值表，问最少使用多少个二输入与非门能够实现这个真值表的功能。

94502453b15742200df7577dd478d4a9

题解

初始值

  • $15 - 00001111$
  • $51-00110011$
  • $85-01010101$

用一个 $vector$ 表示当前具有的表达式，每次 $dfs$ 都选取两个做与非运算，加入队列再继续 $dfs$ ，有以下几个剪枝

  • 标记 $vector$ 中的元素，避免重复加入
  • $dfs$ 的参数传入上一次的选取的两个值的下标，每次只取上一次右边的数

代码

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
int ans[256];
vii v;
bool vis[256];
void dfs(int dep,int l,int r){
    if(dep==11)return;
    int len=v.size();
    for(int i=l;i<len;i++)
    for(int j=(i==l?r:0);j<=i;j++){//只取小于i的数，避免重复
        int tm=255^(v[i]&v[j]);
        ans[tm]=min(ans[tm],dep);
        if(!vis[tm]){
            vis[tm]=1;
            v.pu_b(tm);
            dfs(dep+1,i,j);
            v.pop_back();
            vis[tm]=0;
        }
    }
}
int main() {
    v.pu_b(15);v.pu_b(51);v.pu_b(85);
    meminf(ans);
    ans[0]=vis[0]=ans[255]=vis[255]=1;
    for(int i:v)ans[i]=vis[i]=1;
    dfs(2,0,0);
    for0(i,256){
        printf("%d\n",ans[i]);
    }
    return 0;
}

J. Square

题意

给你一个 $n*n(n\le8)$ 的棋盘，上面有一些格子必须是黑色。其它可以染黑或者染白。对于一个棋盘，定义它的优美度为它上面最大的连续白色子正方形的边长，对于每个 $0\le k\le n$，问有多少种染色方案使得棋盘的优美度为 $k$ ？

题解

将问题转化为求优美度小于 $k$ 的染色方案， $dp[i][sta]$ 表示第 $i$ 行状态为 $sta$ 的方案数，状态为一个 $k$ 进制数，第 $j$ 位表示区间 $j\sim j+k-1$ (每行下标从 $0$ 开始)往上延伸都为白色的最大高度，接下来枚举每行的染色方案。

代码

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
ull ans[10];
ull dp[10][1200];
int val[10];
int Pow[10][10];
char s[10];
int main() {
    int t,n;
    for (int i = 1; i <= 9; i++){
        Pow[i][0]=1;
        for (int j = 1; j <= 9; j++)Pow[i][j]=Pow[i][j-1]*i;
    }
    in(t);
    ans[0]=dp[0][0]=1;
    while(t--){
        in(n);
        int tot=0;
        for (int i = 1; i <= n; i++){
            in(s);
            val[i]=0;
            for (int j = 0; j < n; j++){
                val[i]*=2;
                if(s[j]=='o')val[i]++,tot++;
            }
        }
        for (int k = 2; k <= n; k++){
            ull tmp=0;
            for (int i = 1; i <= n; i++){
                for (int j = 0; j < Pow[k][n-k+1]; j++)dp[i][j]=0;
                for(int s=val[i];;s=(s-1)&val[i]){
                    for(int t=0;t<Pow[k][n-k+1];t++){
                        if(!dp[i-1][t])continue;
                        bool is=1;
                        ll mask=Pow[2][k]-1;
                        int tt=t,ts=t;
                        for(int j=0;j<=n-k;j++,mask*=2){
                            if((s&mask)==mask){
                                if(tt%k==k-1)is=0;
                                else 
                                ts+=Pow[k][j];
                            }else{
                                ts-=(tt%k)*Pow[k][j];
                            }
                            tt/=k;
                        }
                        if(is)dp[i][ts]+=dp[i-1][t];
                    }
                    if(s==0)break;
                }
            }
            for (int i = 0; i < Pow[k][n-k+1]; i++)tmp+=dp[n][i];
            ans[k-1]=tmp;
        }
        __int128 tm=1;
        tm<<=tot;
        ans[n]=tm-ans[n-1];
        for(int i=n-1;i>0;i--) ans[i]-=ans[i-1];
        for (int i = 0; i < n+1; i++)out((ll)(ans[i]%mod),1);
    }
    return 0;
}

K. Colorful Toy

题意

给 $N$ 个点，$M$ 条边，用 $C$ 种颜色给点染色，其中图形旋转后相同的染色方案只算一种，求有多少种不同的染色方案。

题解

因为给的点都是整数点，图形只有在旋转 $90^\circ 180^\circ,270^\circ$ 时才可能与原图重合，旋转方案只有四种。

代码

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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
struct Point{
    db x,y;
    Point(){}
    Point(db _x,db _y) : x(_x),y(_y){}
    Point operator + (const Point &k1) const{return Point(k1.x+x,k1.y+y);}
    Point operator - (const Point &k1) const{return Point(x-k1.x,y-k1.y);}
    Point operator * (const db k1) const{return Point(x*k1,y*k1);}
    Point operator / (const db k1) const{return Point(x/k1,y/k1);}
    db operator * (const Point b) const{return x * b.x + y * b.y;}//点积
    db operator ^ (const Point b) const{return x * b.y - y * b.x;}//叉积,顺时针为负
    bool operator == (const Point &k1) const{return db_cmp(x,k1.x)==0&&db_cmp(y,k1.y)==0;}
    Point & operator += (const Point &k1) {x+=k1.x;y+=k1.y;return *this;}
    Point & operator -= (const Point &k1) {x-=k1.x;y-=k1.y;return *this;}
    Point & operator *= (const db k1) {*this=*this*k1;return *this;}
    Point & operator /= (const db k1) {*this=*this/k1;return *this;}
    Point rotate(db k1){return Point(x*cos(k1)-y*sin(k1),x*sin(k1)+y*cos(k1));}// 逆时针旋转 
    Point rotate90(){return Point(-y,x);}
    db abs(){return sqrt(x*x+y*y);}
    db abs2(){return x*x+y*y;}
    Point unit(){return *this/abs();}
    db angle(){return atan2(y,x);}
    void out(){printf("%.10f %.10f\n",x,y);}
};
typedef Point Vector;
ll qPow(ll a, ll b, ll c) {  //求(a^b) % c
    ll ret = 1;
    
    while (b) {
        if (b & 0x1) ret = ret * a % c;
        a = a * a % c;
        b >>= 1;
    }
    return ret;
}
map<pii,int>ma;
bool Map[100][100];
int ying [100];
bool vis[100];
int qu(db x){
    int tt=x;
    if(db_cmp(x,tt)==0)return tt;
    else if(db_cmp(x,tt-1)==0)return tt-1;
    else if(db_cmp(x,tt+1)==0)return tt+1;
    else return inf;
}
bool check(pair<db,db>x){
    if(qu(x.fi)<inf&&qu(x.se)<inf)return 1;
    else return 0;
}
int main() {
    int t,n,m,c,u,v;
    in(t);
    while(t--){
        ma.clear();
        in(n,m,c);
        db tx=0,ty=0;
        for1(i,n){
            in(u,v);
            ma[pii(u,v)]=i;
            tx+=u;
            ty+=v;
        }
        assert(ma.size()==n);
        mem0(Map);
        for0(i,m){
            in(u,v);
            Map[u][v]=Map[v][u]=1;
        }
        pii center;
        ll ans=qPow(c,n,mod);
        if(qu(tx/n*2)==inf||qu(ty/n*2)==inf){
            out(ans,1);
            continue;
        }else center=pii(qu(tx/n*2),qu(ty/n*2));
        int mu=1;
        bool is=1;
        mem0(vis);
        for(auto i:ma){
            pii p=i.fi;
            int id=i.se;
            pii op(center.fi-p.fi,center.se-p.se);
            if(ma.count(op)){
                v=ma[op];
                if(vis[v]){
                    is=0;
                    break;
                }else{
                    vis[v]=1;
                    ying[id]=v;
                }
            }else {
                is=0;
                break;
            }
        }
        if(is){
            for1(i,n)
            for1(j,n){
                if(Map[i][j]){
                    if(!Map[ying[i]][ying[j]]){
                        is=0;
                        goto ss;
                    }
                }
            }
        }
        ss:
        if(is){
            ans=(ans+qPow(c,(n+1)/2,mod))%mod;
            mu++;
        }else {
            out(ans,1);
            continue;
        }
        Point cen(center.fi/2.0,center.se/2.0);
        // pair<db,db> cen=pair<db,db>(center.fi/2.0,center.se/2.0);
        // cout<<cen.x<< ' '<<cen.y<<endl<<endl;
        mem0(vis);
        for(auto i:ma){
            pii p=i.fi;
            int id=i.se;
            Vector dir(p.fi-cen.x,p.se-cen.y);
            // cout<<dir.x<<' '<<dir.y<<endl;
            dir=dir.rotate90();
            // cout<<dir.x<<' '<<dir.y<<endl;
            dir=dir+cen;
            pair<db,db>tmp(dir.x,dir.y);
            // cout<<tmp.fi<< ' '<<tmp.se<<endl;
            // cout<<check(tmp)<<endl;
            if(check(tmp)){
                pii op(qu(tmp.fi),qu(tmp.se));
                // cout<<op.fi<<' '<<op.se<<endl;
                if(ma.count(op)){
                    v=ma[op];
                    if(vis[v]){
                        is=0;
                        break;
                    }else{
                        vis[v]=1;
                        ying[id]=v;
                    }
                }else {
                    is=0;
                    break;
                }
            }else{
                is=0;
                break;
            }
        }

        if(is){
            for1(i,n)
            for1(j,n){
                if(Map[i][j]){
                    if(!Map[ying[i]][ying[j]]){
                        is=0;
                        goto sp;
                    }
                }
            }
        }
        sp:
        // cout<<is<<endl;
        if(is){
            mu+=2;
            ans=(ans+2*qPow(c,(n+3)/4,mod))%mod;
            // puts("fdsfs");
        }
        // out(ans,1);
        // out(mu,1);
        out(ans*qPow(mu,mod-2,mod)%mod,1);
    }
    return 0;
}