帶分數–第四屆藍橋杯省賽C++B/C組

• 2022 年 2 月 21 日
• 筆記
• C++, 演算法, 藍橋杯, 藍橋杯知識點練習

第四屆藍橋杯省賽C++B/C組—-帶分數

思路：

1.先枚舉全排列
2.枚舉位數
3.判斷是否滿足要求
這道題也就是n=a+b/c，求出符合要求的abc的方案數。進行優化時，可以對等式進行改寫，改寫成：b=cn-ca。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 30;
int target,ans = 0;
bool had_use[N],ever[N];

bool check(int a, int c)
{
    int b = c*target - c*a; //寫出式子，算出b
    if (!a || !b || !c) return false;
    memcpy(ever, had_use, sizeof had_use); //拷貝had_use數組給ever，這樣能不改變原來的數組
    while (b)
    {
        int t = b % 10;
        if (!t || ever[t]) return false;
        ever[t] = true;
        b /= 10;
    }
    for (int i = 1; i <= 9; i++)//判斷1-9每個數字有沒有都被用到
        if (!ever[i])   return false;
    return true;
}

void dfs_c(int x, int a, int c)//x表示用了多少個數字，a表示枚舉的a的大小，c表示c的大小
{
    if (x >= 10)    return;//如果1-9全部都已經被枚舉了，則退出
    if (check(a,c)) ans++; //檢驗a和c是否滿足要求，滿足則方案書+1
    for (int i = 1; i <= 9; i++)
    {
        if (!had_use[i])
        {
            had_use[i] = true;
            dfs_c(x+1, a, c*10+i);
            had_use[i] = false;
        }
    }
}

void dfs_a(int u, int a)//u表示枚舉到第幾個位置，也就是用了多少個數字，t表示當前的a是多少
{
    if (a >= target) return;
    if (a) dfs_c(u, a, 0); //如果a滿足要求，則對c進行枚舉
    
    for (int i = 1; i <= 9; i++)
    {
        if (!had_use[i])
        {
            had_use[i] = true;
            dfs_a(u+1, a * 10 + i);//將i加在a的各位
            had_use[i] = false; //回溯，恢復現場
        }
    }
    
}
int main()
{
    scanf("%d", &target);
    dfs_a(0,0); //先枚舉a
    printf("%d", ans);
    return 0;
}