备战蓝桥杯---DP刷题2

1.树形DP:

即问那几个点在树的直径上,类似ROAD那题,我们先求一下每一个子树根的子树的最大值与次大值用d1,d2表示,直径就是d1+d2的最大值,那么我们如何判断是否在最大路径上,其实就是看一下从某一点出发的所有路劲(可以向父节点)的最大2条的和==直径,就在!因此我们还要维护一下向上的最大值(自上而下),我们假设j是i的父节点,此时i如果选择向j走,那么它可以向上即up[j],也可以向下即d1[j],假如d1[j]就是i到J的边,那么我们选d2[j],

下面是AC代码(注意更新时只考虑d1,对于一个父节点,不会用d2,否则就冲突了):

#include<bits/stdc++.h>
using namespace std;
const int N=200010,M=2*N;
int n;
int h[N],e[M],ne[M],idx;
int d1[N],d2[N],p1[N],up[N];
int maxd;
void add(int a,int b){e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
void dfs_d(int u,int fa){for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(j==fa) continue;dfs_d(j,u);int dis=d1[j]+1;if(dis>d1[u]){d2[u]=d1[u];d1[u]=dis;p1[u]=j;}else if(dis>d2[u]) d2[u]=dis;}maxd=max(maxd,d1[u]+d2[u]);
}
void dfs_u(int u,int fa){for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(j==fa) continue;up[j]=up[u]+1;if(p1[u]==j){up[j]=max(up[j],d2[u]+1);}else up[j]=max(up[j],d1[u]+1);dfs_u(j,u);}
}
int main(){cin>>n;memset(h,-1,sizeof(h));for(int i=0;i<n-1;i++){int a,b;scanf("%d%d",&a,&b);add(a,b);add(b,a);}dfs_d(0,-1);dfs_u(0,-1);for(int i=0;i<n;i++){int d[3]={d1[i],d2[i],up[i]};sort(d,d+3);if(d[1]+d[2]==maxd) printf("%d\n",i);}
}

2.DP+矩阵快速幂:

首先不考虑规模,我们用f[i][j]表示由i个帅子在一起最上面数字为j的所有合法方案。

我们枚举第i-1个帅子的最上面,总共就是f[i][j]=4(f[i-1][1]+...+f[i-1][6]).

我们考虑限制,我们假设2不能贴1,也就是说最上面是2的话加1后最上面不能是5,那么前面的系数要么是0,要么是4.

又由于每一层的限制完全一样,我们考虑矩阵快速幂。

【f[i][1],f[1][2],f[i][3],f[i][4],f[i][5],f[i][6]】=【f[i-1][1],f[i-1][2],f[i-1][3],f[i-1][4],f[i-1][5],f[i-1][6]】*A(6*6的矩阵)

如何构造矩阵?原来填满了4

假如1与2不能相邻,即1不能5,2不能4,即我们把第一行第5列变为0,同理(2,4)变为0,即题目给了(x,y),我们就把(x,y(对应)),(y,x(对应))变为0。

下面是AC代码:

注意这里我们扩充了含有f的矩阵(为了方便)

#include<bits/stdc++.h>
using namespace std;
const int N=6;
int n,m,mod=1e9+7;
int ge(int x){if(x>=3) return x-3;return x+3;
}
int t[N][N];
void mul(int c[][N],int a[][N],int b[][N]){memset(t,0,sizeof(t));for(int i=0;i<6;i++){for(int j=0;j<6;j++){for(int k=0;k<6;k++){t[i][j]=(t[i][j]+(long long)a[i][k]*b[k][j])%mod;}}}memcpy(c,t,sizeof(t));
}
int main(){cin>>n>>m;int a[N][N];for(int i=0;i<N;i++){for(int j=0;j<N;j++){a[i][j]=4;}}while(m--){int x,y;cin>>x>>y;x--,y--;a[x][ge(y)]=0;a[y][ge(x)]=0;}int f[N][N]={4,4,4,4,4,4};//其他扩充0for(int k=n-1;k;k>>=1){if(k&1) mul(f,f,a);mul(a,a,a);}int res=0;for(int i=0;i<6;i++) res=(res+f[0][i])%mod;cout<<res;
}

3.DP

我们令f[i][j][k][c]表示走到(i,j)已经取了k个物品最后物品价值c的集合。

首先我们按照往下走和往右走来分,我们再分取和不取,取的话再枚举前一个即可。

注意边界f[1][1][0][-1](这里就可以让后面任何数都可)f[1][1][1][w[1]]

下面是AC代码:

