首页 > 其他分享 >米哈游4-15 笔试第三题 数位dp

米哈游4-15 笔试第三题 数位dp

时间:2023-04-16 12:34:59浏览次数:32  
标签:15 int LL pos 米哈 limit dp mod

一、题意:找到第k(k上限1e12)大的,不包括4并且能被7整除的数。
题解:二分+数位dp。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;

const int MAXN = 100;
LL dp[MAXN][7], digit[MAXN];

LL dfs(int pos, int mod, bool limit){
    if (pos == -1){
        return mod==0;
    }
    
    if (!limit && dp[pos][mod] != -1){
        return dp[pos][mod];
    }

    int up = limit ? digit[pos] : 9;
    LL ans = 0;
    for (int i = 0; i <= up; ++i)
    {
        if (i == 4)continue;
        int newmod = (mod * 10 + i) % 7;
        LL tmp = dfs(pos - 1, newmod, limit && (i == up));
        ans += tmp;
    }

    if (!limit)dp[pos][mod] = ans;

    return ans;
}

LL solve(LL x){
    memset(dp, -1, sizeof(dp));
    int pos=0;
    while(x){
        digit[pos++]=x%10;
        x/=10;
    }
    return dfs(pos-1, 0, true) - 1;
}

int main(){
    LL k;
    cin >> k;
    LL l=1, r=1e18;
    while(l<=r){
        LL mid=(l+r)>>1;
        LL tmp=solve(mid);
        if(tmp<k)l=mid+1;
        else r=mid-1;
    }
    
    cout<<l<<endl;
    return 0;
}

标签:15,int,LL,pos,米哈,limit,dp,mod
From: https://www.cnblogs.com/JohnRan/p/17323080.html

相关文章

  • 退划 2 23.4.15
    与世隔绝压抑,喘不过气来。或者是说整个实验一都是比较死板的,如一潭死水般,没有新鲜的源头。我渴望一片充满阳光的绿茵地可是我被装进一间铁屋子里而我,也如密不透风的铁屋子里那唯一燃烧的蜡烛随着氧气耗尽,最终也会熄灭只希望我在所有的热情都被磨灭殆尽之日,可以熔出一个小......
  • CF1816F Xor Counting - dp - 分治 -
    题目链接:https://codeforces.com/contest/1816/problem/F题解:一道有趣的题。首先发现\(m=1\)和\(m\geq3\)时结论是平凡的。\(m=1\)时结论显然,下面讨论一下\(m\geq3\)时:首先可以构造\([x,(n-x)/2,(n-x)/2,\cdots]\),其中\(x\)和\(n\)同奇偶,显然此时异或值可以......
  • DP动态规划
    题目描述有一长度为N(1<=N<=10)的地板,给定两种不同瓷砖:一种长度为1,另一种长度为2,数目不限。要将这个长度为N的地板铺满,一共有多少种不同的铺法?输入格式输入有多组,每组只有一个数N,代表地板的长度输出格式对于每组数据,输出一个数,占一行,代表所有不同的瓷砖铺放......
  • 汉诺塔DP
    题目描述如果将课本上的汉诺塔问题稍做修改:给定N只盘子,3根柱子,但是允许每次最多移动相邻的M只盘子(当然移动盘子的数目也可以小于M),最少需要多少次?输入格式输入数据仅有一行,包括两个数N和M(0<=M<=N<=8)输出格式仅输出一个数,表示需要移动的最少次数 #in......
  • 华为手表开发:WATCH 3 Pro(15)传感器订阅加速度计
    华为手表开发:WATCH3Pro(15)传感器订阅加速度计初环境与设备加速度传感器介绍与说明鸿蒙开发文件夹:文件重点新增展示的文本标记index.hmlindex.cssindex.js初希望能写一些简单的教程和案例分享给需要的人鸿蒙可穿戴开发环境与设备系统:window设备:HUAWEIWATCH3ProNew开发工具:Dev......
  • Java中创建线程的方式以及线程池创建的方式、推荐使用ThreadPoolExecutor以及示例
    场景Java中创建线程的方式有三种1、通过继承Thread类来创建线程定义一个线程类使其继承Thread类,并重写其中的run方法,run方法内部就是线程要完成的任务,因此run方法也被称为执行体,使用start方法来启动线程。2、通过实现Runanle接口来创建线程首先定义Runnable接口,并重写Runnable接口......
  • 2023.15 人工智能训练师
    AI在消灭一些职业岗位的同时,也会带来一些新的岗位,人工智能训练师就是其中之一。2020年,「人工智能训练师」正式成为新职业并纳入国家职业分类目录,是指「使用智能训练软件,在人工智能产品实际使用过程中进行数据库管理、算法参数设置、人机交互设计、性能测试跟踪及其他辅助作......
  • CF1815C
    1解法设\(f_i\)为\(i\)最多出现多少次,那么一个限制\((u,v)\)可以写成\(f_u\leqf_v+1\),把\(f\)看做最短路中的\(dis\)数组,上面的式子就是在图上连一条从\(u\)到\(v\)边权是\(1\)的边,由于边权都是\(1\),所以可以直接用\(\text{bfs}\)做.然后考虑如何构造使......
  • day46(2023.4.15)
    1.多表查询 2.迪卡尔乘积 3.等值连接 4.非等值连接 5.自连接 6.99交叉连接 7.99自然连接 8.99内连接 9.外连接查询 10.多表查询,连接小练习 day46(2023.4.15)......
  • 【CVE-2017-12615】Tomcat 远程代码执行漏洞复现
    0x00环境搭建用vulhub的环境查看配置文件conf/web.xml中readonly的设置0x01漏洞复现访问主页,抓包后修改数据包可通过PUT方式创建一个JSP文件。虽然Tomcat对文件后缀有一定检测(不能直接写jsp),但我们使用一些文件系统的特性(如Linux下可用/)来绕过了限制。改完包的时候......