当前位置：首页 > news >正文

题解：AT_abc244_e [ABC244E] King Bombee

news 来源：原创 2025/7/13 15:09:40

一道图上 DP 的好题。

（题目自己看，我就不说了。）

首先一看到求方案数，首先就要反应的是 DP 或者排列组合，反正考试的时候我写半天排列组合没写出来，所以就只能是 DP 了。~~（好牵强的理由啊……）~~

既然是 DP，那我们看看 DP 表示什么。自然是求啥设啥，那应该开几维呢？怎么写状态转移方程呢？

首先我们来解决第一个问题：我们看看题目中有几个不定量。不难发现，最主要的一共有三个：当前所在的点、总长度和经过 $X$ 的次数。所以 DP 一共就有三维。（正好开下数据范围。）

接着我们来写状态转移方程，其实我们把 DP 设出来之后就很好写状态转移方程了，具体如下：

$\begin{cases} dp_{i,j,0}=dp_{i,j,0}+dp_{i-1,to,0},dp_{i,j,1}=dp_{i,j,1}+dp_{i-1,to,1}&j\not=t\\dp_{i,j,0}=dp_{i,j,0}+dp_{i-1,to,1},dp_{i,j,1}=dp_{i,j,1}+dp_{i-1,to,0}&j=t\end{cases}$

其中 $t o$ 表示从 $j$ 能到的点。

AC 代码：

#include<bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;
int n,m,k,s,t,x,dp[2006][2006][2];
vector<int>v[2006];
signed main()
{cin>>n>>m>>k>>s>>t>>x;for(int i=1,y,z;i<=m;i++){cin>>y>>z;v[y].emplace_back(z);v[z].emplace_back(y);}dp[0][s][0]=1;for(int i=1;i<=k;i++){for(int j=1;j<=n;j++){for(auto l:v[j]){if(j==x){dp[i][j][0]+=dp[i-1][l][1],dp[i][j][0]%=mod;dp[i][j][1]+=dp[i-1][l][0],dp[i][j][1]%=mod;}else{dp[i][j][0]+=dp[i-1][l][0],dp[i][j][0]%=mod;dp[i][j][1]+=dp[i-1][l][1],dp[i][j][1]%=mod;}}}}cout<<dp[k][t][0]%mod;return 0;
}

题解：AT_abc244_e [ABC244E] King Bombee

一道图上 DP 的好题。 （题目自己看，我就不说了。） 首先一看到求方案数，首先就要反应的是 DP 或者排列组合，反正考试的时候我写半天排列组合没写出来，所以就只能是 DP 了。（好牵强的理由啊………...

编程日记 2025/7/13 15:09:40

C++显式声明explicit

C显示声明explicit 在 C 中，explicit 关键字用于修饰单参数构造函数或多参数构造函数（C11 起），其核心作用是禁止编译器的隐式类型转换。一、必须加 explicit 的典型场景 1. 单参数构造函数当构造函数只有一个参数时&#xff…...

编程日记 2025/6/28 23:37:16

哈希查找方法

已知哈希表长度为11，哈希函数为H（key）＝key％11，随机产生待散列的小于50的8个元素，同时采用线性探测再散列的方法处理冲突。任意输入要查找的数据，无论是否找到均给出提示信息。 int f…...

编程日记 2025/7/11 8:45:57

AI编程辅助哪家强？深度解析主流AI编程工具的现状与未来-优雅草卓伊凡

AI编程辅助哪家强？深度解析主流AI编程工具的现状与未来-优雅草卓伊凡引言：AI编程的崛起与开发者的新选择在当今快速发展的科技时代，AI编程辅助工具已经成为开发者不可或缺的得力助手。作为一名资深的程序员，”优雅草卓伊凡”经…...

编程日记 2025/6/28 22:14:18

Python打卡训练营day27-函数-装饰器

知识点回顾： 装饰器的思想：进一步复用函数的装饰器写法注意内部函数的返回值作业： 编写一个装饰器 logger，在函数执行前后打印日志信息（如函数名、参数、返回值） 装饰器实际上是一个增强函数，它…...

编程日记 2025/6/28 21:58:21

EtherCAT通信协议

EtherCAT（Ethernet for Control Automation Technology）是一种高性能的实时工业以太网通信协议，专为工业自动化和控制系统的需求设计。它结合了以太网的灵活性和工业实时通信的高效性，广泛应用于运动控制、机器人、过程自动化等领…...

编程日记 2025/6/29 1:13:01

