当前位置：首页 > article >正文

0x02递推与递归

article 2025/2/24 0:10:24

(1)递归

AcWing 92. 递归实现指数型枚举

选or不选

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int>a;
void dfs(int x){
    if(x==n+1){
        for(int i=0;i<a.size();i++){
            printf("%d ",a[i]);
        }
        printf("\n");
        return;
    }
    dfs(x+1);
    a.push_back(x);
    dfs(x+1);
    a.pop_back();
}
int main(){
    scanf("%d",&n);
    dfs(1);
    return 0;
}

AcWing 93. 递归实现组合型枚举

加减枝，关于到不了和超了

#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int>a;
void dfs(int x){
    if(a.size()>m||(n-x+1+a.size())<m)return ;//******************
    if(x==n+1){
        for(int i=0;i<a.size();i++){
            printf("%d ",a[i]);
        }
        printf("\n");
        return;
    }
    a.push_back(x);
    dfs(x+1);
    a.pop_back();
    dfs(x+1);

}
int main(){
    scanf("%d%d",&n,&m);
    dfs(1);
    return 0;
}

AcWing 94. 递归实现排列型枚举

随机选，记录已选的

#include<bits/stdc++.h>
using namespace std;
int n,vis[10];
vector<int>a;
void dfs(int x){
    if(x==n+1){
        for(int i=0;i<a.size();i++){
            printf("%d ",a[i]);
        }
        printf("\n");
        return;
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            vis[i]=1;
            a.push_back(i);
            dfs(x+1);
            a.pop_back();
            vis[i]=0;
        }
    }

}
int main(){
    scanf("%d",&n);
    dfs(1);
    return 0;
}

AcWing 95. 费解的开关

枚举第一行方案，剩下的行数模拟下去，判断是否可行，更新答案

#include<bits/stdc++.h>
using namespace std;
int n=5,T,a[10][10],tmp[10][10];
char s[10][10];
void cz(int i,int j){
    tmp[i][j]^=1;tmp[i-1][j]^=1;tmp[i+1][j]^=1;tmp[i][j-1]^=1;tmp[i][j+1]^=1;
}
bool check(){
    for(int i=1;i<=n;i++)if(!tmp[n][i])return 0;
    return 1;
}
int main(){
    scanf("%d",&T);
    while(T--){
        int flag=1,ans=1e9;
        for(int i=1;i<=n;i++){
            scanf("%s",s[i]+1);
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                a[i][j]=s[i][j]-'0';
            }
        }
        for(int s=0;s<(1<<n);s++){
            int cnt=0;
            for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)tmp[i][j]=a[i][j];
            for(int i=1;i<=n;i++){
                if(s>>i-1&1){
                    cz(1,i);
                    cnt++;
                }
            }
            for(int i=2;i<=n;i++){
                for(int j=1;j<=n;j++){
                    if(tmp[i-1][j]==0){
                        cz(i,j);
                        cnt++;
                    }
                }
            }
            if(cnt<=6&&check()){
                flag=0;
                ans=cnt;
            }
        }
        if(flag)printf("-1\n");
        else printf("%d\n",ans);
    }
    return 0;
}

(2)递推

AcWing 96. 奇怪的汉诺塔

三塔模式d[n]=2*d[n-1]+1，表示把n-1个移到B柱，把最大的移到C柱，最后把n-1个移到C柱

四塔f[n]=min{2*f[i]+d[n-i]} 其中 $i\in [1,n-1]$ ，表示把i个移到B柱，把n-i个移到D柱，再把剩下的i个再移到D柱

#include<bits/stdc++.h>
using namespace std;
long long f[70][70],n=4,m=12;
void init(){
    for(int i=3;i<=n;i++)f[i][1]=1;
    for(int i=2;i<=m;i++){
        f[3][i]=f[3][i-1]*2+1;
    }
}
int main(){
    init();
    for(int i=4;i<=n;i++){
        for(int j=2;j<=m;j++){
            f[i][j]=1e9;
            for(int k=1;k<j;k++){
                f[i][j]=min(f[i][k]*2+f[i-1][j-k],f[i][j]);
            }
        }
    }
    for(int i=1;i<=m;i++)printf("%d\n",f[n][i]);
    return 0;
}

(3)分治

AcWing 97. 约数之和

求等比数列

c为奇数时

sum（p,c)=p+p^2+...+p^c

=1+p+p^2+...+p^(c-1)/2+p^(c+1)/2+...+p^c

=sum(p,(c-1)/2)*(1+p^(c+1)/2)

c为偶数

sum（p,c)=sum(p,c/2)*(1+p^(c/2-1))+p^c

#include<bits/stdc++.h>
using namespace std;
long long a,b,ans=1;
const long long mod=9901;
long long ksm(long long a,long long b){
    long long res=1;
    while(b){
        if(b&1)res=res*a%mod;
        b>>=1;a=a*a%mod;
    }
    return res;
}
long long calc(long long p,long long n){
    if(n==0)return 1;if(n==1)return (p+1)%9901;
    if(n&1)return calc(p,(n-1)/2)*(1+ksm(p,(n+1)/2))%mod;
    else return (calc(p,n-1)+ksm(p,n))%mod;
}
int main(){
    scanf("%lld%lld",&a,&b);
    if(a==0){printf("0");return 0;}
    for(long long i=2;i*i<a;i++){
        long long cnt=0;
        while(a%i==0){a/=i;cnt++;}
        ans=(ans*calc(i,cnt*b))%mod;
    }
    if(a>1)ans=(ans*calc(a,b))%mod;
    printf("%lld",ans);
    return 0;
}

(4)分形

AcWing 98. 分形之城

四份四份分形，记录左上角坐标及尺寸

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll T,n,a,b;
pair<ll,ll> calc(ll n,ll p){
    if(n==0)return {0,0};
    ll len=1ll<<(n-1),cnt=1ll<<(2*n-2);
    pair<ll,ll>q=calc(n-1,p%cnt);
    ll x=q.first,y=q.second;
    long long m=p/cnt;
    if(m==0)return {-y-len,-x+len};
    if(m==1)return {x+len,y+len};
    if(m==2)return {x+len,y-len};
    return {y-len,x-len};
}
double js(){
    pair<ll,ll>x=calc(n,a),y=calc(n,b);
    return sqrt(((double)(x.first-y.first)*(double)(x.first-y.first)+(double)(y.second-x.second)*(double)(y.second-x.second)))*5;
}
int main(){
    scanf("%lld",&T);
    while(T--){
        scanf("%lld%lld%lld",&n,&a,&b);
        a--,b--;
        printf("%.0lf\n",js());
    }
    return 0;
}

AcWing 118. 分形

这个不用说

#include<bits/stdc++.h>
using namespace std;
int n,mp[2505][2505];
void init(){
    mp[1][1]=1;
    int len=1;
    for(int s=1;s<=7;s++){
        for(int i=1;i<=len;i++){
            for(int j=1;j<=len;j++){
                mp[i+len*2][j]=mp[i][j];
                mp[i+len*2][j+len*2]=mp[i][j];
                mp[i][j+len*2]=mp[i][j];
                mp[i+len][j+len]=mp[i][j];
            }
        }
        len*=3;
    }
}
int main(){
    init();
    while(scanf("%d",&n)){
        if(n==-1)return 0;
        else{
            n--;
            for(int i=1;i<=pow(3,n);i++){
                for(int j=1;j<=pow(3,n);j++){
                    printf("%c",(mp[i][j])?'X':' ');
                }
                printf("\n");
            }
            printf("-\n");
        }
    }
    return 0;
}

查看全文

http://www.kler.cn/a/549132.html