新闻详情

新闻详情

首页 / 资讯中心 / 详情

P17406 【MX-X31-T2】「FAOI-R14」警察抓小偷

发布时间:2026/11/17 3:48:06来源:尧图网络
P17406 【MX-X31-T2】「FAOI-R14」警察抓小偷
进食后入题目没有保证连通思路题目中每个点都有且只有一条连向其它点的单向边那么整张图是一棵基环树。题目的要求就是每个点有且仅有一条出边所以基环树属于基环内向树。因此所有的警察最终全部会移动到环上。由于小偷可以不移动所以叶子结点上都必须布置警察。由于叶子结点上全都布置了警察所以小偷最终必定会被逼到环上。那么是不是在叶子结点和环上全部布置警察就行了可行但不是最优。很容易发现若环上一开始就布置满警察那么经过足够的步数后必定有叶子结点的警察走到环上并且与环上的警察重叠。这样就造成了浪费。所以环上的每个点我们可以记录一下若一开始就在这里布置一个警察xxx有哪些点布置的警察最终会与警察xxx重叠。那么为什么会有多种情况呢有两种情况。第一种如上图选取两个点中的任意一个都可满足条件。第二种题目中对于wiw_iwi​的规定是0≤wi≤1090\le w_i\le10^90≤wi​≤109存在代价为零的情况。因此在选好一个方案后剩下的代价为 0 的点都可以选或不选。最终的实现先找环然后计算每个非环点会与环上的哪个警察重叠我写的是倍增最后计算答案和方案。code#includebits/stdc.h#defineintlonglong//#define lc p1//#define rc p1|1#defineendlputchar(\n)#definepspputchar( )usingnamespacestd;typedefunsignedlonglongull;typedeflonglongll;constintN1e65;constintmod998244353;intread(){intx0,f1;charcgetchar();while(c0||c9){if(c-)f-1;cgetchar();}while(c0c9)x(x3)(x1)c-0,cgetchar();returnx*f;}voidprint(intx){if(x0)putchar(-),x-x;if(x10){putchar(x0);return;}print(x/10);putchar(x%100);}voidputstr(string s){for(inti0;is.size();i)putchar(s[i]);}intlowbit(intx){returnx-x;}intn,m,k;intT;intw[N];vectorinta[N];intvis[N];vectorinthas[N];inton[N];intd[N];intleaf[N];intdis[N];intnex[21][N];voidxfs(intfa,intx){nex[0][x]fa;if(vis[x])return;vis[x]1;for(inti0;ia[x].size();i){intya[x][i];xfs(x,y);}}intto[N];voidzfs(intx){if(vis[x])return;vis[x]1;for(inti0;ia[x].size();i){intya[x][i];zfs(y);dis[x]min(dis[x],dis[y]1);to[x]to[y];}}intdont[N];signedmain(){//ios::sync_with_stdio(0);Tread();while(T--){nread();for(inti1;in;i)a[i].clear(),has[i].clear(),on[i]1,leaf[i]0,dis[i]1e9,vis[i]0,nex[0][i]0,to[i]0,dont[i]0;for(inti1;in;i)d[i]0;for(inti1;in;i)w[i]read();for(inti1;in;i){intxread();d[x];a[i].push_back(x);}//找环queueintq;for(inti1;in;i)if(d[i]0)q.push(i),on[i]0,leaf[i]1;while(!q.empty()){intxq.front();q.pop();for(inti0;ia[x].size();i){intya[x][i];if(--d[y]0){on[y]0;q.push(y);}}}for(inti1;in;i){if(on[i]){dis[i]0;}}intans0;for(inti1;in;i)if(leaf[i])answ[i];//叶子必选for(inti1;in;i){if(on[i]!vis[i]){xfs(i,i);}}for(intlen1;len20;len){for(inti1;in;i){if(!on[i])continue;to[i]i;nex[len][i]nex[len-1][nex[len-1][i]];}}for(inti1;in;i){if(!vis[i]){zfs(i);}}for(inti1;in;i){//存储会与当前警察重合的警察if(on[i]){has[i].push_back(i);}else{intonlto[i];inttimdis[i];for(intlen20;len0;len--){if((1len)tim){tim-(1len);onlnex[len][onl];}}if(leaf[i])dont[onl]1;//由于叶子必选所以对应的环上点可以不选elsehas[onl].push_back(i);}}inttot1;for(inti1;in;i){if(!on[i])continue;if(dont[i]){for(intj0;jhas[i].size();j){//处理 0 的情况intyhas[i][j];if(w[y]0)(tot*2)%mod;}}else{intmul1;for(intj0;jhas[i].size();j){intyhas[i][j];if(w[y]0)(mul*2)%mod;}if(mul!1){(tot*(mul-1)%mod)%mod;//每个 0 都可以选或不选但是不能全不选}else{mul0;intmn1e18;//由于需要最优所以只能在最小值里面选for(intj0;jhas[i].size();j){intyhas[i][j];mnmin(mn,w[y]);}ansmn;for(intj0;jhas[i].size();j){intyhas[i][j];if(mnw[y]){mul;}}(tot*(mul)%mod)%mod;}}}print(ans),psp,print((tot%modmod)%mod),endl;}}
网站建设高端定制企业官网
RELATED

