首页/新闻资讯/正文详情

打卡信奥刷题(3591)用C++实现信奥题 P11562 【MX-X7-T3】[LSOT-3] 寄存器

发布时间:2026/9/26 18:49:04 来源:云帆数科 栏目:资讯中心
打卡信奥刷题(3591)用C++实现信奥题 P11562 【MX-X7-T3】[LSOT-3] 寄存器
P11562 【MX-X7-T3】[LSOT-3] 寄存器题目背景原题链接https://oier.team/problems/X7D。这里不是 APIO所以这个题也不是让你手搓 CPU。题目描述有n nn个寄存器编号为1 ∼ n 1 \sim n1∼n。这些寄存器由n − 1 n-1n−1条带有开关的电线连接。为了保证交换信息的顺利保证每两个寄存器都可以通过若干条电线连接。初始时每个寄存器存储的信息都是0 00。小 H 每次可以独立地操纵所有电线的开关然后选择一个寄存器通电。若一个寄存器与一个通电的寄存器有开启的电线相连则这个寄存器也会通电。所有通电的寄存器都会反转存储的信息0 00会变成1 111 11会变成0 00。小 H 想让寄存器存储他想要的信息他希望你告诉他最少需要进行多少次通电。输入格式第一行一个正整数n nn表示寄存器个数。第二行n nn个非负整数a 1 , … , a n a_1, \ldots, a_na1​,…,an​表示小 H 希望寄存器i ii存储a i a_iai​。保证a i a_iai​为0 00或1 11。接下来n − 1 n - 1n−1行每行两个正整数u , v u, vu,v表示寄存器u uu和v vv之间有一根电线。保证每两个寄存器都可以通过若干条电线连接。输出格式仅一行一个非负整数表示最少进行多少次通电。输入输出样例 #1输入 #15 1 0 0 1 0 1 2 2 3 2 4 3 5输出 #12输入输出样例 #2输入 #215 1 0 0 0 0 1 0 1 1 1 0 0 1 1 0 10 2 1 7 1 5 9 7 14 2 4 11 6 5 9 15 4 5 5 3 5 14 13 5 5 8 5 12输出 #24说明/提示【样例解释 #1】先将电线( 1 , 2 ) (1, 2)(1,2)关闭其余开启给寄存器1 11通电此时1 11的信息翻转所有寄存器存储的信息变为1 0 0 0 0。然后将电线( 2 , 4 ) (2, 4)(2,4)关闭其余开启给寄存器4 44通电此时4 44的信息翻转所有寄存器存储的信息变为1 0 0 1 0满足要求。可以证明不存在更优的方案。【数据范围】本题采用捆绑测试。子任务 120 分n ≤ 5 n\le 5n≤5。子任务 220 分对于第i ii根电线u i uiuiv i 1 vi1vi1。子任务 330 分不存在一对相邻的寄存器希望储存的信息相同。子任务 430 分无特殊性质。对于全部的数据1 ≤ n ≤ 10 6 1\le n\le 10^61≤n≤1061 ≤ u , v ≤ n 1\le u,v\le n1≤u,v≤n0 ≤ a i ≤ 1 0 \le a_i \le 10≤ai​≤1每两个寄存器都可以通过若干条电线连接。C实现#includebits/stdc.h#defineintlonglongusingnamespacestd;intn;inta[1000005]{114514};vectorintadj[1000005];intmaxp,maxd;voiddfs(intcur,intpar,intdeep){if(a[cur]!a[par])deep;if(a[cur]1deepmaxd){maxddeep;maxpcur;}for(inti:adj[cur])if(i!par)dfs(i,cur,deep);}signedmain(){ios::sync_with_stdio(0);cin.tie(nullptr);cinn;boolnoonetrue;// 特判一波全为0for(inti1;in;i){cina[i];if(a[i]1)noonefalse;}if(noone){cout0;return0;}for(inti1;in;i){intu,v;cinuv;adj[u].push_back(v);adj[v].push_back(u);}dfs(1,0,0);maxd0;dfs(maxp,0,0);cout(maxd1)/2;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容

相关推荐

基于Codex与Agent Toolkit的论文PDF知识库构建:从解析到问答
基于Codex与Agent Toolkit的论文PDF知识库构建:从解析到问答

