每日一题<AcWing 1209. 带分数>

简介: 每日打卡

image.png

本题来自于第四届蓝桥杯省赛C++B/C组,对于刚开始学习算法的人来讲可能相对较难,题目要求将一个分数分解成三个部分,一个整数一个分子一个分母,这里分别用a b c 来分别表示。同时要求1~9的所有数字都必须出现,且不能出现0。这里至少我们可以将数字的使用个数固定,不妨通过枚举的方式,对a c进行枚举(b的数字较c大所以枚举c的效率更高)。之后用剩下的位数将b反推出来,最后用数学方法判断当前的方案是否可行,若可行便可以记录在结果之中,全部枚举一遍之后就可以得出最后的答案。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 10;
bool sta[N], backup[N];
int n, ans;
bool check(int a, int c)   //判断方案的可行性
{
    long long b = n * (long long)c - a * c;
    if (!a || !c || !b) return false;
    memcpy(backup, sta, sizeof(sta));
    while (b)
    {
        int z = b % 10;
        if (!z || backup[z]) return false;
        backup[z] = true;
        b /= 10;
    }
    for (int j = 1; j <= 9; j++)
    {
        if (!backup[j])
        {
            return false;
        }
    }
    return true;
}
void dfs_c(int u, int a, int c)  //枚举c
{
    if (u > 9) return;
    if (check(a, c))
    {
        ans++;
    }
    for (int i = 1; i <= 9; i++)
    {
        if (!sta[i])
        {
            sta[i] = true;
            dfs_c(u + 1, a, c * 10 + i);
            sta[i] = false;
        }
    }
}
void dfs_a(int u, int a)  //枚举a
{
    if (a >= n) return;
    if (a) dfs_c(u, a, 0);
    for (int i = 1; i <= 9; i++)
    {
        if (!sta[i])
        {
            sta[i] = true;
            dfs_a(u + 1, a * 10 + i);
            sta[i] = false;
        }
    }
}
int main()
{
    scanf("%d", &n);
    dfs_a(0, 0);
    cout << ans << endl;
    return 0;
}

image.gif


目录
相关文章
AcWing 1265. 数星星(每日一题)
AcWing 1265. 数星星(每日一题)
AcWing 562. 壁画(每日一题)
AcWing 562. 壁画(每日一题)
|
存储 人工智能 测试技术
【AcWing每日一题】4644. 求和
【AcWing每日一题】4644. 求和
72 0
【每日一题】4.LeetCode——杨辉三角
【每日一题】4.LeetCode——杨辉三角
|
存储 算法 测试技术
【AcWing每日一题】4653. 数位排序
【AcWing每日一题】4653. 数位排序
116 0
|
人工智能 算法 测试技术
【AcWing每日一题】4655. 重新排序
【AcWing每日一题】4655. 重新排序
58 0
|
机器学习/深度学习
《蓝桥杯每日一题》背包dp·AcWing3382. 整数拆分
《蓝桥杯每日一题》背包dp·AcWing3382. 整数拆分
71 0
|
存储
每日一题——螺旋矩阵
每日一题——螺旋矩阵
蓝桥杯:带分数
蓝桥杯:带分数
74 0
|
算法
【AcWing&&牛客】打表找规律
【AcWing&&牛客】打表找规律
86 0