[NOIP 2022] 建造军营 题解
题目
P1 边双缩点
观察样例二,可以发现边双内的边可选可不选。由此考虑边双缩点,Tarjan 找桥即可,缩点后变成一棵树。
P2 设计状态
用最终合法答案形态截这颗树,设计 f u f_u fu 表示 u u u 子树内非空,且子树内军营到 u u u 的边均被保护的方案数。
P3 转移
为方便转移,记 g u g_u gu 表示 u u u 子树空的方案数,遍历 u u u 的儿子 v v v:
- v v v 不选,则 v v v 之前非空, f u × 2 × g v f_u \times 2\times g_v fu×2×gv。
- v v v 选, ( f u + g u ) × f v (f_u+g_u) \times f_v (fu+gu)×fv。
g u = ∏ ( 2 × g v ) g_u = \prod(2 \times g_v) gu=∏(2×gv)。
记 u u u 所在边双点数为 V u V_u Vu,边数为 E u E_u Eu。初值: f u = 2 V u + E u − 2 E u , g u = 2 E u f_u=2^{V_u+E_u}-2^{E_u},g_u=2^{E_u} fu=2Vu+Eu−2Eu,gu=2Eu。
P4 统计答案
假定只选 i i i 子树内的点,此时子树外的边均可选可不选。然而这样在 i i i 祖先处统计会重复计算 i i i 的贡献,强制不选 i → f a i i \to fa_i i→fai 这条边即可,其余子树外的边任意。
P5
#include <iostream>
#include <vector>
#define int long longusing namespace std;const int N = 5e5 + 5;
const int M = 1e6 + 5;
const int mod = 1e9 + 7;int n, m, pw[N + M];struct Edge{int to, nxt;
}e1[M << 1], e2[M << 1];int tot1 = 1, head1[N];
void add1(int u, int v)
{e1[++tot1] = {v, head1[u]}; head1[u] = tot1;
}int tot2 = 1, head2[N];
void add2(int u, int v)
{e2[++tot2] = {v, head2[u]}; head2[u] = tot2;
}int low[N], dfn[N], idx;
bool bridge[M << 1];
void Tarjan(int u, int from)
{low[u] = dfn[u] = ++idx;for(int i=head1[u]; i; i=e1[i].nxt){if((i ^ 1) == from) continue;int v = e1[i].to;if(!dfn[v]) // tree edge{Tarjan(v, i);low[u] = min(low[u], low[v]);if(low[v] >= dfn[v])bridge[i] = bridge[i ^ 1] = 1;}else low[u] = min(low[u], dfn[v]); // back edge}
}int cnt, belong[N], V[N], E[N];
void dfs0(int u)
{belong[u] = cnt, V[cnt] ++ ;for(int i = head1[u]; i; i = e1[i].nxt){int v = e1[i].to;if(belong[v] or bridge[i]) continue;dfs0(v);}
}int ans, siz[N], f[N], g[N];
void dfs(int u, int from)
{f[u] = pw[E[u]] * (pw[V[u]] - 1) % mod,g[u] = pw[E[u]], siz[u] = E[u];for(int i = head2[u]; i; i=e2[i].nxt){if((i ^ 1) == from) continue;int v = e2[i].to;dfs(v, i);siz[u] += siz[v] + 1;f[u] = f[u] * 2 * g[v] % mod + (f[u] + g[u]) * f[v] % mod; f[u] %= mod;g[u] *= 2 * g[v]; g[u] %= mod;}if(u == 1) ans += f[u], ans %= mod;else ans += f[u] * pw[m - siz[u] - 1] % mod, ans %= mod;
}signed main()
{cin >> n >> m;pw[0] = 1; for(int i=1; i<=m; i++) pw[i] = (pw[i-1] << 1) % mod;for(int i=1; i<=m; i++){int u, v;cin >> u >> v;add1(u, v); add1(v, u);}Tarjan(1, 0);for(int i=1; i<=n; i++){if(!belong[i]) ++ cnt, dfs0(i);}for(int i=2; i<=tot1; i++){int u = e1[i].to, v = e1[i ^ 1].to;if(belong[u] == belong[v]) E[belong[u]] ++ ;else add2(belong[u], belong[v]);}for(int i=1; i<=cnt; i++) E[i] >>= 1;dfs(1, 0);cout << ans;
}
相关文章:
[NOIP 2022] 建造军营 题解
题目 P1 边双缩点 观察样例二,可以发现边双内的边可选可不选。由此考虑边双缩点,Tarjan 找桥即可,缩点后变成一棵树。 P2 设计状态 用最终合法答案形态截这颗树,设计 f u f_u fu 表示 u u u 子树内非空,且子树…...
射频识别技术(RFID)在智能制造模具管理中的应用
背景介绍 模具是工业生产的核心装备,被誉为“工业之母”,广泛应用于机械、汽车、轻工、电子、化工、冶金、建材等各个行业,是制造加工企业的重要资产,然而,传统的人工纸质记录方式已无法满足模具管理的需求࿰…...
奖品定制经营商城小程序的作用是什么
奖品是激励人员团体很好的方式,也是荣誉象征,奖牌、奖杯、高端礼盒等,同时市场中团体非常多,其需求也是很多,尤其定制方面,就更是不用说。 对奖品定制企业来说,除了线下门店获客经营外…...
深度学习常用脚本总结
👨💻个人简介: 深度学习图像领域工作者 🎉工作总结链接:https://blog.csdn.net/qq_28949847/article/details/128552785 链接中主要是个人工作的总结,每个链接都是一些常用demo,…...
hive数据表创建
目录 分隔符 分区表 二级分区 分桶表 外部表 分隔符 CREATE TABLE emp( userid bigint, emp_name array<string>, emp_date map<string,date>, other_info struct<deptname:string, gender:string>) ROW FORMAT DELIMITED FIELDS TERMINATED BY \t COL…...
查看本机Arp缓存,以及清除arp缓存
查看Arp缓存目录 Windows 系统使用 winR,输入cmd 在命令窗口输入 arp -a 删除Arp缓存目录 在命令窗口输入 arp -d * 查看主机路由表...
Unity MRTK Hololens2眼动交互
/** ** UnityVersion : 2021.3.6f1* Description : 眼部交互基类* Author: * CreateTime : 2023-10-11 09:43:20* Version : V1.0.0* * */using System.Collections.Generic; using Microsoft.MixedReality.Toolkit.Input; using UnityEngine;namespace MRTKExtend.EyeTrackin…...
接口自动化测试 —— 协议、请求流程
一、架构 CRM客户关系管理系统 SAAS Software As A Service 软件即服务 PAAS Platform AS A Service 平台即服务 快速交付→ 快:自己去干、有结果、事事有回音、持续改进 单体架构——》垂直架构——》面向服务架构——》微服务架构(分布式…...
JDK安装详细教程
JDK安装详细教程 国内大多数使用的是1.8的版本,对于初学者来说这个版本很友善,不过由于我安装过了1.8,所以我这里演示JDK21 的安装,过程并无区别,只在下载时注意选择1.8版本。1.8就是JDK8. 文章目录 JDK安装详细教程一…...
vulnhub_Fowsniff靶机渗透测试
Fowsniff靶机 靶机地址:https://www.vulnhub.com/entry/fowsniff-1,262/ 文章目录 Fowsniff靶机信息收集web渗透密码碰撞POP3邮件服务器渗透获取权限权限提升靶机总结 信息收集 通过nmap扫描,靶机开放22 80 110 143端口,110是pop3邮件服务…...
FPGA面试题(3)
一.FPGA和CPLD区别 FPGA:现场可编程门阵列CPLD:复杂可编程逻辑器件 二.多位异步信号如何同步 单比特异步信号 慢时钟域->快时钟域:同步打拍快时钟域->慢时钟域:先拓展位宽再同步打拍 多比特异步信号 1.异步FIFO2.保持…...
Avalonia常用小控件Menu
1.项目下载地址:https://gitee.com/confusedkitten/avalonia-demo 2.UI库Semi.Avalonia,项目地址 https://github.com/irihitech/Semi.Avalonia 样式预览: axaml代码 : <UserControl xmlns"https://github.com/avalo…...
steam游戏服务器如何选择
steam游戏平台现在在国内市场很吃香,当我们自己开发的游戏想要上架steam我们需要准备什么,在选择服务器的时候我们又需要考虑哪些因素呢,该怎样选择一款适合自己游戏的服务器是很关键的。 Steam专用服务器通常是指由游戏开发商提供的服务器&…...
电脑技巧:推荐一款桌面整理神器TidyTabs
目录 1、软件简介 2、软件功能介绍 3、总结 1、软件简介 TidyTabs是一款Windows应用程序,它可以将多个打开的窗口整理成一个选项卡式的界面,使得用户可以更加方便地切换和管理不同的窗口。 TidyTabs可以将多个窗口整合到一个主窗口中,类似…...
git合并分支-IDEA
有1个主分支,我从主分支拉取过来了,数据然后改好了,现在想合并到主分支上,并且将主分支的内容更新到我的分支下。用git怎么操作? 1.将主分支(master)的内容合并到我的分支(master-shi)中 在我的分支下执行 git merge master ID…...
winscope使用方法
Ubuntu下Android T的winscope工具使用方法 1. 在Android的项目源码中,prebuilts/misc/common/winscope目录下 直接使用chrome浏览器打开文件winscope.html 2. 可能会提示adb问题 进入目录development/tools/winscope/adb_proxy,有文件winscope_proxy.…...
获取西华大学新闻网站信息(爬虫样例)
利用python的爬虫功能进行信息爬取,关键在于源码分析,代码相对简单。 1 源代码分析 访问网站,按下F12,进行元素查找分析。 2 代码实现 from requests import get from bs4 import BeautifulSoupdef getXhuNews(pageNum1):&qu…...
【Linux】https协议
文章目录 📖 前言1. 引入https协议2. 常见的加密方式2.1 对称加密:2.2 非对称加密:2.3 数据摘要&&数据指纹: 3. 对加密方式的探究3.1 只使用对称加密:3.2 只使用非对称加密:3.3 双方都使用非对称加…...
基于工业5G网关的工业机器人监测控制方案
随着智能制造、自动化生产的发展进步,工业机器人的身影越来越多地出现在工厂现场,成为新型无人化、智能化生产制造的中坚力量。 工业机器人的运行伴生着海量的数据采集、传输、分析和反馈执行,因此也需要高速、低延迟的5G网络,支撑…...
[Machine learning][Part4] 线性回归模型技巧
目录 正规方程法 梯度下降法 缩放特征 学习率选择 正规方程法 这种方法可以不多次迭代梯度下降函数就能得到w,b。但是缺点是在大量数据训练情况下效率较低,其次是这种算法仅仅在线性回归中实现了,并没有在其他模型中实现,因此,…...
JavaScript 中的 ES|QL:利用 Apache Arrow 工具
作者:来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗?了解下一期 Elasticsearch Engineer 培训的时间吧! Elasticsearch 拥有众多新功能,助你为自己…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...
第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...
从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...
自然语言处理——循环神经网络
自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元(GRU)长短期记忆神经网络(LSTM)…...
RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文全面剖析RNN核心原理,深入讲解梯度消失/爆炸问题,并通过LSTM/GRU结构实现解决方案,提供时间序列预测和文本生成…...
HubSpot推出与ChatGPT的深度集成引发兴奋与担忧
上周三,HubSpot宣布已构建与ChatGPT的深度集成,这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋,但同时也存在一些关于数据安全的担忧。 许多网络声音声称,这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...
从面试角度回答Android中ContentProvider启动原理
Android中ContentProvider原理的面试角度解析,分为已启动和未启动两种场景: 一、ContentProvider已启动的情况 1. 核心流程 触发条件:当其他组件(如Activity、Service)通过ContentR…...
