历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1209. 带分数（y总字幕版本，思路贼清晰）原题链接简单

作者：

Elegant , 2021-03-08 10:58:40 , 所有人可见 , 阅读 13363

341

145

全是 $y$ 总原话~~

内容有点长，大家耐心看~~

$1$、y总的核心思想是：我们如果用暴力解法的话，$n$ 是用不到的，只能用于最后的判断，所以这个时候我们考虑把两边同时乘上 $c$，把乘法转换为除法，然后等式就成了 $n$$\times$$c$=$c$$\times$$a$+$b$，那么我们就可以用上 $n$ 了，（当然了这个不是重点）。

$2$、而且我们通过观察这个式子，我们本来需要枚举 $a$ 和 $b$ 和 $c$ ，但是我们现在只需要枚举一下 $a$ 和 $c$ 就可以了，因为这样子的话 $b$ 可以通过 $b$=$c$$\times$$n$-$c$$\times$$a$ 直接把 $b$ 算出来，就不需要枚举 $b$ 了

$3$、这样子的话可以优化很多。当然了，光有这个思路还是远远不够的，这才只是一个思路，但是你想把这个转换成代码还是很有难度的，特别是对于我这种初学者来说，所以我们还需要分析一下如何写代码。

$4$、所以我们现在枚举的方式就变成了先枚举 $a$，然后对于每一个枚举的 $a$ 来说，我们再去枚举$c$，那么对于每一个枚举的 $c$ 来说，$a$ 和 $c$ 已经确定了，那么 $b$ 也就确定了，就可以进行一个 $check$ 的判断

$5$、虽然这里的话是做了一个很大的一个优化，但是代码写起来还是比较复杂的

$6$、我们先写一个 ${dfs}$${a}$ 函数，先 ${dfs}$ 一下 $a$

$7$、$a$ 其实是一个排列对吧，枚举一个排列，1,2,3,4…然后在${dfs}$$a$的内部，在每一个叶子节点的时候，每一个叶子节点的地方，（因为每一个叶子就代表每一个 $a$ 的可能成立的方案），那么在 $a$ 的每一个叶子节点的地方，我们都需要再枚举一下 $c$

$8$、也就是我们要把 $a$ 的每一个节点扩展成一个搜索树（即在 $a$的每一个叶节点的时候$dfs$一下 $c$），叶子上的每一棵树都是对 $c$ 的搜索，因此我们这里其实是$dfs$的一个嵌套关系，（即在一个$dfs$的过程中，把它的叶节点再$dfs$一下）所以我们需要在$dfs$搜索 $a$ 的时候在 $a$ 的叶节点的基础上搜索一下对应的 $c$ 是多少

$9$、那搜完 $c$ 之后的话我们再去判断一下 $b$ 就可以了，也就是在 $c$ 的每一个叶子节点上判断一下 $b$ 就可以了。所以整个树的话会比较复杂一些。

$10$、开一个判重数组，首先$dfs$一下 $a$ ，第一个参数表示我们当前已经用了多少个数字，第二个参数表示 $a$ 是多少，然后直接输出答案

$11$、然后写一下${dfs}$$a$ ，首先判断一下，如果 $a$$\geq$$n$ 了，那么就不满足条件了对吧，那就直接 return 了。如果 $a$ 是可行的，那么我们就$dfs$一下 $c$

$12$、对于${dfs}$$a$，然后我们来枚举一下当前这个位置能用哪几个数字，从 $1$ 到 $9$ 进行循环，如果说当前这个位置上的数没有被用过的话，那么我们就用它，并做上标记，然后我们再$dfs$到下一层，同时更新一下 $a$ ，传到下一层的参数应该是第一个参数+$1$，然后$a$应该变成 $a$$\times$$10$+$i$。然后最后要记得恢复现场，因为这里存在一个回溯。

$13$、这个是${dfs}$$a$,那么我们现在实现一下 ${dfs}$$c$，${dfs}$$c$的话有三个参数，${dfs}$$c$的第一个参数和${dfs}$$a$的参数一样，表示我们当前已经用了多少个数，第二参数的话是 $a$ 的值，因为我们要利用 $a$ 的值，第三个参数代表当前 $c$ 的值。

$14$、如果说第一个参数已经等于 $n$ 了，那就说明我们用完 $n$ 个数字了对吧，那我们就可以直接 return 了。否则的话那我们就可以 $check$ 一下，如果说 $check$ 成功的话，那我们的答案就++。（$check$ 函数的话就是用来判断一下 $a$ 和 $c$ 是否满足要求，传的第一个参数为 $a$，第二个参数为 $b$）