#include<bits/stdc++.h>
using namespace std;
const int N=55,mod=1e9+7;
int n,m,k;
int w[N][N];
int f[N][N][13][14];
int main(){cin>>n>>m>>k;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>w[i][j];w[i][j]++;}}f[1][1][1][w[1][1]]=1;f[1][1][0][0]=1;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){for(int u=0;u<=k;u++){for(int v=0;v<=13;v++){int &vv=f[i][j][u][v];vv=(vv+f[i-1][j][u][v])%mod;vv=(vv+f[i][j-1][u][v])%mod;if(u>0&&v==w[i][j]){for(int c=0;c<v;c++){vv=(vv+f[i-1][j][u-1][c])%mod;vv=(vv+f[i][j-1][u-1][c])%mod;}}}}}}int res=0;for(int i=0;i<=13;i++) res=(res+f[n][m][k][i])%mod;cout<<res;
}

4.DP

我们假设第一项x,第二项x+d1,第三项x+d1+d2.

nx+(n-1)d1+(n-2)d2+...dn-1=s

此时x属于任意整数,我们转化一下,x=(s-(n-1)d1-...)/n为整数。

于是我们只要让(n-i)di%n求和与s%n相同,这样子就是组合问题。

我们令f[i][j]表示所有只考虑前i项当前和%n==j的方案,

易得转移方程:f[i][j]=f[i-1][(j-ia)%n]+f[i-1][(j+ib)%n].

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/1323661.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

聊一聊单点登录

互联网工程师 一、单点登录的概念 单点登录&#xff08;Single Sign-On&#xff0c;简称SSO&#xff09;是一种身份认证和授权技术&#xff0c;旨在解决用户在访问多个应用系统时需要重复登录的问题。该技术允许用户在一个应用系统中完成登录后&#xff0c;就可以访问其他相互信…

地表径流分布数据/水文站点分布/降雨量分布/辐射分布数据

引言 大气降水落到地面后&#xff0c;一部分蒸发变成水蒸气返回大气&#xff0c;一部分下渗到土壤成为地下水&#xff0c;其余的水沿着斜坡形成漫流&#xff0c;通过冲沟&#xff0c;溪涧&#xff0c;注入河流&#xff0c;汇入海洋。这种水流称为地表径流。 正文 数据简介 来自…

Linux简单介绍

Linux简单介绍 编译器VMware虚拟机Ubuntu——LinuxOS为什么使用LinuxOS&#xff1f; 目录结构Windows目录结构Linux操作系统home是不是家目录&#xff1f; Linux常用命令终端命令行提示符与权限切换命令tab 作用&#xff1a;自动补全上下箭头pwd命令ls命令mkdir命令touch命令rm…

基于SSM的师生交流平台

目录 背景 技术简介 系统简介 界面预览 背景 传统的师生互动平台主要依赖于面对面的线下交流&#xff0c;用户必须亲自到场以获取和交流相关信息。然而&#xff0c;随着信息技术的广泛传播&#xff0c;众多教育机构开始转向线上发展&#xff0c;寻求更多样化的发展途径。线…

QML嵌套页面的实现学习记录

StackView是一个QML组件&#xff0c;用于管理和显示多个页面。它提供了向前和向后导航的功能&#xff0c;可以在堆栈中推入新页面&#xff0c;并在不需要时将页面弹出。 ApplicationWindow {id:rootvisible: truewidth: 340height: 480title: qsTr("Stack")// 抽屉:…

计算机的发展历程

