uva 10624 - Super Number

简介: 点击打开链接 题目意思:  给定n和m 现在要求找到一个m位数的树使得,对于m的前i位数都是i的倍数,n m时候说明已经找到了,并且我们已经从0开始搜索,那么得到的答案就是最小值,这时候可以直接输出                       4  注意事项:由于刚开始,我认为前i-1个位数是不用要求被当前的位数整除,并且认为第一个数就是1,然后就开了一段WA历程,后来找到了数据才发现尼玛坑爹啊哥哥我错了。

点击打开链接


题目意思:  给定n和m 现在要求找到一个m位数的树使得,对于m的前i位数都是i的倍数,n <= i <= m, 而且这个数的第一位数不能为0,如果找到就输出这个数,否则输出-1


解题思路:    1  目前只懂得用深搜回溯做,只是这一题的数据没有想象中的那么大,所以加上一些剪枝即可水过(数据强的话肯定TLE)
                      2  我们知道这个解空间树有m层,每一层的可能取值有10种(第一个除外),那么最大的m = 29 ,那么时间复杂都就是 10^29次方,这么大的时间你敢用吗。由于这一 题的数据比较水,那么可以过。但是由于最大的数值超过了int,我们必须用数组模拟。
                      3  思路: 从第一层开始搜索,注意第一层不能为0,我们用k(这里第一层k = 1)表示当前的层数。对于k < n时候我们不用考虑能否被k整除直接往下搜素,当k >= n 时候我们就要考虑当前的这个大数能否被k整除,如果可以就往下继续搜索,最后如果当k > m时候说明已经找到了,并且我们已经从0开始搜索,那么得到的答案就是最小值,这时候可以直接输出
                      4  注意事项:由于刚开始,我认为前i-1个位数是不用要求被当前的位数整除,并且认为第一个数就是1,然后就开了一段WA历程,后来找到了数据才发现尼玛坑爹啊哥哥我错了。第一位值不一定为1,所以我们必须从第一层开始向下搜索至m层,所以看到这个m这么大,你敢这么做吗


代码:

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
using namespace std;

int t , n , m , flag;
int ans[50];

//判断当前数值能否被整除
int judge_divisible(int *tmp , int k){
    int d = 0;//d是于数
    for(int i = 1 ; i <= k ; i++){//从小到大来模拟除法运算
        d = d*10+tmp[i];
        d %= k;
    }
    return d;//直接返回说明有没有于数存在
}

//深搜(就去枚举每一个位数的情况)
void dfs(int Tans[] , int k){
    if(k > m) { 
        memcpy(ans , Tans , sizeof(ans));
        flag = 1 ; return;
    }//如果当前的位数超过了m说明找到了这个标记flag为1
    for(int i = 0 ; i <= 9 ; i++){//枚举10个可能的值     
        Tans[k] = i;//令这个位数的数值为i,就去判断能否符合
        if(Tans[1] != 0){
           if(k < n || k >= n && !judge_divisible(Tans , k)) 
              dfs(Tans , k+1);//继续深搜
           if(flag) return;//找到了就直接返回不再去搜索就是剪枝
        }
    }
}

//主函数
int main(){
    //freopen("input.txt" , "r" , stdin);
    int i , j;
    scanf("%d" , &t);
    for(i = 1 ; i <= t ; i++){
        scanf("%d%d" , &n , &m); 
        memset(ans , 0 , sizeof(ans));
        flag = 0 ; dfs(ans , 1);
        printf("Case %d: " , i);
        if(flag){//如果当前有最小值输出这个值
            for(j = 1 ; j <= m ; j++) printf("%d" , ans[j]);
        }//没有的话输出-1
        else printf("-1");
        printf("\n");
    }   
    return 0;
}


目录
相关文章
|
11月前
|
算法
Leetcode 313. Super Ugly Number
题目翻译成中文是『超级丑数』,啥叫丑数?丑数就是素因子只有2,3,5的数,7 14 21不是丑数,因为他们都有7这个素数。 这里的超级丑数只是对丑数的一个扩展,超级丑数的素因子不再仅限于2 3 5,而是由题目给定一个素数数组。与朴素丑数算法相比,只是将素因子变了而已,解法还是和朴素丑数一致的。
92 1
|
存储
LeetCode 313. Super Ugly Number
编写一段程序来查找第 n 个超级丑数。 超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。
91 0
LeetCode 313. Super Ugly Number
uva 10706 - Number Sequence
点击打开链接uva 10706 题目意思:    有一个数组 s[1] = 1 , s[2] = 1 2 , .......s[k] = 1....k,要求给定一个n表示数组的第几位,要求这个第几位是什么数。
947 1
|
机器学习/深度学习
uva 10591 - Happy Number
点击打开链接 题目意思:  给定一个数n,然后进行操作,先求出这个数每一位的平方和,然后这个和替代n继续做这个操作,知道当前的n为1 或 n之前以经出现过 ,如果n等于则是happy number ,反之不是。
874 0
|
4月前
|
存储 SQL 算法
LeetCode 题目 65:有效数字(Valid Number)【python】
LeetCode 题目 65:有效数字(Valid Number)【python】
|
5月前
|
存储 算法
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
40 0