$15$、否则的话我们就从 $1$ 到 $9$ 枚举一下 $c$，如果这个数没被用过的话，那我们就把它标记一下，并把它放在 $c$ 的后面，再$dfs$下一层，下一层的参数就是第一个参数+$1$，然后第二个参数不变，第三个参数就是 $c$$\times$$10$+$i$ ，然后我们还是要恢复现场。

$16$、然后最后再实现一下这个 $check$ 函数，函数的第一个参数就是 $a$ ，第二个参数就是 $c$

$17$、我们来判断一下 $a$ 和 $c$ 是不是满足要求的。那判断a和c是否满足要求我们需要先利用 $b$=$c$$\times$$n$-$c$$\times$$a$ 把计算出来对吧，然后我们再对b的每一位数字分析，第一点看一下它有没有和 $a$ 和 $c$ 有相同的数字冲突

$18$、第二点看一下 $a$，$b$，$c$ 是否已经把 $9$ 个数字全部用完了

$19$、那这里的话我们可以搞一个判重数组，我们先把原来的那个数组 $copy$ 过来，因为我们要对这个判重数字进行修改，但是我们原来的判重数组是需要保证其是原样的，因为它需要恢复现场（回溯），所以这就是我们多开一个判重数组的原因。

$20$、然后我们来取出 $b$ 的每一位进行判断。在判断的过程中，如果 $b$ 的某位是 $0$ 或者 $b$ 的某位已经出现过了，那就说明出错了，那就直接 return false

$21$、否则的话我们给它标记一下它已经用过了，然后我们最后再去遍历一下数组中从 $1$ 到 $9$的每个数字是否已经被用了（这里不需要判断是否存在多用的情况，因为不可能存在，因为我们每次都会标记，只有没被用过的数字才会被使用，如果已经被用过的数字将不会被使用）

$22$、如果判断过程中存在没有被用过的数字，那说明不满足条件，直接 return false

$23$、如果上述情况都满足，那就最后 return true

$24$、当然了这个里面的话我们可以提前判断一些边界，这个题目中 $a$ 和 $b$ 和 $c$ 都不能为 $0$ 对吧，所以我们可以在 $check$ 的一开始判断一下，$a$ 或 $b$ 或 $c$ 中是否存在 $0$，如果存在，直接 return false，这样就可以做到一个小小的优化以及边界的判定。

总的来说就是我们先枚举一下 $a$，然后对于每个 $a$ 枚举一下 $c$，然后对于每个 $a$ 和 $c$ 我们去判断一下
$a$ ，$b$，$c$ 是否满足条件就可以了

通过公式的转化，将枚举三个变量转换成枚举两个变量（因为第三个变量可以计算出来）
枚举 $a$
对于每个 $a$ ，枚举 $c$
对于每个枚举的 $a$ 和 $c$ 来说，我们来判断一下 $b$ 是否成立就可以了

另外

加一点供大家拓展的东西，就是洛谷上面有一道类似的题，和这题很像，做法是一样的，可以供大家巩固这个算法。

题目：三连击（升级版）

附上相同解法博客链接：三连击dfs解法

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>

using namespace std;

const int N=520;

int had_use[N],ever[N];

int ans=0;

int n;

bool check(int a,int c)
{
    int b = n * c - a * c;//把公式整理一下，然后先把b计算出来

    if(!a||!b||!c)return false;

    memcpy(ever,had_use,sizeof had_use);//因为我们要对这个判断是否出现的数组进行修改，但是原数组又不能变化，所以我们
    //额外开一个数组进行使用，这样就可以达到判断且不会改变原数组的目的
    while(b)
    {
        int t=b%10;//取它的每一位，用来更新一下用过的数字
        b/=10;//删掉这个已经被选中的数
        if(!t||ever[t])return false;
        ever[t]=1;
    }
    for(int i=1;i<=9;i++)//遍历一下，判断每个数
      if(!ever[i])
      return false;

   return true;
}

