题解 P7794 [COCI2014-2015#7] JANJE

· · 题解

这道题不难。

很坑。

其实答案就是颜色方案数与图片方案数的乘积。

切入正题。

Bojan的图片

观察题目，切入点就在两句加粗的话：

每张图片最多使用三种不同的颜色着色。

永远不会用同一种颜色给两个相邻的区域上色。

由于图片在附件中给出，所以手动推算方案数是必要的。

除 8 外所有图片求方案数，都是首先确定一个图形可选颜色数量，然后确定其相邻图形可选颜色数量，以此类推，最终将所有图形的可选颜色数相乘。

但是注意，上面一段话并不完全正确，原因会在下面说明。

1

头可涂的颜色为三种，下面那一段可选的颜色就只有两种。

依此类推，共有 20 段，方案数为 2^{19}\times 3。

2

房顶为 3，顶上的窗户、墙壁、门、窗户的一半为 2，窗户的另一半为 1。

方案数为 2^{5}\times 3。

3

最外围一圈为 3 ，中间的三个圆均为 2。

方案数为 2^{3}\times 3。

4

帽子为 3，其余的圆为 2。

方案数为 2^{13}\times 3。

5

最中间上半部分为 3，下半部分为 2，中间的圆环为 1，外围的上半部分为 2，下半部分为 1。

方案数为 2^{2}\times 3。

6

不要被吓到了，其实很简单。

最上面一块为 3 ，第二排左边一块为 2，其他的就全部确定颜色了。

方案数为 3\times 2。

7

花瓣为 3，花蕊、茎、花盆和叶的一半为 2，叶的另一半为 1。

方案数为 3\times 2^5。

8

唯一一个方法与众不同的图。

我起先认为它的方案数为 2^{30}(1073741824) 害我提交22次。但 DFS 后知道正确的方案数为 1073741826 。

DFS 程序如下：

#include<bits/stdc++.h>
using namespace std;
long long dfs(int x,int y){
    if(x==30)return y==1?0:1;
    x++;
    switch(y){
        case 1:return dfs(x,2)+dfs(x,3);
        case 2:return dfs(x,1)+dfs(x,3);
        case 3:return dfs(x,1)+dfs(x,2);
    }
}

int main(){
    cout<<dfs(1,1)*3;
}

于是我们就得出了所有图片的方案数。

65分做法

得出方案数后，很自然地认为答案为 C(n,3)\times l_n。

代码：

#include<bits/stdc++.h>
using namespace std;
int m(int k){
    return pow(2,k);
}
long long l[9]={0,m(19),m(5),m(3),m(13),m(2),m(1),m(5),107371826},n,k;
int main(){
    for(int i=1;i<=7;i++)
        l[i]*=3;
    cin>>n>>k;
    cout<<l[n]*(k*(k-1)*(k-2)/6);
}

于是一片花红柳绿。

120分做法

在经过半个小时的修改与提交后发现 1、3、4、8 四张图可以只涂两种颜色。

因此四张图的方案数必须减去 A(3,2)=6，然后将答案加上 C(n,2)\times 2。

核心代码：

ans+=l[n]*(k*(k-1)*(k-2)/6);
ans+=b[n]*k*(k-1);//b储存图片是否能只由两种颜色涂成。

代码的其余部分就不放出来了， 相信各位都有能力能写出来。