相关资讯

更多精彩内容,欢迎继续阅读

较早相关资讯

最新相关资讯

【外设】之大彩串口显示屏 2026/11/15 4:54:16

【外设】之大彩串口显示屏

大彩串口屏初步使用 1 .官网下载 STM32 屏幕 GUI 设计资料 http://www.gz-dc.com/category/typeid/4112 找到 STM32 Keil 工程,移植相关代码因项目而异进行移植,由于项目简单,本人只对用到的指令接口进行修改。 比如:注意事项&…

阅读更多 →
无法下载Windows系统iso文件 2026/11/15 2:04:12

无法下载Windows系统iso文件

当我遇到这个问题的时候,我打开了一个网站: 登录 然后我打算下载的时候: 突然那个官方的连接就可以下载了:

阅读更多 →
【清华代码熊】DeepSeek V4.1 Flash 后训练详解 2026/11/16 19:23:38

【清华代码熊】DeepSeek V4.1 Flash 后训练详解

📌 上期解析了 DeepSeek V4.1 Flash 模型架构改进,本期解析 DeepSeek V4.1 Flash 预训练/后训练技术: 🌟 预训练:45T 文本 多模态混合语料、直接训练 sparse attention(取消 DeepSeek V4 的 dense 冷启动&…

阅读更多 →
Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ... 2026/11/16 6:47:19

Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ...

文章主要内容和创新点 主要内容 本文聚焦于多模态大语言模型(MLLM)强化学习(RL)训练中的效率问题,提出了一个名为Shuffle-R1的框架。研究发现,当前RL训练存在两个关键缺陷: 优势值坍缩(Advantage Collapsing):批次中大多数优势值集中在零附近,导致有效梯度信号被淹…

阅读更多 →
PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction 2026/11/14 16:35:50

PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction

一、文章主要内容总结 本文聚焦于利用大型语言模型(LLMs)实现个人身份信息(PII)脱敏的研究,旨在解决传统脱敏方法(如基于规则的系统、领域特定命名实体识别(NER)模型)泛化能力差、跨格式/跨语境适应性弱的问题。 研究通过全面评估多种LLM架构(包括密集型LLM(D-LLM…

阅读更多 →
LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model 2026/11/16 17:28:18

LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model

文章主要内容和创新点 主要内容 本文聚焦于二进制图像-文本相关性评估任务(判断图像与文本“相关”或“不相关”),针对该任务中文本格式多样、相关性定义随场景变化等挑战,提出了基于多模态大语言模型(MLLM)的解决方案LLaVA-RE。 模型设计:LLaVA-RE基于LLaVA 1.5架构,…

阅读更多 →

今日资讯

本周资讯

本月资讯

看完文章仍有疑问?

联系尧图顾问,获取一对一建站咨询

立即免费咨询 📞 400-888-8888
📞 ✉