CCPC-Wannafly Winter Camp Day8 (Div1, onsite) 题解+代码(ABEG)

2023-11-30 14:40

本文主要是介绍CCPC-Wannafly Winter Camp Day8 (Div1, onsite) 题解+代码(ABEG),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

比赛链接:(Onsite) (Online mirror)

A. Aqours(13 通过,已补题)

其实就是一个挺简单的树上问题。。。当时没时间看这道题,血亏。。。但是需要注意,这道题输入量高达$3 \cdot 10^6$,最好使用快读,不然很可能被卡常数。

出题人题解:给出的点可以视为是按照 BFS 序给的,也就是说从浅到深给出。可以再给每个节点 u 维护一个 f_u 值, 表示离 u 最近的叶子节点到它的距离。所以每当扫到一个叶子节点,就可以暴力往根节点跳,边跳边更新 f 值,直到跳到一个已被其他叶子节 点跳到过的节点为止。 那么对于当前的叶子节点,离它最近的编号小于它的叶子节点到它的距离就是跳到这个终止节点的 f 值 +跳的步数。 在求完之后,还要从上述的终止节点沿着原路更新一下 f 值,因为可能当前叶子比较深但之前有比较浅 的叶子节点。 因为点是按从浅到深的顺序给出,所以一个节点的 f 值只会被最先跳到它的叶子节点赋值一次,也只会被更新一次,所以复杂度是 O(n) 的。

Status: 已补题(2019-01-29)


#include<bits/stdc++.h>
#define rep(i, n) for(int i = 1; i <= n; ++i)
using namespace std;
typedef long long ll;const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)template<typename T> void read(T &x){x = 0; int f = 1; char ch = gc();while(!isdigit(ch) ) { if(ch == '-') f = -1; ch = gc();}while( isdigit(ch) ) {x = x * 10 + ch - 48; ch = gc();}x *= f;
}const int MAXN = 100200;
int fa[MAXN], n, f[MAXN], root = 1;
vector<int> G[MAXN], leaf;inline void link(int x, int y) {G[x].push_back(y);G[y].push_back(x);
}int main() {memset(f, -1, sizeof f);read(n);if(n == 1) { puts("1 -1"); return 0; }for(int i = 2; i <= n; ++i)read(fa[i]), link(i, fa[i]);for(int i = 2; i <= n; ++i) if(G[i].size() == 1u) leaf.push_back(i);for(auto v : leaf) {int p = v, cnt = -1;printf("%d ", v);while(p != root && f[p] == -1)f[p] = ++cnt, p = fa[p];if(p == root && f[p] == -1) {f[p] = ++cnt;puts("-1");} else {printf("%d\n", cnt + f[p] + 1);}f[p] = min(f[p], cnt + 1);int to = p, cur = cnt + f[p] + 1; p = fa[v];while(p != to) {f[p] = min(f[p], --cur);p = fa[p];}}return 0;
}

 

B. 玖凛两开花(34 通过,场上AC)

要求的是一个最小值的最大,很容易联想到二分。假设答案是x,则0, 1, ..., x - 1这些数一定要被匹配,显然有贪心结论:0, 1, ..., x - 1之间一定不能连边。那么把0, 1, ..., x - 1放在一边,x, x + 1, ..., n - 1放在另一边,跑最大匹配,这就是一个二分图匹配问题,可以用Dinic解决。复杂度

这篇关于CCPC-Wannafly Winter Camp Day8 (Div1, onsite) 题解+代码(ABEG)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:https://blog.csdn.net/qq_41255467/article/details/86696224
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/437421

相关文章

深入解析 Java Future 类及代码示例

《深入解析JavaFuture类及代码示例》JavaFuture是java.util.concurrent包中用于表示异步计算结果的核心接口,下面给大家介绍JavaFuture类及实例代码,感兴... 目录一、Future 类概述二、核心工作机制代码示例执行流程2. 状态机模型3. 核心方法解析行为总结:三

python获取cmd环境变量值的实现代码

《python获取cmd环境变量值的实现代码》:本文主要介绍在Python中获取命令行(cmd)环境变量的值,可以使用标准库中的os模块,需要的朋友可以参考下... 前言全局说明在执行py过程中,总要使用到系统环境变量一、说明1.1 环境:Windows 11 家庭版 24H2 26100.4061

pandas实现数据concat拼接的示例代码

《pandas实现数据concat拼接的示例代码》pandas.concat用于合并DataFrame或Series,本文主要介绍了pandas实现数据concat拼接的示例代码,具有一定的参考价值,... 目录语法示例:使用pandas.concat合并数据默认的concat:参数axis=0,join=

C#代码实现解析WTGPS和BD数据

《C#代码实现解析WTGPS和BD数据》在现代的导航与定位应用中,准确解析GPS和北斗(BD)等卫星定位数据至关重要,本文将使用C#语言实现解析WTGPS和BD数据,需要的可以了解下... 目录一、代码结构概览1. 核心解析方法2. 位置信息解析3. 经纬度转换方法4. 日期和时间戳解析5. 辅助方法二、L

Python使用Code2flow将代码转化为流程图的操作教程

《Python使用Code2flow将代码转化为流程图的操作教程》Code2flow是一款开源工具,能够将代码自动转换为流程图,该工具对于代码审查、调试和理解大型代码库非常有用,在这篇博客中,我们将深... 目录引言1nVflRA、为什么选择 Code2flow?2、安装 Code2flow3、基本功能演示

IIS 7.0 及更高版本中的 FTP 状态代码

《IIS7.0及更高版本中的FTP状态代码》本文介绍IIS7.0中的FTP状态代码,方便大家在使用iis中发现ftp的问题... 简介尝试使用 FTP 访问运行 Internet Information Services (IIS) 7.0 或更高版本的服务器上的内容时,IIS 将返回指示响应状态的数字代

MySQL 添加索引5种方式示例详解(实用sql代码)

《MySQL添加索引5种方式示例详解(实用sql代码)》在MySQL数据库中添加索引可以帮助提高查询性能,尤其是在数据量大的表中,下面给大家分享MySQL添加索引5种方式示例详解(实用sql代码),... 在mysql数据库中添加索引可以帮助提高查询性能,尤其是在数据量大的表中。索引可以在创建表时定义,也可

使用C#删除Excel表格中的重复行数据的代码详解

《使用C#删除Excel表格中的重复行数据的代码详解》重复行是指在Excel表格中完全相同的多行数据,删除这些重复行至关重要,因为它们不仅会干扰数据分析,还可能导致错误的决策和结论,所以本文给大家介绍... 目录简介使用工具C# 删除Excel工作表中的重复行语法工作原理实现代码C# 删除指定Excel单元

Python实现一键PDF转Word(附完整代码及详细步骤)

《Python实现一键PDF转Word(附完整代码及详细步骤)》pdf2docx是一个基于Python的第三方库,专门用于将PDF文件转换为可编辑的Word文档,下面我们就来看看如何通过pdf2doc... 目录引言:为什么需要PDF转Word一、pdf2docx介绍1. pdf2docx 是什么2. by

Spring Security介绍及配置实现代码

《SpringSecurity介绍及配置实现代码》SpringSecurity是一个功能强大的Java安全框架,它提供了全面的安全认证(Authentication)和授权(Authorizatio... 目录简介Spring Security配置配置实现代码简介Spring Security是一个功能强