Fanfaredash

Fanfare's blog

HDUMUTC2020-03 LAYOUT

Intro 学业稍微有点重，趁着假期和几个朋友打打比赛复健一下。 不是很在状态，所以难题这里基本上都不会有，基本上都是签到题。 http://acm.hdu.edu.cn/contests/contest_show.php?cid=881 题目 1004 Tokitsukaze and Multiple 题意 给定一个数列 $A_n$，你可以把相邻的数任意合并成它们的和，要使得若干次操作后...

Posted by fpdqwq on July 29, 2020

HDUMUTC2020-02 LAYOUT

Intro 学业稍微有点重，趁着假期和几个朋友打打比赛复健一下。 不是很在状态，所以难题这里基本上都不会有，基本上都是签到题。 http://acm.hdu.edu.cn/contests/contest_show.php?cid=880 题目 1001 Total Eclipse 题意 给定一个图，每个点有权值。每次操作可以给一个连通块点权 -1，求全变 0 的最少操作次数。 题解 联想...

Posted by fpdqwq on July 25, 2020

【算法】最小环

前言 本文将介绍有关有向图/无向图求解最小环长的算法。 前置知识 图论基础（概念） 广度优先搜索/BFS 最短路算法（dijkstra, floyd） 最小环 问题描述：在一个图 $G = (E, V)$ 中求最小环长。边权非负。 在本文中，记 $N = V ...

Posted by fpdqwq on March 16, 2020

AGC034F RNG and XOR

前言 前置知识 期望方程的设立 线性代数（矩阵乘法、矩阵的逆） 快速沃尔什变换（FWT） 一些其它反演 以上为阅读本文章的前置知识，而并非解决本题必备知识。 相关阅读 yyb前辈的FWT学习笔记 VFK的《炫酷反演魔术》 本文取材自上述两篇博客/讲义/文章。 题解 记号与概念 反演：已知 $f(n)=\sum_{k}{a_{n,k}g(...

Posted by fpdqwq on March 14, 2020

【算法】支配树

前言 本文章取材自此篇博客，以及李煜东的《图连通性若干问题探讨》。 由于支配树的 $Lengauer-Tarjan$ 算法涉及到较多性质和引理的证明，容易遗忘，所以作者在这里把证明的大致框架整理出来。 在下文中，不妨对图重标号，使得 $u=dfn_u$ —— 即下文中，对两个点进行比较实质上是对其 dfs序 进行比较。 支配树 流图 (Flow Graph)：若有...

Posted by fpdqwq on March 11, 2020

ABOUT ME

OIer

FRIENDS