C++奥赛一本通递归题解

举报
小哈里 发表于 2022/05/10 22:43:12 2022/05/10
【摘要】 title: C++奥赛一本通刷题记录(递归) date: 2017-11-09 tags: 一本通openjudege categories: OI C++奥赛一本通刷题记录(递归) ...

title: C++奥赛一本通刷题记录(递归)
date: 2017-11-09
tags:

  • 一本通
  • openjudege
    categories: OI

C++奥赛一本通刷题记录(递归)

2017.11.9 By gwj1139177410

  1. 逆波兰表达式 openjudge1696

    //栈比较坑。。。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
char a[3010];
double trans(){ //float is bugs
    scanf("%s",a);
    if(strlen(a)==1){
        if(a[0]=='+')return trans()+trans();
        if(a[0]=='-')return trans()-trans();
        if(a[0]=='*')return trans()*trans();
        if(a[0]=='/')return trans()/trans();
    }else{
        return atof(a);
    }
}
int main(){
    printf("%f\n", trans());
    return 0;
}

    
   
      
    
    • 1
      • 
    
    • 2
      • 
    
    • 3
      • 
    
    • 4
      • 
    
    • 5
      • 
    
    • 6
      • 
    
    • 7
      • 
    
    • 8
      • 
    
    • 9
      • 
    
    • 10
      • 
    
    • 11
      • 
    
    • 12
      • 
    
    • 13
      • 
    
    • 14
      • 
    
    • 15
      • 
    
    • 16
      • 
    
    • 17
      • 
    
    • 18
      • 
    
    • 19
      • 
    
    • 20
      • 
    
    • 21
      •

  2. 全排列 openjudge1750

    //直接套模板，据说STL也能水
#include<cstdio>
#include<cstring>
const int maxn = 110;
char a[maxn], b[maxn];
int n, vis[maxn];
void dfs(int cur){
    if(cur == n){
        for(int i = 0; i < n; i++)putchar(b[i]);
        printf("\n");
    }else for(int i = 0; i < n; i++){
        if(!vis[i]){
            vis[i] = 1;
            b[cur] = a[i];
            dfs(cur+1);
            vis[i] = 0;
        }
    }
}
int main(){
    scanf("%s", a); n = strlen(a);
    dfs(0);
    return 0;
}

    
   
      
    
    • 1
      • 
    
    • 2
      • 
    
    • 3
      • 
    
    • 4
      • 
    
    • 5
      • 
    
    • 6
      • 
    
    • 7
      • 
    
    • 8
      • 
    
    • 9
      • 
    
    • 10
      • 
    
    • 11
      • 
    
    • 12
      • 
    
    • 13
      • 
    
    • 14
      • 
    
    • 15
      • 
    
    • 16
      • 
    
    • 17
      • 
    
    • 18
      • 
    
    • 19
      • 
    
    • 20
      • 
    
    • 21
      • 
    
    • 22
      • 
    
    • 23
      • 
    
    • 24
      •

  3. 分解因数 openjudge1751

    //这题我第一个想法是排列组合，数论，然后。。。。
#include<iostream>
using namespace std;
int f(int n, int m){ //找n的分解方案数
    if(n == 1)return 0;
    int ans = 1; //加上题目自己算一个值
    for(int i = m; i*i <= n; i++)//枚举n的每个约数，每次除掉(从小到大去重)
        if(n%i==0)ans += f(n/i,i);
    return ans;
}
int main(){
    int T;  cin>>T;
    while(T--){
        int n;  cin>>n;
        cout<<f(n,2)<<"\n";//找约数从2开始
    }
    return 0;
}

    
   
      
    
    • 1
      • 
    
    • 2
      • 
    
    • 3
      • 
    
    • 4
      • 
    
    • 5
      • 
    
    • 6
      • 
    
    • 7
      • 
    
    • 8
      • 
    
    • 9
      • 
    
    • 10
      • 
    
    • 11
      • 
    
    • 12
      • 
    
    • 13
      • 
    
    • 14
      • 
    
    • 15
      • 
    
    • 16
      • 
    
    • 17
      • 
    
    • 18
      •

  4. 斐波那契数列 openjudge1755

    //╮(￣▽￣)╭数据太水我也没办法
