std的博客

博客

Contribution 系统说明

2021-05-13 07:50:29 By std

在强大的 hy 的指导下,QOJ 的 contribution 系统上限了。

具体的计算方法涉及 hy 算法机密,在一百年内不能公开。

同时,你可以在进行投票时查看投票详情,并补充你的投票理由,详情可参考投票框旁 Details 页面。

此外,对于 rating 较高的用户,其可拥有更高的评分上限。目前每个等级的评分上限如下:

Usergroup Value
Legendary Grandmaster $8$
International Grandmaster $7$
Grandmaster $6$
International Master $5$
Master $4$
Candidate Master $3$
International Expert $3$
Expert $2$
Specialist $1$
Pupil $1$
Newbie $1$

你可以通过多次点击“好评”或“差评”来投票,但你的评分的绝对值不能超过你所在用户组的评分上限。

对于差评数过多的帖子,将会被隐藏。详情效果可以见评论区1,2.

托福120(L30W30R30S30),雅思9.0分,分享我的经验

2019-10-07 14:07:39 By std

楼主在7天备考时间内轻松达到这个说高不算高,说低不算低的成绩。

我是怎么做到的呢,因为我是CGL,所以直接满分了。

谢谢大家。

酒酿OI 2019 Round 2 题解

2019-09-13 17:00:07 By std

Problem 1 珠江夜游cruise

题目大意: n+1 艘船,告诉你每艘船距离终点的长度、船身的长度和最高行驶速度。在行驶的过程中不允许超越(即后面的船最多也只能船头贴着前一辆船的船尾,后以同样的速度前进)。问这些船均驶过终点需要多长时间。

第一种方法:把第 i 辆船追上第 i+1 辆船当作一个事件,显然只有 n 个事件,且第 i 辆船追上第 i+1 辆船只可能会对第 i−1 辆船追上第 i 辆船的时间产生影响,且时间一定是变小,因此可以维护船之间的距离和速度来计算事件发生时间,用堆来找出最早发生的事件,不停处理直到距离终点最远的船通过终点。同时还需要记录行驶过程中,以相同速度前进的一系列船的最前面的船的编号,和最后面的船的编号,复杂度为 O(nlogn)。

第二种方法:可以直接二分最终时间,然后从第一辆船开始递推求出每辆船的最终位置。复杂度为 O(nlogC),也可以过。二分给定一个 mid,进行 check 的时候,我们只需要记录下来前一辆船船头最终能到达的位置-前一辆船的长度的值,然后计算当前这辆船的船头能到达的最远距离( 在没有船挡路的情况下),然后在两者之间取一个 min 就是该船船头能到达的最终位置。递推计算最远的船能否通过终点即可。(任何一辆船达不到终点即可返回)。

第三种方法:O(n) 的做法,也是最简单的做法。最终通过终点的时候,一定是一个船后面堵着剩余所有的船,那么影响时间的就只有最前面这辆船,所以对于每一辆船,假设是它是和 0 船堵在一起的最靠前的一辆船,那么可以计算出一个值,所有的船的计算值的最大值就是答案。计算的时候一定不要忘了算上这堵在一起的一堆船的船身长度,因为最后一辆船的车头通过终点,才算结束。

Problem 2 旅行计划travelling

题目大意:给定一个任意的无向图, 问最少画几笔, 使得所有的边被画过一次且仅一次。

解法:每个连通块显然是独立的。对于一个连通块(除了单个点的),如果奇度数点个数为 k,那么至少需要 max(k/2,1)条路径。这是因为在一个无向图中,将两个度数为奇数的点连起来,就可以消去两个奇数点。所以如果一个无向图要有欧拉回路(全部点的度数全为偶数),只要加 k/2 条边就可以了。于是乎,我们只要将一个连通块变成欧拉图,搜一遍得到路径,再将我们人为添加的边删掉,剩下的就是这个连通块的"笔画"了。

