李白打酒加强版 -- 题解 c++
题目链接 :
4408. 李白打酒加强版 - AcWing题库
用户登录
二进制搜索
只能过10%,极限暴力
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
typedef long long LL;
const int mod = 1e9+7;
const int N = 2e5+10;
using namespace std;int n , m , p ;string f(int x){string s = bitset<32>(x).to_string() ;return s.substr(16) ;
}int get(LL x){int cnt = 0 ;while(x){x = x & (x-1) ;cnt ++ ;}return cnt ;
}bool pd(int x){if(get(x)!=n) return false ;int f = 2 ;for(int i=p-1;i>=0;i--){if((x>>i)&1) f *= 2 ;else{if(f==0) return false ;f--;}}if(f==0) return true ;else return false ;
}inline void solve(){cin >> n >> m ;p = n + m ;// 0 : 花 , 1 : 酒 LL ans = 0 ;for(int i=0;i<(1<<p);i++){if(pd(i)){ans ++ ;
// cout << f(i) << endl ;}}cout << ans << endl ;
}signed main()
{IOSint _ = 1;while(_ --) solve();return 0;
}
DFS
没啥好讲的,直接看代码,能过、40%
#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7 ;
typedef long long LL;
int n , m ;
LL ans ;void dfs(int i,int j,int k,int z){//i次店,j次花,剩余k酒,z:当前位置//最后一次必为花,且酒刚好为0if(z==n+m-1){//倒数第二次if(k==1&&i==n&&j==m-1){ans ++ ;}return ;}if(k<=0) return ;// 遇到店dfs(i+1,j,k*2,z+1);//遇到花dfs(i,j+1,k-1,z+1);
}int main(){cin >> n >> m ; // 店n次,花m次dfs(0,0,2,0);ans = ans % MOD ;cout << ans << endl ;return 0 ;
}
DP
dp[i][j][k] 表示为前i次,有j次遇到店,剩下酒为k斗 的方案数
详细请看题解
#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7 ;
const int N = 201 ;
typedef long long LL;
int n , m ;
LL ans ;
LL dp[N][N][N] ;// dp[i][j][k] 表示为前i次,有j次遇到店,剩下酒为k斗 的方案数int main(){cin >> n >> m ; // 店n次,花m次dp[0][0][2] = 1 ;//初始2for(int i=1;i<=n+m;i++){for(int j=0;j<=n;j++){for(int k=0;k<=100;k++){//最多消耗100瓶// 上一次遇到花dp[i][j][k] += dp[i-1][j][k+1];// 上一次遇到酒if(j && k%2==0){dp[i][j][k] += dp[i-1][j-1][k/2] ;}dp[i][j][k] %= MOD ;}}}dp[n+m][n][0] = dp[n+m-1][n][1] ;cout << dp[n+m][n][0] << endl ;return 0 ;
}
相关文章:
李白打酒加强版 -- 题解 c++
题目链接 : 4408. 李白打酒加强版 - AcWing题库 用户登录 二进制搜索 只能过10%,极限暴力 #include<bits/stdc.h> #define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define endl \n typedef long long LL; const int mod 1e97; const int N 2e510;…...
蓝桥杯——玩具蛇
题目 小蓝有—条玩具蛇,一共有16节,上面标着数字1至16。每—节都是一个正方形的形状。相邻的两节可以成直线或者成90度角。 小蓝还有一个44的方格盒子,用于存放玩具蛇,盒子的方格上依次标着字母A到Р共16个字母。 小蓝可以折叠自…...
百度SSL证书免费申请
百度云也有免费SSL证书可以申请,很多用户找不到,云服务器吧yunfuwuqiba.com整理百度云SSL免费证书申请入口: 1、打开百度云SSL证书购买页面 yunfuwuqiba.com/go/baidu_ssl 点立即购买,如下图: 百度云SSL证书 2、免费…...
SpringBoot Assert断言
文章目录 前言一、Assert说明二、Assert方法三、使用示例四、总结前言 在Spring Boot中,Assert类提供了一系列用于断言的静态方法,用于在代码中进行条件检查和错误处理。这些方法可以帮助我们在开发过程中快速发现和解决问题,提高代码的可靠性和健壮性。 一、Assert说明 在…...
test4121
欢迎关注博主 Mindtechnist 或加入【Linux C/C/Python社区】一起学习和分享Linux、C、C、Python、Matlab,机器人运动控制、多机器人协作,智能优化算法,滤波估计、多传感器信息融合,机器学习,人工智能等相关领域的知识和…...
UI自动化测试重点思考(下)--装饰器/生成器/夹具的使用/描述符的作用/ddt驱动/多线程
UI自动化测试重点思考--装饰器 装饰器装饰器定义装饰器代码示例装饰器的执行如何将装饰器融合到pytest框架里面 生成器创建生成器生成器的定义如何将生成器融合到pytest框架里面 fixture(夹具)使用pytest fixture 中 scope 参数的详细解释 描述符的总结描…...
C# 字段和属性的区别
区别 在C#中,字段(Field)和属性(Property)都是用来封装对象状态的方式,但它们有以下区别: 访问级别: 字段通常是private,而属性可以有不同级别的访问限制(…...
备考ICA----Istio实验17---TCP流量授权
备考ICA----Istio实验17—TCP流量授权 1. 环境准备 1.1 环境部署 kubectl apply -f <(istioctl kube-inject -f istio/samples/tcp-echo/tcp-echo.yaml) -n kim kubectl apply -f <(istioctl kube-inject -f istio/samples/sleep/sleep.yaml) -n kim1.2 测试环境 检测…...
[C++][算法基础]树的重心(树图DFS)
给定一颗树,树中包含 n 个结点(编号 1∼n)和 n−1 条无向边。 请你找到树的重心,并输出将重心删除后,剩余各个连通块中点数的最大值。 重心定义:重心是指树中的一个结点,如果将这个点删除后&a…...
探秘ChatGPT:如何利用AI提升论文写作效率
ChatGPT无限次数:点击直达 html 探秘ChatGPT:如何利用AI提升论文写作效率 在当今信息爆炸的时代,论文写作是许多人工作者每天都要面对的任务。如何更高效地撰写出内容丰富、结构严谨的论文,一直是许多学者和研究人员所追求的目标。随着人…...
多无人机集群协同避障
matlab2020a正常运行 场景1规划结果 场景2规划结果 场景3规划结果 代码地址: 多无人机集群协同避障效果(5架)资源-CSDN文库...
基于velero和minio实现k8s数据的备份
1.30部署minio rootk8s-harbor:/etc/kubeasz/clusters/k8s-cluster1# docker run \ -d --restartalways -p 9000:9000 -p 9090:9090 –name minio -v /data/minio/data:/data -e “MINIO_ROOT_USERadmin” -e “MINIO_ROOT_PASSWORD12345678” quay.io/minio/minio server…...
【Java核心技术】第4章 对象与类
1 面向对象 2 自定义类 形式: class ClassName { field // 字段 constructor // 构造器(构造函数) method // 方法 } 如: class Employee {private String name;private double salary;private LocalDate hireDay;public Emp…...
【LeetCode】回溯算法类题目详解
所有题目均来自于LeetCode,刷题代码使用的Python3版本 回溯算法 回溯算法是一种搜索的方法,在二叉树总结当中,经常使用到递归去解决相关的问题,在二叉树的所有路径问题中,我们就使用到了回溯算法来找到所有的路径。 …...
java实现请求缓冲合并
业务背景: 我们对外提供了一个rest接口给第三方业务进行调用,但是由于第三方框架限制,导致会发送大量相似无效请求,例如:接口入参json包含两个字段,createBy和receiverList,完整的入参json示例…...
分布式锁的原子性问题
4.6 分布式锁的原子性问题 更为极端的误删逻辑说明: 线程1现在持有锁之后,在执行业务逻辑过程中,他正准备删除锁,而且已经走到了条件判断的过程中,比如他已经拿到了当前这把锁确实是属于他自己的,正准备删…...
从零自制docker-8-【构建实现run命令的容器】
文章目录 log "github.com/sirupsen/logrus"args...go moduleimport第三方包失败package和 go import的导入go build . 和go runcli库log.SetFormatter(&log.JSONFormatter{})error和nil的关系cmd.Wait()和cmd.Start()arg……context.Args().Get(0)syscall.Exec和…...
2024.03.31 校招 实习 内推 面经
绿*泡*泡VX: neituijunsir 交流*裙 ,内推/实习/校招汇总表格 1、自动驾驶一周资讯 -小米SU7上市24小时,大定达88898台;小鹏汽车正式进入德国市场;地平线递交港股上市申请 自动驾驶一周资讯 -小米SU7上市24小时&…...
邦芒职场:塑造职场人气王的秘诀
在职场中,有些人总能吸引众人的目光,成为团队的焦点;而有些人却常常默默无闻,难以融入。那么,如何在职场中脱颖而出,成为一个受欢迎的人呢?下面,让我们来探讨一下塑造职场人气王的秘…...
滤波器网络变压器的作用
网络变压器的作用主要包括以下几点: 1. 信号传输:网络变压器可以将PHY送出来的差分信号用差模耦合的线圈耦合滤波以增强信号,并且通过电磁场的转换耦合到不同电平的连接网线的另外一端以达到传输数据的目的。 2. 电气电压隔离:…...
MFC内存泄露
1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...
微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...
oracle与MySQL数据库之间数据同步的技术要点
Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异,它们的数据同步要求既要保持数据的准确性和一致性,又要处理好性能问题。以下是一些主要的技术要点: 数据结构差异 数据类型差异ÿ…...
【git】把本地更改提交远程新分支feature_g
创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...
3-11单元格区域边界定位(End属性)学习笔记
返回一个Range 对象,只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意:它移动的位置必须是相连的有内容的单元格…...
Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...
html-<abbr> 缩写或首字母缩略词
定义与作用 <abbr> 标签用于表示缩写或首字母缩略词,它可以帮助用户更好地理解缩写的含义,尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时,会显示一个提示框。 示例&#x…...
USB Over IP专用硬件的5个特点
USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中,从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备(如专用硬件设备),从而消除了直接物理连接的需要。USB over IP的…...
c++第七天 继承与派生2
这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分:派生类构造函数与析构函数 当创建一个派生类对象时,基类成员是如何初始化的? 1.当派生类对象创建的时候,基类成员的初始化顺序 …...
