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

ARC142D Deterministic Placing

ARC142D Deterministic Placing

题目大意

有一棵nnn个顶点的树,每个点上最多放一张卡片,你可以做如下操作:

  • 同时将所有的卡片移到它所在顶点的相邻的一个顶点上

一个操作我们说它是好的,当下列条件满足:

  • 每条边最多被某张卡片经过
  • 每个顶点最多被一张卡片占据

TTT可以选择一个或多个顶点来放置卡片,一个顶点放置一张卡片。他有2n−12^n-12n1种方式,求满足以下条件的方案数:
对于每个非负整数kkk

  • 它能连续进行kkk次好的操作
  • SkS_kSk表示经过刚好kkk次操作后被卡片占据的点的集合,则SkS_kSk是唯一的

题解

第一步:分树为链

我们可以发现,每一张卡片都是在两个点上反复横跳的。我们把每个反复横跳的边拿出来,那一定是若干条不相交的链。且这些链一定是以空点为顶部,有卡片的点为中部和尾部(一条链不能只有一个空点)。这些链一定能填满整棵树。

假设x,yx,yx,y为相邻的两个点且在不同的链上,为了避免重复和不合法的情况,我们做一些规定。

  • 如果xxx链的端点且yyy为链的中间点,则在第二次操作时,在yyy上的卡片可以向xxx移动,则SkS_kSk不唯一
  • 如果x,yx,yx,y都是链的顶部,则第一次操作后两条链合并成一条链,可以往两个方向移动,SkS_kSk不唯一
  • 如果x,yx,yx,y都是链的尾部,则第一次操作时xxx的位置空出了,yyy所在可以往链头或xxx移动,SkS_kSk不唯一

其余情况都是合法的。


第二步:树形DP

定义fu,if_{u,i}fu,i表示点uuuiii种状态下的方案数。各种状态如下:

  • fu,0f_{u,0}fu,0表示uuu为链身,且uuu在链上无前无后
  • fu,1f_{u,1}fu,1表示uuu为链身,且uuu在链上有前无后
  • fu,2f_{u,2}fu,2表示uuu为链身,且uuu在链上无前有后
  • fu,3f_{u,3}fu,3表示uuu为链身,且uuu在链上有前有后
  • fu,4f_{u,4}fu,4表示uuu为链头,且uuu在链上无后面的点
  • fu,5f_{u,5}fu,5表示uuu为链头,且uuu在链上有后面的点
  • fu,6f_{u,6}fu,6表示uuu为链尾,且uuu在链上无后面的点
  • fu,7f_{u,7}fu,7表示uuu为链尾,且uuu在链上有后面的点

有前或有前面的点即存在链头,有后或有后面的点即存在链尾。

为了防止在转移的时候计算重复,我们还需要定义gu,ig_{u,i}gu,i。假设当前枚举的是uuu的各个儿子,且枚举到的儿子为vvv,则fu,if_{u,i}fu,i表示点uuu在统计vvv之前的各种状态的方案数,ggg表示统计vvv之后的方案数,则可以用fu,if_{u,i}fu,ifv,if_{v,i}fv,i来更新ggg,在vvv的贡献计算完之后再将ggg的值赋值给fff,然后计算uuu的下一个儿子。

因为状态比较多,所以转移式也比较多。除去不合法的情况,有202020种转移方法,具体见代码。

对于每个点,状态0,4,60,4,60,4,6fff的初值为111。最后的答案为f1,3+f1,5+f1,7f_{1,3}+f_{1,5}+f_{1,7}f1,3+f1,5+f1,7


总结

这道题主要是用树形DP,考虑各种状态来进行状态转移。时间复杂度为O(n)O(n)O(n)

注:代码中gt(v1,v2,v3)gt(v1,v2,v3)gt(v1,v2,v3)表示gu,v1=fu,v2×fv,v3g_{u,v1}=f_{u,v2}\times f_{v,v3}gu,v1=fu,v2×fv,v3vvvuuu的儿子。这一步即用uuu点的状态v2v2v2fffvvv点的状态v2v2v2fff值更新ggg的状态v1v1v1

code