多线程下如何保证事务的一致性

以下是关于Java多线程的详细介绍，适合作为知识博客的内容。我将从基础概念开始，逐步深入到分布式场景、线程池配置以及Spring Cloud集成等高级主题，并提供丰富的业务场景示例。 Java多线程核心概念 1. 线程与进程的区别进程：程…...

编程日记 2025/7/13 2:28:09

OpenCv高阶（8.0）——答题卡识别自动判分

文章目录前言一、代码分析及流程讲解（一）初始化模块正确答案映射字典（题目序号: 正确选项索引）图像显示工具函数 （二）轮廓处理工具模块（三）几何变换核心模块二、主处理流程图像读取…...

编程日记 2025/6/28 23:40:45

量子通信技术：原理、应用与未来展望

在当今数字化时代，信息安全是全球关注的焦点。随着量子计算技术的飞速发展，传统的加密方法面临着前所未有的挑战。量子通信技术作为一种新兴的通信手段，以其绝对安全的特性，为信息安全领域带来了新的希望。本文将深入探讨量子通信…...

编程日记 2025/6/28 22:13:10

Token的组成详解：解密数字身份凭证的构造艺术

在当今的互联网身份认证体系中，Token如同数字世界的"安全护照"，承载着用户的身份信息和访问权限。据统计，现代应用中80%以上的身份验证依赖于Token机制。本文将深入解析Token的各个组成部分，通过典型实例揭示其设计原理…...

编程日记 2025/6/29 1:27:12

【SFT监督微调总结】大模型SFT全解析：从原理到工具链，解锁AI微调的核心密码

文章目录一. 什么是监督微调（SFT）？二. SFT的核心原理与流程2.1 基本原理2.2 训练流程三、SFT训练的常用方法四、SFT训练用的数据格式4.1、基础单轮指令格式1. Alpaca 格式2. 单轮QA格式3. 代码-注释对4.2、多轮对话格式1. ShareGPT 格式2. 层次化对话格式3. 角色扮演对话4.…...

编程日记 2025/6/28 22:08:53

MacBook Air A2179（Intel版）安装macOS Catalina所需时间

MacBook Air A2179（Intel版）安装macOS Catalina所需时间如下： 一、标准安装时间范围常规安装（通过App Store） • 下载时间：约30-60分钟（取决于网络速度，安装包约8GB） •…...

编程日记 2025/6/29 1:32:04

Git的windows开发与linux开发配置

Git的基本配置安装 linux可以使用包管理器安装windows可以使用 mingw的git：https://git-scm.com/downloadsTortoiseGit：https://tortoisegit.org/download/ 配置分为系统配置–system、全局配置–global、项目配置–local 配置名称和邮箱 git co…...

编程日记 2025/6/28 21:58:22

使用Mathematica绘制一类矩阵的特征值图像

