2020.4.3 阿里巴巴 笔试题
第一题：
小强和小明是很好的朋友，有一天小强在刷题的时候遇到一一个他从来没遇到过的问题，问题是这样描述的:
给你一个长度n数组a,问数组中有多少有价值的数?规定若ax为有价值的数，当且仅当:
x左侧存在大于ax的数，右侧存在小于ax的数，论左侧最小的大于ax的数为f，右侧小于ax的最大的数记为g: f为g的倍数。
输入描述:
输入包含两行，第1行仅一个整数n,表示数组的长度接下来一行有n个整数,表示数组a
保证全部数据: 1≤n≤10^5,1≤ai≤10^18
输出描述:
输出仅一行，表示数组中有价值的数的个数。
给你一个长度n数组a,问数组中有多少有价值的数?规定若ax为有价值的数，当且仅当:
x左侧存在大于ax的数，右侧存在小于ax的数，论左侧最小的大于ax的数为f，右侧小于ax的最大的数记为g: f为g的倍数。
输入描述:
输入包含两行，第1行仅一个整数n,表示数组的长度接下来一行有n个整数,表示数组a
保证全部数据: 1≤n≤10^5,1≤ai≤10^18
输出描述:
输出仅一行，表示数组中有价值的数的个数。
测试用例：
3
4 3 2
输出1
第二题：
小强有一天想去郊区玩，但是路上会经过一片山路。山路可以看作是一个n * m (n行m列)的网格，每个网格代表一个区域。山路崎岖不平，每一个区域都有一个会消耗的体力值。小强在走山路的时候，只能从一个区域走到相邻的4个(上下左右的网格)区域中的任意一个。每到一个区域，会消耗对应的体力值。小强初始位置在第1行上方，需要去到第n行下方(可以在第1行任意区域作为起点，第n行任意区域作为终点)
小强想找种走法，使得经过山路的总体力值消耗最小。请你帮小强找到这么一条路，并输出最小的总体力值消耗。
输入描述:
第一行包含两个数字n，m,分别代表山路的行数和列数。
接下来有几行，每行m个数字。第i行j列的数字吃，代表对应位置的区域的体力值。
其中1≤n,m ≤ 1000,0< Vi,j≤1000
测试用例：
小强想找种走法，使得经过山路的总体力值消耗最小。请你帮小强找到这么一条路，并输出最小的总体力值消耗。
输入描述:
第一行包含两个数字n，m,分别代表山路的行数和列数。
接下来有几行，每行m个数字。第i行j列的数字吃，代表对应位置的区域的体力值。
其中1≤n,m ≤ 1000,0< Vi,j≤1000
测试用例：
3 3
3 1 3
3 1 0
3 1 3
输出3
3 4
9 9 1 1
9 1 1 9
1 1 9 9
输出4
9 9 1 1
9 1 1 9
1 1 9 9
输出4
第二题的代码，超时了，ac60%
#include "bits/stdc++.h"
using namespace std;
int dx[4] = {1, 0, 0, -1};
int dy[4] = {0, 1, -1, 0};
int main() {
int n, m , t;
cin >> n >> m;
int a[n][m];
long long dp[n][m];
long long res = INT_MAX;
queue<pair<int, int>> q;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> t;
a[i][j] = t;
if (i == 0) {
q.emplace(i, j);
}
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (i == 0) {
dp[i][j] = a[i][j];
} else
dp[i][j] = INT_MAX;
}
}
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
if (x == 0) {
int tx = x + dx[0];
int ty = y + dy[0];
if (tx >= 0 && tx < n && ty >= 0 && ty < m && (dp[tx][ty] > dp[x][y] + a[tx][ty])) {
dp[tx][ty] = dp[x][y] + a[tx][ty];
q.emplace(tx, ty);
}
} else if (x == n - 1) {
} else {
for (int i = 0; i < 4; ++i) {
int tx = x + dx[i];
int ty = y + dy[i];
if (tx >= 0 && tx < n && ty >= 0 && ty < m && (dp[tx][ty] > dp[x][y] + a[tx][ty])) {
dp[tx][ty] = dp[x][y] + a[tx][ty];
q.emplace(tx, ty);
}
}
}
}
for (int j = 0; j < m; ++j) {
res = min(dp[n-1][j], res);
}
cout << res << endl;
return 0;
} 