猿辅导校招笔试真题（软开）求职宝典理工科版
1.12.1 小猿的依赖循环
【题目描述】
小猿在加载一个网页，这个网页共需要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。
输入样例：
2
3
0 1 0
0 0 1
1 0 0
3
0 1 0
0 0 0
0 0 0
输出样例：
1
0
说明：
第一组数据：1依赖于2，2依赖于3，3依赖于1，存在循环依赖。第二组数据：只有1依赖于2，不存在循环依赖。
【解题思路】
使用dfs优先遍历搜索来查看是否产生了循环。
注意事项：不能够直接dfs（0）,即所有的未走过的节点都要进行一次dfs，即图中的连通图的dfs遍历方式。即会有一种情况产生：a、b、c之间没有产生循环依赖，且a、b、c都没有依赖d和e，但是d和e却产生了依赖。但是如果只有一个dfs（0）就会产生错误，误以为这组数据没有产生循环依赖，事实却是产生了循环依赖，只是恰巧不在dfs（0）可以遍历到的范围之内罢了。
【参考代码】
#include<iostream>
using namespace std;
int n, t;
int p[505][505];
bool pd[505];
int ans = 0;
void init(int x) {
for (int i = 0; i < x; i++) {
for (int j = 0; j < x; j++) {
p[i][j] = 0;
}
pd[i] = false;
}
ans = 0;
}
void dfs(int x) {
if (pd[x] == true) {
ans = 1;
return;
}
pd[x] = true;
for (int i = 0; i < t; i++) {
if (p[x][i] == 1) {
dfs(i);
}
}
pd[x] = false;
}
int main() {
cin >> n;
while (n != 0) {
cin >> t;
init(t);
for (int i = 0; i < t; i++) {
for (int j = 0; j < t; j++) {
cin >> p[i][j];
}
}
//dfs(0);
//上面这行代码就是只从0这个点开始导致了错误。
//下面这部分for循环代码就是为了能够遍历所有的未走过的节点，由此得出的答案才是正确答案。
for (int i = 0; i < t; i++) {
if (pd[i] == false) {
dfs(i);
if (ans == 1) {
break;
}
}
}
cout << ans << endl;
n--;
}
return 0;
}
1.12.2 最小特殊的数字
【题目描述】
用全部N(N<=10)个0-9的数字组成一个“有效”整数（即没有前置0的整数），求这些组成的数中能被K(0<K<10^10)整除的最小数字。
输入描述：
输入分两行，第一行输入N, K，第二行输入N个数字。
输出描述：
输出满足条件的最小的数（不含前置0），如果没有满足条件的数输出 -1。
备注：
数字中不能使用前置0，例如四个数字0、1、2、3组成的满足条件的最小数不能是0123。
输入样例1：
4 7
4 0 1 3
输出样例1：
1043
说明：
413 % 7 = 0， 但是有前置0，所以满足条件的最小数是 1043 % 7 = 0。
输入样例2：
1 142
0
输出样例2：
0
【解题思路】
看到数据范围1~10，直接next_permutation枚举数组全排列，判断前导为0的情况，注意会爆longlong。
【参考代码】
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n;
ll k;
int a[100];
bool ck(ll x){
int cnt=0;
if(x==0) cnt=1;
while(x){
cnt++;
x/=10;
}
return cnt==n;//如果位数不一样说明有前导0不符合要求
}
int main(){
cin>>n>>k;
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n);
do{
ll res=0;
for(int i=0;i<n;i++) res=res*10+a[i];
if(ck(res)&&res%k==0){
cout<<res<<endl;return 0;
}
}while(next_permutation(a,a+n));
puts("-1");
return 0;
}
......
资料全部内容请看《2025届求职宝典-理工科版》
不收费，2人组团即可免费领取！已经发出10000份，涵盖各大公司求职资料，助你事半功倍！
资料包含：
- 30+大厂面试真题+解析
- 软件方向：阿里、腾讯、百度、小米、华为、美团......
- 硬件方向：华为、比亚迪、汇川、新华三、中兴、海康威视......
- 机械方向：比亚迪、华为、美的、长江存储、宁德时代......
- 30+大厂岗位薪资爆料
- 30+大厂offer攻略
拿offer，别犹豫，点击马上领取>>https://www.nowcoder.com/link/campus_ziliao2024-0604115
电脑端请微信扫码>>
多说无益，直接上资料截图
每个方向专栏售价69元，但是参与2人组团就可免费领取！
点击马上领取>>https://www.nowcoder.com/link/campus_ziliao2024-0604115
#校招笔试真题#
查看12道真题和解析