知能科技 软件开发 笔试

#软件开发2023笔面经#

随便投的一个公司，发现居然也要在牛客上笔试

A. cf原题

https://codeforces.com/contest/1802/problem/B

#include<bits/stdc++.h>

int A[100005];

void solve() {
  int n;
  std::cin >> n;
  for (int i = 1; i <= n; i++) {
    std::cin >> A[i];
  }
  int x = 0, y = 0, unknown = 0, pre = 0, ans = 0;
  for (int i = 1; i <= n; i++) {
    if (A[i] == 1) {
      ++unknown;
    } else if (A[i] == 2) {
      pre += unknown;
      unknown = 0;
    }
    std::cerr << i << ' ' << ans << ' ' << unknown << ' ' << pre << ' ' << unknown + pre / 2 + 1 << '\n';
    if (pre) {
      ans = std::max(ans, unknown + pre / 2 + 1);
    } else {
      ans = std::max(ans, unknown);
    }
  }
  std::cout << ans << '\n';
}

int main() {
  std::cin.tie(nullptr) -> sync_with_stdio(false);
  int T = 1;
  //std::cin >> T;
  while (T--) {
    solve();
  }
  return 0;
}

B. 构造题

定义美丽值为矩阵相邻数字的绝对值大小种类，例如:

[1 2

4 3]

有|1 - 4| = 3, |1 - 2| = 1, |2 - 3| = 1, |4 - 3| = 1, 有两种。

给定一个n <= 150, 构造 n * n矩阵使得美丽值最大。

构造思路：

n为奇数：

1, n, 2, n - 1, 3

n -2, 4, n - 3....

..........

n为偶数：

1, n, 2, n - 1, 3

....n - 3, 4, n - 2

...................

不难看出这样构造是可以达到最优值的。

#include<bits/stdc++.h>

int A[2222][2222];
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};

int n;
void solve(int cas) {
  std::cin >> n;
  if (n == 2) {
    std::cout << "1 3\n4 2\n";
    return ;
  }
  if ((n & 1)) {
    int flag = 0;
    int x = 1, y = n * n;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (!flag) {
          A[i][j] = x++;
        } else {
          A[i][j] = y--;
        }
        flag ^= 1;
      }
    }
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        std::cout << A[i][j] << " \n"[j == n];
      }
    }
  } else {
    std::map<int, int> mp;
    int flag = 1;
    int x = 1, y = n * n;
    for (int i = 1; i <= n; i++) {
      if (i & 1) {
        for (int j = 1; j <= n; j++) {
          if (!flag) {
            A[i][j] = x++;
          } else {
            A[i][j] = y--;
          }
          flag ^= 1;
        }
      } else {
        for (int j = n; j >= 1; j--) {
          if (!flag) {
            A[i][j] = x++;
          } else {
            A[i][j] = y--;
          }
          flag ^= 1;
        }
      }
    }
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        std::cout << A[i][j] << " \n"[j == n];
      }
    }
  }
}
void solve() {
  // std::cin >> n;
  // for (int i = 1; i <= n; i++) {
  //   for (int j = 1; j <= n; j++) {
  //     std::cin >> A[i][j];
  //   }
  // }
  std::set<int> st;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      for (int k = 0; k < 4; k++) {
        int nx = i + dir[k][0], ny = j + dir[k][1];
        if (nx >= 1 and ny >= 1 and nx <= n and ny <= n) {
          st.emplace(std::abs(A[i][j] - A[nx][ny]));
          //std::cerr << i << ' ' << j << ' ' << A[i][j] << ' ' << A[nx][ny] << '\n';
        }
      }
    }
  }
  std::cerr << "debug: "  << st.size() << '\n';
}

int main() {
  std::cin.tie(nullptr) -> sync_with_stdio(false);
  int T = 1;
  //std::cin >> T;
  while (T--) {
    solve(T);
    solve();
  }
  return 0;
}

附加题：求一个长度为n(n <= 200000) 的序列中，长度不小于k的最大中位数，只需要给出思路

思路：二分答案，原数组可以转化成-1，1，那么求一个前缀和，对于每个位置 i，我都考查一下 [1, i - k + 1] 中是否存在一个Sum[j]，使得 Sum[i] - Sum[j] >= 0 即可，这个可以维护前缀最小值去实现。

时间复杂度 O(nlogn), 空间复杂度 O(n)。