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

HBCPC2025 补题（F、I)

news 来源：原创 2025/7/7 11:13:09

HBCPC2025 补题

补题连接:Codeforces

I 感染

做法1：std做法：树上dp统计贡献找最大

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define int long long
#define pb push_back
#define pii pair<int,int>
#define FU(i, a, b) for(int i = (a); i <= (b); ++ i)
#define FD(i, a, b) for(int i = (a); i >= (b); -- i)
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const int maxn= 5e5+5,MAXN = maxn;int n;
vector<int> G[maxn];
int s[maxn];
int f[maxn];
int dep[maxn];
int sum1=0;void dfs1(int x,int fa){dep[x]=dep[fa]+1;for(int e:G[x]){if(e==fa)continue;dfs1(e,x);s[x]+=s[e];}
}void dfs2(int x,int fa){for(int e:G[x]){if(e==fa)continue;f[e]=f[x]+sum1-2*s[e];dfs2(e,x);}
}void solve() {cin>>n;sum1=0;memset(f,0,sizeof(f));for(int i=1;i<=n;i++){G[i].clear();}for(int i=1;i<n;i++){int u,v;cin>>u>>v;G[u].pb(v);G[v].pb(u);}for(int i=1;i<=n;i++){s[i]=G[i].size();sum1+=s[i];}dep[0]=-1;dfs1(1,0);for(int i=1;i<=n;i++){f[1]+=dep[i]*G[i].size();} dfs2(1,0);int maxans=0;vector<int>ans;for(int i=1;i<=n;i++){int tans = n*sum1-f[i];if(tans==maxans){ans.pb(i);}else if(tans > maxans){maxans = tans;ans.clear();ans.pb(i);}}cout<<ans.size()<<endl;for(int e:ans){cout<<e<<" ";}cout<<endl;
}	signed main() {
#ifdef ONLINE_JUDGE
#elsefreopen("../in.txt", "r", stdin);
#endifcin.tie(0)->ios::sync_with_stdio(0);int T = 1;cin >> T;while (T--) {solve();}return 0;
}

做法2：猜结论要找的是树的重心，于是答案只可能有1或2个点。这个真的是神人了，赛时其实猜到了但被骗了于是把自己否了。

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;const int N = 500010;
int n, ans = N;
vector<int> g[N];
int Size[N], weight[N], centroid[2];void GetCentroid(int cur, int fa) {Size[cur] = 1;weight[cur] = 0;for (int v : g[cur]) {if (v != fa) {GetCentroid(v, cur);Size[cur] += Size[v];weight[cur] = max(weight[cur], Size[v]);}}weight[cur] = max(weight[cur], n - Size[cur]);if (weight[cur] <= n / 2) {centroid[centroid[0] != 0] = cur;}
}int main() {int T;cin >> T;while (T--) {cin >> n;centroid[0]=0,centroid[1]=0;for(int i=1;i<=n;i++){g[i].clear();Size[i]=0;weight[i]=0;}for (int i = 0; i < n - 1; i++) {int a, b;cin >> a >> b;g[a].push_back(b);g[b].push_back(a);}GetCentroid(1, 0);int a = centroid[0], b = centroid[1];if (a > b)swap(a, b);if (a && b) {cout << 2 << endl;cout << a << " " << b << endl;} else {cout << 1 << endl;cout << b << endl;}}return 0;
}

F 不死国的生命树

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define int long long
#define pb push_back
#define pii pair<int, int>
#define FU(i, a, b) for (int i = (a); i <= (b); ++i)
#define FD(i, a, b) for (int i = (a); i >= (b); --i)
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 5, MAXN = maxn;
int n;
int a[maxn];
int fa[maxn];
int up[maxn][21]; // 2^(i-1)
int dep[maxn];
vector<int> G[maxn];
int j[maxn];
void dfs(int x) {for (int e : G[x]) {dep[e] = dep[x] + 1;dfs(e);}
}
void dfs1(int x) {int oldj = j[a[x]]; // 保存当前状态j[a[x]] = x;up[x][1] = j[a[x] + 1];for (int i = 2; i <= 20; i++) {if (up[x][1] == 0)break;up[x][i] = up[up[x][i - 1]][i - 1];if (up[x][i] == 0)break;}for (int e : G[x]) {dfs1(e);}j[a[x]] = oldj;
}
int query(int s, int t) {int ans = 1;while (dep[s] > dep[t]) {int k = 0;for (int i = 20; i >= 1; i--) {if (up[s][i] != 0 && dep[up[s][i]] >= dep[t]) {k = i;break;}}if (k == 0)break;ans += 1 << (k - 1);s = up[s][k];}return ans;
}void solve() {cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];up[i][0] = i;}fa[1] = -1;for (int i = 2; i <= n; i++) {cin >> fa[i];G[fa[i]].pb(i);}dep[0] = -1;dep[1] = 0;dfs(1);dfs1(1);int Q;cin >> Q;while (Q--) {int s, t;cin >> s >> t;cout << query(s, t) << endl;}
}signed main() {cin.tie(0)->ios::sync_with_stdio(0);
#ifdef ONLINE_JUDGE
#elsefreopen("../in.txt", "r", stdin);
#endifint T = 1;while (T--) {solve();}return 0;
}

