1824
syoj 1824. 剪纸题解
题目链接 给你一个 01 矩阵,求满足第一行、最后一行、第一列、最后一列均无 0 的最大子矩阵面积。\(n,m<=200\)。 不难想到对于每个点,预处理出,向其上下左右最大限度扩展。这种方法类似于单调栈的预处理。 预处理后,以每个点为矩阵左上角,向右下枚举矩阵右上角。此时我们已经确定了这个矩阵的第 ......
洛谷P1824 进击的奶牛 题解 二分答案
题目链接:https://www.luogu.com.cn/problem/P1824 题目大意: 本题相当于在 \(n\) 个数中选 \(c\) 个数,使得这 \(c\) 个数中相差最小的两个数之差尽可能地大。 解题思路: 我们首先可以给 \(a_1 \sim a_n\) 从小到大排一下序(这里有 ......
CF1824B1 LuoTianyi and the Floating Islands (Easy Version) 题解
题意: 思路: 由于 $ k ∈ [1,3] $ ,分类讨论: 当 $ k = 1 $ 时,有人结点自身即为好结点,每种情况的期望为 $ \frac{1}{n} $ , $ n $ 种情况的期望和为 $ 1 $ 。最终答案即为 $ 1 $ 。 当 $ k = 2 $ 时,$ 2 $ 个有人结点之间的 ......
《CF1824E LuoTianyi and Cartridge》 解题报告
好题。 模拟赛出了这题,抽象。 初步化简: 由于 \(\min (A,C)\) 不好处理,我们考虑从大到小加边加点,或者从小到大删边删点。 一般题目是考虑加边加点好操作一点,这题是考虑删边删点好操作。 然后我们记当前枚举的 \(\min (A,C)\) 的最小值是多少,记为 \(x\) 。然后称大于 ......
【题解】CF1824 合集
CF1824A LuoTianyi and the Show 我们可以较为容易地得出一个贪心策略,就是先去放一个以第 \(3\) 中方式入座的人,再在两边放 \(1,2\) 种方式的人,如果放的时候占用了第三种方式的人的座位就跳过该座位,最后将剩下的以第 \(3\) 中方式入座的人放进去。 当然还有 ......
洛谷p1824 进击的奶牛
P1824 进击的奶牛 题目描述 Farmer John建造了一个有N(2<=N<=100,000)个隔间的牛棚,这些隔间分布在一条直线上,坐标是x1,...,xN (0<=xi<=1,000,000,000)。 他的C(2<=C<=N)头牛不满于隔间的位置分布,它们为牛棚里其他的牛的存在而愤怒。为 ......
CF1824D
[原题](https://codeforces.com/contest/1824/problem/C) [翻译](https://www.luogu.com.cn/problem/CF1824C) 我们定义$f(l,r,x)=\sum_{j=1}^{x}{\sum_{i=l}^{\min{(j,r) ......
CF1824C
[原题](https://codeforces.com/contest/1824/problem/C) [翻译](https://www.luogu.com.cn/problem/CF1824C) 首先考虑一个朴素的 $dp$ ,我们设$dp_{i,j}$表示以$i$为根的子树全部变成$b_j$最少 ......
CF1824B2
[原题](https://codeforces.com/contest/1824/problem/B2) [翻译](https://www.luogu.com.cn/problem/CF1824B2) 首先根据~~猜结论~~数学归纳法可以想到在$k$为奇数时答案依然是$1$ 因此我们只考虑$k$是偶 ......
CF1824B1
[原题](https://codeforces.com/contest/1824/problem/B1) [翻译](https://www.luogu.com.cn/problem/CF1824B1) 这题不算难,但我想错了 当$k = 1$时,答案就是关键点;当$k = 3$时,答案就是三个节点组 ......
[CF1824D] LuoTianyi and the Function
## 题目描述 LuoTianyi gives you an array $ a $ of $ n $ integers and the index begins from $ 1 $ . Define $ g(i,j) $ as follows: - $ g(i,j) $ is the large ......
CF1824D LuoTianyi and the Function【线段树】
给定长为 $n$ 的数组 $a$,如下定义 $g(i,j)$:当 $i \leq j$ 时,$g(i,j)$ 是满足 $\{ a_p : i \leq p \leq j \} \subseteq \{a_q : x \leq q \leq j\}$ 的最大整数 $x$。否则 $g(i,j) = 0$ ......
CF1824A LuoTianYi and the Show
题意 有 $n$ 个人、编号为 $1$ 至 $m$ 的 $m$ 个座位与三种坐座位的方式: 坐在最左边的人的左边,当 $1$ 号座位也不为空时就不坐了,当没有人坐在座位上时坐在 $m$ 号座位上; 坐在最右边的人的右边,当 $m$ 号座位也不为空时就不坐了,当没有人坐在座位上时坐在 $1$ 号座位上 ......
CF1824B2 LuoTianyi and the Floating Islands (Hard Version) - 概率期望 - 树的重心 -
题目链接:https://codeforces.com/contest/1824/problem/B2 题解: 考虑一棵 $n$ 个点的树,假如已经选定了 $k$ 个特殊点,如何判断某一个点是否为好点? 显然将这个点提到根没有影响,那么好点的充要条件是对于所有子树的 $S_u$ 值都 $\leq k ......
CF1824B
一种不同于官方题解的 $O(n)$ 做法 考虑一个点在什么情况下能作为答案。 发现应当满足这个点为根时,他的每个儿子的字数内点数均不超过 $\frac{k}{2}$。 若 $k$ 为奇数,那么这样的点唯一;否则这样的点将形成一条链(实际上不需要用到这一性质)。 设这个点若干子树大小分别为 $x_1, ......