自动搬运

查看原文

来自洛谷，原作者为

	Hanriver 。

搬运于2025-08-24 21:38:48，当前版本为作者最后更新于2019-12-16 19:51:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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;
}

结束咯！