第三届adpc冬季赛 G. MP4

摘要
Title: 第三届adpc冬季赛 G. MP4
Tag: dfs、字典序第K小数字
Memory Limit: 256 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

G. MP4

• 题意

  1~n的数字按字典序排序，求前50个

• 思路

  dfs爆搜即可

  • dfs(l, r, k) 表示边界为l,r，找k个
  • 举个例子$n = 100$
  • 优先考虑大的数，所以10倍扩大范围（因为0是最优的），直到不能扩了，如$1, 10, 100$
  • 其次开始在$l, r$中枚举，如$11,12,...19$
  • 当到了10的倍数时，意味着此位数字换了，也就是此位数字为$x$的数枚举完了，return即可

• 代码

  /*
  * @Author: NEFU AB-IN
  * @Date: 2022-03-27 10:13:00
  * @FilePath: \ACM\Contest\g.cpp
  * @LastEditTime: 2022-03-27 17:07:56
  */
  #include <bits/stdc++.h>
  using namespace std;
  #define int long long
  #define MP make_pair
  #define SZ(X) ((int)(X).size())
  #define IOS                                                                                                            \
      ios::sync_with_stdio(false);                                                                                       \
      cin.tie(0);                                                                                                        \
      cout.tie(0);
  #define DEBUG(X) cout << #X << ": " << X << endl;
  typedef pair<int, int> PII;
  const int INF = 0x3f3f3f3f;
  
  int n, sum;
  
  void dfs(int l, int r, int k)
  {
      if (r > n)
          r = n;
      for (int i = l; i <= r; i++)
      {
          if (i != l && i % 10 == 0)
              return;
          sum++;
          if (sum <= k)
          {
              printf("%lld.mp4\n", i);
              if (sum == k)
                  return;
          }
          if (i * 10 <= n)
              dfs(i * 10, i * 100 - 1, k);
      }
      return;
  }
  signed main()
  {
      scanf("%lld", &n);
      dfs(1, 9, 50);
      return 0;
  }