学习过线性代数的，都知道：矩阵的特征值非常神秘，但却携带着矩阵的重要信息。今天，我们将展示：一类矩阵，其特征值集体有着很好的分布特征。 modifiedroots[c_List] : Block[{a DiagonalMatrix[ConstantAr…...

编程日记 2025/6/28 23:26:14

C++中的宏

0 资料最值宏do{}while(0)的宏封装技巧 1 最值宏 - C最值的宏，在两个头文件中，分别为cfloat和climits。其中，float的最值宏在cfloat中，且cfloat没有负值的最小宏，而其他char、int和double是在climits中。如下// --…...

编程日记 2025/6/29 0:41:07

谷粒商城的三级分类实现

先查出全部的数据再分类分类的一级分类是根据数据的Parent_id进行确定的，所以要进行筛选： 主方法： public List<CategoryEntity> listWithTree() {//1.查出所有分类List<CategoryEntity> entities baseMapper.selectList(nul…...

编程日记 2025/6/29 0:42:13

基于大模型预测的闭合性髌骨骨折诊疗全流程研究报告

目录一、引言 1.1 研究背景与目的 1.2 研究意义与价值二、大模型预测原理与方法 2.1 大模型概述 2.2 预测方法与数据输入 2.3 模型训练与优化三、术前预测分析 3.1 骨折类型预测 3.2 损伤程度评估 3.3 潜在风险预测四、手术方案制定 4.1 传统手术方案对比 4.…...

编程日记 2025/6/28 21:57:50

基于CodeBuddy的Craft完成一个数字华容道的小游戏

参考 CodeBuddy，AI 时代的智能编程伙伴插件功能入门总结本文主要基于CodeBuddy的Craft 完成一个数字华容道的小游戏，如果读者还不清楚怎么安装，在本文的前面附上了CodeBuddy 编程助手的安装步骤。读者可以根据需求自行确定从那开始。 …...

编程日记 2025/6/28 22:03:42

一文掌握vue3基础，适合自学入门案例丰富

Vue3 本文从Vue3的基础语法出发，全面系统的介绍了Vue3的核心概念与应用，旨在帮助自学者更轻松地掌握Vue3。文章内容由浅入深，从通过CDN引入Vue3开始，逐步介绍了组合式API、模块化开发、以及常见的Vue3指令和功能并从单个html的使…...

编程日记 2025/6/28 21:58:51

OpenHarmony 5.0设置应用设置手势导航开关打开后重新关闭导航栏和设置界面重合

目录 1.背景 2.解决方案 1.背景在OpenHarmony 5.0中从设置界面打开手势导航开关然后重新关闭，此时设置界面导航栏和设置列表主界面重合，导致设置界面无法点击最下面的关于设备 2.解决方案首先参考之前的如何设置导航栏文档，我们可以自己…...

编程日记 2025/6/28 23:30:29

[ARM][汇编] 02.ARM 汇编常用简单指令

目录 1.数据传输指令 MRS - Move from Status Register 指令用途指令语法代码示例读取 CPSR 到通用寄存器在异常处理程序中读取 SPSR 使用场景 MSR - Move to Status Register 指令语法使用场景示例代码改变处理器模式为管理模式设置条件标志位异常处理…...

编程日记 2025/6/28 22:17:35

系统架构设计（十七）：微服务数据一致性和高可用策略

数据一致性问题问题本质由于每个微服务拥有独立数据库，跨服务操作不能用传统的数据库事务，面临“分布式事务”一致性挑战。数据一致性策略策略核心思想应用场景优缺点强一致性（Strong Consistency）所有操作实时同步成功&a…...

编程日记 2025/6/29 0:03:22

获取屏幕宽度/屏幕高度/状态栏高度/导航栏高度/刘海高度/设备型号/系统版本号... DevicesUtil import window from ohos.window; import { common } from kit.AbilityKit; import display from ohos.display; import deviceInfo from ohos.deviceInfo; import i18n from ohos.…...

编程日记 2025/6/28 21:58:34

Python60日基础学习打卡D31

如何把一个文件，拆分成多个具有着独立功能的文件，然后通过import的方式，来调用这些文件？这样具有几个好处： 可以让项目文件变得更加规范和清晰可以让项目文件更加容易维护，修改某一个功能的时候&#xff0…...

编程日记 2025/6/28 21:57:58

命名常量集合接口INamedConstantCollection＜T＞实现

public interface INamedConstantCollection<TObject, TName> : IEnumerable<TObject>, IEnumerable where TName : IComparable{TObject this[TName name] { get; }TObject this[int index] { get; }int Count { get; }int Capacity { get; }} 这是一个泛型接口&…...

编程日记 2025/6/28 21:58:02

TYUT-企业级开发教程-第6章

这一章考点不多什么是缓存？为什么要设计出缓存？ 企业级应用为了避免读取数据时受限于数据库的访问效率而导致整体系统性能偏低，通常会在应用程序与数据库之间建立一种临时的数据存储机制，该临时存储数据的区域称为缓存。缓存…...

编程日记 2025/6/28 21:57:47

反射在spring boot自动配置的应用

目录一，背景二，知识回顾 2.1 理解使用反射技术，读取配置文件创建目标对象（成员变量，方法，构造方法等） 三，springboot自动配置 3.1 反射在自动配置中的工作流程 3.2 浏览源码…...

编程日记 2025/6/28 21:57:48

项目进度延误，如何按时交付？

项目进度延误可以通过加强计划管理、优化资源分配、强化团队沟通、设置关键里程碑和风险管理机制等方式来实现按时交付。加强计划管理、优化资源分配、强化团队沟通、设置关键里程碑、风险管理机制。其中，加强计划管理尤为关键，因为明确而详细的计划能提…...

编程日记 2025/6/29 0:44:14

内网穿透：轻松实现外网访问本地服务

异步通知的是需要通过外网的域名地址请求到的，由于我们还没有真正上线，那支付平台如何请求到我们本地服务的呢？ 这里可以使用【内网穿透】技术来实现，通过【内网穿透软件】将内网与外网通过隧道打通，外网可以读取内网…...

编程日记 2025/6/29 0:53:11

缺乏进度跟踪机制，如何掌握项目状态？

要有效掌握项目状态，必须建立明确的进度跟踪机制、使用专业的项目管理工具、定期召开沟通会议、设立清晰的关键里程碑和实施风险监控。其中，建立明确的进度跟踪机制是关键，通过系统地追踪项目各个阶段的完成情况，及时发现问题并采…...

编程日记 2025/6/29 1:28:05

ES 调优帖：关于索引合并参数 index.merge.policy.deletePctAllowed 的取值优化

最近发现了 lucene 9.5 版本把 merge 策略的默认参数改了。 * GITHUB#11761: TieredMergePolicy now allowed a maximum allowable deletes percentage of down to 5%, and the defaultmaximum allowable deletes percentage is changed from 33% to 20%. (Marc DMello)也就是…...

编程日记 2025/6/28 22:09:29

基于 STM32 单片机的实验室多参数安全监测系统设计与实现

一、系统总体设计本系统以 STM32F103C8T6 单片机为核心，集成温湿度监测、烟雾检测、气体泄漏报警、人体移动监测等功能模块，通过 OLED 显示屏实时显示数据，并支持 Wi-Fi 远程传输。系统可对实验室异常环境参数（如高温、烟雾、燃气泄漏）及非法入侵实时报警，保障实验室安…...

编程日记 2025/7/5 10:24:11

Spring Boot-Swagger离线文档(插件方式）

Swagger2Markup简介 Swagger2Markup是Github上的一个开源项目。该项目主要用来将Swagger自动生成的文档转换成几种流行的格式以便于静态部署和使用，比如：AsciiDoc、Markdown、Confluence。项目主页：https://github.com/Swagger2Markup/swagg…...

编程日记 2025/6/28 22:23:17

Linux下Docker使用阿里云镜像加速器

在中国大陆环境中配置 Docker 使用阿里云镜像加速器，并确保通过 Clash 代理访问 Docker Hub 我这里用的Debian12。步骤 1：获取阿里云镜像加速器地址登录阿里云容器镜像服务控制台：(qinyang.wang) 网址：阿里云登录 - 欢迎登录阿…...

编程日记 2025/6/28 21:59:14

每日c/c++题备战蓝桥杯（洛谷P1440 求m区间内的最小值详解（单调队列优化））

洛谷P1440 求m区间最小值：单调队列优化详解（从暴力到O(n)的蜕变） tags: [算法, 数据结构, 滑动窗口, 洛谷, C] 引言在处理序列数据的区间查询问题时，暴力枚举往往难以应对大规模数据。本文以洛谷P1440为切入点，深入…...

编程日记 2025/6/28 22:03:55

从代码学习深度学习 - 预训练word2vec PyTorch版

文章目录前言辅助工具1. 绘图工具 (`utils_for_huitu.py`)2. 数据处理工具 (`utils_for_data.py`)3. 训练辅助工具 (`utils_for_train.py`)预训练 Word2Vec - 主流程1. 环境设置与数据加载2. 跳元模型 (Skip-gram Model)2.1. 嵌入层 (Embedding Layer)2.2. 定义前向传播3. 训练…...

编程日记 2025/7/5 2:54:27

OpenCV图像边缘检测

1.概念图像边缘检测是计算机视觉和图像处理中的基础任务，用于识别图像中像素值发生剧烈变化的区域，这些区域通常对应物体的边界、纹理变化或噪声。 1.1原理图像中的边缘通常表现为灰度值的突变（如从亮到暗或从暗到亮的急剧变化&#xff09…...

编程日记 2025/6/29 0:26:10

AI能源危机：人工智能发展与环境可持续性的矛盾与解决之道

AI对能源的渴求正在演变成一个巨大的挑战。这不仅仅关乎电费支出，其环境影响也十分严重，包括消耗宝贵的水资源、产生大量电子垃圾，以及增加温室气体排放。随着AI模型变得越来越复杂并融入我们生活的更多领域，一个巨大的问题悬而…...

编程日记 2025/6/28 23:39:20

基于flask+vue的电影可视化与智能推荐系统

基于flaskvue爬虫的电影数据的智能推荐与可视化系统，能展示电影评分、评论情感分析等直观的数据可视化图表，还能通过协同过滤算法为用户提供个性化电影推荐，帮助用户发现更多感兴趣的电影作品，具体界面如图所示。本系统主要技术架…...

编程日记 2025/6/28 21:57:56

初步认识HarmonyOS NEXT端云一体化开发

视频课程学习报名入口：HarmonyOS NEXT端云一体化开发 1、课程设计理念本课程采用"四维能力成长模型"设计理念，通过“能看懂→能听懂→能上手→能实战”的渐进式学习路径，帮助零基础开发者实现从理论认知到商业级应用开发的跨越。该模型将学习过程划分为四个维度…...

编程日记 2025/6/28 22:09:43

基于单片机的车辆防盗系统设计与实现

标题:基于单片机的车辆防盗系统设计与实现内容:1.摘要随着汽车保有量的不断增加，车辆被盗问题日益严峻，车辆防盗成为人们关注的焦点。本研究的目的是设计并实现一种基于单片机的车辆防盗系统。采用单片机作为核心控制单元，结合传感器技术、…...

编程日记 2025/6/29 0:41:34

LSM Tree算法原理

LSM Tree（Log-Structured Merge Tree）是一种针对写密集型场景优化的数据结构，广泛应用于LevelDB、RocksDB等数据库引擎中。其核心原理如下： ‌1. 写入优化：顺序写代替随机写‌ ‌内存缓冲（MemTable）‌：写入操作首先被写入内存中的数据结构（如跳表或平衡树），…...

编程日记 2025/6/28 21:57:51

通过 API 获取 1688 平台店铺所有商品信息的完整流程

在电商运营和数据分析中，获取 1688 平台店铺的商品信息是一项重要的任务。1688 作为国内领先的 B2B 电商平台，提供了丰富的开放平台 API 接口，方便开发者获取店铺商品的详细信息。本文将详细介绍如何通过 Python 调用 1688 的 API 接口&#…...

编程日记 2025/6/28 21:58:47

Python代码加密与发布方案详解

更多内容请见： python3案例和总结-专栏介绍和目录文章目录一、基础加密方案二、商业级加密方案三、高级混淆方案四、商业化发布方案五、反逆向技术六、最佳实践建议七、常见问题解决Python作为解释型语言，其源代码容易被查看和修改。本文将详细介绍多种Python代码保护方案，…...

编程日记 2025/6/29 0:47:46

Tractor S--二维转一维，然后最小生成树

P3073 [USACO13FEB] Tractor S - 洛谷转成一维点图，然后最小生成树，最后的最大值就是最后一个点，记得记录维护连通块同样的二维转一维---Cow Ski Area G---二维图转一维tarjan缩点-CSDN博客 #include<bits/stdc.h> using namespac…...

编程日记 2025/6/29 0:10:27

5月20日day31打卡

文件的规范拆分和写法知识点回顾规范的文件命名规范的文件夹管理机器学习项目的拆分编码格式和类型注解作业：尝试针对之前的心脏病项目，准备拆分的项目文件，思考下哪些部分可以未来复用。补充介绍： pyc文件的介绍知识点回顾 …...

编程日记 2025/6/28 21:57:52

基于Spring Boot + Vue的教师工作量管理系统设计与实现

一、项目简介随着高校信息化管理的发展，教师工作量管理成为教务系统中不可或缺的一部分。为此，我们设计并开发了一个基于 Spring Boot Vue 的教师工作量管理系统，系统结构清晰，功能完备，支持管理员和教师两个角色。…...

编程日记 2025/6/29 0:08:30

海康工业相机白平衡比选择器对应的值被重置后，如何恢复原成像

做项目的时候，有时候手抖，一不小心把一个成熟稳定的项目的相机配置，重置了，如何进行恢复呢，在不知道之前配置数据的情况下。我在做项目的时候，为了让这个相机成像稳定一点，尤其是做颜色检测时…...

编程日记 2025/7/7 6:17:54

VMWare清理后，残留服务删除方案详解

VMWare清理后，残留服务删除方案详解在虚拟化技术日益普及的今天，VMWare作为行业领先的虚拟化软件，广泛应用于企业和服务器的管理中。然而，由于其复杂的架构和深层次的系统集成，VMWare的卸载过程往往并不顺利。即使通…...

编程日记 2025/6/28 21:57:54

STM32定时器简单采集编码器脉冲

MCU：STM32H723ZGT6 编码器：（欧姆龙）E6B2-CWZ1X；1000P/R；8根线信号线分别为 A A- B B- Z Z- 以及5V和GND； A 脉冲输出 B 脉冲输出 Z 零点信号当编码器旋转到零点时，Z信号会发出一个脉…...

编程日记 2025/6/28 21:57:53

相关文章：