在讨论《神秘小贪心 75pts 求 hack》回复：

我的建议是特判一下lim[i] == a[i+1] - 1的情况，将f[i] 更新为 f[i + 1]

在讨论《神秘小贪心 75pts 求 hack》回复：

问题在于我有可能有一段连续的a，但是我这一段的cnt[a] = 1，导致f[i+1]并不是这一段的顶端

蒟蒻今天刷老师给的图论题单的时候意外自己切了一道紫题，于是来写题解。 我们先观察一下两个限制。 限制一，对于所有 $i=1,2,\ldots,M$，都有 $P_{s_i} using namespace std; #define N 200005 int n, m, cnt, l[N], r[N], ind1[N],…

#### 赛事 容易想到的一种做法。 先跑一遍原图最小生成树，只存树上的边。 枚举村庄城市化方案，暴力加边，重新做最小生成树。 复杂度 $O(2^k \cdot n \cdot k \cdot (\log(n \cdot k) + \alpha(n)))$。 容易发现一种优化。 发现新的方案的答案的边一定存在于其子集的…

在讨论《MnZn有一个问题》回复：

我知道了，sb c++可以把函数名定义成stl库中已经有的 pow，但是你调用pow的时候他会优先调用stl库中的pow，导致最后pow计算过程中一直用的是int，导致溢出

在讨论《MnZn有一个问题》回复：

捞

在讨论《请求撤下本题的唯一一篇题解》回复：

他好像很喜欢猜结论

为什么存字符串长度前缀和的数组用 int 过不了(wa on test 2, 8 9, 10)，用 long double 就能过，句子的总长不应该小于等于 $30 \times n_{max}$ 也就是小于 int 的范围吗？ code（只有第四五行定义数组的地方有区别） AC代码 ```cpp #include u…

题目很快就切了，全靠 tag 打的好。 做不出题怪大脑，胡出来题自称佬。 注意到答案上界为 $n$ 所以暴力模拟的操作次数为 $n ^ 2$ 次 ，不可接受。注意到对于每次操作的 $a_i$ 和 $b_i$ 其中必然有一个会清零，对于为零的值我们的操作实际上没有意义，所以我们本质上有意义的操作只有 $n$ 次。 考虑如…

某模拟赛 T2，自己做法是 $\operatorname{O}(n \cdot k)$ 时间复杂度，发现题解是 $\operatorname{O}(n \cdot k ^ 2)$ 时间复杂度的，且原题题解区中没有 $\operatorname{O}(n \cdot k)$ 做法，意识到爆标，遂来写题解。 首先，发现可以…

某模拟赛 T1，赛后发现爆标（题解是 $\operatorname{LCA}$ 做法），遂来写题解。 我们发现不含 $0$ 的路径 $\operatorname{mex} = 0$。含 $0$ 的路径 $\operatorname{mex} > 0$，所以可以先单独计算不含 $0$ 的路径数，求出 $ans_0$。 对…

在文章《CF2144E题解》发表评论：

%%%

### 题面转化 给定一个序列，问子序列中最长下降子序列长度小于等于 $2$ 的子序列，有多少个。 ### solution 首先，我们发现这道题并不关心子序列的最长下降子序列的长度，只关心子序列的最长下降子序列是否大于 $2$。所以我们的动规状态只需要记录有可能使最长上升子序列的长度大于 $2$ 的值。具体的，对于…

我们要求的是 $\sum(a_i + b_i) \mod m$。 变形一下就是 $\sum a_i \mod m + b_i \mod m - [a_i \mod m + b_i \mod m \ge m] \times m$。 再变形一下就是 $\sum a_i \mod m + \sum b_i \mod m -…

在讨论《似乎将颜色重编号可以大概率卡过莫队？》回复：

%%% orz

### $n \le 10$ 枚举哪些人和小 i 交朋友，然后check ### $k = 0$ 发现任何人都不可能得到两个来源的小 i 的秘密，所以无论如何交朋友小 i 都不会从陌生人口中听见自己的秘密。直接贪心拿最大的 $m$ 个 $a_i$。 ### $k = \frac{n \cdot (n - 1)}{2}$…

### $n \le 5$ & $n \le 1000$ ~~不知道留给谁的~~ ### $n \le 10^5$ 留给不会快速读入的人或实现不好的人 ### $a_i \le 0$ 发现怎么穿越到过去都不优， 所以不穿越， 答案为数组的和 ### $a_i \ge 0$ 发现从尾穿越到头最优，所以答案就是 $(k +…

# 题解 ### 题面描述 有 $n$ 种物体，每种物体有 $a$ 和 $b$ 两个属性，数量无穷多，且物体单价只与 $\frac{b}{a}$ 有关，若 $\frac{b}{a}$ 不降，则物体单价不降，且物体间可无限合并，问 $a$ 不大于 $m$ 时物体的总价最大为多少。 ### sol 若随意合并，则合并后可产…

在文章《常数 dp 学习笔记》发表评论：

大佬你说得对， 但是刚学 IO 1ms 的 MnZn 不懂就问，为什么 f(i, 0) = i！ 即 i 的阶乘

在文章《题解：AT_arc197_d [ARC197D] Ancestor Relation》发表评论：

%%%

在文章《题解：AT_arc197_b [ARC197B] Greater Than Average》发表评论：

%%%

在文章《题解：CF1547F Array Stabilization (GCD version)》发表评论：

第五段有个错别字， “指数” 应为 “质数”

解法比较抽象，但貌似比较快。 首先我们知道求 $$\gcd$$ 就是对两个数所有质因数的指数求最小值，那么最后操作得到的元素一定是所有质因数最小指数次幂的积。 有点抽象，所以我举个例子 $$12$$ 是由 $$3$$ 的一次方和 $$2$$ 的平方乘积得到的，$$16$$ 是由 $$2$$ 的三次方得到的，所以二者的…

在文章《题解：P11487 「Cfz Round 5」Gnirts 10》发表评论：

%%%

在文章《题解：P6775 [NOI2020] 制作菜品》发表评论：

蒟蒻口胡出来的第一道黑题

## 无解 容易发现前 $t$ 分钟最多做 $t$ 瓶饮料，所以当 第 $i$ 个人需要在小于 $i$ 的时间取走饮料时，无解。 即存在 $t_i using namespace std; const int N = 2e5 + 5; int n, t[N], a[N], stk[N], tp; long long a…

## $m \ge n - 1$ 对于这种情况我们有一个显而易见的贪心，设数量最少的原料为第 $i$ 个，数量最多的原料为第 $j$ 个。如果 $d_i \ge k$ 我们直接将其做成一道菜，否则我们将 $d_i$ 全部用作一道菜，同时在这道菜中加入 $d_j$ 的一部分，使得其符合要求。 首先先证明一下贪心的正确性，…

在文章《P1248 加工生产调度》发表评论：

%%%

T1 95/100 T2 56/100 T3 0/100 T4 25/100 T1我寻思写法应该是正解吧，但是感觉写的可能不太优美，被卡常了（赛后听别人说好像有更优秀的解法（我的时间复杂度是 $ o(n log^2 n) $ ，但是好像有 $ o( n log n) $ 的做法） ~~菜~~ T2 不说了，挂分有点狠，…

在文章《CSP 2024 游记》发表评论：

很喜欢yny的一句话