1. 论文PDF知识库的构建思路与整体设计1.1 为什么我要做这件事手里攒了几百篇论文PDF,这个状态大概持续了两年多。每次写综述或者找某个具体方法的时候,我都要打开一个个PDF,用CtrlF搜关键词,搜不到就换个词再搜,有时候… · 2026/9/26 18:48:37

AI Agent从工具调用到自主决策:架构拆解与工程落地实战
AI Agent从工具调用到自主决策:架构拆解与工程落地实战

1. 从"会说话"到"会办事":AI Agent到底跨过了哪道坎如果你在过去两年里持续关注大模型领域,应该能明显感觉到一个分水岭:2024年之前,大家比拼的是"模型能不能答对题";到了2025年下半年&… · 2026/9/26 18:48:37

PG Loss与VF Loss深度解耦:强化学习工程落地的核心范式
PG Loss与VF Loss深度解耦:强化学习工程落地的核心范式

1. 为什么必须把 PG Loss 和 VF Loss 拆开讲透——不是“两个损失加起来”,而是两种思维范式的碰撞 在强化学习的实战圈里,我见过太多人把 Actor-Critic 当成一个“黑盒网络结构”来用:搭好 actor 网络输出动作、critic 网络输出状态价值&… · 2026/9/26 18:48:31

《代码随想录》刷题打卡day41:单调栈-part01
《代码随想录》刷题打卡day41:单调栈-part01

文章目录【739.每日温度】1. 怎么能想到用单调栈呢? 什么时候用单调栈呢?2. 那么单调栈的原理是什么呢?为什么时间复杂度是O(n)就可以找到每一个元素的右边第一个比它大的元素位置呢?3. 在使用单调栈的时候首先要明确如下几点&… · 2026/9/26 19:32:55

国企转大模型:模型进不了公网,能力要求反而更清楚
国企转大模型:模型进不了公网,能力要求反而更清楚

版权与内容来源声明 本文为原创整理。文中涉及官方文档、开源仓库、论文与公开报道的内容,均在附表 A 中标注来源;引用官方原文保持原样,不作改写。文中命令、版本号与界面截图以本文成文时的实测/核验结果为准,标注「待验证」的部… · 2026/9/26 19:32:49

监控器芯片选型与实战:从复位阈值到看门狗电路避坑指南
监控器芯片选型与实战:从复位阈值到看门狗电路避坑指南

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/26 19:32:36

数据库课后习题答案(第四版)PDF:SQL Server实操验证与自动化脚本
数据库课后习题答案(第四版)PDF:SQL Server实操验证与自动化脚本

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/26 19:32:36

AI coding工具数据安全实测:Zcode、Agent与Skill架构解析
AI coding工具数据安全实测:Zcode、Agent与Skill架构解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/26 19:32:36

图书管理系统MySQL数据库设计实战:五张核心表与索引优化
图书管理系统MySQL数据库设计实战:五张核心表与索引优化

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/26 19:32:30

数据库课后习题答案别硬背:当测试用例集刷,效率翻倍
数据库课后习题答案别硬背:当测试用例集刷,效率翻倍

简介:万常选版《数据库原理与设计》课后习题答案资源,覆盖第2至6章及第9章,适合正在学习关系模型、数据库建模、关系数据理论与模式求精的本科生、自学者作为复习与自测材料。压缩包共7个文件,含3个doc参考答案、2个sql示例脚本、… · 2026/9/26 0:00:21

OpenClaw 替代品?Hermes Agent 踩坑实录:macOS 飞书接入 TaoToken 配置
OpenClaw 替代品?Hermes Agent 踩坑实录:macOS 飞书接入 TaoToken 配置

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/26 0:00:40

向下兼容与向上兼容:接口设计中的兼容性策略与工程实践
向下兼容与向上兼容:接口设计中的兼容性策略与工程实践

一次版本升级事故,是很多团队绕不过去的坎。线上环境里,服务端明明已经上线了新版接口,老的移动端还在照着旧文档传参数。请求一到网关,校验直接拒绝,用户操作失败,客服群炸了锅,开发群里开始互… · 2026/9/26 0:00:46

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码