2019南大CS考研机试题目及解答

机试题目

19机试最高分是290,第三题dp不能满分感觉很奇怪(by 咸鱼)

第三题90分解答by烟雨迷楼

机试解答12题　by 你好

机试1-2题代码实现 by佚名

机试第一题数位dp做法 by咸鱼

若输入数字为N则该题采用dfs的做法枚举复杂度是O(符号要求的数字个数)大致与N一个数量级，但是采用数位dp可以做到O(log(N))．在此写下提供一些新思路．

大致思路如下：dp状态记录p当前的位，n上一个位的数字，f之前的数字是否已经比限制小，z之前是否为全0.采用记忆化搜索实现数位dp是比较常见的写法．状态转移看代码应该能懂．

由于数字过大一般此类题目需要取mod.

#include <bits/stdc++.h>

using namespace std;

#define ADD(x, y) (x = (x + y) % MOD)

// brute force for check
int bf(int lim) {
  int cnt = 0;
  for(int y = 10; y <= lim; y++) {
    int yy = y;
    int last = -1;
    int f = 1;
    while(yy > 0) {
      int x = yy % 10;
      yy /= 10;
      if(last != -1 && abs(last - x) != 1) {
        f = 0;
        break;
      }
      last = x;
    }
    cnt += f;
  }
  return cnt;
}

const int MAXN = 1e5;
const long long MOD = 1e9 + 7; // the MOD can be arbitrary
int a[MAXN];
long long dp[MAXN][10][2][2];
int len;

long long DP(int p, int n, int f, int z) {
  if(dp[p][n][f][z] != -1) return dp[p][n][f][z];
  if(p > len - 1) {
    return 1;
  }
  long long dpv = 0;
  int next[2];
  memset(next, -1, sizeof next);
  if(n == 9) next[0] = 8;
  else if(n == 0) next[0] = 1;
  else next[0] = n + 1, next[1] = n - 1;
  if(z) {
    ADD(dpv, DP(p + 1, 0, 1, 1));
    for(int i = 1; i < 10; i++) {
      if(p == 0 && i > a[p]) break;
      if(p == 0 && i == a[p]) ADD(dpv, DP(p + 1, i, 0, 0));
      else ADD(dpv, DP(p + 1, i, 1, 0));
    }
    return dp[p][n][f][z] = dpv;
  }
  for(int i = 0; i < 2; i++) {
    if(next[i] != -1) {
      if(f) ADD(dpv, DP(p + 1, next[i], f, 0));
      else {
        if(next[i] < a[p]) {
          ADD(dpv, DP(p + 1, next[i], 1, 0));
        }
        else if(next[i] == a[p]) {
          ADD(dpv, DP(p + 1, next[i], 0, 0));
        }
      }
    }
  }
  return dp[p][n][f][z] = dpv;
}

char c[MAXN];

long long get_ans(char* s) {
  len = strlen(s);
  for(int i = 0; i < len; i++) a[i] = s[i] - '0';
  if(len <= 1) return 0;
  for(int i = 0; i < len; i++) {
    a[i] = c[i] - '0';
  }
  memset(dp, -1, sizeof dp);
  long long ans = DP(0, 0, 0, 1) - 10;
  return ans;
}

int main() {
  while(scanf("%s", c) != EOF) cout << get_ans(c) << endl;
  /*
  for(int i = 10; i < 1000; i++) {
    int x = i;
    int p = 0;
    while(x > 0) {
      c[p++] = x%10+'0';
      x /= 10;
    }
    c[p] = 0;
    reverse(c, c+p);
    cout << i << " " << bf(i) << " " << get_ans(c) << endl;
    assert(bf(i) == get_ans(c));
  }
  */
  return 0;
}