「CQOI2016」手机号码

题目链接:LOJ 2044

Description

求$[l,r]$中有多少个同时满足以下$2$个条件的数:(保证给定的$l,r$都是$11$位数)

  • 数位中不同时存在$4$和$8$。
  • 至少有$3$位连续相同的数位。

Data Range

$10^{10} \leq l,r < 10^{11}$

Solution

考虑数位DP,定义$f[s1][fg1][fg2][s2][s3][s4]$。
从左到右分别表示考虑到$s1$个数位,$fg1$表示是否出现过$8$,$fg2$表示是否出现过$4$,$s2$表示当前最长的连续,$s3$表示当前连续的个数,$s4$表示上一个数位上的数。
注:需要特别注意边界问题。

Code

#include <bits/stdc++.h>

using namespace std;

long long f[15][2][2][15][15][11];
int dct;
int dig[15];

long long dfs(int pos, bool limup, int p8, int p4, int lcty, int cty, int lnu) {
  if (!pos) {
    return (long long) (lcty >= 3);
  }
  if (pos == dct) {
    int up = dig[pos];
    long long res = 0;
    for (int i = 1; i <= up; i++) {
      res += dfs(pos - 1, limup && (i == up), i == 8, i == 4, 1, 1, i); 
    }
    return res;
  }
  if (!limup && f[pos][p8][p4][lcty][cty][lnu] != -1) {
    return f[pos][p8][p4][lcty][cty][lnu];
  }
  int up = limup ? dig[pos] : 9;
  long long res = 0; 
  int flg1, flg2;
  for (int i = 0; i <= up; i++) {
    if ((p8 && (i == 4)) || (p4 && (i == 8))) {
      continue;
    }
    flg1 = (int) (p8 || (i == 8));
    flg2 = (int) (p4 || (i == 4)); 
    if (i == lnu) {
      int len = max(lcty, cty + 1);
      res += dfs(pos - 1, limup && (i == up), flg1, flg2, len, cty + 1, i); 
    }
    else {
      res += dfs(pos - 1, limup && (i == up), flg1, flg2, lcty, 1, i); 
    }
  }
  if (!limup) {
    f[pos][p8][p4][lcty][cty][lnu] = res; 
  }
  return res;
}

long long solve(long long x) {
  for (dct = 0; x; x /= 10) {
    dct++;
    dig[dct] = x % 10;
  }
  if (dct <= 10) {
    return 0; 
  }
  return dfs(dct, 1, 0, 0, 1, 1, 0); 
}

int main() {
  memset(f, -1, sizeof f);
  long long l, r;
  cin >> l >> r;
  cout << solve(r) - solve(l - 1) << '\n';
  return 0; 
}
最后修改:2019 年 09 月 07 日 08 : 07 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论