HBCPC2025 补题（F、I)

HBCPC2025 补题补题连接:Codeforces I 感染做法1：std做法：树上dp统计贡献找最大 #include <bits/stdc.h> using namespace std; typedef long long ll; #define endl \n #define int long long #define pb push_back #define pii pair<int,…...

编程日记 2025/7/7 11:13:09

针对 CSDN高质量博文发布的详细指南

结合技术写作规范与平台特性，分为内容规划、写作技巧、排版优化、发布策略四部分，确保专业性与传播效果： 一、内容规划：精准定位与深度挖掘选题策略热点结合：追踪技术趋势（如2025年AIGC、量子计算&am…...

编程日记 2025/7/4 0:17:02

python读写bin文件

import numpy as np# 创建二进制数据 data np.array([0x33, 0x34, 0x35, 0x36], dtypenp.uint8)# 写入bin文件 with open(example.bin, wb) as f:data.tofile(f)print("bin文件生成成功")data np.fromfile(example.bin, dtypenp.uint8) print("numpy读取结果:…...

编程日记 2025/6/27 23:05:39

矩阵的秩（Rank）

矩阵的秩（Rank）是线性代数中的核心概念，表示矩阵中线性无关的行（或列）的最大数量，反映了矩阵所包含的“独立信息”的多少。以下是其核心要点： 1. 秩的定义行秩：矩阵中线性无关的行…...

编程日记 2025/6/27 23:29:55

Vue响应式系统演进与实现解析

一、Vue 2 响应式实现详解 1. 核心代码实现 // 依赖收集器（观察者模式） class Dep {constructor() {this.subscribers new Set();}depend() {if (activeEffect) {this.subscribers.add(activeEffect);}}notify() {this.subscribers.forEach(effect &g…...

编程日记 2025/6/29 8:37:35

【SPIN】高级时序规范（SPIN学习系列--6）

时序操作符[]（总是）和 <>（最终）可应用于任何LTL公式，因此 []<><>A 和 <>[]<>(A ∧ []B) 在语法上是正确的。本书不涉及LTL的演绎理论（如公理、推理规则及公式的结合律、交换…...

编程日记 2025/6/27 23:38:23

C语言学习之内存函数

今天我们来学习一下C语言中内存函数以下内存函数的使用均需要包含头文件<string.h> 目录 memcpy函数的使用及其模拟实现 memcpy函数的模拟实现 memmove函数的使用和模拟实现 memmove函数的模拟实现 memset函数的使用 memcmp函数的使用 memcpy函数的使用及其模拟实现…...

编程日记 2025/7/7 11:03:50

Python 数据库编程

一、数据库连接基础 1. 标准流程 import database_module # 如mysql.connector, sqlite3等 # 1. 建立连接 connection database_module.connect( host"localhost", user"username", password"password", database"dbnam…...

编程日记 2025/6/27 23:29:29

软考软件评测师——软件工程之开发模型与方法

目录一、核心概念二、主流模型详解 （一）经典瀑布模型 （二）螺旋演进模型 （三）增量交付模型 （四）原型验证模型 （五）敏捷开发实践三、模型选择指南四…...

编程日记 2025/6/27 22:58:55

机器学习入门

机器学习入门 1 . 机器学习是什么？ 机器学习（Machine Learning, ML）是一种用数据经验替代显式规则编程来完成任务的方法──模型从样本 (X, y) 中学习映射函数 f: X → Y，并在新样本上做出预测。和传统“if … else”程序相比&…...

编程日记 2025/6/27 23:24:34

git学习与使用（远程仓库、分支、工作流）

文章目录前言简介git的工作流程git的安装配置git环境：git config --globalgit的基本使用新建目录初始化仓库（repository）添加到暂存区新增/修改/删除文件状态会改变提交到仓库查看提交（commit）的历史记录git其他命令…...

编程日记 2025/6/27 23:25:03

