avatar
文章
215
标签
0
分类
1
主页
分类
标签
归档
友链
爱飞鱼的blog树上连通块计数
搜索
主页
分类
标签
归档
友链

树上连通块计数

发表于2023-12-21|更新于2025-03-04|ICPC
|浏览量:

title: 树上连通块计数
categories:
- ICPC
tags:
- null
abbrlink: 254db057
date: 2023-12-21 00:00:00

树上连通块计数

《解决树上连通块问题的一些技巧和工具》 学习笔记 - evenbao - 博客园 (cnblogs.com)

文章作者: WTY
文章链接: https://my-mathmaster-github-io.vercel.app/posts/254db057.html
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 爱飞鱼的blog！
cover of previous post
上一篇
欧拉路
title: 欧拉路categories: - ICPCtags: - nullabbrlink: cad745fdate: 2023-12-10 00:00:00欧拉路构造题中的欧拉回路 | tyqtyq 的博客 2018的国家集训队论文《欧拉图相关的生成与计数问题探究》 [Tricks] 记各类欧拉回路问题 - 樱雪喵 - 博客园 欧拉路径是满足恰经过所有边一次的通路 欧拉回路是起点和终点相同的一条欧拉路径. 判别法则： 有向图存在欧拉回路: G中所有度数非0的点是强连通的，且所有点入度均等于出度. 有向图存在欧拉通路: 将边看成无向边后，G中所有度数非0的点是连通的。 最多只有一个点入度比出度大 1，作为欧拉通路的起点 最多只有一个点出度比入度大 1，作为欧拉通路的终点 其他所有点入度均等于出度 无向图存在欧拉回路: G中所有度数非0的点是连通的且所有点度数均为偶数. 无向图存在欧拉通路: G中所有度数非0的点是连通。并且G中恰好存在0或2个奇度点。 其他所有点度数均为偶数。那两个奇度点中, 一个作为欧拉通路之起点,...
cover of next post
下一篇
CCPC2023秦皇岛
title: CCPC2023秦皇岛categories: - ICPCtags: - nullabbrlink: d7d0f40cdate: 2023-12-22 00:00:00CCPC2023秦皇岛C.题意：给定一个字符串，多次区间询问给定一个子串。问有多少种方案删掉最短的区间使得子串变成回文串Sol：考虑每次询问可以独立处理，当然并不是指把子串单独提出来，而是按顺序正常回答。 一个关键的点是，考虑如果第一个字符和最后一个字符不一样，那一定要删一个，依次推理下去，我们可以得到应该保留最长回文前缀或最长回文后缀。 再考虑如果第一个字符和最后一个字符一样，那我们类双指针缩小删除区间，直到两边不一样。此时又回归到第一种情况。 根据上面这个观察，我们得到获得最小删除代价的做法： 对于一个区间[l, r] 我们首先可以先让首尾相同字符不断相消, 最后剩余区间[x, y], 如果这个区间为空则为回文串。这一部分等价于求原串后缀l 和反串后缀n − r + 1 的最长公共前缀( LCP ), 再对区间长度取min。 如果不为回文串, 那么$str[x] =...
avatar
WTY
理性思考，和平交流
文章
215
标签
0
分类
1
Follow Me
目录
  1. 1. title: 树上连通块计数categories: - ICPCtags: - nullabbrlink: 254db057date: 2023-12-21 00:00:00
  • 树上连通块计数
    • 最新文章
    贪心
    贪心2024-12-22
    Z_exkmp
    Z_exkmp2024-12-21
    Codeforces Round 895 (Div. 3)
    Codeforces Round 895 (Div. 3)2024-12-16
    可持久化字典树（Trie）
    可持久化字典树（Trie）2024-12-16
    网格图上问题
    网格图上问题2024-12-15
    ©2022 - 2025 By WTY
    框架 Hexo|主题 Butterfly
    Copyright 爱飞鱼
    搜索
    数据加载中