阿里算法岗3月4号笔试情况(附带题解)

感觉这次题目还挺难的，还好最后10分钟全部A掉了

第一题太简单了，简单模拟一下就行了，就是题意比较绕，其实就是求A 中满足 "A[i]的字符串表示" 包含 "i的字符串表示"的个数

C++代码和Python代码如下：

#include<bits/stdc++.h>
using namespace std;
int main() {
  int t; cin >> t;
  while (t--) {
    int n; cin >> n;
    vector<int> A(n); for (auto &a: A) cin >> a;
    int ans = 0;
    for (int i = 0; i < n; i++) {
      string sn = to_string(A[i]);
      string si = to_string(i+1);
      if (sn.find(si) != string::npos) ans++;
    }
    cout << ans << endl;
  }
}

t = int(input())
while t>0:
    t-=1
    n = int(input())
    a = input().split()
    ret = 0
    for i in range(n):
        x = str(i+1)
        if a[i].find(x) != -1:
            ret +=1
    print(ret)

第二题其实是错排，前面都说的很啰嗦，其实就是打印前t个错排

一个错误的想法是模拟next_permuation去不断构造下一个错排，这个做法有很多边界条件需要处理

比较容易写的算法是递归，在剩下的集合中从小到大选择能放到当前位置的数字

C++代码如下:

#include<bits/stdc++.h>
using namespace std;
int n, t;  //输入
vector<int> A; //保存递归枚举的状态
set<int> S;  //未被使用的数字
void dfs(int i) {  //枚举位置 i
  if (i == n) {
    t--;
    for (auto a: A) cout << a + 1 << " "; cout << endl;
    return;
  }
  for (auto it = S.begin(); it != S.end(); it++) {
    auto x = *it;
    if (x == i) continue;
    A[i] =x;
    S.erase(x);
    dfs(i+1);
    if (t == 0) break;
    it = S.insert(x).first;
  }
}
int main() {
  cin >> n >> t;
  A.resize(n);
  for (int i = 0; i < n; i++) S.insert(i);
  dfs(0);
}

第三题就太难了，卡了好久，最后想出来dp的转移了

题目是交叉高低难度求刷题方案，其实就是求满足A[0]为 k，且sum(A) 为 n 的波形数组的方案数

1、假如枚举第 i 个数为 x，且x 为波峰/波谷，则会得到一个 O(N^3)的算法，容易超时

2、用dp(n, k, o)表示当前剩下 n，上一位是 k，且当前为0-波峰，1-波谷；利用记忆化技巧，可以得到一个O(N^2)的算法（需要特判输入n==k的情况）

dp(n, k, 0/1) = 0 n<0

dp(0, k, 0/1) = 1

dp(n, k, 0) = ∑dp(n-i, i, 1) i<k<=n

dp(n, k, 1) = ∑dp(n-i, i, 0) 0<i< k (且 i < n)

C++代码如下:

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

const int MOD = 1e9+7;
const int MAXN = 512;
long long cache[MAXN][MAXN][2];
long long dp(int n, int k, int o) {
  if (n < 0) return 0;
  auto &res = cache[n][k][o];
  if (res != -1) return res;
  if (n == 0)  return res = 1;
  res = 0;
  if (o == 0)  while (++k<=n)  res = (res + dp(n-k, k, 1)) % MOD;
  else while (--k>0)  res = (res + dp(n-k, k, 0)) % MOD;
  return res;
}

int main() {
  int n, k; cin >> n >> k;
  memset(cache, -1, sizeof(cache));
  if (n == k) cout << 1 << endl;
  else cout << (dp(n-k, k, 0) + dp(n-k, k, 1)) % MOD << endl;
}

#阿里巴巴##笔经#