二分

仍然是中规中矩的一场模拟赛。前两题正解,第三题暴力,第四题不会。

简略题解

A – 激光

考虑是否有两条及以上双向连边,若是则无解,若有一条则枚举要将哪一侧的发射器旋转到哪一方向。简单模拟即可。

B – 碰撞

这类数轴上带标号小球相撞的题目都有一个经典套路:两球相撞调转方向时,我们不认为是球本身转向,而认为两球仍然保持原方向运动,而其编号交换(更多…)

More
  • 2022年11月20日

或许是人品不错,最近两天接连刷到三道排列组合相关的题。在此作简单整理。

AtCoder ABC226 F – Score of Permutations

题意参见原题面。

很自然地想到,对于一个排列P=(p1,p2,,pn)P = (p_1, p_2, \dots, p_n),有nnipii \rightarrow p_i的连边。因为排列中正整数1,2,,n1, 2, \dots, n恰好出现仅有一次,所以等价于每个点有且仅有一条出边一条入边的图。容易发现这个图由若干个有向环构成(包括自环——即pi=ip_i = i的情况)。例如排列P=(1,3,4,2)P = (1, 3, 4, 2)代表由111 \rightarrow 123422 \rightarrow 3 \rightarrow 4 \rightarrow 2两个环组成的图。

(更多…)

More
  • 2021年11月14日

洛谷题库 P1852 跳跳棋

我仍然坚持认为这道题不应该放在LCA的专题里面

一拿到题我毫无头绪……这看起来跟最近公共祖先没有半毛钱关系啊?我的第一反应是“递推出从某个状态开始能达到的所有状态”,时间复杂度大约是O(2N)\mathbf{O}(2^{|N|})(至于为什么底数为22,请看完下一节后思考)。但很明显,坐标在±109\pm 10^9范围内的数据可容不下这般折腾。

但鉴于它被放在这个专题中,我们就尝试从的角度来考虑。

(更多…)

More
  • 2021年7月25日