1873

题目描述见：P1873 思路比较明确qwq因为答案显然满足单调性：当x超过某个数一定是错的（收集的木材大于m)，而小于x一定是对的，并且x是从0一直递增。故我们只需二分法找到x。 直接看代码吧qwq精髓是check函数直接模拟题目要求ww #include <iostream> using name ......

这题其实可以数学方法差小积大解决。 差越小积越大，那肯定是让最小的数加一啦。将所有数的积除以最小值再乘上最小值加一。 #include<bits/stdc++.h> using namespace std; signed main(){ int T; cin>>T; while(T--){ long ......

这题看到第一眼就是二分。 单调性 二分最关键的东西是单调性在哪。单调性是如果高度越高，需要的水就越多，高度越矮，要用的水越少。 不难得出代码： check 函数： int check(int mid){ int sum=0; for(int i=1;i<=n;i++){ sum+=max(0ll,m ......

CF1873F Money Trees 双指针好题，但是我用的队列（ 考虑先找出所有极长的、满足任意一个数都能被它后面的那个数整除的连续段。显然这个操作可以在 \(\mathcal{O}(n)\) 的时间复杂度内完成。 求出每个极长连续段的答案，取 \(\max\) 即为最终答案。那么现在的问题就是 ......

A Short Sort 题解 题目大意 给定一个长度为 \(3\) 、由 \(a,b,c\) 组成的字符串，问可以不变或交换两个字符是的变为 \(\texttt{abc}\)。 解题思路 由于大小固定，所以预处理可行的字符串（仅包含 \(\texttt{abc acb bac cba}\)）即可。 ......

思路 要求最长长度，想到可以二分答案。 那么现在需要考虑如何快速验证答案是否正确。 可以 \(O(n)\) 枚举区间左端点，因为有了长度，所以可以直接获得右端点的值，直接验证右端点是否合法。 因为要求区间的每个数都是右边的数的倍数，所以可以提前预处理每个点最远的满足这个条件的右端点，直接判断合不合法 ......

思路 首先发现，无论是 AB 变 BC，还是 BA 变 CB，最重要的都是 A，因为 B 的数量不会变化，C 既不是变化所需要的，数量还会变多，只有 A 是需要的并且数量还会变少。 首先思考 AB 变 BC 的情况，什么情况下可以继续变化呢？很显然 AB 前还有 A就可以继续变化，而后面因为 C的出 ......

其他题解怎么又 Tarjan 又 Dijkstra 的，这是 div4H 的样子吗，来个简单好写的做法。 题面里的人名太复杂了，本题解中称为警察和小偷。 注意到，如果小偷成功到达了环上，那么一定不会被警察抓到。因为小偷知道警察下一步会走到哪里，他可以执行相同的操作（顺时针/逆时针/静止），使得他和警 ......

题意描述 马塞尔和瓦勒里乌（Valeriu）所在的疯狂城市由 \(n\) 栋建筑和 \(n\) 条双向道路组成。 马塞尔和瓦勒里乌（Valeriu）分别从 \(a\) 号和 \(b\) 号建筑开始。马塞尔想赶上瓦勒里乌（换句话说，与他在同一栋楼里或在同一条路上相遇）。 在每次移动过程中，他们都会选择 ......

CF1873H - Mad City 知识点：基环树找环 题意 给定一张具有 \(n\) 个点 \(n\) 条边的无向图。现在有两个人，第一个人在 \(a\) 点，第二个人在 \(b\) 点，第一个人要追到第二个人。 两个人每一回合都同时进行操作，要么停留在当前位置，要么走邻接的下一个点。同时，第一 ......

基环树上的“追及相遇”问题。 考虑什么情况下，Valeriu 能“无限期”地从 Marcel 手中逃离。参考样例 1，我们发现当 Valeriu 进入基环树的环中，他总能通过预判，逃往 Marcel 的反方向，避免被抓；而如果两者都在子树中，Marcel 就能步步紧逼，将 Valeriu 堵在叶子结 ......

二分+前缀和。 要求使得区间和小于 \(k\) 的子区间长度，显然可以二分处理。二分区间长度，枚举区间左端点，check 两项内容：区间是否合法（符合 \(h_i \mod h_{i+1}=0\) ），区间和是否小于 \(k\)。对于当前区间长度，只要有一个区间满足条件，即返回真。 区间和可以通过前 ......

# 1873. 计算特殊奖金 2023年8月12日20:24:22 [1873. 计算特殊奖金](https://leetcode.cn/problems/calculate-special-bonus/) 简单 SQL Schema Pandas Schema 表: `Employees` ``` ......