#include<iostream>
using namespace std;
int f(int n){
    return n==1||n==2?1:f(n-1)+f(n-2);
}
int main(){
    int T;  cin>>T;
    while(T--){
        int n;  cin>>n;
        cout<<f(n)<<"\n";
    }
    return 0;
}

    
   
      
    
    • 1
      • 
    
    • 2
      • 
    
    • 3
      • 
    
    • 4
      • 
    
    • 5
      • 
    
    • 6
      • 
    
    • 7
      • 
    
    • 8
      • 
    
    • 9
      • 
    
    • 10
      • 
    
    • 11
      • 
    
    • 12
      • 
    
    • 13
      • 
    
    • 14
      •

  5. pell数列 openjudge1788

    //(⁄ ⁄•⁄ω⁄•⁄ ⁄)这个没有记忆化药丸了
#include<iostream>
using namespace std;
int f[1000010];
int fn(int n){
    return f[n]?f[n]:f[n]=(2*fn(n-1)+fn(n-2))%32767;
}
int main(){
    f[1]=1; f[2]=2;
    int T;  cin>>T;
    while(T--){
        int n;  cin>>n;
        cout<<fn(n)<<"\n";
    }
    return 0;
}

    
   
      
    
    • 1
      • 
    
    • 2
      • 
    
    • 3
      • 
    
    • 4
      • 
    
    • 5
      • 
    
    • 6
      • 
    
    • 7
      • 
    
    • 8
      • 
    
    • 9
      • 
    
    • 10
      • 
    
    • 11
      • 
    
    • 12
      • 
    
    • 13
      • 
    
    • 14
      • 
    
    • 15
      • 
    
    • 16
      •

  6. 括号匹配问题 openjudge2705

    //模拟题一番水
#include<iostream>
#include<string>
#include<stack>
using namespace std;
int main(){
    string s, t;
    stack<int>sk, tk;
    while(getline(cin,s)){
        t.resize(s.size());
        for(int i = 0; i < s.size(); i++){
            t[i] = ' ';
            if(s[i]=='(')sk.push(i);
            if(s[i]==')'){
                if(sk.size())sk.pop();
                else tk.push(i);
            }
        }
        while(sk.size()){
            t[sk.top()] = '$';
            sk.pop();
        }
        while(tk.size()){
            t[tk.top()] = '?';
            tk.pop();
        }
        cout<<s<<"\n"<<t<<"\n";
    }
    return 0;
}

    
   
      
    
    • 1
      • 
    
    • 2
      • 
    
    • 3
      • 
    
    • 4
      • 
    
    • 5
      • 
    
    • 6
      • 
    
    • 7
      • 
    
    • 8
      • 
    
    • 9
      • 
    
    • 10
      • 
    
    • 11
      • 
    
    • 12
      • 
    
    • 13
      • 
    
    • 14
      • 
    
    • 15
      • 
    
    • 16
      • 
    
    • 17
      • 
    
    • 18
      • 
    
    • 19
      • 
    
    • 20
      • 
    
    • 21
      • 
    
    • 22
      • 
    
    • 23
      • 
    
    • 24
      • 
    
    • 25
      • 
    
    • 26
      • 
    
    • 27
      • 
    
    • 28
      • 
    
    • 29
      • 
    
    • 30
      •

  7. 爬楼梯 openjudge3089

    #include<iostream>
using namespace std;
int a[50];
int f(int n){
    return a[n]?a[n]:a[n]=f(n-1)+f(n-2);
}
int main(){
    a[1]=1; a[2]=2; //稍微注意一下边界就好啦
    int n;
    while(cin>>n){
        cout<<f(n)<<"\n";
    }
    return 0;
}

    
   
      
    
    • 1
      • 
    
    • 2
      • 
    
    • 3
      • 
    
    • 4
      • 
    
    • 5
      • 
    
    • 6
      • 
    
    • 7
      • 
    
    • 8
      • 
    
    • 9
      • 
    
    • 10
      • 
    
    • 11
      • 
    
    • 12
      • 
    
    • 13
      • 
    
    • 14
      •

  8. 汉诺塔问题 openjudge6261

    //这种就是经常出现在初赛看程序写结果里面的
