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;
}
