Christmas

E - Christmas Color Grid 1 https://atcoder.jp/contests/abc334/tasks/abc334_e 思路 https://www.cnblogs.com/Lanly/p/17923753.html Code https://atcoder.jp/ ......

Cnblogs 线段树优化 dp？线段树优化 dp！ Solution 题目来源：ABC334F（in 洛谷| in AtCoder）题目大意很清晰就不讲了。 我们发现礼物是固定从 \(1\sim n\) 房间送的，唯一要分讨的地方就是什么时候要回去拿礼物。所以很容易想到二维 dp。 定义 \(f_ ......

B - Christmas Trees https://atcoder.jp/contests/abc334/tasks/abc334_b 思路 对于起始种树点A 在 [L, R]区间的位置情况，三种 A < L A> R A>=L, A<=R Code https://atcoder.jp/con ......

题目传送门 一道 dfs 题。 先统计出绿连通块数量，然后对于每个红色方块统计涂成绿色方块后会变成多少个连通块。正常涂成绿色后应该会增加一个大小为 \(1\) 的绿连通块，但若是有不同的绿连通块与其相邻，答案又会减少 \(1\)。 Code #include <bits/stdc++.h> cons ......

UNIQUE VISION Programming Contest 2023 Christmas (AtCoder Beginner Contest 334) A - Christmas Present 代码: #include <bits/stdc++.h> using namespace std ......

洛谷传送门 AtCoder 传送门 考虑相当于把每个标记点的边全部断掉，然后求连通块个数。 考虑一条边 \((u, v)\)（设 \(u < v\)）的出现时间，不难发现是 \([1, u - 1] \cup [u + 1, v - 1] \cup [v + 1, n]\)。于是考虑直接套线段树分治 ......

设 \(f_i\) 表示假设只有编号为 \(1\sim i\) 的点，此时的答案。\(f_n\) 即为所求。 显然有： \[f_i=\min\limits_{i-k\le j < i}\{f_j+dis(s\to j+1\to j+2\to\cdots\to i)\}+dis(i\to s) \]当 ......

先求出初始时绿连通块数量。 枚举每个红色格子，将其染成绿色本应增加一个绿连通块，但是它每与一个绿连通块相邻，就又会减少一个绿连通块。根据上述规则可以求出每个红色格子染绿后的绿连通块数量，求平均值即可。 时间复杂度 \(O(nm)\)。 // Problem: E - Christmas Color ......

先求出初始时绿连通块数量。 将一个绿色格子染成红色，会改变绿连通块数量，当且仅当这个绿色格子是孤点或割点。如果是孤点，会使得绿连通块数量减少一；如果是割点，会使得绿连通块数量增加它所在的点双数量减一。根据上述规则可以求出每个绿色格子染红后的绿连通块数量，求平均值即可。 时间复杂度 \(O(nm)\) ......

## _Decription_ 一颗圣诞树由 $n$ 个底边为 $d$，高度为 $h$ 的等腰三角形组成，每个三角形以 $y$ 轴为对称轴，底边均平行于 $x$ 轴，三角形有可能重叠。 给出 $n,d,h$ 以及每个三角形底边与 $x$ 轴的距离,求该圣诞树的面积。 ## _Solution_ ![ ......

洛谷传送门 AtCoder 传送门 不难猜想有解充要条件为 $n \ge 5$ 且 $\frac{n(n-1)}{2} \bmod 3 = 0$。 发现如果钦定一个点的出边都为同一种颜色，那么条件 $2$ 一定满足。 那么题目等价于把 ${0,1,...,n-1}$ 分成 $3$ 组使得每组的和相等 ......

题目分析： 感觉这个题目难度适中，而且换根 $dp$ 的过程相当好写并且很 educational，所以就当作换根 $dp$ 的典例，来讲讲换根 $dp$ 到底是个啥吧。 换根 $dp$ 其实就是用来解决：树上询问以每个点为根的相关信息，以指定某个点为根的时候信息很好求解，在换根的时候只会影响极少点 ......