Vanilla_chan

永远可爱 永远善良

Problem

给一棵根为 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\)

阅读全文 »

Problem

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

Problem

怪物们在一棵有 \(n\) 个顶点的树上,编号为 \(i(1\le i\le n)\) 的怪物位于编号为 \(i\) 的顶点上,攻击力为 \(a_i\) 。你需要与怪物战斗 \(10^{100}\) 个回合。在每个回合中,会依次发生以下两步:

  1. 所有活着的怪物攻击你。你的生命值会按照所有活体怪物攻击点的总和减少。
  2. 您选择一些(可以选全部,也可以不选)怪物并杀死它们。被杀死的怪物将不会再进行攻击。

限制条件:在一个回合内不能杀死相邻的两只怪物。

如果您以最佳选择方式攻击的怪物,那么在所有回合后,您的健康值减少的最小值是多少?

\(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\)

阅读全文 »

CF1992E Novice's Mistake

Problem

Noobish_Monk 有 \(n\in [1,100]\) 个朋友。每个朋友都给了他 \(a\in [1,10000]\) 个苹果作为生日礼物。Noobish_Monk收到礼物后非常高兴,他把 \(b\in[1,\min\{10000,a\cdot n\}]\) 个苹果还给了朋友们。Noobish_Monk 还剩下多少个苹果?"

K1o0n 写了一个解法,但不小心把 \(n\) 的值看成了字符串,所以 \(n \cdot a - b\) 的值的计算方法不同。具体来说

  • 当用字符串 \(n\) 乘以整数 \(a\) 时,他将得到字符串 \(s=\underbrace{n + n + \dots + n + n}_{a\ \text{times}}\)
  • 从字符串 \(s\) 中减去整数 \(b\) 时,将删除最后的 \(b\) 个字符。如果 \(b\) 大于或等于字符串 \(s\) 的长度,则字符串将变为空。

现在 ErnKor 想知道在给定的 \(n\) 中,有多少对 \((a, b)\) 满足问题的约束条件且 K1o0n 的解法给出了正确答案。

“解法给出了正确答案”意味着得到了一个非空字符串,且这个字符串转换成整数后等于正确答案,即 \(n \cdot a - b\) 的值。

\(1\le t\le 100,1\le n \le 100\)

阅读全文 »

要求对被评价对象进行的客观公正合理的全面评价。一般,需要对很多个同类对象进行评价,被评价的对象往往涉及多个属性或指标。需要根据系统的属性判断确定这些这些系统状况或者未来发展孰优孰劣,即按照优劣对被评价对象进行排序或者分类。这类问题又称为多属性(多指标)综合评价问题。

阅读全文 »

Problem - E - Codeforces

爱丽丝和鲍勃玩摸球游戏。有 \(n\) 个球,其中 \(k\) 个是特殊球。每个球都有其价值。

他们轮流且不放回地摸球,每回合随机摸一个球并获得该球的价值。特别地,如果摸到了特殊球(且至少还有一个球)则这名玩家继续摸球。如果摸到的是普通球,则换人摸球。这样轮流摸球直到没有剩余球,游戏结束。Alice先手。

求游戏结束时双方的期望得分,对取模 \(10^9+7\)

\(t\le2\times10^5,1\le k\le n\le 4\times 10^5,1 \le v_i \le 10^7,\sum n\le 5\times 10^5\)

阅读全文 »

在许多实际问题当中,衡量一个方案的好坏标准可能不只一个。比如生产某个东西的时候想要“物美价廉”——既要质量好,又要成本低。这一类问题统称为多目标最优化问题或者多目标规划问题

标准形式

多目标规划问题一般可以写成如下形式: \[ \begin{aligned} \min & f_1(x) \\ \min & f_2(x) \\ & \vdots \\ \min & f_p(x) \\ \text { s.t. } & g_i(x) \leq 0, i=1,2, \ldots, m \end{aligned} \]

其中, \(x=\left(x_1, x_2, \ldots, x_m\right)^T \in R^m, p \geq 2\)

阅读全文 »

Here's something encrypted, password is required to continue reading.
阅读全文 »