就这？搞了半天还没通过，猿辅导算法笔试题

第一题

时间限制：C/C++ 5秒，其他语言10秒

空间限制：C/C++ 32M，其他语言64M

用全部N(N<=10)个0-9的数字组成一个"有效"整数（即没有前置0的整数），求这些组成的数中能被K(0<K<10^10)整除的最小数字。

输入描述:

输入分两行，第一行输入N, K，第二行输入N个数字。

输出描述:

输出满足条件的最小的数（不含前置0），如果没有满足条件的数输出 -1。

输入例子1:

4 74 0 1 3

输出例子1:

1043

例子说明1:

413 % 7 = 0， 但是有前置0，所以满足条件的最小数是 1043 % 7 = 0。

输入例子2:

1 1420

输出例子2:

0

解法

乍一看这道题很复杂，要把若干数排列到一起，然后还必须是K的倍数，并且要找到最小的这样的组合。

但仔细分析一下会发现全部的难点都集中在找排列上，只要我们能找到全部的组合，哪怕是一个一个枚举也一定可以找到答案。所以剩下的问题就是怎么找到全排列呢？

关于全排列的问题，在LeetCode当中非常常见，前两百题就有好几道，既有递归的算法也有非递归的方法，大家感兴趣可以自行去调研一下。我们之所以不用关心全排列的问题，是因为在C++的STL库当中已经为我们提供了现成的库函数，可以自动生成下一个排列，我们只需要直接调用即可。

在STL中这个函数叫做next_permutation，存放的位置是algorithm这个包，我们只需要在开头将它include进来就可以使用了。

由于这题当中需要找到最小的排列，所以我们可以先将题目给我们的元素进行排序，之后从最小的排列开始枚举，直到找到答案。每次调用next_permutation这个函数，它会返回一个bool值，表示是否还有下一个排列，当返回false的时候表示已经生成了最大的排列。我们可以用一个do while循环来实现，具体细节可以查看代码。

这题有一个小trick，就是K的范围，题目给的范围是，这个范围已经超过了int的界限，所以要用long long。

代码

#include <iostream>#include <cstdio>#include <cstring>#include <queue>#include <vector>#include <cmath>#include <cstdlib>#include <string>#include <map>#include <set>#include <algorithm>#include "time.h"#include <functional>#define rep(i,a,b) for (int i=a;i<b;i++)#define Rep(i,a,b) for (int i=a;i>b;i--)#define foreach(e,x) for (__typeof(x.begin()) e=x.begin();e!=x.end();e++)#define mid ((l+r)>>1)#define lson (k<<1)#define rson (k<<1|1)#define MEM(a,x) memset(a,x,sizeof a)#define L ch[r][0]#define R ch[r][1]#define pii pair<int, int>#define LL long long using namespace std;const int N=500005;const long long Mod=99997867;int main() {    LL n, k;    cin >> n >> k;    vector<int> v(n);    rep(i, 0, n) {        cin >> v[i];    }    // 排列，从最小排列开始    sort(v.begin(), v.end());    LL res = -1;    do {        // 跳过首位为0的情况        if (v[0] == 0 && n != 1) continue;        LL ret = 0;        // 将排列转化成数        rep(i, 0, n) {            ret = ret * 10 + v[i];        }        // 当整除的时候跳出循环        if (ret % k == 0) {            res = ret;            break;        }    }while (next_permutation(v.begin(), v.end()));    printf("%lld
", res);    return 0;}

第二题

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 256M，其他语言512M

小猿在加载一个网页，这个网页共需要N个相关资源，这些资源之间有一些依赖关系。如果这些资源中存在循环依赖，我们认为这个网页不能加载成功，否则可以加载成功。存在循环依赖是指，这些资源中存在资源X，X依赖的资源Y直接或间接依赖于X。

你能帮助小猿判断一下这个网页能否加载成功吗？

输入描述:

第一行输入T（T ≤ 10），表示输入T组数据。每组数据第1行，输入一个数N（1 ≤ N ≤ 500）表示该组case有编号为1~N的N项资源。每组数据第2到 N+1 行，输入一个 N*N 的零一矩阵。矩阵第 i 行第 j 列数字为 a[i][j] 表示编号为 i 的资源是否依赖于编号为 j 的资源，1表示依赖，0表示不依赖。数据保证a[i][i] = 0。

输出描述:

输出包含T行，每行输出对应每组case中是否存在循环依赖。存在输出1，不存在输出0。

输入例子1:

230 1 00 0 11 0 030 1 00 0 00 0 0

输出例子1:

10

例子说明1:

第一组数据：1依赖于2，2依赖于3，3依赖于1，存在循环依赖。第二组数据：只有1依赖于2，不存在循环依赖。

解法

寻找循环依赖的问题，很容易可以想到将依赖看成边来建图，这样循环依赖其实就转化成了有环图，所以这题本质上是一个判断是否有环的问题。判断有环的方式非常简单，我们只需要判断是否存在一个点它存在一条路径可以返回它本身，如果存在，那么就说明有环。

这里的难点在于很多人想不到要将它转化成图来做，也不知道如何存储一张图。不过好在这题的范围不大，只有500，我们用二维数组也存储得下。

当转化成图之后就是一个简单的递归，没有什么难度，不展开细讲了，具体细节可以查看代码。

代码

#include <iostream>#include <cstdio>#include <cstring>#include <queue>#include <vector>#include <cmath>#include <cstdlib>#include <string>#include <map>#include <set>#include <algorithm>#include "time.h"#include <functional>#define rep(i,a,b) for (int i=a;i<b;i++)#define Rep(i,a,b) for (int i=a;i>b;i--)#define foreach(e,x) for (__typeof(x.begin()) e=x.begin();e!=x.end();e++)#define mid ((l+r)>>1)#define lson (k<<1)#define rson (k<<1|1)#define MEM(a,x) memset(a,x,sizeof a)#define L ch[r][0]#define R ch[r][1]#define pii pair<int, int>#define LL long long using namespace std;const int N=500005;const long long Mod=99997867;int n, t;int mp[505][505];bool dfs(int target, int cur) {    bool flag = false;    if (mp[cur][target]) return true;    rep(i, 0, n) {        if (mp[cur][i] == 0) continue;        flag |= dfs(target, i);        if (flag) return 1;    }    return 0;}int main() {    scanf("%d", &t);    rep(z, 0, t) {        scanf("%d", &n);        MEM(mp, 0);        rep(i, 0, n) {            rep(j, 0, n) {                scanf("%d", &mp[i][j]);            }        }        bool flag = true;        rep(i, 0, n) if (dfs(i, i)) {            puts("1");            flag = false;            break;        }        if (flag) puts("0");        }        return 0;}

这题还有一个坑点在于我的代码提交之后会报内存超界的错误，但实际上我只存储25w个int，不至于内存超界，我检查了很久做了很多尝试也没有发现问题所在，非常恼火。如果有同学知道内存超界的原因，还请后台给我留言。

End.

爱数据网专栏作者：承志

作者介绍：前阿里人，推荐算法专家，一年更新400篇博文的勤奋作者

个人微信公众号：TechFlow（ID：techflow2019）

本文为爱数据网站专栏作者原创文章，未经允许禁止转载，需要转载请微信联系授权（微信号：lovedata0520）

更多文章前往首页浏览http://www.itongji.cn/