制造业或跨境电商相关行业三种模式：OEM、ODM、OBM

一、基础概念对比模式定义核心能力利润来源控制权OEM代工生产（贴牌生产）纯生产制造能力加工费（薄利）品牌方掌控一切ODM设计生产（自主设计代工）设计研发能力设计溢价生产利润制造商掌握设计OBM自主品牌&am…...

编程日记 2025/6/27 22:58:56

APPtrace 智能参数系统：重构 App 用户增长与运营逻辑

一、免填时代：APPtrace 颠覆传统参数传递模式传统 App 依赖「邀请码 / 手动绑定」实现用户关联，流程繁琐导致 20%-30% 的用户流失。APPtrace 通过 **「链接参数自动传递安装后智能识别」** 技术，让用户在无感知状态下完成关系绑定、场景还…...

编程日记 2025/6/27 23:37:02

在 Excel 中使用 C# .NET 用户定义函数操作步骤

点开选项点击加载项点击跳转点击浏览选择仙盟excel...

编程日记 2025/6/27 23:29:36

PyTest

一、基本用法: 1.测试框架做了什么: (1).测试发现 a.创建test_开头的文件 b.创建Test开头的类 c.创建test_开头的函数或方法 pytest中以每一个函数或方法作为一个用例 pytest主要以名字区分普通函数(方法)、用例 pytest的启动方式:在给定的项目中执行pytest命令即可 p…...

编程日记 2025/6/27 23:28:32

Python Day27 学习

今天学习讲义Day17的内容：无监督算法中的聚类浙大疏锦行 Q1. 什么是聚类？ 本质上就是一种分组分类关于聚类的准备工作： 代码实现 # 先运行之前预处理好的代码 import pandas as pd import pandas as pd #用于数据处理和分析&#xff…...

编程日记 2025/6/27 23:22:39

在 Win 10 上，Tcl/Tk 脚本2个示例

set PATH 新增 D:\Git\mingw64\bin where tclsh D:\Git\mingw64\bin\tclsh.exe where wish D:\Git\mingw64\bin\wish.exe 编写 test_tk.tcl 如下 #!/usr/bin/tclsh # test 文件对话框 package require Tk# 弹出文件选择对话框，限制选择.txt文件 set filePath […...

编程日记 2025/6/27 22:59:17

渐开线少齿差传动学习笔记

之前看到了一个渐开线一齿差的视频，觉得比较有意思，想自己动手做一个看看，下面是最开始尝试的一个失败的结果，不知道小伙伴们发现问题了没？ 本来就是想凑一凑看看，但是发现不是凑起来不是件容易的事。那么…...

编程日记 2025/6/27 23:05:02

基于CATIA参数化圆锥建模的自动化插件开发实践——NX建模之圆锥体命令的参考与移植（二）

引言在CATIA二次开发领域，参数化建模技术可提升复杂几何体的创建效率达60%。本文基于PySide6 GUI框架与pycatia接口库，深度解析锥体自动化建模工具的开发实践。该工具创新性地融合了NX的交互逻辑与CATIA的混合建模技术，实现双模式输入（高度/锥角）的智能参数转换，较传统…...

编程日记 2025/6/27 23:01:19

Java集合框架详解：单列集合与双列集合

目录 1. 引言：为什么需要集合框架 2. 基础概念：集合框架概述 2.1 集合框架的结构编辑编辑 2.2 集合与数组的比较 3. 前置知识：理解集合框架背后的基础数据结构 3.1 数组 3.2 链表 3.3 哈希表 3.4 二叉树与二叉查找树 3.5 红…...

编程日记 2025/7/7 11:07:06

leetcode 33. Search in Rotated Sorted Array

题目描述可以发现的是，将数组从中间分开成左右两部分的时候，一定至少有一部分的数组是有序的。左部分[left,mid-1]，右部分[mid1,right]。第一种情况：左右两部分都是有序的，说明nums[mid]就是整个数组的最大值。此时…...

编程日记 2025/6/27 23:11:10

OpenCV 图像色彩空间转换

一、知识点: 1、色彩空间转换函数 (1)、void cvtColor( InputArray src, OutputArray dst, int code, int dstCn 0, AlgorithmHint hint cv::ALGO_HINT_DEFAULT ); (2)、将图像从一种颜色空间转换为另一种。 (3)、参数说明: src: 输入图像，即要进行颜…...

编程日记 2025/6/27 23:22:12

python-leetcode 69.最小栈

题目： 设计一个支持push,pop,top,操作，并能在常数时间内检索到最小元素的栈。辅助栈法： 1：使用两个栈，一个主栈用于存储所有元素，另一个辅助栈用于存储当前元素的最小值 2: 每次push时，将元…...

