P4179 [Cqoi2010]鼹鼠

· · 题解

题目传送门

emm...当我看到这个题的时候，第一反应就是打表，于是就开始了漫长的推算之旅。。。

第一步数格子的个数，数了很久推出一个式子：4* a[i-1]+2* (i-1)

可是数完之后发现这样没用啊，还不一定是对的，于是打标思路愉快地GG。（也许可以只是我没推出来）

于是我就发现数量上行不通，从形状上总可以吧。于是推着推着就发现乱七八糟的图形是可以转化成为一个中学数学题。

那么规律是什么呢？举个例子：

你还没有发现规律吗？那就再来一组：

此时，不难发现规律，地图的左上角以及右上角的空，以及左下和右下的地洞是上一个的图形。这样分形就愉快的完成了。

此时突然发现，没有数据范围，好吧,我默默的打开了bzoj1817,发现了数据范围（n≤12,0≤α<90）（还无耻的请管理员加一下数据范围）那么有了数据范围就可以算出最大边长，及2^{12}-1=4095，所以就可以轻松的用一个二维数组存下来。

接下来应该就是考虑水在方格中的位置了。

仔细观察，我们不难发现顶部的一个格子的水在格子中大概是这样的，再根据题意可看出，可以推出为基准高度为cosα（这是三角函数，不要问我为什么），但是中间的怎么办呢？其实也就是从周围四个格子相互连通中推导而来,想到周围的四个格子就想到了搜索（建议用dfs，感觉bfs会爆空间，毕竟n≤12）,那么只需从四个方向（左上，右上，左下，右下）推出即可。

举个例子（又要看图）：

就不难看出准高为h+sinα（左下），至于剩下的三个方向就不画图了， 直接告诉大家准高吧，分别是：h+cosα（右下），h-sinα（左上），h-cosα（右上）， 其实大家学过三角函数的都知道吧，而且都应该能自己推出来（不会推的也不要慌，毕竟我也推了好久）

知道准高以后，就可以面积就可以进行分类讨论（与cosα,sinα）

分三段后求解，然后这个题就应该可以通过搜索做出来了

温馨提示：为了保证精度，最后在进行除法运算，小数点后取六位哦~~

最后就是你们想要的AC代码了：

#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
int n,jd,len=1;
double sinn,coss,sum,ans;
const double p=4.0*atan(1.0);
bool vis[4100][4100],mapp[4100][4100],hole[4100][4100];
double min(double i,double j){return i<j?i:j;}
bool rule(int x,int y){
    if(x>=1&&y>=1&&x<=len&&y<=len&&!vis[x][y]&&mapp[x][y])return 0;
    return 1;
}
void dfs(int x,int y,double h){
    if(h<1e-10||rule(x,y))return;
    vis[x][y]=1;
    h=min(sum,h);
    if(jd==0)ans++;
    else{
        double s=sinn,c=coss;
        if(jd>45)swap(s,c);
        if(h<=s)ans+=h*h;
        else if(h<=c)ans+=(2.0*h-s)*s;
        else ans+=2.0*s*c-(s+c-h)*(s+c-h); 
    }
    dfs(x+1,y,h+coss),dfs(x,y+1,h+sinn);
    dfs(x-1,y,h-coss),dfs(x,y-1,h-sinn);
    return;
}
int main(){
    scanf("%d%d",&n,&jd);
    mapp[1][1]=1;
    for(int k=1;k<n;k++){
        for(int i=1;i<=len;i++){
            for(int j=1;j<=len;j++){
                hole[len-j+1][i]=hole[j][len+1+len-i+1]=!mapp[i][j];
                hole[len+1+i][j]=hole[len+1+i][len+j+1]=mapp[i][j];
            }
        }
        for(int i=1;i<=2*len+1;i++)hole[len+1][i]=1;
        for(int i=1;i<=len;i++)hole[i][len+1]=1;
        len*=2,len++;
        for(int i=1;i<=len;i++){
            for(int j=1;j<=len;j++)mapp[i][j]=hole[i][j];
        }   
    }
    double angle=(1.0*jd*p/180);
    sinn=sin(angle);
    coss=cos(angle);
    sum=coss+sinn;
    for(int i=1;i<=len;i++)dfs(1,i,coss);
    if(jd>0)ans/=(2.0*sinn*coss);
    printf("%0.6lf",ans);
    return 0;
}