1873
【洛谷】P1873 [COCI 2011/2012 #5] EKO / 砍树 (二分)
题目描述见:P1873 思路比较明确qwq因为答案显然满足单调性:当x超过某个数一定是错的(收集的木材大于m),而小于x一定是对的,并且x是从0一直递增。故我们只需二分法找到x。 直接看代码吧qwq精髓是check函数直接模拟题目要求ww #include <iostream> using name ......
CF1873B题解
这题其实可以数学方法差小积大解决。 差越小积越大,那肯定是让最小的数加一啦。将所有数的积除以最小值再乘上最小值加一。 #include<bits/stdc++.h> using namespace std; signed main(){ int T; cin>>T; while(T--){ long ......
CF1873E Building an Aquarium 题解
这题看到第一眼就是二分。 单调性 二分最关键的东西是单调性在哪。单调性是如果高度越高,需要的水就越多,高度越矮,要用的水越少。 不难得出代码: check 函数: int check(int mid){ int sum=0; for(int i=1;i<=n;i++){ sum+=max(0ll,m ......
CF1873F Money Trees
CF1873F Money Trees 双指针好题,但是我用的队列( 考虑先找出所有极长的、满足任意一个数都能被它后面的那个数整除的连续段。显然这个操作可以在 \(\mathcal{O}(n)\) 的时间复杂度内完成。 求出每个极长连续段的答案,取 \(\max\) 即为最终答案。那么现在的问题就是 ......
CF1873(Div. 4) 题解 (A to E)
A Short Sort 题解 题目大意 给定一个长度为 \(3\) 、由 \(a,b,c\) 组成的字符串,问可以不变或交换两个字符是的变为 \(\texttt{abc}\)。 解题思路 由于大小固定,所以预处理可行的字符串(仅包含 \(\texttt{abc acb bac cba}\))即可。 ......
CF1873F Money Trees
思路 要求最长长度,想到可以二分答案。 那么现在需要考虑如何快速验证答案是否正确。 可以 \(O(n)\) 枚举区间左端点,因为有了长度,所以可以直接获得右端点的值,直接验证右端点是否合法。 因为要求区间的每个数都是右边的数的倍数,所以可以提前预处理每个点最远的满足这个条件的右端点,直接判断合不合法 ......
CF1873G ABBC or BACB
思路 首先发现,无论是 AB 变 BC,还是 BA 变 CB,最重要的都是 A,因为 B 的数量不会变化,C 既不是变化所需要的,数量还会变多,只有 A 是需要的并且数量还会变少。 首先思考 AB 变 BC 的情况,什么情况下可以继续变化呢?很显然 AB 前还有 A就可以继续变化,而后面因为 C的出 ......
题解 CF1873H【Mad City】
其他题解怎么又 Tarjan 又 Dijkstra 的,这是 div4H 的样子吗,来个简单好写的做法。 题面里的人名太复杂了,本题解中称为警察和小偷。 注意到,如果小偷成功到达了环上,那么一定不会被警察抓到。因为小偷知道警察下一步会走到哪里,他可以执行相同的操作(顺时针/逆时针/静止),使得他和警 ......
题解 CF1873H Mad City
题意描述 马塞尔和瓦勒里乌(Valeriu)所在的疯狂城市由 \(n\) 栋建筑和 \(n\) 条双向道路组成。 马塞尔和瓦勒里乌(Valeriu)分别从 \(a\) 号和 \(b\) 号建筑开始。马塞尔想赶上瓦勒里乌(换句话说,与他在同一栋楼里或在同一条路上相遇)。 在每次移动过程中,他们都会选择 ......
[题解] CF1873H - Mad City
CF1873H - Mad City 知识点:基环树找环 题意 给定一张具有 \(n\) 个点 \(n\) 条边的无向图。现在有两个人,第一个人在 \(a\) 点,第二个人在 \(b\) 点,第一个人要追到第二个人。 两个人每一回合都同时进行操作,要么停留在当前位置,要么走邻接的下一个点。同时,第一 ......
1873H Mad City
基环树上的“追及相遇”问题。 考虑什么情况下,Valeriu 能“无限期”地从 Marcel 手中逃离。参考样例 1,我们发现当 Valeriu 进入基环树的环中,他总能通过预判,逃往 Marcel 的反方向,避免被抓;而如果两者都在子树中,Marcel 就能步步紧逼,将 Valeriu 堵在叶子结 ......
CF1873F
二分+前缀和。 要求使得区间和小于 \(k\) 的子区间长度,显然可以二分处理。二分区间长度,枚举区间左端点,check 两项内容:区间是否合法(符合 \(h_i \mod h_{i+1}=0\) ),区间和是否小于 \(k\)。对于当前区间长度,只要有一个区间满足条件,即返回真。 区间和可以通过前 ......
1873. 计算特殊奖金
# 1873. 计算特殊奖金 2023年8月12日20:24:22 [1873. 计算特殊奖金](https://leetcode.cn/problems/calculate-special-bonus/) 简单 SQL Schema Pandas Schema 表: `Employees` ``` ......