编程日记 2025/7/6 11:16:26

C#基础：yield return关键字的特点

一、特点 1.最终返回的结果是IEnumerable<T> 2.使用yield return时，返回的是单个元素（即T） 3.好处：延迟加载，需要时才计算二、验证通过打断点可知，只有当listB遍历的时候，才会进入Get…...

编程日记 2025/7/7 11:05:25

机器学习集成学习方法之随机森林

集成学习方法之随机森林 1 集成学习2 随机森林的算法原理2.1 Sklearn API2.2 示例 1 集成学习机器学习中有一种大类叫集成学习（Ensemble Learning），集成学习的基本思想就是将多个分类器组合，从而实现一个预测效果更好的集成分类…...

编程日记 2025/6/27 23:31:27

【Vue篇】组件的武林绝学：状态风暴下的乾坤挪移术

引言 🔍 Vue组件迷雾重重？ ✧ Scoped如何实现样式隔离？ ✧ Data为何必须是函数？ ✧ 父子组件如何跨域通信？ ✧ Props单向数据流如何破局？ 🚀 本文直击组件化七大核心： ▸ 样式隔离原…...

编程日记 2025/7/7 11:09:14

使用亮数据代理IP+Python爬虫批量爬取招聘信息训练面试类AI智能体（手把手教学版）

文章目录一、为什么要用代理IP？(重要！！！)二、环境准备（三件套走起）2.1 安装必备库（pip大法好）2.2 获取亮数据代理（官网注册送试用） 三、编写爬虫代码&#x…...

编程日记 2025/6/27 23:05:53

【MySQL】第七弹——复习总结视图

文章目录 🌏客户端和数据库操作🌏表操作🌏CRUD 增删改查总结🌏数据库约束🌏表的设计🌏分组查询🌏聚合函数🌏联合查询🌏SQL语句中各部分的执行顺序🪐视图 &…...

编程日记 2025/7/7 11:02:57

基于Springboot + vue3实现的工商局商家管理系统

项目描述本系统包含管理员、商家两个角色。管理员角色： 用户管理：管理系统中所有用户的信息，包括添加、删除和修改用户。许可证申请管理：管理商家的许可证申请，包括搜索、修改或删除许可证申请。许可证审批管理…...

编程日记 2025/7/7 11:03:51

前端开发——前端样式BUG调试全指南2025终极版

前端开发——前端样式BUG调试全指南2025终极版前端样式BUG调试指南（2025终极版）一、调试方法论与工具链1. 问题定位三板斧(1) 现象复现与特征提取(2) 现代调试工具组合拳(3) 三维问题定位法 2. 深度排查六步法步骤1：样式覆盖检测步骤2&#…...

编程日记 2025/6/27 23:20:48

【DeepSeek】为什么需要linux-header

编译Linux驱动程序时，通常需要 Linux内核头文件（linux-headers），而不是完整的源代码（linux-source）。以下是详细解释： 1. 为什么需要内核头文件？ 头文件的作用： 内核头文…...

编程日记 2025/7/7 9:36:59

c语言刷题之实际问题

小乐乐定闹钟代码如下： 小乐乐排电梯代码如下： 小乐乐与欧几里得代码如下： 小乐乐改数字代码如下： 小乐乐走台阶代码如下： 台阶为1,2时走法分别1，2种 1:(1) 2:(1,1),(2) 要走完n阶时，即我…...

编程日记 2025/6/27 23:10:50

【图像大模型】Kolors：基于自监督学习的通用视觉色彩增强系统深度解析

Kolors：基于自监督学习的通用视觉色彩增强系统深度解析一、项目架构与技术原理1.1 系统定位与核心能力1.2 核心算法突破1.2.1 色彩感知表征学习1.2.2 动态色彩变换矩阵二、系统实现与训练策略2.1 训练框架设计2.1.1 自监督预训练 2.2 损失函数设计三、实战部署指…...

编程日记 2025/6/27 23:16:06

生产消费者模型读写者模型

概念生产者消费者模式就是通过一个容器来解决生产者和消费者的强耦合问题。生产者和消费者彼此之间不直接通讯，而通过阻塞队列来进行通讯，所以生产者生产完数据之后不用等待消费者处理，直接扔给阻塞队列，消费者不找生产者要数据…...

编程日记 2025/6/27 23:29:31

每日Prompt：双重曝光