本文 我们来说说计算机的发展历程 世界上第一台计算机 1946年2月世界上第一台计算机埃尼阿克ENIAC (Electronic Numerical Integrator AndComputer 电子数字积分式计算机) 在美国诞生 是由宾夕法尼亚大学物理学家约翰.莫克利(J.Mauchly) 和工程师普雷斯伯.埃克特(J.P.Eckert…

redis事务(redis features)

redis支持事务&#xff0c;也就是可以在一次请求中执行多个命令。redis中的事务主要是通过MULTI和EXEC这两个命令来实现的。 MULTI命令用来开启一个事务&#xff0c;事务开启之后&#xff0c;所有的命令就都会被放入到一个队列中&#xff0c;最后通过一个EXEC命令来执行事务中…

windows@软件显示模糊@屏幕显示器分辨率和精细度

文章目录 refsDPIPPIPPI (Pixels Per Inch)DPI (Dots Per Inch) 屏幕尺寸数windows中DPI设置对单个应用设置DPI兼容性设置使用系统全局设置 获取屏幕(监视器)信息&#x1f47a;获取监视器的型号pnp 监视器windows 获取屏幕分辨率 高分辨率屏幕高分辨率和高精细度屏幕&#x1f4…

数字化赋能农业创新:数字乡村促进农村产业融合

随着信息技术的迅猛发展和广泛应用&#xff0c;数字化已经成为推动农业创新发展的重要引擎。数字乡村建设通过引入现代信息技术&#xff0c;为农业产业带来了前所未有的发展机遇&#xff0c;促进了农村产业的深度融合与升级。本文将从数字化赋能农业创新的角度&#xff0c;探讨…

ubuntu安装sublime3并设置中文

安装Sublime Text 3 在Ubuntu上安装Sublime Text 3可以通过以下步骤进行&#xff1a; 打开终端。 导入Sublime Text 3的GPG密钥&#xff1a; wget -qO- https://download.sublimetext.com/sublimehq-pub.gpg | sudo apt-key add - 添加Sublime Text 3的存储库&#xff1a; …

2024最新AI创作系统ChatGPT源码+Ai绘画网站源码,GPTs应用、AI换脸、插件系统、GPT文档分析、GPT语音对话一站式解决方案

一、前言 SparkAi创作系统是基于ChatGPT进行开发的Ai智能问答系统和Midjourney绘画系统&#xff0c;支持OpenAI-GPT全模型国内AI全模型。本期针对源码系统整体测试下来非常完美&#xff0c;那么如何搭建部署AI创作ChatGPT&#xff1f;小编这里写一个详细图文教程吧。已支持GPT…

vivado适用于 UltraScale 和 UltraScale+ 器件的 eFUSE 寄存器访问和编程

FUSE_DNA &#xff1a; 唯一的器件 DNA 每个 UltraScale 器件都有唯一的器件 ID &#xff0c; 称为器件 DNA &#xff0c; 且赛灵思已将此 DNA 编程到器件中。用户无法对 FUSE_DNA 进行编程。 UltraScale 器件具有 96 位 DNA 。您可在 Vivado Design Suite Tcl 控制台中…

Qt项目通过.pri文件将众多文件按功能模块分类显示,开发大型项目必备

Chapter1 Qt项目通过.pri文件将众多文件按功能模块分类显示&#xff0c;开发大型项目必备 Chapter2 在Qt项目中添加pri文件 原文链接&#xff1a;在Qt项目中添加pri文件_qtpri-CSDN博客 前言 一般我们创建Qt项目工程的时候&#xff0c;都是直接把所有的项目&#xff0c;头文…

代码随想录阅读笔记-二叉树【合并二叉树】

题目 给定两个二叉树&#xff0c;想象当你将它们中的一个覆盖到另一个上时&#xff0c;两个二叉树的一些节点便会重叠。 你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠&#xff0c;那么将他们的值相加作为节点合并后的新值&#xff0c;否则不为 NULL 的节…

Day18-【Java SE进阶】多线程

一、线程 1. 什么是线程? 线程(Thread)是一个程序内部的一条执行流程。程序中如果只有一条执行流程&#xff0c;那这个程序就是单线程的程序。 2. 多线程 多线程是指从软硬件上实现的多条执行流程的技术(多条线程由CPU负责调度执行) 3. 如何在程序中创建出多条线程? Ja…

软件设计师27--规范化理论

软件设计师27--规范化理论 考点1&#xff1a;规范化理论基本概念函数依赖规范化理论--Amstrong公理体系候选键主属性与非主属性例题&#xff1a; 考点2&#xff1a;范式判断规范化理论规范化理论 - 范式例题&#xff1a; 考点3&#xff1a;范式分解保持函数依赖分解无损分解模式…

【大数据存储】实验4 NoSQL数据库

实验4 NoSQL数据库 NoSQL数据库的安装和使用实验环境&#xff1a; Ubuntu 22.04.3 Jdk 1.8.0_341 Hadoop 3.2.3 Hbase 2.4.17 Redis 6.0.6 mongdb 6.0.12 mogosh 2.1.0 Redis 安装redis完成 新建终端启动redisredis-server新建一个终端redis-cli 建表操作 尝…

文心一言指令词宝典之旅行篇

作者&#xff1a;哈哥撩编程&#xff08;视频号、抖音、公众号同名&#xff09; 新星计划全栈领域优秀创作者博客专家全国博客之星第四名超级个体COC上海社区主理人特约讲师谷歌亚马逊演讲嘉宾科技博主极星会首批签约作者 &#x1f3c6; 推荐专栏&#xff1a; &#x1f3c5;…

OSPF中配置静态路由负载分担实验简述

OSPF中配置静态路由负载分担 实验简述 在静态路由负载分担中&#xff0c;多个路由器被配置为共享负载的目标&#xff0c;以实现流量的均衡分配。 到达目的地有N条相同度量值的路径&#xff0c;默认值60&#xff0c;N条路由是等价路由&#xff0c;数据报文在N条链路上轮流发送。…

单机多实例mysql8.x数据库主从配置

单机配置多实例mysql8.x集群 要求&#xff1a; 在一台服务器上配置两个&#xff08;一主一从&#xff09;mysql8.X版本数据库&#xff0c;两台服务ip相同&#xff0c;端口不同 数据库版本 mysql-8.0.31-linux-glibc2.12-x86_64.tar 下载地址&#xff1a;https://downloads.m…