柚子快報激活碼778899分享：職場和發(fā)展 藍(lán)橋杯 砍竹子

http://yzkb.51969.com/

原題鏈接?砍竹子

其實最多也就砍6次，測評程序如下（C++）

#include

#include

using namespace std;

int main(){

long long x = 1e18;

while(x>1){

x=sqrt(x/2+1);

cout<

}

return 0;

}

顯而易見，每個數(shù)據(jù)代表砍一次，這里選用了最大的數(shù)據(jù)

源代碼如下：

#include

#include

#include

#include

using namespace std;

typedef long long LL;

const int N = 200010, M = 20;//測試一下一個竹子最多砍6次，一共N棵竹子，砍M下

int n, m;//用n、m表示最多多少層,m表示一層最多有多少個節(jié)點

LL f[N][M];//每一層里的每個數(shù)

int main()

{

scanf("%d", &n);//棵數(shù)

LL stk[M];//逆序一下，需要從下往上存，畢竟竹子是從上往下砍

int res = 0;//定義一下答案

for (int i = 0; i < n; i ++ )

{

LL x;

int top = 0;//定義棧頂元素

scanf("%lld", &x);//高度

while (x > 1) stk[ ++ top] = x, x = sqrtl(x / 2 + 1);//x>1的時候每次都要把x存下來

res += top;

m = max(m, top);

for (int j = 0, k = top; k; j ++, k -- )//將操作步數(shù)逆序取下來

f[i][j] = stk[k];

}

for (int i = 0; i < m; i ++ )//枚舉所有層

for (int j = 1; j < n; j ++ )//每一層里相同高度的個數(shù)

if (f[j][i] && f[j][i] == f[j - 1][i])//相鄰的相同數(shù)

res -- ;

printf("%d\n", res);

return 0;

}

本博客參考了acwing的視頻

柚子快報激活碼778899分享：職場和發(fā)展 藍(lán)橋杯 砍竹子

http://yzkb.51969.com/

精彩內(nèi)容