提示词双重曝光，Midjourney 风格，融合、混合、叠加的双重曝光图像，双重曝光风格。一幅由 Yukisakura 创作的杰出杰作，展现了一个奇妙的双重曝光构图，将阿拉贡阿拉松之子的剪影与生机勃勃春季里中土世界视觉上引人注目…...

编程日记 2025/6/27 22:59:58

基于springboot3 VUE3 火车订票系统前后端分离项目适合新手学习的项目包含智能客服换乘算法

博主介绍：专注于Java（springboot ssm 等开发框架） vue .net php phython node.js uniapp 微信小程序等诸多技术领域和毕业项目实战、企业信息化系统建设，从业十五余年开发设计教学工作 ☆☆☆ 精彩专栏推荐订阅☆☆☆☆☆…...

编程日记 2025/6/27 23:39:45

DAY29 超大力王爱学Python

知识点回顾类的装饰器装饰器思想的进一步理解：外部修改、动态类方法的定义：内部定义和外部定义作业：复习类和函数的知识点，写下自己过去29天的学习心得，如对函数和类的理解，对python这门工具的理解等&…...

编程日记 2025/6/27 23:28:25

jvm对象压缩

最近在看一些文章，知道64位jvm在启动时指定-XX:UseCompressedOops后就会开启压缩，但是怎么压缩的，以及什么情况下压缩失效，没有一篇文章讲的特别透彻，在这里记录一下，后面抽时间进行更新。参考文档 https…...

编程日记 2025/6/27 23:39:04

TripGenie：畅游济南旅行规划助手：个人工作纪实(十八）

本周，我增加了网页搜索并在右侧显示搜索链接与标题的功能，通过这个功能，可以帮助用户搜索网络上关于济南旅游的信息，提高用户检索信息的速度，用户可以通过点击网页链接了解更多关于济南的信息。首先，我设计…...

编程日记 2025/6/27 23:11:54

Brooks Polycold快速循环水蒸气冷冻泵客户使用手含电路图，适用于真空室应用

Brooks Polycold快速循环水蒸气冷冻泵客户使用手含电路图，适用于真空室应用...

编程日记 2025/6/27 23:15:02

Rofin PowerLine E Air维护和集成手侧激光Maintenance and Integration Manual

Rofin PowerLine E Air维护和集成手侧激光Maintenance and Integration Manual...

编程日记 2025/6/27 23:40:06

C++中String类

1.String学习前的了解 1.1范围for和auto关键字范围 for 循环范围 for 循环是 C11 引入的一种语法糖，用于简化遍历容器或序列的代码。其基本语法如下： 迭代器版本： 范围for主要用来遍历一个容器(数据结构).范围for的（&#xf…...

编程日记 2025/7/4 9:41:53

LSTM语言模型验证代码

#任务：基于已有文本数据，建立LSTM模型，预测序列文字 1 完成数据预处理，将文字序列数据转化为可用于LSTM输入的数据。 2 查看文字数据预处理后的数据结构，并进行数据分离操作 3 针对字符串输入（“In the hea…...

编程日记 2025/6/27 23:24:22

Nextjs App Router 开发指南

Next.js是一个用于构建全栈web应用的React框架。App Router 是 nextjs 的基于文件系统的路由器，它使用了React的最新特性，比如 Server Components, Suspense, 和 Server Functions。术语树(Tree): 一种用于可视化的层次结构。例如，包含父…...

编程日记 2025/6/27 23:19:38

测试W5500的第3步_使用ioLibrary库创建TCPServer

W5500是一款具有8个Socket的网络芯片，支持TCP Server模式，最多可同时连接8个客户端。本文介绍了基于STM32F10x和W5500的TCP Server实现，包括SPI初始化、W5500复位、网络参数配置、Socket状态管理等功能，适用于需要多客户端连接的嵌…...

编程日记 2025/6/27 23:09:26

Python训练营打卡——DAY31（2025.5.20）

目录一、机器学习项目的流程二、文件的组织 1. 项目核心代码组织 2. 配置文件管理 3. 实验与探索代码 4. 项目产出物管理三、注意事项 if name "main" 编码格式类型注解四、通俗解释 1. 拆分文件和目录：整理房间一样管理代码 2. 导…...

编程日记 2025/6/27 23:20:03

P1152 欢乐的跳

P1152 欢乐的跳 - 洛谷使用map映射来解 #include<bits/stdc.h> using namespace std; int n,a[1005],c[1005]; map<int,int>b;//因为要记录1~n-1是否都出现了 int main(){cin>>n;cin>>a[1];for(int i2;i<n;i){cin>>a[i];//c[i-1]a[i]-a[…...

编程日记 2025/6/27 23:29:47