3.12晚 滴滴笔试 (AC代码)

选择题是真滴恶心... 算法题是真的简单... 第一次算法花的时间比选择少

第一道好像是求分配方法的

一看数据很水 N M<=20 时间限制三秒 直接暴力搜索就出答案了

#include <bits/stdc++.h>

using namespace std;
#define debug(x) cout << #x << " = " << x << endl
typedef long long ll;
const int SIZE = 1e5;
const int INF = 0x3f3f3f3f;

int n, m, p;

int arr[50] = {0};
bool FOUND = false;

void dfs(int idx, int last) {
  if (idx == m) {
    ll cur = 0;
    for (int i = 0; i < n; i++) {
      cur += arr[i] * arr[i];
    }
    if (cur == p) {
      for (int i = 0; i < m; i++) {
        cout << arr[i] << " ";
      }
      FOUND = true;
      return;
    }
  }
  if (last == 0 || FOUND) return;
  for (int i = 1; i <= last; i++) {
    arr[idx] = i;
    dfs(idx + 1, last - i);
    arr[idx] = 0;
  }
}

int main() {
  std::ios::sync_with_stdio(false);
  cin >> n >> m >> p;
  dfs(0, n);
  if (!FOUND) {
    cout << -1;
  }
  return 0;
}

第二题稍微麻烦一点...(指字多) 但是思维难度不大, 回溯即可

#include <bits/stdc++.h>

using namespace std;
#define debug(x) cout << #x << " = " << x << endl
typedef long long ll;
const int SIZE = 2048;
const int INF = 0x3f3f3f3f;
char matrix[SIZE][SIZE];

void Print(int i1, int j1, int i2, int j2, char color) {
  for (int i = i1; i <= i2; i++) {
    for (int j = j1; j <= j2; j++) {
      matrix[i][j] = color;
    }
  }
}

void color(int i1, int j1, int i2, int j2, int n) {
  if (i1 == i2 && j1 == j2) {
    return;
  }
  int i3 = (i1 + i2) / 2;
  int j3 = (j1 + j2) / 2;
  int i4 = i3 + 1;
  int j4 = j3 + 1;
  if (n & 1 == 1) {
    // odd
    Print(i1, j1, i3, j3, 'B');
    Print(i4, j4, i2, j2, 'B');
    color(i4, j1, i2, j3, n + 1);
    color(i1, j4, i3, j2, n + 1);
  } else {
    // even
    Print(i4, j1, i2, j3, 'B');
    Print(i1, j4, i3, j2, 'B');
    color(i1, j1, i3, j3, n + 1);
    color(i4, j4, i2, j2, n + 1);
  }
}

int main() {
  std::ios::sync_with_stdio(false);
  int n, q;
  cin >> n >> q;
  n = (int)pow(2, n);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      matrix[i][j] = 'W';
    }
  }
  color(1, 1, n, n, 1);
  while (q--) {
    int x;
    cin >> x;
    for (int i = 1; i <= n; i++) cout << matrix[x][i];
    cout << endl;
  }
}