第二场周赛(递归递推个人Rank赛)——题解
很高兴给大家出题,本次难度低于上一场,新生的六个题都可以直接裸递归式或者裸递推式解决,对于老生的汉诺塔3,需要找出一般式,后两题分别为裸ST算法(或线段树)/线性DP。
正确的难度顺序为
- 种花
- 角谷定律
- 猴子和椰子
- 汉诺塔1
- 汉诺塔2
- 整数划分
- 跳台阶
- 汉诺塔3
- 夏目友人帐(一)
- 夏目友人帐(二)
一、种花
本题很容易能推出递推式或者一般式,对于第一快地,有3种种植方法,对于后面的每一快地有不同于前一块地的两种种植方法。
- a1 = 3;
- an = 2*(an-1);
代码:
#include <bits/stdc++.h>
using namespace std; int a[]; void init(){
a[] = ;
for(int i = ; i <= ; i++){
a[i] = a[i-]*;
}
} int main(){
freopen("test.out","w",stdout);
int n;
init();
while(cin>>n){
cout << a[n] << endl;
}
return ;
}
二、角谷定律
本题按照给出的式子操作即可,用另外一个变量记录操作次数。
代码:
#include <bits/stdc++.h>
using namespace std; int cnt = ;
void fun(long long n){
if(n == )
return ;
if(n&)
cnt++,fun(*n+);
else
cnt++,fun(n/);
} int main(){
int n;
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
while(cin>>n){
cnt = ;
fun(n);
cout << cnt << endl;
}
return ;
}
三、猴子和椰子
可能你们也在其他地方看见过本题,设初始椰子为A,最后一次分给每个人的椰子为n,很容易推得一个A关于n得常数式子,因为要保证能够按照题目分下去,所以要保证每次分椰子都为正整数,已得答案为15621(5^6 - 4)。算是个小学数学题。
输出15621即可。
四、汉诺塔1
这是一个汉诺塔的基本变式,其实用汉诺塔的思想去想也不难,要移动n根木根从A至C,可划分为下面几个步骤。
- 先移动n-1根木根到C
- 移动第n根木棍到B
- 移动C上的n-1根木棍到A
- 移动B上的第n根木棍到C
- 移动A上的n-1根木棍到C
至此,完成这个汉诺塔的移动,我们把移动n根木棍从A到C计为F(n)。
则F(n) = F(n-1) + 1 + F(n-1) + 1 + F(n-1) = 3*F(n-1) + 2;且F(1) = 2;
按照这个步骤写出递归函数即可。代码:
#include <bits/stdc++.h>
using namespace std; long long fun(int n){
if(n == )
return ;
return *fun(n-)+;
} int main(){
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
int n;
while(cin>>n){
cout << fun(n) << endl;
}
return ;
}
五、汉诺塔2
在汉诺塔1的基础上多了可以把最长的木棍放在最上面,还是按照上面的步骤,移动n根木棍从A到C可划分为
- 移动n-1根木棍从A到B
- 移动第n根木棍到B上
- 移动第n根木棍到C上
- 移动n-1根木棍从B到C
至此,完成汉诺塔的移动,我们把移动n根木根从A到C计为F(n),移动n根木棍到邻柱子计为T(n),关于T(n)的公式这里就不推了,演变方式一样。
所以有F(n) = T(n-1)+1+1+T(n-1) = 2*T(n-1)+2;且F(1) = 2;
代码:
#include <bits/stdc++.h>
using namespace std; int fc(int n){
if(n == )
return ;
return *fc(n-)+;
} int fun(int n){
if(n == )
return ;
return *fc(n-)+;
} int main(){
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
int n;
while(cin>>n){
cout << fun(n) << endl;
}
return ;
}
六、整数划分
其实这个题题面以及给出了一点提示,把n分成m个正整数的和,要直接求n的划分个数比较难,但是我们可以求n-1、n-2,,,的划分,设n = ΣDi,且max(Di) <= k,
即Di为n的一种划分方案,最大数字不超过k,把它计为F(n,k),那么本题也就是求F(n,n);根据 n,k的不同大小关系,可得下列递归式
- F(n, k) = 1; (n =1 or k = 1)
- F(n, k) = F(n, n); (n < k)
- F(n, k) = F(n, k-1) + 1; (n = k)
- F(n, k) = F(n-k, k) + F(n, k-1); (n > k)
所以可以写出代码:
#include <bits/stdc++.h>
using namespace std; int fun(int n,int m){
if(n == || m == )
return ;
else if(n < m)
return fun(n,n);
else if(n == m)
return fun(n,n-)+;
else if(n > m)
return fun(n,m-)+fun(n-m,m);
} int main(){
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
int n;
while(cin>>n){
cout << fun(n,n) << endl;
}
cerr << clock() << endl;
return ;
}
七、跳台阶
其实很容易推出对于n阶台阶的方案有
F(n) = Σ(F(n-Pi)); (P1 = 1,Pi = 质数集合)
边界条件F(1) = F(0) = 1;
所以代码显而易见了,其实本题还想卡一下数据范围,因为34好像就会爆int,还是算了,就只给你们弄到30,而且本题开了4s,其实我STD只跑了1.7s,奈何只能取整,干脆就4s得了。
代码:
#include <bits/stdc++.h>
using namespace std; int prime[],primesize,phi[];
bool isprime[]; int n; void getlist(int listsize){
memset(isprime,,sizeof(isprime));
isprime[]=false;
for(int i=;i<=listsize;i++)
{
if(isprime[i])prime[++primesize]=i;
for(int j=;j<=primesize&&i*prime[j]<=listsize;j++)
{
isprime[i*prime[j]]=false;
if(i%prime[j]==)break;
}
}
prime[] = ;
} int fun(int n){
int sum = ;
if(n == || n == )
return ;
for(int i = ; i <= primesize; i++){
if(n < prime[i])
break;
sum += fun(n-prime[i]);
}
return sum;
} int main(){
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
ios_base::sync_with_stdio(false);
getlist();
int n;
while(cin>>n){
cout << fun(n) << endl;
}
cerr << clock() <<endl;
}
八、汉诺塔3
四柱汉诺塔问题,我都懒得写如何推了,易得下面递归式
F(n) = min(2*F(n-r)+2r-1),1 <= r <= n;
但是直接用上面式子写递归式肯定会时间爆炸,不信你试试。
最大n不超过100,所以其实你先递推出任意一项就可以了= =,这样的话预处理时间为O(n2),查询时间为O(1)。为了你们好= =所以我没有卡这种算法。
但其实也可以得出一般式,根据Frame-Stewart算法可得出当r = floor((sqrt(8*n+1)-1)/2)时,有最小值,且最小值F(n) = (n - (r2-r+2)/2)*2r+1;
即可以在O(1)时间内得出任意n根木棍需要的最小转移次数。
代码:
#include <bits/stdc++.h>
using namespace std; int a[] = {}; int init(){
fill(a,a+,0x3f3f3f3f);
a[] = ,a[] = ,a[] = ;
for(int i = ; i <= ; i++){
for(int j = ; j < 32; j++){
temp = *a[j]+pow(2LL,(long long)j)-;
a[i] = min(a[i],temp);
}
}
} int main(){
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
int n;
while(cin>>n){
int r = floor((sqrt(*n+)-1.0)/2.0);
int ans = (n-(r*r-r+)/2.0)*pow(2.0,r)+;
cout << ans << endl;
}
cerr << clock() << endl;
return ;
}
九、夏目友人帐(一)
经典RMQ问题,ST/线段树都可以。
本来想卡线段树做法,想了一下不卡算了= =。
代码:
#include <bits/stdc++.h>
using namespace std; //线段树
#define lson l,m,p<<1
#define rson m+1,r,p<<1|1
#define Max(a,b) (a<b?b:a)
#define Min(a,b) (a<b?a:b)
#define INF 999999999 int N,M;
int MaxP[*+];
int maxT;
void Update(int val,int K,int l,int r,int p){
int m=(l+r)>>;
if(l==r){
MaxP[p]=val;
return;
}
if(K<=m)
Update(val,K,lson);
else
Update(val,K,rson);
MaxP[p]=Max(MaxP[p<<],MaxP[p<<|]);
}
void Query(int L,int R,int l,int r,int p){
int m=(l+r)>>;
if(L<=l&&r<=R){
maxT=Max(maxT,MaxP[p]);
return;
}
if(L<=m)
Query(L,R,lson);
if(R>=m+)
Query(L,R,rson);
}
int main(){
freopen("test2.in","r",stdin);
freopen("test2.out","w",stdout);
int i,val,a,b;
scanf("%d %d",&N,&M);
for(i=;i<=N;i++){
scanf("%d",&val);
Update(val,i,,N,);
}
for(i=;i<=M;i++){
scanf("%d %d",&a,&b);
maxT=;
Query(a,b,,N,);
printf("%d\n",maxT);
}
cerr << clock() << endl;
return ;
} //ST算法
int N,M;
int A[];
int FMax[][]; void Init(){
int i,j;
for(i=;i<=N;i++)
FMax[i][]=A[i];
for(i=;(<<i)<=N;i++){
for(j=;j+(<<i)-<=N;j++){
FMax[j][i]=max(FMax[j][i-],FMax[j+(<<(i-))][i-]);
}
}
} int Query(int l,int r){
int k=(int)(log(r-l+)/log());
return max(FMax[l][k],FMax[r-(<<k)+][k]);
} int main(){
freopen("test1.in","r",stdin);
freopen("test1.out","w",stdout);
int i,a,b;
scanf("%d %d",&N,&M);
for(i=;i<=N;i++)
scanf("%d",&A[i]);
Init();
for(i=;i<=M;i++){
scanf("%d %d",&a,&b);
printf("%d\n",Query(a,b));
}
cerr << clock() << endl;
return ;
}
十、夏目友人帐(二)
这里就不说怎么推的了,到时候认真听我黑板上讲23333。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll; const int N = ;
const int Q = ;
int f[Q][N][N];
int p[Q];
int c[N][N]; int main(){
freopen("test3.in","r",stdin);
freopen("test3.out","w",stdout);
ios_base::sync_with_stdio(false);
cin.tie();
cout.tie();
int n,q;cin>>n>>q;
for(int i = ; i <= n; i++){
for(int j = ; j <= n; j++){
cin>>c[i][j];
}
}
for(int i = ; i <= q; i++){
cin>>p[i];
}
memset(f,0x3f,sizeof(f));
int INF = f[][][];
p[] = ;
f[][][] = ;
for(int i = ; i <= q; i++){
for(int x = ; x <= n; x++){
for(int y = ; y <= n; y++){
if(x != p[i] && y != p[i])
f[i][x][y] = min(f[i][x][y],f[i-][x][y]+c[p[i-]][p[i]]);
if(p[i] != y && p[i] != p[i-])
f[i][p[i-]][y] = min(f[i][p[i-]][y],f[i-][x][y]+c[x][p[i]]);
if(p[i] != x && p[i] != p[i-])
f[i][x][p[i-]] = min(f[i][x][p[i-]],f[i-][x][y]+c[y][p[i]]);
}
}
}
int ans = INF;
for(int i = ; i<= n; i++){
for(int j = ; j<= n; j++){
ans = min(ans,f[q][i][j]);
}
}
cout << ans << endl;
cerr << clock() << endl;
return ;
}
P.S. 其实很多题目都可以卡你们算法,不卡不卡,怕被打= =,后面给你们出卡常数233333
最新文章
- 【BZOJ-1127】KUP 悬线法 + 贪心
- ASP.NET MVC Bootstrap极速开发框架
- SQLServer:删除log文件和清空日志的方法
- LightOJ 1012 简单bfs,水
- 一个安邦逻辑漏洞爆破密码的py脚本
- Wordpress编辑器(Tinymce)在Chrome中动态修改图片大小
- VS2010中将当前选定项目做为启动项
- golang的ssh例子
- Android中ExpandableListView,每次只展示一个分组
- poj 3667 Hotel
- linux在shell中获取时间
- 深圳尚学堂:Java中Class对象
- Ext:ComboBox实战
- 【原创】java NIO FileChannel 学习笔记 FileChannel 简介
- 使用MBROSTool 工具制作U盘多启动盘的方法总结
- java中this和super关键字的使用
- es6入门总结
- 201621123075 week8-集合
- 【原创】基于Bootstrap的Modal二次封装
- Retrofit2+Rxjava+OkHttp的使用和网络请求
热门文章
- scala之构造器详解
- 帝国CMS(EmpireCMS) v7.5后台任意代码执行
- 既然synchronized是";万能";的,为什么还需要volatile呢?
- 01 Python网络爬虫简介
- 用java自制简易线程池(不依赖concurrent包)
- maven出现:Failed to execute goal on project ...: Could not resolve dependencies for project ...
- springboot项目中的普通Session和使用redis存储session
- 2019-在iOS里添加admob横幅广告示例
- 自己搭建传统ocr识别项目学习
- oauth2.0授权详解