题解 UVA1073 【Glenbow Museum】

如果有一个点能看到各个顶点,那么这个点的上下左右一定要对应四个RR

如果有OO,那么这两个270°的角延伸出去的角的可视范围没有交集,即它们不能被同时被看到(点A能看到点B,那么点B也能看到点A。反之B一定不能看到点A),如下图所示:(延伸出去的角可能是R也可能是O,这里以R为例)

所以一定不能有OO

如果没有OO,但是有OR。那么OR前面一个字符一定是R。(否则就有OO了)。这O,R两个角的可视范围是有交集的。如下图所示:

同样地,相邻的RR两角的可视范围也是有交集的。至少它们两个角是可以被同时看到的。

如果一个点能看到所有内角,那么它的正对的上下左右一定都是RR。因为如果某个方向是RR,显然成立。如果某个方向上的角度序列有OR,那么这个方向的角度序列只能是OROROR…ORR。即只能以RR结尾。(如果一直不结尾,那就不构成多边形。如果以OO结尾,那么不合法)。

既然以RR结尾,那么能同时看到这个RR的点一定在如图所示的灰色区域。

反过来说,一个点的正对的上下左右四个方向一定是RR

稍加思考可以发现,只要满足上下左右四个方法有RR,且整个序列没有OO,那么一定满足条件。(没有OO意味着不会往外拐)

L个内角代表L条边,根据多边形内角和公式:
90R+270O=(L-2)* 180.

又因为R+O=L.

所以有R=(L+4)/2,O=(L-4)/2.

所以我们要求的就是(L+4)/2R(L-4)/2R的字符串中,有至少四个RR且没有OO的个数。注意L<4或者L为奇数时无解。(为奇数时的内角和不为180°的整数倍)

前两个实现方法参考《算法竞赛入门经典:训练指南》:

方法一:

f(i,j,b,e)表示有iRjO,开头为b0表示R1表示O),结尾为e

f(x,0,0,0)=f(0,1,1,1)=1,x > 0.

f(i,j,b,0)=f(i-1,j,b,1)+f(i-1,j,b,0).

f(i,j,b,1)=f(i,j-1,b,0).(不能出现OO

答案就很显然了(把几个f(i,j,b,e)加起来),你可以自行推一推或者见代码。

递归加上记忆化即可O(n)解决。(直接递推则需O(n^2)

代码:

#include<cstdio>
#include<cstring>
int L,kase;
long long d[520][520][2][2];
long long f(int i,int j,int b,int e){
    if(~d[i][j][b][e]){
        return d[i][j][b][e];
    }
    if(!j){
        return i&&!b&&!e;
    }
    if(!i){
        return j==1&&b==1&&e==1;
    }
    if(e){
        return d[i][j][b][e]=f(i,j-1,b,0);
    }
    else{
        return d[i][j][b][e]=f(i-1,j,b,0)+f(i-1,j,b,1);
    }
}
int main(){
    memset(d,-1,sizeof(d));
    long long ans;
    while(~scanf("%d",&L)&&L){
        ans=0;
        if(!(L&1||L<4)){
            ans+=f((L+4)/2,(L-4)/2,0,0);
            ans+=f((L+4)/2,(L-4)/2,1,0);
            ans+=f((L+4)/2,(L-4)/2,0,1);
        }
        printf("Case %d: %lld\n",++kase,ans);
    }
    return 0;
}

方法二:

d(i,j,k)表示以k开头,有iR,有j对相邻的RRRR算两对,ROR0对),且以R结尾的方案数。

d(1,0,0)=d(1,0,1)=1.

其余d(i,j,k)=d(i-1,j,k)+d(i-1,j-1,k).表示当前字符串可由某个R结尾的字符加上ORR来得到。

A=(L+4)/2

答案是d(A,4,1)+d(A,3,0)+d(A,4,0).

第一项表示O开头R结尾。

第二项表示R开头R结尾。求的是字符串中只有3RR。但是把开头和结尾这一对算上就有4对了。

第三项很难理解,它表示R开头O结尾。每一个R开头O结尾的合法字符串都对应一个把最后一个O去掉之后的,R开头R结尾的字符串。因为最后一个字符是O,不能和前面的R接在一起,所以需要保证前面就有4R

也就是说把4RR对的R开头R结尾的字符串后面加上一个O就可以得到4RR对的R开头O结尾的字符串。

代码:

#include<cstdio>
#include<cstring>
int L,kase;
long long d[520][520][2];
long long f(int i,int j,int k){
    if(i==1){
        return !j;
    }
    if(~d[i][j][k])return d[i][j][k];
    return d[i][j][k]=f(i-1,j,k)+f(i-1,j-1,k);
}
int main(){
    memset(d,-1,sizeof(d));
    while(~scanf("%d",&L)&&L){
        if(L&1||L<4){
            printf("Case %d: 0\n",++kase);
            continue;
        }
        printf("Case %d: %lld\n",++kase,
            f((L+4)/2,3,0)+//R...R
            f((L+4)/2,4,1)+//O...R
            f((L+4)/2,4,0)  //R...O
        );
    }
    return 0;
}

方法三:(参考了KobeDuu的博客

组合计数。

其实可以发现,只要有A=(L+4)/2RB=(L-4)/2O(其实B=A-4),并且OO不相连,那么一定可以保证有4个RR对。

可以这样想:把A \ge 4R连成一个环,那么有ARR对。

再把B=A-4O插入,每插入一个O,就会少一个RR对。

所以最后剩下A-B=4RR对。刚好满足条件。

所以可以这样利用组合数算,把所有RR排成一行之后:

1.在开头放O

那么,最后一个位置不能放O。剩下A-1个位置可以放,要放下B-1O

计数C_{A-1}^{B-1}

2.不在开头放O

那么剩下A个位置可以放BO
计数C_{A}^{B}.

所以答案为C_{A-1}^{B-1}+C_{A}^{B}.

代码太简单就略了吧。

祝AC。

留下评论

您的电子邮箱地址不会被公开。