202407月度小结
7月,从军训到ACM。军训虽枯燥,但教官对我们很友好;如果说军训是身体上的考验,那么随后的ACM则是精神和耐心的考验了。希望我在个人能力上有些进步吧。
7月,从军训到ACM。军训虽枯燥,但教官对我们很友好;如果说军训是身体上的考验,那么随后的ACM则是精神和耐心的考验了。希望我在个人能力上有些进步吧。
在两人竞技比赛中,对于任何正整数 \(a\) ,我们定义 \(BO(2 a-1)\) 如下:两名玩家继续竞争,直到其中一人获胜 \(a\) 次,那么他赢得整个比赛。\(BO(2 a-1)\) 最多包含 \(2a-1\) 小局游戏,最少包含 \(a\) 小局游戏。
现在两个人进行一场 DotA2 比赛,使用的是 \(BO(2b-1)\ \texttt{of}\ BO(2a-1)\) 赛制。该赛制由最多 \(2b-1\) 最少 \(b\) 场主要比赛组成,每个主要比赛都是一个 \(BO(2a-1)\),由最多 \(2a-1\) 最少 \(a\) 局次要比赛组成。
假如比赛的结果是预先确定的:有一个长度为 \(n\) 的 \(0-1\) 串 \(T\) ,其中 1
表示 A 获胜,0
表示 B 获胜。A 和 B 的每一局次要游戏结果都从串 \(T\) 中获取。假如从 \(T\) 串的每个位置开始重复获取次要游戏结果,求最后谁赢了?
\(1\le n,a,b\le 10^5\)
Neko has two integers \(a\) and \(b\). His goal is to find a non-negative integer \(k\) such that the least common multiple of \(a+k\) and \(b+k\) is the smallest possible. If there are multiple optimal integers \(k\), he needs to choose the smallest one.
Given his mathematical talent, Neko had no trouble getting Wrong Answer on this problem. Can you help him solve it?
找 \(k\ge 0\) 使 \(\min\operatorname{lcm}(a+k,b+k)\),若有多个 \(k\),取最小的。
\(1\le a,b\le10^9\)
There are \(2\cdot n\) cards arranged in a row, with each card numbered from \(1\) to \(n\) having exactly 2 copies.
Each time, Red can choose a subarray of consecutive cards (at least \(2\) cards) to remove from the deck. The chosen subarray must satisfy that the first and last cards have the same number. The score for this operation is: the number of cards multiplied by the number on the first card. Now Red wants to know what is the maximum value of the final score?
给你一个长度为 \(2n\) 的数组,\(1\) 到 $ n$ 每个数字恰好出现两次。你可以进行这样的操作:选择两个相同的数字 \(x\) (必须都还存在于数组中),将这两个数以及其间的所有数字(共计 \(cnt\) 个)全部拿走,并获得 \(x\cdot cnt\) 得分。求最终最多能够获得多少分?
\(1\le n\le 3\times 10^3\)
给一棵根为 1 的有根树,点 \(i\) 具有一个权值 \(A_i\) 。
定义一个点对的值 \(f(u, v)=\max \left(A_u, A_v\right) \times\left|A_u-A_v\right|\) 。
你需要对于每个节点 \(i\) ,计算 \(a n s_i=\sum_{u \in \operatorname{subtree}(i), v \in \operatorname{subtree}(i)} f(u, v)\) ,其中 \(\operatorname{subtree}(i)\) 表示 \(i\) 的子树。
请你输出 \(\oplus\left(a n s_i \bmod 2^{64}\right)\) ,其中 \(\oplus\) 表示 XOR。
\(n \leq 5 \times 10^5, 1 \leq A_i \leq 10^6\)
Sajin最近深入研究了最小生成树,现在他已经掌握了MST的算法。他渴望通过一系列查询来评估您对最小生成树概念的掌握程度。
您将面临一个加权无向图,该图包含没有任何自环的 \(n\) 个顶点和 \(m\) 条边。
Sajin提出 \(q\) 询问。对于每个顶点集,都给出了一个顶点集 \(S\) 。您的目标是确定 \(S\) 的诱导子图(induced subgraph)并找到其最小生成树的权重。如果 \(S\) 的诱导子图断开,则输出-1
。
图的诱导子图是另一个图,由图的顶点子集和原始图中的所有边组成,连接该子集中的顶点对。即,对于图 \(G=(V,E)\) ,给定 \(V^\prime\) ,则有 \(E^\prime=\{(u,v) \mid u,v\in V^\prime,(u,v)\in E\}\),诱导子图为 \(G^\prime=(V^\prime,E^\prime)\)。
\(2\le n\le 10^5,1\le m,q\le10^5\)
\(1 \le |S_i|\le n,\sum S_i\le 10^5\)
CF1988D The Omnipotent Monster Killer
怪物们在一棵有 \(n\) 个顶点的树上,编号为 \(i(1\le i\le n)\) 的怪物位于编号为 \(i\) 的顶点上,攻击力为 \(a_i\) 。你需要与怪物战斗 \(10^{100}\) 个回合。在每个回合中,会依次发生以下两步:
限制条件:在一个回合内不能杀死相邻的两只怪物。
如果您以最佳选择方式攻击的怪物,那么在所有回合后,您的健康值减少的最小值是多少?
\(1\le t\le 10^4,1\le n\le 3\cdot 10^5,1\le a_i \le 10^{12},\sum n\le 3\cdot 10^5\)