#include<bits/stdc++.h>
using namespace std;
int n,x,y,tot=0,d[500005],l[500005],r[500005];
long long v[10],f[200005][8];
long long mod=998244353;
void add(int xx,int yy){l[++tot]=r[xx];d[tot]=yy;r[xx]=tot;
}
void pt(int v1,int v2,int v3){v[v1]=(v[v1]+f[x][v2]*f[y][v3]%mod)%mod;
}
void dfs(int u,int fa){f[u][0]=f[u][4]=f[u][6]=1;for (int i=r[u];i;i=l[i]){if(d[i]==fa) continue;dfs(d[i],u);for (int j=0;j<8;j++) v[j]=0;x=u;y=d[i];pt(0,0,3);pt(1,0,4);pt(1,0,1);pt(1,1,3);pt(2,0,6);pt(2,0,2);pt(2,2,3);pt(3,2,4);pt(3,1,6);pt(3,1,2);pt(3,2,1);pt(3,3,3);pt(4,4,7);pt(5,5,7);pt(5,4,2);pt(5,4,6);pt(6,6,5);pt(7,7,5);pt(7,6,1);pt(7,6,4);for(int j=0;j<8;j++) f[u][j]=v[j];}
}
int main()
{scanf("%d",&n);for(int i=1;i<n;i++){scanf("%d%d",&x,&y);add(x,y);add(y,x);}dfs(1,0);printf("%lld",(f[1][3]+f[1][5]+f[1][7])%mod);return 0;
}

相关文章:

ARC142D Deterministic Placing

ARC142D Deterministic Placing 题目大意 有一棵nnn个顶点的树&#xff0c;每个点上最多放一张卡片&#xff0c;你可以做如下操作&#xff1a; 同时将所有的卡片移到它所在顶点的相邻的一个顶点上 一个操作我们说它是好的&#xff0c;当下列条件满足&#xff1a; 每条边最…...

阶段八:服务框架高级(第二章:分布式事务)

阶段八&#xff1a;服务框架高级&#xff08;第二章&#xff1a;分布式事务&#xff09;Day-分布式事务0.学习目标1.分布式事务问题1.1.本地事务1.2.分布式事务1.3.演示分布式事务问题2.理论基础2.1.CAP定理2.1.1.一致性2.1.2.可用性2.1.3.分区容错2.1.4.矛盾2.2.BASE理论2.3.解…...

RPC异步化原理

深入RPC&#xff0c;更好使用RPC&#xff0c;须从RPC框架整体性能考虑问题。得知道如何提升RPC框架的性能、稳定性、安全性、吞吐量及如何在分布式下快速定位问题。RPC框架如何压榨单机吞吐量&#xff1f; 1 前言 TPS一直上不去&#xff0c;压测时CPU压到40%&#xff5e;50%就…...

C# 多窗口切换的实现

1、目的在主窗口中根据不同的按钮选择不同的子窗口显示。2、实现&#xff08;1&#xff09;、创建Winform窗体程序&#xff0c;放入SplitContainer控件splitContainer1将窗体分成左右2部分&#xff1b;&#xff08;2&#xff09;、在左侧splitContainer1.panel1中放入3个Button…...

【深度学习】RNN

1. 什么是RNN 循环神经网络&#xff08;Recurrent Neural Network, RNN&#xff09;是一类以序列&#xff08;sequence&#xff09;数据为输入&#xff0c;在序列的演进方向进行递归&#xff08;recursion&#xff09;且所有节点&#xff08;循环单元&#xff09;按链式连接的递…...

招聘岗位,机会难得

岗位需求 费话不多说&#xff0c;直接上JD&#xff1a; 嵌入式开发工程师&#xff1a; 17:411.计算机、通信等相关专业。 2.熟悉网络基础知识&#xff0c;熟悉802.11a/b/g/n/ac协议&#xff0c;能通过抓包等分析手段排查定位各种wifi相关问题。 3.熟悉路由器主要功能及实现原…...

web打印的几种方法(2023)

在工作中出现web打印的情况是非常多的&#xff0c;其实这也是一个比较烦人的问题&#xff0c;这篇博客整理一下关于Web打印的一些方法或者方式。 1. window.print() 这个方法是用来打印网页的&#xff0c;页面上的其他的元素也会被打印处理&#xff0c;在打印的时候页眉页脚是…...

代码随想录算法训练营day44 | 动态规划之完全背包 518. 零钱兑换 II 377. 组合总和 Ⅳ

day44完全背包基础知识问题描述举个栗子518. 零钱兑换 II1.确定dp数组以及下标的含义2.确定递推公式3.dp数组如何初始化4.确定遍历顺序5.举例推导dp数组377. 组合总和 Ⅳ1.确定dp数组以及下标的含义2.确定递推公式3.dp数组如何初始化4.确定遍历顺序5.举例来推导dp数组完全背包基…...

IntelliJ IDEA 实用插件推荐(包含使用教程)

IntelliJ IDEA 实用插件推荐 背景&#xff1a;电脑重装了&#xff0c;重新下载了最新版的IntelliJ IDEA&#xff0c;感觉默认模式有点枯燥&#xff0c;于是决定从网上下载一些实用美观的插件优化自己以后吃饭的工具&#xff0c;现在推荐的都是目前还能用的&#xff08;亲身实践…...

