3.6阿里笔试

第一题

dp(i,j,k,l)表示第i列的数字排列情况是（j,k,l)的方案数，枚举下一列情况即可复杂度O(n*27*27)

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>
#define fir first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define ull unsigned long long
#define cl(a, b) memset(a, b, sizeof(a))
#define quickio(a) ios::sync_with_stdio(a)
#define datatest() freopen("data.in", "r", stdin)
#define makeans() freopen("data.out", "w", stdout)
#define makedata() freopen("data.in", "w", stdout)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
using namespace std;
const int maxn = 5e4 + 10;
const int maxm = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const int maxblock = sqrt(maxn) + 10;
const double eps = 1e-7;
const ll INF = 1e16;
int n;
int dp[maxn][30];
int checklegal(int pos1, int pos2, int pos3, int i, int j, int k) {
  if (i == pos1 || j == pos2 || k == pos3) return false;
  return true;
}
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
      for (int j = 0; j < 30; j++) {
        dp[i][j] = 0;
      }
    }
    for (int i = 1; i <= 3; i++) {
      for (int j = 1; j <= 3; j++) {
        if (i == j) continue;
        for (int k = 1; k <= 3; k++) {
          if (k == j) continue;
          dp[1][9 * (i - 1) + 3 * (j - 1) + (k - 1)] = 1;
        }
      }
    }
    for (int i = 2; i <= n; i++) {
      for (int pos1 = 1; pos1 <= 3; pos1++) {
        for (int pos2 = 1; pos2 <= 3; pos2++) {
          for (int pos3 = 1; pos3 <= 3; pos3++) {
            if (pos1 == pos2 || pos2 == pos3) continue;
            for (int i1 = 1; i1 <= 3; i1++) {
              for (int j1 = 1; j1 <= 3; j1++) {
                if (i1 == j1) continue;
                for (int k1 = 1; k1 <= 3; k1++) {
                  if (k1 == j1) continue;
                  // dp[1][9 * (i - 1) + 3 * (j - 1) + (k - 1)] = 1;
                  if (checklegal(pos1, pos2, pos3, i1, j1, k1)) {
                    int mask1 = 9 * (pos1 - 1) + 3 * (pos2 - 1) + (pos3 - 1);
                    int mask2 = 9 * (i1 - 1) + 3 * (j1 - 1) + (k1 - 1);
                    dp[i][mask2] = (dp[i][mask2] + dp[i - 1][mask1]) % mod;
                  }
                }
              }
            }
          }
        }
      }
    }
    ll res = 0;
    for (int i = 0; i < 30; i++) res = (res + dp[n][i]) % mod;
    printf("%lld\n", res);
  }
  return 0;
}

第二题

若两个地铁具有相同站点就在这两个地铁连边跑一遍floyd就可以了

tip:s==t的时候输出0 不管有没有线路

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>
#define fir first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define ull unsigned long long
#define cl(a, b) memset(a, b, sizeof(a))
#define quickio(a) ios::sync_with_stdio(a)
#define datatest() freopen("data.in", "r", stdin)
#define makeans() freopen("data.out", "w", stdout)
#define makedata() freopen("data.in", "w", stdout)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
using namespace std;
const int maxn = 1e6 + 10;
const int maxm = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const int maxblock = sqrt(maxn) + 10;
const double eps = 1e-7;
const ll INF = 1e16;
int n, S, T;
int w[510][510];
vector<int> g[510];
vector<int> line[510];
map<int, vector<int>> ma;
int dis[510][510];
int vis[510];
queue<int> q;
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf("%d %d %d", &n, &S, &T);
    for (int i = 0; i < 510; i++) line[i].clear(), g[i].clear();
    for (int i = 0; i < 510; i++) {
      for (int j = 0; j < 510; j++) w[i][j] = inf;
    }
    for (int i = 1; i <= n; i++) {
      int num;
      scanf("%d", &num);
      for (int j = 0; j < num; j++) {
        int a;
        scanf("%d", &a);
        line[i].pb(a);
      }
    }
    ma.clear();
    for (int i = 1; i <= n; i++) {
      for (auto &it : line[i]) {
        ma[it].pb(i);
      }
    }
    for (auto &it : ma) {
      auto &l = it.second;
      for (int i = 0; i < l.size(); i++) {
        for (int j = 0; j < l.size(); j++) {
          if (l[i] == l[j]) {
            // w[l[i]][l[i]] = 0;
            continue;
          }
          w[l[i]][l[j]] = 1;
          w[l[j]][l[i]] = 1;
        }
      }
    }

    for (int k = 1; k <= n; k++) {
      for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
          w[i][j] = min(w[i][j], w[i][k] + w[k][j]);
        }
      }
    }
    auto &l1 = ma[S];
    auto &l2 = ma[T];
    int Min = inf;
    for (auto &it1 : l1) {
      for (auto &it2 : l2) {
        if (it1 == it2) {
          Min = 1;
          continue;
        }
        Min = min(Min, w[it1][it2] + 1);
      }
    }

    if (S == T) {
      printf("0\n");
      continue;
    }
    assert(Min == inf || Min <= n);
    if (Min == inf) Min = -1;
    printf("%d\n", Min);
  }

  return 0;
}

#笔试题目##阿里巴巴#