//ha2():将n个盘子从a经过c移动到b
#include<iostream>
using namespace std;
void ha2(int n, char a, char b, char c){
    if(!n)return ;
    ha2(n-1,a,c,b); //把前n-1个盘子移动到辅助的杆c
    cout<<a<<"->"<<n<<"->"<<b<<"\n";//然后把自己移动到目标杆b
    ha2(n-1,c,b,a);//最后再把前n-1个盘子通过辅助的杆a辅助移动到目标杆b
}
int main(){
    int n; char a, b, c;
    cin>>n>>a>>b>>c;
    ha2(n,a,b,c);
    return 0;
}

    
   
      
    
    • 1
      • 
    
    • 2
      • 
    
    • 3
      • 
    
    • 4
      • 
    
    • 5
      • 
    
    • 6
      • 
    
    • 7
      • 
    
    • 8
      • 
    
    • 9
      • 
    
    • 10
      • 
    
    • 11
      • 
    
    • 12
      • 
    
    • 13
      • 
    
    • 14
      • 
    
    • 15
      • 
    
    • 16
      •

  9. 放苹果 openjudge666

    //已经很水啦，貌似递推做过呢
#include<iostream>
using namespace std;
int f(int m, int n){
    if(m==0 || n==1)return 1;
    return n>m?f(m,m):f(m,n-1)+f(m-n,n);
}
int main(){
    int T;  cin>>T;
    while(T--){
        int m, n;  cin>>m>>n;
        cout<<f(m,n)<<"\n";
    }
    return 0;
}

    
   
      
    
    • 1
      • 
    
    • 2
      • 
    
    • 3
      • 
    
    • 4
      • 
    
    • 5
      • 
    
    • 6
      • 
    
    • 7
      • 
    
    • 8
      • 
    
    • 9
      • 
    
    • 10
      • 
    
    • 11
      • 
    
    • 12
      • 
    
    • 13
      • 
    
    • 14
      • 
    
    • 15
      •

  10. 求最大公约数问题 openjudge7592

    #include<iostream>
using namespace std;
typedef long long LL;
LL gcd(LL a, LL b){
    return !b?a:gcd(b,a%b);
}
int main(){
    LL a, b;  cin>>a>>b;
    cout<<gcd(a,b)<<"\n";
    return 0;
}

    
   
      
    
    • 1
      • 
    
    • 2
      • 
    
    • 3
      • 
    
    • 4
      • 
    
    • 5
      • 
    
    • 6
      • 
    
    • 7
      • 
    
    • 8
      • 
    
    • 9
      • 
    
    • 10
      • 
    
    • 11
      •

  11. 2的幂次方表示 openjudge8758

    //直接模拟就好啦
#include<iostream>
using namespace std;
void dfs(int dep, int n){
    //if(n<=2){ cout<<n; return; }
    int flag = 0;
    for(int i = dep; i >= 0; i--){
        if(n&(1<<i)){
            if(flag)cout<<"+";
            if(i == 1)cout<<2;
            else if(i==0||i==2)cout<<"2("<<i<<")";//等价于边界条件
            else{
                cout<<"2(";
                dfs(dep,i);
                cout<<")";
            }
            flag = 1;
        }
    }
}
int main(){
    int n;  cin>>n;  dfs(30,n);
    return 0;
}

    
   
      
    
    • 1
      • 
    
    • 2
      • 
    
    • 3
      • 
    
    • 4
      • 
    
    • 5
      • 
    
    • 6
      • 
    
    • 7
      • 
    
    • 8
      • 
    
    • 9
      • 
    
    • 10
      • 
    
    • 11
      • 
    
    • 12
      • 
    
    • 13
      • 
    
    • 14
      • 
    
    • 15
      • 
    
    • 16
      • 
    
    • 17
      • 
    
    • 18
      • 
    
    • 19
      • 
    
    • 20
      • 
    
    • 21
      • 
    
    • 22
      • 
    
    • 23
      • 
    
    • 24
      •

  12. 分数求和 openjudge12

    //gcd&lcm
