题解P2539【矿藏编码】

· · 题解

longlong都过不了

如2^50恐怖的数据

好吧只能用double

好了进入正题（题目点这里）

首先点明中心思想：

看看下面的dalao们都用的是递归，我就膜拜了。（本蒟蒻最怕递归，而且这题真的不用递归）
在这里给出一个平民易懂的朴素思想：用一个类似栈的top（其实就是一个指针）代表层数，每逢“2”++，逢“1”不做任何操作，逢“0”计数器s加上一个
(1<<(k-top))·(1<<(k-top))

（1<<（k-top）等同于pow（2，k-top），解释一下为什么是2的k-top次方：top就是层数，相当于已经把整块分成了2^top块，这时整块空地的面积就是2^k-2^top，计算以后得(1<<(k-top))·(1<<(k-top))）

这时还有一个问题要考虑，那就是满4大块后怎么回退呢？这里我只能想到用q数组来存储已经完整的块的数量，满4进1，并把top--。

接下来放我80分代码（逃而又回）（不知道为什么，第7和第9没过，可能是double精度还太低，恳请各位大佬帮我找一下）

#include <bits/stdc++.h>
using namespace std;
char a[200];
int q[201];//标记
int main()
{
    int k,top=0;
    double s=0;
    scanf("%d",&k);
    cin>>a;
    for(int i=0;i<strlen(a);i++)
    {
        if(a[i]=='2') top++;
        else q[top]++;
        if(a[i]=='0') s+=(double)(pow(2,k-top)*pow(2,k-top))/1000000000000000000;//精髓
        while(q[top]==4)//清标记
        {
            q[top--]=0;
            q[top]++;
        }
    }
    printf("%.0lf",s*1000000000000000000);
    return 0;
}

结束咯！