思路 由于题目中给出了所有 $x$ 都不相同，所有的 $y$ 也不相同，那么我们发现，只有两个不同方向的奶牛才有相交的可能。 所以，我们为了方便，在输入的时候直接把奶牛给分成两组，然后两层循环遍历一下，记录所有有可能发生的路径相交。 由于奶牛只往右或者上走，所以对于一直奶牛，最靠左下的那一次相交时最先发生的。 然后就可u有直接计算了。 代码 #in…

思路 由于确定一个矩形后这个矩形里面有哪些奶牛是确定的，而且如果确定矩形的上下左右的边的位置，这个矩形就是确定的，所以这道题就改为计算有多少个不同矩形，使得每个矩形里面至少有一个一个奶牛，而且每个奶牛是在矩形的边上的（用来防止多个矩形内的奶牛一样）。 那么，我们可以先枚举两个奶牛确定两个奶牛作为上下两条边。然后可以计算出靠左边的奶牛的左边有多少奶牛…

思路 我们可以想到，每次在一个点翻倍到足够把子节点都覆盖的时候传播到子节点，至于传播后多余的有两种情况，一种情况是传输到子节点，使得子节点的翻倍数量减少。但是实际发现这样是不现实的，因为传输需要用的时间比翻倍需要用的时间更多（可以感性的理解一下，因为具体的证明我也不会） 代码 #include <bits/stdc++.h> using…

题目描述 思路 我们第一步应该想到优先做截止时间靠前的任务，所以我们按截止时间从小到大为第一关键字，收益从大到小为第二关键字。 但是这个时候，有一类型的样例有可能会 hack 掉这个做法： 7 1 2 1 3 2 5 2 7 3 10 3 11 3 12 33 我们会发现我们可以舍弃所有的截止时间为第一天的任务，而去做第二天和第三天的。 所以我们可…

题目描述 思路 我们可以把这道题的输入数据想象成一个一座山，有很多个山峰和山谷。 我们从左往右计算，如果正在上山，那么答案增加一。下山的时候，如果这个点在上山的时候已经出现过了，就不统计，只是消除比这个点高的点的记录（因外后面如果出现比这个点高的点，那么也不是这座山峰了），否则统计。 我们发现这个其实可以做成前缀和，如果想获得从第一个到第 $i$ …

题目链接：https://www.luogu.com.cn/problem/P11839 思路 由于我们看到了题目要求字典序最大，那么就是要求选的尽量大，宁愿抛弃一些，也要保证前面尽可能的大。 那么，我们可以想到把输入的数组按值从大到小为第一关键字，在原数组的位置从小到大为第二关键字，因为尽量靠前可以使得后面能接更多的数。 我们按照排序后的数组遍历…

货仓选址原题 给定在一个一维数轴上的多个点，请找出一个位置，使得这个位置和所有点的距离之和最小。 思路 这样的题目在学习数学数形结合的时候其实就学到了，也就是选择最中间的数。这个结论可以通过调整法证明。 证明 我们假设我们选择的数左边还有 $A$ 个数，右边还有 $B$ 个数。 一共有奇数个数 这个时候，由于我们选的数是最中间的数，也就是第 $\f…

题目链接 https://www.luogu.com.cn/problem/P12026 算法 & 数据结构 图论，拓扑排序，建图。 思路 Subtask 1 这个 Subtask 是 $A = B$。 我们首先想到建立一个图，每个 ID 号码为一个点，如果有一个 ID 的牛可以和另一个 ID 的牛交流，那么我们建立一个从第一个 ID 到第…

介绍在 Intel CPU 下的三种 C++ 生成随机数的方法。

前言 最近在写一个博客，在写编辑文章页面的时候想找一个可以支持 Markdown 的编辑器，而且支持 GFM 的一些特性，还有数学公式。 正好想到以前用思源的时候偶然看到的一个项目，就去找了一下，发现这个是最满足我的需求的一个项目了。其他项目要不就是不支持 Latex 或者 GFM，要不就是不是很好看（当然，如果有推荐的可以在评论区发一下）。 Vd…