WideDeep模型

google提出的Wide&deep模型&#xff0c;将线性模型与DNN很好的结合起来&#xff0c;在提高模型泛化能力的同时&#xff0c;兼顾模型的记忆性。wide&deep这种将线性模型与DNN的并行连接模式&#xff0c;后来称为推荐领域的经典模式&#xff0c;奠定了后面深度学习模型的…...

nacos集群模式+keepalived搭建高可用服务

实际工作中如果nacos这样的核心服务停掉了或者整个服务器宕机了&#xff0c;那整个系统也就gg了&#xff0c;所以像这样的核心服务我们必须要搞个3个或者3个以上的nacos集群部署&#xff0c;实现高可用&#xff1b; 部署高可用版本之前&#xff0c;首先你要会部署单机版的naco…...

吉利「银河」负重突围

吉利控股集团最新公布的数据显示&#xff0c;2022年&#xff0c;吉利控股集团汽车总销量超230万辆&#xff0c;同比增长4.3%。其中&#xff0c;新能源汽车销量超64万辆&#xff0c;同比增长100.3%。 在中国本土市场&#xff0c;2022年吉利集团旗下品牌乘用车总交付量为135.84万…...

QT之图形视图框架概述——Graphics View Framework

QT之图形视图框架概述——Graphics View Framework1. 概述2. 核心类3. 事件传递4. Graphics View 坐标系统5. 参考1. 概述 Graphics View Framework是子Qt 4.2引入的&#xff0c;用来取代之前版本中的QCanvas。Graphics View Framework提拱了用于大量2D图形项的管理和交互的能…...

【SQL开发实战技巧】系列(二十二):数仓报表场景(上) 从分析函数效率一定快吗聊一聊结果集分页和隔行抽样实现方式

系列文章目录 【SQL开发实战技巧】系列&#xff08;一&#xff09;:关于SQL不得不说的那些事 【SQL开发实战技巧】系列&#xff08;二&#xff09;&#xff1a;简单单表查询 【SQL开发实战技巧】系列&#xff08;三&#xff09;&#xff1a;SQL排序的那些事 【SQL开发实战技巧…...

小米无线AR眼镜探索版细节汇总

在MWC 2023期间&#xff0c;小米正式发布了一款无线AR眼镜&#xff0c;虽然还没看过实机&#xff0c;但XDA提前上手体验&#xff0c;我们从中进行总结。首先我要说的是&#xff0c;小米这款眼镜和高通无线AR眼镜参考设计高度重叠&#xff0c;产品卖点几乎一致&#xff0c;只是增…...

Web3中文|Litra:简洁而优美的NFT流动性协议,能给NFT市场带来什么?

2021年&#xff0c;NFT元年2021年&#xff0c;无疑是 NFT 的“元年”。这一年推特创始人的首条推特被拍出250万美元&#xff0c;加密艺术家Beeple的数字作品“First 5000 Days”在佳士得以6900万美元价格成交&#xff0c;无聊猿最高上涨了1800倍。2021年11月&#xff0c;在Goog…...

SSL证书对虚拟主机的用处有哪些?

虚拟主机是指在同一台服务器上&#xff0c;通过不同的域名或IP地址为多个网站提供服务的一种网络主机。而SSL证书则是一种数字证书&#xff0c;它用于加密网站与用户之间的通信&#xff0c;确保数据传输的安全性和完整性。在虚拟主机上&#xff0c;SSL证书有以下几个用处&#…...

SpringCloud之MQ笔记分享

MQ异步通信 初始MQ 同步通信 优点&#xff1a;时效性较强&#xff0c;可以以及得到结果 Feign就属于同步方式–问题&#xff1a; 耦合问题性能下降&#xff08;中间的等待时间&#xff09;资源浪费级联失败 异步通信 优点 耦合度低性能提升&#xff0c;吞吐量高故障隔离…...

动态规划背包问题

背包问题的分类 拿到背包问题,最重要的是会归类到哪一种背包问题中,常见的考题里主要是01背包和完全背包,leetcode上连多重背包的题目都没有。实际完全背包问题就是01背包的一种。 对一和零这道题,很多人容易把m看成一个背包,n看成另一个背包,从而当做多重背包。然而这…...

OpenCV4.x图像处理实例-张嘴和闭嘴检测

张嘴和闭嘴检测 在活体验证中,张嘴和闭嘴检测也是一个重要的环节。本文将介绍如何通过检测人脸上唇和下唇的关键点,并计算上唇和下唇的关键点的距离来检测当前人脸状态是否处于张嘴或闭嘴。 张嘴和闭嘴检测主要步骤如下: 第一步,安装依赖库 示例中使用到OpenCV和MediaP…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...