7.31日阿里笔试题目分享

第一题

小强是一个农场主，农场里有n头牛，每头牛有着独一无二的体重，每一头牛的颜色可能是 $m$ 种颜色其中的一种，小强带了一些牛（可能为 $0$ 个）出来吃草。你需要回答出小强带出来的牛的组合一共有多少种可能？

注意：因为一头牛有自己的体重（没有两头牛体重相等），所以如果四头牛的体重分别是 $1,2,3,4$ ，颜色分别是 $y_1, y_2, y_3, y_4$ 和另一种方案：四头牛的体重分别是 $1, 2, 3, 4$ ,颜色分别是 $y_1, y_2, y_3, y_4$ ,即使两个方案的颜色的种类对应的数量是相同的，但是因为颜色对应的体重不同，所以是两个不同的方案。
由于方案书可能很大，请对 $1e9+7$ 取模。
输入描述：
两个整数 $n, m(1 \le n,m \le 10^9)$
输入： $3, 2$
输出： $27$

这道题一开始还挺懵逼的，我怀疑出题人语文没学好，其实你可以把每头牛理解成一个位置，一个位置有m种可选的颜色。

简单模拟样例后可以得到

$ans = \sum_{i=0}^{n}C_n^i2^i$

这里的i可以被理解为，小强打算带出来的牛的个数，每一头带出来的牛颜色有 $2^i$ 种可能，带 $i$ 头牛有 $C_n^i$ 种方案
用二项式定理收拾一下得到 $ans = \sum_{i=0}^{n}C_n^i2^i = (m+1)^{n}$
这样的数据规模，应该用矩阵快速幂可以很快解决。

当然也有直观理解的方法，因为每头牛可以有"不带出来吃草，颜色1，颜色2，颜色3,...,颜色m"这么多不同的选择，直接得到，

$ans = (m+1)^{n}$

#include <bits/stdc++.h>
using namespace std;

const int debug = 1;
const int size  = 5000 + 10; 
const int INF = INT_MAX>>1;
typedef long long ll;

ll quickpow_mod(ll a, ll b, ll m) {
  a %= m;
  ll res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return res;
}
int main(){
    // std::ios::sync_with_stdio(false);cin.tie(0);
    ll n, m;
    cin >> n >> m;
    ll mod = 1e9+7;
    cout << quickpow_mod(m+1, n, mod) << endl;
    return 0;
}

第二题

小强最近在研究某个飘洋过海的游戏。

游戏可以看成一个 $n*m$ 的方格图，从左上角 $(1, 1)$ 到右下角的 $(n, m)$ 有两种地面， $C$ 表示为陆地 $S$ 表示海洋，每次穿行只能到达上下左右四个格子之一，不能走到方格图之外。

在陆地之间穿行一格需要花费三点行动力，在海洋之间穿行一格需要花费2点行动力。
但是从陆地和从海洋到陆地穿行则需要5点行动力。

输入描述：
第一行输入两个整数 $n, m, q$ ,表示方格图的大小和询问次数。
随后 $n$ 行，每行 $m$ 个元素每个元素为'C'或'S',详见样例。

随后q行每行四个数字 $bx, by, ex, ey$ ，分别代表起点的坐标和终点的坐标。

输入：
4 4 2
CCCS
SSSS
CSCS
SSCC
1 1 3 4
3 1 1 3

输出
13
14

可以看到这道题是很简单的最短路问题，因为q的数量不大，所以问一次算一次最短路就可以了，可以直接采用dijkstra算法，代码如下，

# include <climits>
# include <iostream>
# include <iomanip>
# include <vector>
# include <queue>
using namespace std;


const int INF = INT_MAX>>1;
typedef pair<int, int> coord;
typedef pair<int, coord> node;


char g[505][505];
int dist[505][505];

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1,0, 0};

int Dist(int x1, int y1, int x2, int y2){
    if (g[x1][y1] != g[x2][y2])
        return 5;
    if (g[x1][y1] == 'C')
        return 3;
    return 2;
}

int n, m, q;

bool inrange(int x, int y){
    return (1 <= x && x <= n) && (1 <= y && y <= m);
}

int main(){
    cin >> n >> m >> q;
    memset(g, 0, sizeof(g));
    for (int i = 1; i <= n; i++){
        cin >> (g[i]+1);
    }
    while (q--){
        int sx, sy, ex, ey;
        cin >> sx >> sy >> ex >> ey;
        priority_queue<node, vector<node>, greater<node> > pri_que;
        for (int i = 1; i<= n; i++){
            for (int j = 1; j <= m; j++){
                dist[i][j] = INF;
            }
        }
        dist[sx][sy] = 0;
        pri_que.push(node(dist[sx][sy], coord(sx, sy)));
        while (!pri_que.empty()){
            node T = pri_que.top(); pri_que.pop();
            int d = T.first;
            int x = T.second.first;
            int y = T.second.second;
            for (int i = 0; i < 4; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (inrange(nx, ny) && dist[nx][ny] > d +  Dist(x, y, nx, ny)){
                    dist[nx][ny] = d +  Dist(x, y, nx, ny);
                    pri_que.push(node(dist[nx][ny], coord(nx, ny)));
                }
            }
        }
        cout << dist[ex][ey] <<endl;
    }
    return 0;
}

或者说，也可以考虑使用SPFA, SPFA是bellman-fold算法的一个优化版本，最坏情况效率和bellman-fold相同，优点是好些，同时一般的面试不会卡这个算法。

#include <bits/stdc++.h>
using namespace std;

const int INF = INT_MAX>>1;
typedef pair<int, int> coord;

char g[505][505];
int dist[505][505];
int inque[505][505];


int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1,0, 0};


int edge(int x1, int y1, int x2, int y2){
    if (g[x1][y1] != g[x2][y2]) 
        return 5;
    if (g[x1][y1] == 'C')
        return 3;
    return 2;
}


int n, m, q; 


bool inrange(int x, int y){
    return (1 <= x && x <= n) && (1 <= y && y <= m);     

}


int main(){
    cin >> n >> m >> q;
    memset(g, 0, sizeof(g));
    for (int i = 1; i <= n; i++){
        cin >> (g[i]+1);
    }
    while (q--){
        int sx, sy, ex, ey;
        cin >> sx >> sy >> ex >> ey;
        for (int i = 1; i<= n; i++){
            for (int j = 1; j <= m; j++){
                dist[i][j] = INF;
            }
        }
        queue<coord> que;
        dist[sx][sy] = 0;
        que.push(coord(sx, sy));
        inque[sx][sy]= 0;
        while (!que.empty()){
            coord T = que.front(); que.pop();
            int x = T.first;
            int y = T.second;
            inque[x][y] = 0;


            for (int i = 0; i < 4; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];


                if (inrange(nx, ny) && dist[nx][ny] > dist[x][y] +edge(x, y, nx, ny)){
                    dist[nx][ny] = dist[x][y] + edge(x, y, nx, ny);
                    if (!inque[nx][ny]){
                        inque[nx][ny] = 1;
                        que.push(coord(nx, ny));
                    }
                }
            }
        }
        cout << dist[ex][ey] <<endl;
    }
    return 0;
}

图片说明