0x02 递推与递归

【例题】CH0301 递归实现指数型枚举

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <vector>

 using namespace std;

 int n;

 vector<int> chosen;

 void calc(int x) {

     if (x==n+) {

         for (int i=; i<chosen.size(); ++i)

             printf("%d ", chosen[i]);

         cout<<endl;

         return;

     }

     calc(x+);

     chosen.push_back(x);

     calc(x+);

     chosen.pop_back();

 }

 int main() {

     cin>>n;

     calc();

     return ;

 }

【例题】CH0302 递归实现组合型枚举

在前面的基础上加入以下代码即可：

if (chosen.size()>m||chosen.size()+(n-x+)<m)

    return;

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <vector>

 using namespace std;

 int n, m;

 vector<int> chosen;

 void calc(int x) {

     if (chosen.size()>m||chosen.size()+(n-x+)<m)

         return;

     if (x==n+) {

         for (int i=; i<chosen.size(); ++i)

             printf("%d ", chosen[i]);

         cout<<endl;

         return;

     }

     chosen.push_back(x);

     calc(x+);

     chosen.pop_back();

     calc(x+);

 }

 int main() {

     cin>>n>>m;

     calc();

     return ;

 }

【例题】CH0303 递归实现排列型枚举

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <vector>

 using namespace std;

 int n;

 int order[];

 int chosen[];

 void calc(int k) {

     if (k==n+) {

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

             printf("%d ", order[i]);

         puts("");

         return;

     }

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

         if (chosen[i]) continue;

         order[k]=i;

         chosen[i]=;

         calc(k+);

         order[k]=;

         chosen[i]=;

     }

 }

 int main() {

     cin>>n;

     calc();

     return ;

 }

【例题】费解的开关

容易发现3个性质：

1.每个位置最多点击一次

2.固定了第一行，满足题意的点击方案只有一种，如第i行已被固定，第i位为1，则第i+1行该位置需要被点击

3.点击先后顺序不影响最终结果

所以用位运算枚举第一行的点击方案，再递推出2~5行的点击，最后判断第5行是否满足题意即可。

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

int g[][];

char nex[][]={{,},{,-},{-,},{,},{,}};

void turn(int x, int y) {

    for (int i=; i<; ++i) {

        int tx=x+nex[i][];

        int ty=y+nex[i][];

        if (tx>&&tx<=&&ty>&&ty<=)

            g[tx][ty]^=;

    }

}

void print() {

    /*for (int i=1; i<=5; ++i) {

        for (int j=1; j<=5; ++j)

            printf("%1d", g[i][j]);

        printf("\n");

    }

    puts("");*/

}

int solve() {

    int ans=0x3f3f3f3f;

    for (int i=; i<; ++i) {

        int flag=, tot=;

        int tmp[][];

        memcpy(tmp, g, sizeof(tmp));

        for (int j=; j<; ++j)

            if ((i>>j)&)    //如果第j位为1，则第一排的第j位需要被按一下

                { turn(, j+); tot++; print();/*printf("a\n");*/}

        for (int j=; j<; ++j) {

            for (int k=; k<=; ++k)

                if (g[j][k]==)

                    { turn(j+, k); tot++; print();/*printf("b\n");*/}

        }

        for (int j=; j<=; ++j)

            if (g[][j]==) flag=;

        memcpy(g, tmp, sizeof(g));

        if (flag) ans=min(ans, tot);

        else continue;

    }

    if (ans>) return -;

    return ans;

}

int main() {

    //freopen("1.txt", "w", stdout);

    int T;

    scanf("%d", &T);

    while (T--) {

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

        for (int j=; j<=; ++j)

            scanf("%1d", &g[i][j]);

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

    }

    return ;

}

/*

1

11101

11101

11110

11111

11111

*/

巴特西

0x02 递推与递归

最新文章

热门文章