首页 > 代码库 > 洛谷P1573 栈的操作 [2017年6月计划 数论11]

洛谷P1573 栈的操作 [2017年6月计划 数论11]

P1573 栈的操作

题目描述

现在有四个栈,其中前三个为空,第四个栈从栈顶到栈底分别为1,2,3,…,n。每一个栈只支持一种操作:弹出并 压入。它指的是把其中一个栈A的栈顶元素x弹出,并马上压入任意一个栈B中。但是这样的操作必须符合一定的规则才能进行。规则1:A栈不能为空。规则 2:B栈为空或x比B栈栈顶要小。

对于给定的n,请你求出把第四个栈的n个元素全部移到第一个栈的最少操作次数。

由于最少操作次数可能很多,请你把答案对1000007取模。

输入输出格式

输入格式:

一行,一个n

输出格式:

一行,一个正整数,为把最少操作次数 mod 1000007的值

输入输出样例

输入样例#1:
2
输出样例#1:
3

说明

对于30%的数据,n<=8

对于60%的数据,n<=60

对于100%的数据,n<=2*10^9

 

 

四根柱子的汉诺塔问题。

f3[i]表示三根汉诺塔柱子,有i个盘子的操作数

f4[i]表示四跟汉诺塔柱子,有i个盘子的操作数

可得:f4[i] = 2f4[j] + f3[i - j],1 <= i < j <= n

可以这样理解:先把j个盘子放到第三根柱子上,操作数f4[j],然后把剩余的i - j个盘子通过三根柱子放到第四根柱子上,方案数f3[i - j ],

然后把j个盘子通过四根柱子放到第四个盘子上

 

打表出来发现他们的差值有规律:

 

1 2 2 4 4 4 8 8 8 8 16 16 16 16 16 32 32 32 32 32 32.....

技术分享
 1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring>  5 #include <algorithm> 6 #include <vector> 7 #include <queue> 8 inline void read(long long &x){x = 0;char ch = getchar();char c = ch;while(ch > 9 || ch < 0)c = ch, ch = getchar();while(ch >= 0 && ch <= 9)x = x * 10 + ch - 0, ch = getchar();} 9 inline int max(int a, int b){return a > b ? a : b;}10 inline int min(int a, int b){return a < b ? a : b;}11 inline void swap(int &a, int &b){int tmp = a;a = b;b = tmp;}12 13 const int INF = 0x3f3f3f3f;14 const int MOD = 1000007;15 long long n;16 long long base = 1, k = 1, m = 1;17 long long ans = 0;18 19 int main()20 {21     read(n);22     long long k = 1;23     long long i;24     for(;k <= n;n -= k, ++k)25     {26         ans += (k * (base % MOD)) % MOD;27         ans %= MOD;28         base <<= 1;29         base %= MOD;30     }31     printf("%lld", (ans + (((n % MOD) * (base % MOD)) % MOD)) % MOD);32     return 0;33 }
View Code

 

洛谷P1573 栈的操作 [2017年6月计划 数论11]