void dfs_c(int x,int a,int c)//x表示我们已经用了多少个数字
{
    if(x>=10)return;//如果我们把10个数字都用了的话，那就直接return了

    if(check(a,c))ans++;//如果满足要求，那我们判断一下a,c是否符合题目要求，如果符合，那么答案++

    for(int i=1;i<=9;i++)//否则的话我们把c从1到9全部枚举一遍
      if(!had_use[i])
      {
          had_use[i]=1;
          dfs_c(x+1,a,c*10+i);//如果这个数没用过，那么我们就把它放在c的后面,继续dfs下一层
          had_use[i]=0;
      }
}
void dfs_a(int x,int a)
{
    if(a>=n)return;
    if(a)dfs_c(x,a,0);//如果说a是满足情况的，那么我们就枚举一下c,后面那个0表示c的大小

    for(int i=1;i<=9;i++)//枚举一下当前这个位置可以用哪些数字
      if(!had_use[i])
      {
          had_use[i]=1;
          dfs_a(x+1,a*10+i); //如果这个数没有被用过，那么我们就加上它，并且dfs下一层
          had_use[i]=0;//恢复现场，回溯一下
      }
}
int main()
{
    scanf("%d",&n);
    dfs_a(0,0);//第一个0表示我们已经用了多少个数字,后面那个0表示我们当前的a是多少
    printf("%d",ans);
    return 0;
}

$2021$年$3$月$31$日更新

码字不易，点个赞再走呗~~

80 评论

Muaddib 2023-01-09 20:55

这个可惜只能赞一次，小白太需要了啊啊啊啊呜呜呜呜，感谢楼主。

命不该绝 2022-10-06 16:55

实在是不知道错在哪里了，求大佬帮帮😭

import java.io.*;
import java.util.*;

class Main{
    static int n, res;
    static boolean[] backup = new boolean[20];
    static boolean[] st = new boolean[20];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        dfs_a(0, 0);
        System.out.println(res);
    }

    static void dfs_a(int u, int a){
        if(a == n) return ;
        dfs_c(u, a, 0);

        for(int i = 1; i <= 9; i++)
            if(!st[i]){
                st[i] = true;
                dfs_a(u + 1, a * 10 + i);
                st[i] = false;
            }

    }

    static void dfs_c(int u, int a, int c){
        if(u == n) return ;
        if(check(a, c)) res++;

        for(int i = 1; i <= 9; i++)
            if(!st[i]){
                st[i] = true;
                dfs_c(u + 1, a, c * 10 + i);
                st[i] = false;
            }
    }


    static boolean check(int a, int c){
        int b = n * c - a * c;
        if(a == 0 || b == 0 || c == 0) return false;
        backup = Arrays.copyOf(st, st.length);

        while(b >= 0){
            int x = b % 10;
            b /= 10;
            if(x == 0 || backup[x]) return false;
            backup[x] = true;
        }

        for(int i = 1; i <= 9; i++)
            if(!backup[i]) return false;
        return true;
    }
}

墨离 2022-11-29 15:19

你有两处地方错了
1.dfs_c中的u==n应该改成u==10，除此不同于dfs_a,他判断的是当前1~9中有多少个数字已经被用了
2.check函数中if(a == 0 || b == 0 || c == 0) return false;应改成if(a <= 0 || b <=0 || c <= 0)return false;,这样才能把b为负的情况判断进去

何九三 2023-03-02 22:34

好奇怪啊，我也是用java写的，答案就是不对

霍去病. 2022-02-14 01:12

楼主你好，你把N改成15试一下，为什么N为15的时候，AC不了，我测试的如果N为20可以AC，你能告诉我一下是为什么吗

_俗人 2023-04-06 15:01

同问

亦姝 2021-03-29 15:12

我有个问题，这个代码用到的数字不就是这有0-9吗，我给判断数组开了15个，为什么过不了呢，把数组开到20它又可以了，这是为什么0.0.。。

辉小歌 2021-03-29 16:04

long long int b=n(long long )c-ac;把他的代码改成这样就OK了。
N=10也可以。
y神的解答
int b = n * c - a * c这一行中的c可能有8位数，那么和n乘起来以后就会溢出int，那么b就可能变成负数，从而它的个位数字的余数也可能是负数，那么backup[x]的下标就可能是负数，所以下标就越界了。

Elegant 2021-03-29 16:43

这个问题我也不太清楚呢，这边建议写算法题一般数组建议多开大一些，只要在空间限制内就可以，毕竟是算法题只要能过就行，所以为了安全期间就开大一些~~

xwx_9 9个月前

#include <iostream>
#include <cstring>
#include <algorithm>
#include <iostream>


using namespace std;

const int N = 10;
int n;
int st[N],backup[N];//st数组记录1~9数字使用状态 backup数组用于check函数保存st数组以便回溯
int ans;        //保存结果

