作者: ztrztr

78 篇文章

P7150 [USACO20DEC] Stuck in a Rut S
思路 由于题目中给出了所有 $x$ 都不相同,所有的 $y$ 也不相同,那么我们发现,只有两个不同方向的奶牛才有相交的可能。 所以,我们为了方便,在输入的时候直接把奶牛给分成两组,然后两层循环遍历一下,记录所有有可能发生的路径相交。 由于奶牛只往右或者上走,所以对于一直奶牛,最靠左下的那一次相交时最先发生的。 然后就可u有直接计算了。 代码 #in…
P7149 [USACO20DEC] Rectangular Pasture S
思路 由于确定一个矩形后这个矩形里面有哪些奶牛是确定的,而且如果确定矩形的上下左右的边的位置,这个矩形就是确定的,所以这道题就改为计算有多少个不同矩形,使得每个矩形里面至少有一个一个奶牛,而且每个奶牛是在矩形的边上的(用来防止多个矩形内的奶牛一样)。 那么,我们可以先枚举两个奶牛确定两个奶牛作为上下两条边。然后可以计算出靠左边的奶牛的左边有多少奶牛…
P7148 [USACO20DEC] Cowntagion S
思路 我们可以想到,每次在一个点翻倍到足够把子节点都覆盖的时候传播到子节点,至于传播后多余的有两种情况,一种情况是传输到子节点,使得子节点的翻倍数量减少。但是实际发现这样是不现实的,因为传输需要用的时间比翻倍需要用的时间更多(可以感性的理解一下,因为具体的证明我也不会) 代码 #include <bits/stdc++.h> using…
P2949 [USACO09OPEN] Work Scheduling G 题解
题目描述 思路 我们第一步应该想到优先做截止时间靠前的任务,所以我们按截止时间从小到大为第一关键字,收益从大到小为第二关键字。 但是这个时候,有一类型的样例有可能会 hack 掉这个做法: 7 1 2 1 3 2 5 2 7 3 10 3 11 3 12 33 我们会发现我们可以舍弃所有的截止时间为第一天的任务,而去做第二天和第三天的。 所以我们可…
P7300 [USACO21JAN] No Time to Paint S 题解
题目描述 思路 我们可以把这道题的输入数据想象成一个一座山,有很多个山峰和山谷。 我们从左往右计算,如果正在上山,那么答案增加一。下山的时候,如果这个点在上山的时候已经出现过了,就不统计,只是消除比这个点高的点的记录(因外后面如果出现比这个点高的点,那么也不是这座山峰了),否则统计。 我们发现这个其实可以做成前缀和,如果想获得从第一个到第 $i$ …
P11839 [USACO25FEB] The Best Lineup S 题解
题目链接:https://www.luogu.com.cn/problem/P11839 思路 由于我们看到了题目要求字典序最大,那么就是要求选的尽量大,宁愿抛弃一些,也要保证前面尽可能的大。 那么,我们可以想到把输入的数组按值从大到小为第一关键字,在原数组的位置从小到大为第二关键字,因为尽量靠前可以使得后面能接更多的数。 我们按照排序后的数组遍历…
货仓选址问题题解 & 拓展
货仓选址原题 给定在一个一维数轴上的多个点,请找出一个位置,使得这个位置和所有点的距离之和最小。 思路 这样的题目在学习数学数形结合的时候其实就学到了,也就是选择最中间的数。这个结论可以通过调整法证明。 证明 我们假设我们选择的数左边还有 $A$ 个数,右边还有 $B$ 个数。 一共有奇数个数 这个时候,由于我们选的数是最中间的数,也就是第 $\f…
题解:P12026 [USACO25OPEN] Compatible Pairs S
题目链接 https://www.luogu.com.cn/problem/P12026 算法 & 数据结构 图论,拓扑排序,建图。 思路 Subtask 1 这个 Subtask 是 $A = B$。 我们首先想到建立一个图,每个 ID 号码为一个点,如果有一个 ID 的牛可以和另一个 ID 的牛交流,那么我们建立一个从第一个 ID 到第…
Markdown 编辑器 Vditor 的前端与后端的一些坑
前言 最近在写一个博客,在写编辑文章页面的时候想找一个可以支持 Markdown 的编辑器,而且支持 GFM 的一些特性,还有数学公式。 正好想到以前用思源的时候偶然看到的一个项目,就去找了一下,发现这个是最满足我的需求的一个项目了。其他项目要不就是不支持 Latex 或者 GFM,要不就是不是很好看(当然,如果有推荐的可以在评论区发一下)。 Vd…