全排列问题

方法

全排列+检查 递归+回溯（剪枝）

模板

// 转换为一维问题
#include <iostream>
int a[n];
int ans=0;
bool check(){}
void f(int k)
{
    if (k==n)
    {
        if (check())
        {
            ans++;
            return;
        }    
    }

    for (int i=0;i<n;i++)
    {
        {int t=a[i];a[i]=a[k];a[k]=t;}
        f(k+1); // 递归
        {int t=a[i];a[i]=a[k];a[k]=t;} // 回溯
    }
}

int main()
{
    f(0);
     std::cout<<ans<<std::endl;
    return 0;
}

// 二维情况
#include <iostream>

bool check(int i, int j){}
bool vis[n];
int a[xx][yy];

void f(int x, int y)
{
    if (x== && y== ) // 到达边界
    {
        ans++;
        return;
    }
    for (int i=0;i<n;i++)
    {
        if (vis[i]==false)
        {
            a[x][y]=i;
            if (check(x,y)==false) // 剪枝
            {
                a[x][y]=init_num; // 恢复
                return;
            }
            vis[i]=true;
            f(x+1,y+1); // 递归
            vis[i]=false; // 回溯
            a[x][y]=init_num; // 回溯
        }
    }
}

// 使用 next_permutation() 生成全排列
#include <iostream>
#include <algorithm>

bool check(int per[]){}

int main()
{
    int per[]={0,0,0,0,0,0,0,1,1,1,1,1};
    do {
        if (check(per))
            ans++;
    } while(next_permutation(per,per+12));
    std::cout << ans << std::endl;
    return 0;
}

例题

2016-省赛-CA-3

方格填数

如下的10个格子
+–+–+–+
| | | |
+–+–+–+–+
| | | | |
+–+–+–+–+
| | | |
+–+–+–+

填入0~9的数字。要求：连续的两个数字不能相邻。
（左右、上下、对角都算相邻）

一共有多少种可能的填数方案？

#include <iostream>

using namespace std;

int a[10]={0,1,2,3,4,5,6,7,8,9};
int ans=0;

bool check(){
         if(abs(a[0]-a[1])==1||
            abs(a[0]-a[3])==1||
            abs(a[0]-a[4])==1||
            abs(a[0]-a[5])==1||

            abs(a[1]-a[2])==1||
            abs(a[1]-a[4])==1||
            abs(a[1]-a[5])==1||
            abs(a[1]-a[6])==1||

            abs(a[2]-a[5])==1||
            abs(a[2]-a[6])==1||

            abs(a[3]-a[4])==1||
            abs(a[3]-a[7])==1||
            abs(a[3]-a[8])==1||

            abs(a[4]-a[5])==1||
            abs(a[4]-a[7])==1||
            abs(a[4]-a[8])==1||
            abs(a[4]-a[9])==1||

            abs(a[5]-a[6])==1||
            abs(a[5]-a[8])==1||
            abs(a[5]-a[9])==1||

            abs(a[6]-a[9])==1||

            abs(a[7]-a[8])==1||

            abs(a[8]-a[9])==1)
             return false;
    return true;
}

void f(int k)
{
    if (k==10)
    {
        if (check())
            ans++;
        return;
    }

    for (int i=k;i<10;i++)
    {
        {int t=a[i];a[i]=a[k];a[k]=t;}
        f(k+1);
        {int t=a[i];a[i]=a[k];a[k]=t;}
    }
}

int main()
{
    f(0);
    cout<<ans<<endl;
return 0;
} 

#include <iostream>

using namespace std;

int a[5][6];
bool vis[10];
int ans = 0;

bool check(int i, int j)
{
    for (int x = i - 1; x <= i + 1; x++)
        for (int y = j - 1; y <= j + 1; y++)
        {
            if (abs(a[x][y] - a[i][j]) == 1)
                return false;
        }
    return true;
}

void f(int x, int y)
{
    if (x == 3 && y == 4)
    {
        ans++;
        return;
    }

    for (int i = 0; i < 10; i++)
    {
        if (vis[i] == false)
        {
            a[x][y] = i;
            if (!check(x, y)) // 剪枝
            {
                a[x][y] = -10;
                continue;
            }
            vis[i] = true;
            if (y == 4)
                f(x + 1, 1);
            else
                f(x, y + 1);
            vis[i] = false;
            a[x][y] = -10;
        }
    }
}

void init()
{
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 6; j++)
            a[i][j] = -10;
}

int main()
{
    init();
    f(1, 2);
    cout << ans << endl;
    return 0;
}

2016-省赛-CA-6

寒假作业

现在小学的数学题目也不是那么好玩的。
看看这个寒假作业：

□ + □ = □
□ - □ = □
□ × □ = □
□ ÷ □ = □

(如果显示不出来，可以参见【图1.jpg】)

每个方块代表1~13中的某一个数字，但不能重复。
比如：
6 + 7 = 13
9 - 8 = 1
3 * 4 = 12
10 / 2 = 5

以及：
7 + 6 = 13
9 - 8 = 1
3 * 4 = 12
10 / 2 = 5

就算两种解法。（加法，乘法交换律后算不同的方案）

你一共找到了多少种方案？

#include <iostream>

using namespace std;

int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
int ans = 0;

bool check()
{
    if (a[0] + a[1] == a[2] &&
        a[3] - a[4] == a[5] &&
        a[6] * a[7] == a[8] &&
        a[9] % a[10] == 0 &&
        a[9] / a[10] == a[11])
        return true;
    return false;
}

void f(int x)
{
    if (x == 13)
    {
        if (check())
        {
            ans++;
            return;
        }
    }

    for (int i = x; i < 13; i++)
    {
        {
            int t = a[i];
            a[i] = a[x];
            a[x] = t;
        }
        if ((x == 2 && a[0] + a[1] != a[2]) || (x == 5 && a[3] - a[4] != a[5]))
        {
            {
                int t = a[i];
                a[i] = a[x];
                a[x] = t;
            }
            continue;
        }
        f(x + 1);
        {
            int t = a[i];
            a[i] = a[x];
            a[x] = t;
        }
    }
}

int main()
{
    f(0);
    cout << ans << endl;
    return 0;
}