bool check(int a,int c){//传入a,c 判断b 枚举b的每一位
    //c可能有8位数，那么n*c就会溢出 b可能变成负的 那么backup[x]的下标就可能就越界
    long long int b=n*(long long)c-a*c;

    if(!a||!b||!c)return false;

    memcpy(backup, st, sizeof st);
    while (b){      //取b每一位
        int x = b % 10;
        b =  b/ 10;
        if(!x||backup[x])return false;
        backup[x]=true;
    }

    for (int i = 1; i <= 9; i ++ ){//检查1~9是否都已经用了 
        if(!backup[i]){
            return false;
        }
    }
    return true;
}

void dfs_c(int u,int a,int c){
    if(u==10)return;

    if(check(a,c)){//如果满足要求 那我们判断一下a,c是否符合题目要求 如果符合 那么答案++
        ans++;
    }

    for (int i = 1; i<=9; i++ ){
        if(!st[i]){
            st[i]=true;
            dfs_c(u+1,a,c*10+i);
            st[i]=false; //回溯
        }
    }
}

void dfs_a(int u,int a){

    if(a>=n)return;

    if(a)dfs_c(u,a,0);//第一个参数表示已经用了的数字 第二个参数为当前a的值 第三个参数为当前c的值

    for (int i = 1; i <= 9; i ++ ){
        if(!st[i]){
            st[i]=true;
            dfs_a(u+1,a*10+i);
            st[i]=false; //回溯
        }
    }
}
int main()
{
    scanf("%d", &n);

    dfs_a(0,0);//第一个参数表示已经用了的数字 第二个参数为当前a的值

    printf("%d",ans);

    return 0;
}

命不该绝 2022-10-06 15:34

求大佬解析，为啥 N 开 10 就不得行，要多开一倍？

鹿米纳瑞 2022-10-13 15:08

同问

丿丶纯少 2022-12-14 19:46

同问

别催了马上交 2023-02-14 15:46

int溢出了。把check改成这样子就可以只开10了
bool check(int a, int c){
long long b = (n - a);
b *= c;
memcpy(backup, v, sizeof v);
while(b){
int t = b % 10;
if(!t || backup[t]) return false;
b /= 10;
backup[t] = true;
}
for(int i = 1; i <= 9; i ++){
if(!backup[i]) return false;
}
return true;
}

命不该绝 2023-02-14 15:54 回复了别催了马上交的评论

orz

柯基不等式_9 9个月前回复了别催了马上交的评论

想问一下，为什么数组开成20的时候就对了呢？是歪打正着嘛？

别催了马上交 9个月前回复了柯基不等式_9 的评论

不好意思，回复的可能有点迟了，这个地方是因为b这里溢出了int的范围导致成为了负数，此时的t由b%10得到的也是负数，如果数组开的大小为10，-5的话则会改变到1-9范围的数，但是如果开到了20，则-10以内改变不了1-9范围的数，因此两个选择，一个是改为longlong的取值范围，另一个是开大数组。

婶婶不是沈沈 2023-02-19 00:10

墨离 2022-11-29 15:22

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int n,ans;
    static boolean[] used = new boolean[10];
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        dfs_a(0,0);
        System.out.println(ans);
    }

    //进行第一次深搜,x表示用了多少数字，a表示当前的值
    static void dfs_a(int x,int a){
        //a值大于n,不符合题意，返回
        if(a >= n)return;
        if(a != 0)dfs_c(x,a,0);

        for (int i = 1; i <= 9; i++){
            if(!used[i]){
                used[i] = true;
                dfs_a(x+1,a * 10 + i);
                used[i] = false;
            }
        }
    }

    //x表示当前用过的数字数量，a是dfs_a所得到的数，c是dfs_c所得到的的数
    static void dfs_c(int x,int a,int c){
        if(x >= 10)return;

        //满足题目要求带分数的条件,ans加1
        if(check(a,c))ans++;
        for (int i = 1; i <= 9; i++) {
            if(!used[i]){
                used[i] = true;
                dfs_c(x+1,a,c*10 + i);
                used[i] = false;
            }
        }

    }
        //a是dfs_a所得的，c是dfs_c所得的
    static boolean check(int a, int c) {
        int b = c * n - c * a;
        if(a <= 0 || b <=0 || c <= 0)return false;
        boolean[] flag = new boolean[used.length];
        for(int i = 0; i < flag.length; i ++)flag[i] = used[i];
        //判断b是否有位数与a或c重合
        while(b!=0){
            int t = b % 10;
            b /= 10;
            if(t ==0 || flag[t])return false;
            flag[t] = true;
        }

        //判断得到的a,b,c三数是否能覆盖1~9的全部数字
        for (int i = 1; i <= 9; i++) {
            if(!flag[i])return false;
        }
        return true;
    }

}