[AHOI2005]矿藏编码

时间:2024-04-12 14:07:24

嘟嘟嘟

这道题题面我是看了小半天才懂(太菜了),然后就发现好水啊。

只要维护一个栈,存的是t,代表当前的正方形是2t * 2t的,然后从头开始扫序列,如果遇到2,就把栈顶元素取出来,然后放进去四个t - 1;如果遇到0,就往结果中加入当前栈顶元素t的2t * 2t.

此题最大范围是250 * 250,long long也不够,得开double(long long 和 double虽然都只有64位,但因为储存凡是不同,double范围却比long long 大)。

 #include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a) memset(a, 0, sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
const int INF = 0x3f3f3f3f;
const int eps = 1e-;
const int maxn = ;
inline ll read()
{
ll ans = ;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) {last = ch; ch = getchar();}
while(isdigit(ch)) {ans = ans * + ch - ''; ch = getchar();}
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < ) x = -x, putchar('-');
if(x >= ) write(x / );
putchar(x % + '');
} int k;
char s[maxn];
db ans = ;
stack<int> st;
db quickpow(db a, int b)
{
db ret = ;
while(b)
{
if(b & ) ret *= a;
a *= a; b >>= ;
}
return ret;
} int main()
{
k = read();
scanf("%s", s);
int n = strlen(s);
st.push(k);
for(int i = ; i < n; ++i)
{
int t = st.top(); st.pop();
if(s[i] == '') for(int j = ; j <= ; ++j) st.push(t - );
else if(s[i] == '') ans += quickpow(, t) * quickpow(, t);
}
printf("%.0lf\n", ans);
return ;
}