Q779的博客

note[7] 自己瞎推了一个式子，然后打表发现前几项是 \(2^{n-1}\) 。然后改了一改得到这样的式子。 \[ f_0 = 1, ~f_n = \sum_{0 \le i < n} f_i \] 通项为 \(f_n = 2^

2022-10-03 笔记

数学

生成树计数问题咕咕咕... upd 好家伙，原来有个叫矩阵树定理的东西 QAQ 有空学吧（随手记一下这些奇奇怪怪的东西，说不定会派上用场。以下默认为无向图。 \(n\) 个不同的点构成的完全图，其生成树个数为 \(n^{n-2}\)

2022-10-02 OI

数学图论

UOJ460 新年的拯救计划题解题目链接：#460. 新年的拯救计划题意：给定一个 \(n\) 阶完全图 \(K_n\) ，你需要构造 \(K_n\) 的 \(m\) 棵不相交的生成树，求 \(m\) 的最大值并给出方案。输入格

2022-10-02 OI

算法图论构造咕咕

洛谷P4180 [BJWC2010] 严格次小生成树题解题目链接：P4180 [BJWC2010] 严格次小生成树题意：给定一张无向连通图，求出它的严格次小生成树。如果最小生成树选择的边集是 \(E_M\)，严格次小生成树选择的

2022-10-02 OI

算法图论数据结构

洛谷P2478 [SDOI2010]城市规划题解题目链接：P2478 [SDOI2010]城市规划题意：给定一个带点权沙漠（多棵仙人掌），求最大权独立集。此处独立集的定义为集合中任意两个结点的最短路径长度不小于 \(3\) （就

2022-10-01 OI

算法图论 DP 数据结构

CF825G Tree Queries 题解题目链接：CF825G Tree Queries 题意：题目描述：给定一棵包含 \(n\) 个节点的树（从 1 到 \(n\) 编号），初始所有节点都是白色的。你需要处理以下两种类型的

2022-10-01 OI

算法数据结构

距离欧式距离（欧几里得距离）平面直角坐标系中，设点 \(A,B\) 的坐标分别为 \(A(x_1,y_1),B(x_2,y_2)\) ，则两点的欧几里得距离为 \[ |\overrightarrow{AB}| = \sqrt{(x_2

2022-10-01 OI

数学

洛谷P7912 [CSP-J 2021] 小熊的果篮题解题目链接：P7912 [CSP-J 2021] 小熊的果篮题意：小熊的水果店里摆放着一排 \(n\) 个水果。每个水果只可能是苹果或桔子，从左到右依次用正整数 \(1, 2,

2022-09-30 OI

算法数据结构

CF846E Chemistry in Berland 题解题目链接：CF846E Chemistry in Berland 题意： cxy 是 Berland 大学化学系的研究生。她需要进行一个复杂的实验来撰写她的论文，但是 Berl

2022-09-30 OI

算法数据结构

UOJ278 【UTR #2】题目排列顺序题解题目链接：#278. 【UTR #2】题目排列顺序题意： “又要出题了。” 宇宙出题中心主任 —— cxy ，坐在办公桌前策划即将到来的 UOI。这场比赛有 \(n\) 道题， cxy

2022-09-30 OI

算法构造

CF398B Painting The Wall 题解题目链接：CF398B Painting The Wall 题意： cxy 打算漆一堵墙。这个墙由 \(n^2\) 块瓷砖构成，它们构成 \(n \times n\) 的表。有些瓷砖

2022-09-30 OI

算法数学 DP

CF464D World of Darkraft - 2 题解题目链接：CF464D World of Darkraft - 2 题意： cxy 在玩 "World of Dardraft - 2" 游戏，有 \(k\) 种不同的装备，

2022-09-30 OI

算法 DP 玄学