这里为什么一定变成欧拉回路而不是欧拉通路,其实这里欧拉回路和欧拉通路都是可以的,得到的答案是一样的。主要是算法实现上的问题,如果变成欧拉通路,就一定得从剩下的两个奇数点出发,终止。至于为什么这里加 k/2 条边后扫出的结果删掉多加的边就是答案,并且这个答案=max(k/2,1)呢?这是因为一个图中,我们从奇数点开始走,停止的也一定是在奇数点,那么再一遍遍不重复地从图中走出一条条类似前面地路径(奇数点开始,奇数点结束)然后我们将这些路径地终点连接下一条路径的起点(多加的边),这样又因为每一条路径的起止点都为奇数点,一条边删去两个奇数点。所以最终把他们连成欧拉回路所需的边的数量就是 k/2。

Problem 3 基站建设station

题目大意:给你一个 8× 8 的矩阵,你需要遍历上面给定的某些格子。每次从一个点到另一个点的代价两个格子的切比雪夫距离的最大值。求最小总代价。

60分做法:状态压缩动态规划。

100分做法:不妨先考虑一维的情形。也就是说,需要放鹅卵石的格子排成一行。

容易想到,应该“先中间后两边”。更严格地说,现在要把连续的一段格子中的鹅卵石摆放完成,那么把目标位置处于最左边或者最右边的鹅卵石最后放,一定不会更差。下面稍许做些说明:不妨考虑这样一种情况,格子 L~R 中有些格子要放鹅卵石,而且格子L 和 R 一定要放(下面把目标位置为 x 的鹅卵石称为鹅卵石 x)。假如你给我一个方案,鹅卵石 L 和鹅卵石 R 都不是最后放,那么,把这个方案中鹅卵石 L、R 中后放的那一个与最后放的那个鹅卵石交换顺序,答案不会变差。也就是说,让鹅卵石 L 或者鹅卵石 R最后放是不会错过最优解的。(如图 2)

图2

于是,一维的情况就可以使用区间动态规划,每次决策是让最左边还是让最右边的鹅卵石最后放,剩下的部分就变成了一个子问题。

回到原题。由一维的情况,自然地会有如下猜想:放鹅卵石应该“先中间后四周”。或者说,考虑一个矩形区域,$(x_1, y_1)$为左上角,$(x_2, y_2)$为右下角,那么,考虑让某一条边上的鹅卵石最后放,代价不会变大。仔细想想这也不难说明。(如图 3)

图3

这样我们就可以进行动态规划了。枚举把哪一条边上的鹅卵石最后放,余下的便是子问题。

思考:如果题目中的距离变成曼哈顿距离,即$(x_1, y_1)$与$(x_2, y_2)$之间的距离计算公式为$$|x_1 – x_2| + |y_1 – y_2|$$怎么办?

这里稍作提示。 设点 $P_1(x_1, y_1)$, $P_2(x_2, y_2)$,令点 $P_1’$ 为$(x_1 + y_1, x_1 – y_1)$, $P_2’$ 为$(x_2 + y_2, x_2– y_2)$, 则借助恒等式$$max(|a|, |b|) = ( |a + b|, |a – b| ) /2$$可以推出 $$\begin{align*} P_1’ 与 P_2’ 间的切比雪夫距离 &= max(|(x_1– x_2) + (y_1– y_2)|, |(x_1– x_2) – (y_1– y_2)| )\\ &= |x_1 – x_2| + |y_1 – y_2|\\ &= P_1与 P_2间的曼哈顿距离 \end{align*}$$

本质上,我们进行了一次旋转坐标系的操作,可以通过图4直观地理解。

图4

本题的原题中用的就是曼哈顿距离。为了降低难度我直接改成使用切比雪夫距离。这种曼哈顿距离与切比雪夫距离的相互转化的技巧,有时会使用到。

点评:上面采用的分析方法是,先简化问题:先思考一维的简单情形,看看是否能从中得到启发。有时题目的条件很复杂,约束很多,不知如何下手,这时适当想一想“去掉一些条件和约束,我该怎么做” ,有助于找到突破口。

写在最后

感谢 sqy 保佑 酒酿OJ 平稳运转。

OI 千万神,dhw 第一神。

膜 dhw 不规范,爆零两行泪。

酒酿 OJ Easy Round 1

2019-08-14 13:11:46 By std

小 Q 与主力

解析几何送分题。

期望得分 100 分。

小 Q 与踹树

我们观察这么一个数字:

$$ 110101001110 $$

好的这是我瞎写的。那么与它异或最大的那个数字是什么呢?是这个:

$$ 001010110001 $$

咦?似乎它们俩每一位都是反的啊。

正是。

他俩异或完以后是什么样子呢?

$$ 110101001110 \ xor \ 001010110001 \ = \ 111111111111 $$

诶诶诶全是1!!!

正是这样。两个二进制数按位异或,若同一位数不相同则为1,否则为0。

考虑题目名称:Trie树。

每一个节点有2个子节点:0或1。

这样把每个数插入Trie中,然后分别对每个数从Trie里寻找,贪心对每一位找与当前位相反的,没有就只能找与当前位相同的。

然后就是Trie基本练习题了,具体实现可以看std。

灯火将熄

这东西有点难...提供pdf题解,具体私聊陈菜鸡。

酒酿 OJ Round 1 题解

2019-08-14 13:05:55 By std

小 Q 与签到

算法 1

对于比较小的 $k$,手动构造一个解。

期望得分 20 ~ 40 分。

算法 2

暴力枚举 $x,y,z$。显然答案不会超过 $k$。

时间复杂度 $O(k^3)$。

期望得分 40 分

算法 3

经过思考发现枚举了 $x, y$ 后,$z$ 可以通过扩欧计算出来。

时间复杂度 $O(k^2 \log k)$

算法 4

观察到在这个式子中,$x,y,z$ 的地位均等。

期望得分 100 分。

小 Q 与图论

算法 1

暴力枚举出选边涂色的顺序。

时间复杂度 $O(m!)$。

期望通过 Subtask 1,得分 13 分。

算法 2

图为一条链时,链的两端的点只有一条边,因此会被自动涂色。随后,剩下的边也会自动涂色……

图为一棵树时同理。

因此,显然你不需要做任何操作,输出 $0$ 即可。

期望通过 Subtask 3 与 Subtask 4,得分10分。结合算法 1 可得到 23 分。

算法 3

当图为仙人掌时,注意到任意一条边只在一个简单环上,因此只要把这个环破开即可。问题转化为如何找环,可以简单地线性做到。

时间复杂度 $O(n)$,期望通过 Subtask 5,得分 25 分,结合算法 1,2 可得到 48 分。

算法 4

考虑 $n,m \leqslant 300$。

贪心地想,如果有白色度数为 $2$ 的节点,优先涂色。这样做显然是正确的。

更新的复杂度显然不会超过 $O(m)$,时间复杂度 $O(mn)$。期望通过 Subtask 2,得到 20 分。结合上面的做法可以得到 68 分。

算法 5

由于图不一定联通,且每个联通块之间显然是独立的。不妨考虑其中一个联通块 $G$。

首先,我们找到 $G$ 的一个生成树 $T$,然后考虑所有的非树边构成的几何 $H$。设 $t = |G| - |H|$。显然,对于此联通块,答案的上界为 $t$。下面,我们来证明答案的下界也是 $t$。

假设有一种涂色方案使得方案少于 $t$。我们把涂黑操作看作是“删边”,那么相当于如果一个联通块被删成了一棵树,那么就会自动消失。如果这种方案使得图仍然联通,就必定存在一个环(因为 $n$ 个点的联通无向简单图必定只有 $n-1$ 条边),若不然,则递归归纳即可。

综上,我们只需要找到每个联通快的生成树。$O(n \log n)$,期望得分 100 分。

算法 6

注意到,我们其实不关心这棵生成树是啥,只要判一下联通就好了。

时间复杂度 $O(n \alpha (n))$,期望的分 100 分。

算法 7

对于算法 4,有个显然的性质是,所有节点更新次数之和不会超过 $\sum^n_{i=1} \deg i = 2m$。因此采用个数据结构维护。

小 Q 与搜索

算法 1

直接暴力枚举。时间复杂度 $O(3^n \times \text{Poly}(n))$,期望得分 0 ~ 90 分。

所以这不是sb题吗……暴力就90分了,怎么没人写啊

算法 2

卡常数。

期望得分 100 分。

算法 3

四毛子算法。时间复杂度 $O(3^n / \log n)$。期望得分 100 分。

std Avatar