#include<iostream>
using namespace std;
int gcd(int a, int b){
    return !b?a:gcd(b,a%b);
}
int lcm(int a, int b){
    return a/gcd(a,b)*b;
}
int main(){
    int a=0, b=1;
    int T;  cin>>T;
    while(T--){
        int c, d; cin>>c; cin.get(); cin>>d;
        int t = lcm(b,d);
        a = a*(t/b)+c*(t/d);  b = t;
        while((t=gcd(a,b))!=1){
            a/=t; b/=t;
        }
    }
    if(b==1||a==0)cout<<a<<"\n";
    else cout<<a<<"/"<<b<<"\n";
    return 0;
}

    
   
      
    
    • 1
      • 
    
    • 2
      • 
    
    • 3
      • 
    
    • 4
      • 
    
    • 5
      • 
    
    • 6
      • 
    
    • 7
      • 
    
    • 8
      • 
    
    • 9
      • 
    
    • 10
      • 
    
    • 11
      • 
    
    • 12
      • 
    
    • 13
      • 
    
    • 14
      • 
    
    • 15
      • 
    
    • 16
      • 
    
    • 17
      • 
    
    • 18
      • 
    
    • 19
      • 
    
    • 20
      • 
    
    • 21
      • 
    
    • 22
      • 
    
    • 23
      • 
    
    • 24
      •

  13. 因子分解 openjudge22

    #include<iostream>
using namespace std;
int main(){
    int n, flag=0;  cin>>n;
    for(int i = 2; i <= n; i++){
        int cnt = 0;
        while(n%i==0){
            n /= i;  cnt++;
        }
        if(cnt){
            if(flag)cout<<"*";
            if(cnt==1)cout<<i;
            else cout<<i<<"^"<<cnt;
            flag = 1;
        }
    }
    return 0;
}

    
   
      
    
    • 1
      • 
    
    • 2
      • 
    
    • 3
      • 
    
    • 4
      • 
    
    • 5
      • 
    
    • 6
      • 
    
    • 7
      • 
    
    • 8
      • 
    
    • 9
      • 
    
    • 10
      • 
    
    • 11
      • 
    
    • 12
      • 
    
    • 13
      • 
    
    • 14
      • 
    
    • 15
      • 
    
    • 16
      • 
    
    • 17
      • 
    
    • 18
      •

  14. 判断元素是否存在 openjudge41

    //感觉有点绕，拿set水了
#include<iostream>
#include<set>
using namespace std;
set<int>s;
int main(){
    int k, x, t;  cin>>k; cin.get(); cin>>x;
    s.insert(k); t = k; int cnt = 0;
    for(set<int>::iterator it = s.begin(); it!=s.end(); it++){
        s.insert(2*(*it)+1); s.insert(3*(*it)+1);
        if(*(--s.end())>x)cnt++;
        if(cnt>1000)break;//强行搞事情
    }
    if(s.count(x))cout<<"YES\n";else cout<<"NO\n";
    return 0;
}

    
   
      
    
    • 1
      • 
    
    • 2
      • 
    
    • 3
      • 
    
    • 4
      • 
    
    • 5
      • 
    
    • 6
      • 
    
    • 7
      • 
    
    • 8
      • 
    
    • 9
      • 
    
    • 10
      • 
    
    • 11
      • 
    
    • 12
      • 
    
    • 13
      • 
    
    • 14
      • 
    
    • 15
      • 
    
    • 16
      • 
   
    //开个玩笑的,不过这也算递归?
#include<iostream>
using namespace std;
const int maxn = 300010;
int a[maxn];
void enlarge(int x){
    if(x<maxn){
        a[x] = 1;
        enlarge(2*x+1);
        enlarge(3*x+1);
    }else return ;
}
int main(){
    int k, x;  cin>>k; cin.get(); cin>>x;
    enlarge(k);
    if(a[x])cout<<"YES\n";else cout<<"NO\n";
    return 0;
}

    
   
      
    
    • 1
      • 
    
    • 2
      • 
    
    • 3
      • 
    
    • 4
      • 
    
    • 5
      • 
    
    • 6
      • 
    
    • 7
      • 
    
    • 8
      • 
    
    • 9
      • 
    
    • 10
      • 
    
    • 11
      • 
    
    • 12
      • 
    
    • 13
      • 
    
    • 14
      • 
    
    • 15
      • 
    
    • 16
      • 
    
    • 17
      • 
    
    • 18
      •

    ​

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/79059202

【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
C++
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入